Техніки бітбордів: Кодування шахівниці у 64 біти

Чому представляти дошку як біти

Наївне представлення шахівниці – це 8x8 масив, де кожен елемент зберігає код фігури або порожній. Перевірка, чи може слон захопити щось, передбачає пересування на одне поле в кожному напрямку до тих пір, поки не буде знайдено фігуру або край поля, з логічними розгалуженнями на кожному кроці. Це повільно, коли потрібно робити це мільйони разів на секунду під час пошуку. Замість цього представлення бітбордом використовується 12 64-бітних цілих чисел для стандартної шахової позиції: одне для кожної комбінації типу фігури (пішак, кінь, слон, тура, королева, король) та кольору (білий, чорний). Індекс біта n, що змінюється від 0 до 63, відповідає конкретному полю, зазвичай біт 0 – це a1, а біт 63 – h8, скануючи зліва направо, знизу вгору. Якщо у білого коня знаходиться на полі g1, шістнадцятий біт у бітборді білого коня встановлюється в 1; всі інші біти в цьому цілому числа встановлені в 0. Це представлення перетворює запити дошки на арифметику. Загальна зайнятість дошки просто є побітовим оператором І (OR) усіх 12 бітбордів фігур. Загальна зайнятість білими – це І (OR) лише шести бітбордів білих. Щоб знайти, які з цільових квадратів на діагоналі слона містять ворожу фігуру, двигун виконує операцію ІЧЕБІ (AND) між попередньо обчисленим бітбордом атак слона та бітбордом зайнятості супротивника; кожен залишається 1 біт у результаті є законним полем захоплення, яке виявляється без перевірки окремого поля. Практичний результат – швидкість, виміряна в циклах процесора, а не ітераціях циклу. Сучасний процесор виконує 64-бітні операції І (OR), ІЧЕБІ (XOR) або зсув за один цикл, тому операція, яка потребувала б десяток або більше порівнянь у масивному представленні дошки, стискається в одну інструкцію. Помножте цю економію на мільйони позицій, які перевіряє сильний двигун за секунду під час глибокого пошуку, і різниця між представленням на основі масивів та бітбордами стає різницею між програмою для хобі та конкурентним двигуном. Це також пояснює, чому бітборди не є унікальними для шахів: Оthello (шашки), checkers (решітка) та Connect Four, а також інші ігри з фіксованою сіткою з двозначним станом зайнятості, використовують ту ж саму хитрощі, коли розмір сітки поміщається комфортно в машинне слово.

Основні бітові операції на дошці

Чотири операції виконують майже всю роботу в двигуні бітбордів, і кожна з них безпосередньо відповідає за шахове поняття. AND знаходить перетини. Зведення (AND) бітборду атаки певної фігури з бітбордом зайнятості супротивника дає точно ті квадрати, які ця фігура може захопити. Зведення (AND) бітборда прямого руху пішака з бітбордом вільних клітин (бітове заперечення, NOT, загальної зайнятості) підтверджує, чи є клітина перед нею дійсно вільною для переміщення. OR об'єднує множини без втрати інформації, оскільки встановлення біта, який вже дорівнює 1, нічого не змінює. Це використовується для побудови бітбордів зайнятості: зведення (OR) всіх бітбордів фігур одного кольору, щоб отримати зайняті квадрати цього кольору, а потім зведення (OR) обох кольорів разом для отримання загальної зайнятості. Його також використовують для додавання фігури до бітборда, зводячи (OR) в бітборд, який містить лише встановлений у цьому квадраті біт. XOR перемикає біти, що відбувається точно тоді, коли рухається фігура: біт початкової клітинки змінюється з 1 на 0, а біт цільової клітинки змінюється з 0 на 1, це досягається шляхом зведення (XOR) бітборду фігури з бітбордом, який має лише два встановлені біти. XOR також використовується для оновлення захопленого бітборда фігури, очищаючи біт у цільовій клітинці. Ця властивість робить XOR самоінвертуючою, що зручно для скасування ходів під час пошуку: застосування ідентичного XOR повторно відновлює оригінальний бітборд точно. Зсуви моделюють рух у напрямку. Зсув бітборда пішака білого кольору на 8 бітових позицій (оскільки кожен ряд шириною 8 бітів) генерує всі квадрати, на які може просунутися пішак, перш ніж перевіряти блокуючі елементи або промоцію. Діагональні захоплення пішаків використовують зсуви на 7 або 9 позицій, а спочатку застосовується маска для запобігання обертанню бітів від краю дошки з файлу a на файл h або навпаки, що є артефактом упаковки одновимірної дошки в одновимірний бітовий рядок. Крім цих чотирьох, двигуни покладаються ще на дві основні операції: підрахунок встановлених бітів (підрахунок кількості бітів, встановлених у 1, корисний для оцінки матеріалу та оцінки мобільності) і сканування бітів (знаходження індексу встановленого біта), де трюк з послідовністю Де Бройна, розглянутий пізніше в цій статті, стає ключовим.

Проблема зі скочуванням

Сьокери, королі та пішаки мають фіксовані, короткодіапазонні шаблони руху: атака сьокера з будь-якої заданої позиції завжди є одним і тим же фіксованим набором відсутків, тому його повний набір можливих атак bitboardів, один для кожного стартового квадрата, може бути попередньо обчислений та збережений у таблиці з 64 записами без додаткової роботи під час виконання. Rоки, слони та королеви відрізняються тим, що вони котяться до тих пір, поки не зіткнуться з краєм дошки або блокуючим шматком, дружнім чи ворожим. Рок на d4 без перешкод може дістатися всього d-ряду та 4-го ряду; той самий рок із пішаком на d6 може дістатися лише d5 і d6 вгору, перш ніж блокуючий шматок зупинить його. Таким чином, набір легальних цільових квадратів залежить не тільки від положення рока, але й від повного шаблону зайнятих квадратів по його рядку та стовпчику, який називається заповненням. Насправді, це означає повторне обчислення законних ходів шляхом проміння з квадрат в квадрат, перевіряючи кожен квадрат на наявність блокуючого шматка перед продовженням, що призводить до того ж циклічного обчислювального процесу, який bitboardів було призначено усунути. Кількість можливих конфігурацій блокуючих шматочків, які є актуальними для рока, велика: до 2 в 12 степені для рока поблизу центру дошки (12 відповідних квадратів по його рядку та стовпчику, не враховуючи краї, оскільки край сам по собі завжди є дійсним точкою зупинки незалежно від заповнення). Зберігання попередньо обчисленої відповіді для кожної можливої ​​загальної схеми заповнення, для кожного квадрата, як для рока, так і для слона, є принципово здійсненним, оскільки загальні суми доходять до кількох сотень тисяч записів у таблиці, що вписується в сучасний бюджет пам'яті двигуна. Залишається лише алгоритмічна проблема: враховуючи будь-який випадковий 64-бітний bitboard заповнення, як швидко та без конфліктів, які б повернули неправильну відповідь, перетворити відповідні біти блокуючих шматочків на компактний індекс у цю попередньо обчислену таблицю? Це питання саме те, на яке було створено magic bitboardів, і це тема наступного розділу.

Магічні бітборди: Хешування заповненості індексом

Ця магічна техніка бітбордів вирішує проблему пошуку фігурок, використовуючи лише одне множення. Для кожної клітинки та кожного типу фігурок, двигун попередньо обчислює бітборд-маску, що відображає лише ті клітинки, які дійсно мають значення для цієї клітинки, яка називається відповідною маскою заповненості (relevant occupancy mask). Ця маска свідомо виключає зовнішній край дошки в цьому напрямку, оскільки будь-який хід фігуркою завжди зупиняється на цьому краю, незалежно від того, що там знаходиться. Враховуючи реальне положення шахівниці, двигун спочатку витягує лише біти з бітборду заповненості, які потрапляють у цю відповідну маску, використовуючи операцію AND. Ця замаскована заповненість множиться на спеціально обране 64-бітне число – «магічне число», і верхні біти цього 64-бітного результату витягуються шляхом зсуву вправо. Отримане значення є достатньо малим, щоб безпосередньо служити індексом у попередньо обчисленому таблиці атаки для цієї клітинки. Що робить «магічне число» справді «магічним», так це те, що для конкретного обмеженого набору заповнених патернів, які реально досяжні для цієї клітинки з її відповідною маскою, множення розподіляє вхідні біти по верхніх бітах результату таким чином, щоб уникнути колізій, або, принаймні, так, що будь-які колізії, які все ж таки виникають, відбуваються лише між заповненими патернами, які відображають однакові законні ходи, роблячи колізію безнешкодною. Знаходження таких констант історично потребувало випадкового пошуку: генерувати кандидат 64-бітне число, тестувати його проти всіх можливих відповідних заповнених патернів для цієї клітинки та перевіряти, чи верхні біти результату не збігаються руйнівним чином; якщо вони збігаються, відхилити кандидата і спробувати інший. Цей груборубний пошук надійно знаходить робочі «магічні числа» протягом секунд обчислювального часу, а після їхнього виявлення вони стають фіксованими константами, вбудованими у код двигуна, і залишаються незмінними назавжди, оскільки пошук потрібно проводити лише один раз під час розробки двигуна, а не під час гри. Результат при роботі надзвичайно вигідний. Обчислення повної легальної-рухової бітборду шашка чи слона, враховуючи будь-якого можливого блокуючого елемента, стає: одне AND для маскування відповідної заповненості, одне множення на «магічне число», один зсув вправо для вилучення індексу та один пошук у таблиці. Чотири швидкі операції замінюють те, що інакше було б циклом розкидання по дошці, і оскільки немає розгалужень на основі вмісту дошки, ця послідовність виконується з передбачуваною, трубопровідною швидкістю на сучасних процесорах, що має величезне значення, коли вона відбувається мільярди разів під час глибокого пошуку.

Де Бройнські послідовності: Швидке знаходження найнижчого встановленого біта

Двигуни бітбордів постійно потребують відповідати на більш вузьке питання: враховуючи 64-бітне ціле число з встановленими бітами, який квадрат відповідає найнижчому встановленому біту? Це виникає кожного разу, коли двигун ітерується по окремих квадратах бітборда, наприклад, переглядаючи кожен квадрат, який атакує пішак, щоб генерувати окремий хід для кожного. Наївний підхід полягає в тому, щоб перевіряти біт 0, потім біт 1, потім біт 2 і так далі, доки не знайдеться 1, що є циклом до 64 ітерацій у найгіршому випадку. Класична бітова хитриця прискорює пошук самого найнижчого встановленого біта: обчислюється операція AND між бітбордом та його власною двохопорною копією, що ізолює найнижчий встановлений біт у 64-бітному значенні, з усіма іншими бітами очищеними, в одній операції. Це залишає друге питання: враховуючи це ізольоване однобітове значення, який із 64 можливих позицій воно представляє, як ціле число без урахування бітового шаблону? Тут на допомогу приходять Де Бройнські послідовності. Де Бройнівська послідовність порядку k над бінарним алфавітом є циклічною послідовністю довжиною 2 в степені k, де кожна можлива підпослідовність довжиною k з'являється рівно один раз, коли послідовність читається з переповненням. Для сканування 64-бітного бітборда двигуни використовують конкретну Де Бройнівську константу порядку 6, оскільки 2 в степені 6 дорівнює 64. Чудова властивість полягає в тому, що якщо взяти ізольоване однобітове значення, помножити його на цю Де Бройнівську константу та потім зсунути 64-бітний продукт на 58 біт (зберігаючи лише верхні 6 бітів), то отримане 6-бітне число є унікальним індексом від 0 до 63, і цей індекс безпосередньо подається в невелику таблицю з 64 записами, яка була попередньо обчислена один раз для відображення кожного з цих 64 можливих значень індексу на фактичний номер квадрата оригінального бітборда. Причина, чому це працює, полягає в тому, що множення на добре побудовану Де Бройнівську константу змушує кожне з 64 можливих однобітових входів зміщувати шаблон константи на різну, унікальну величину, таким чином верхні 6 біт продукту відрізняються для кожного можливого вхідного положення, що ідеально відповідає властивості хешування, яку гарантують Де Бройнівські послідовності за їх комбінаційному побудові. Вся операція – ізолювати найнижчий біт, множити, зсувати та шукати – виконується за невелику константу інструкцій машини незалежно від того, де саме знаходиться встановлений біт, замінюючи змінну довжиною циклу фіксованою, передбачуваною, без умовних переходів, що і є точною метою дизайну магічних бітбордів для пересувних пішаків.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Bitboard Techniques: Encoding a Chessboard in 64 Bits і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.