Краткое описание
Эта статья рассказывает о некоторых нюансах в использовании «битбордов» (64-битного целого числа, каждый бит которого представляет одно поле шахматной доски). В далеком 1994 г., после симпозиума по шахматам, проводимом ACM в Кейп Мей в штате Нью-Джерси, я решился на полную замену программы для Cray Blitz (компьютерная программа, написанная Робертом Хайатом, Гарри Нельсоном и Альбертом Говером для суперкомпьютера Cray — прим. перевод.). Мне было интересно попробовать метод битбордов, опробованный Слейтом и Аткином в «Chess 4.x» (шахматная программа, разработанная в Северо-Западном университете штата Иллинойс, и доминирующая в 70-х гг. XX в. — прим. перевод.), чтобы решить для себя, годится он для шахмат или нет. В ходе разработки этой новой программы была придумана концепция «вращаемых битбордов», и оказалось, что это то самое, что было нужно, чтобы заставить этот тип структуры данных работать с приемлемой производительностью.
1. Вступление
Битборды упоминаются множество раз в компьютерной шахматной литературе. В середине 1970-х Слейт и Аткин придумали и описали метод использования двенадцати 64-битных целых чисел, каждое из которых представляло один тип шахматных фигур на доске (шесть для белых и шесть для черных). Тут надо заметить, что команда KAISSA (Донской и другие), по-видимому, изобрела ту же самую идею независимо от команды Северо-Западного университета, и что за последние 25 лет было написано много других программ, использующих тот же подход.
Слейт предложил сопоставить биты полям шахматной доски; бит со значением 1 служил признаком присутствия фигуры на шахматном поле, тогда как бит 0 указывал на ее отсутствие. Таким образом, в битборде white_pawn, который соответствует полям, занятыми белыми пешками, может быть самое большее восемь битов со значением 1. (В этой статье, поля нумеруются от 0 до 63, где позиция 0 соотвествует полю A1, 7 соотвествует полю H1, 56 соотвествует полю A8, а 63 — полю H8. Биты, которые в 64-битном целом числе стоят в позиции 0, называются «наиболее значимыми битами», а бит в позиции 63 называется «наименее значимым битом».) (most significant bit, MSB и least significant bit, LSB — прим. перевод.)
Помимо хранения в этих двенадцати 64-битных словах информации о позиции на доске, Слейт и Аткин описали, как сгенерировать и последовательно обновлять два дополнительных набора битбордов, предназначенных для информации другого рода. attacks_from[64] — массив битбордов со значениями 1 для каждого поля, которое может быть атаковано фигурой, стоящей на заданном поле. К примеру, attacks_from[E4] дает нам поля, напрямую атакованные фигурой, стоящей на поле E4. В дополнение, массив attacks_to[64] содержит битборды с битами 1 для всех полей, занятыми атакующими данное поле фигурами. К примеру, attacks_to[E4] — это битборд, который содержит биты 1 для всех полей на доске, где есть бьющая поле E4 фигура.
Эти два набора битбордов являются предметом рассмотрения данной статьи, описывающей новый и очень быстрый способ динамического расчета битборда attacks_from[] без существенного снижения скорости выполнения, что имело место для метода обновлений, описанного Слейтом и Аткином. (Надо заметить, что Слейт/Аткин использовали последовательное обновление потому, что описанная ниже процедура слишком медленная для вычисления атак дальнобойных фигур «на лету». Чтобы хоть как-то заставить битборды работать и при этом избежать высокой вычислительной стоимости, они прибегли к последовательному обновлению.)
Есть и другие полезные свойства битбордов, которые делают их очень полезными в шахматных программах. Одно из этих свойств — это нечто, что можно было бы назвать «битово-параллельными» операциями. К примеру, в традиционных шахматных программах, если у вас пешка стоит на поле E4, и вы хотите проверить, является ли она проходной, вам придется проверить поля D5, E5, F5, D6, E6, F6, D7, E7, F7, чтобы убедиться, что там не стоит вражеских пешек. Это требует девять операций сравнения. Используя битборды, вам надо просто заранее вычислить массив масок для каждого поля, где может стоять пешка, и затем взять маску is_passed_white[E4] и произвести операцию побитового «И» (AND) с битбордом для черных пешек. Если вы правильно вычислили маску так, что она имеет единицы в каждом из девяти верхних полей, то одна операция AND может определить отсутствие черных пешек или, наоборот, их присутствие, что не позволит белой пешке на E4 быть проходной. Фактически мы выполнили 9 различных проверок параллельно и всего одной операцией AND ответили на девять вопросов в одно и то же время.
Есть и другие преимущества, но тема этой статьи — вращаемые битборды и то, как они могут быть использованы по мере необходимости для получения данных массивов attacks_from[64] и attacks_to[64], без ограничений, накладываемых последовательными обновлениями, и без сложных/медленных циклов.
2. Расчет массива attacks_from[64] с использованием обычных битбордов
Перед тем как перейти к методу вращаемых битбордов, необходимо обратить внимание на трудоемкость вычисления attacks_from[]. Для недальнобойных фигур это, разумеется, очень просто; мы можем, к примеру, заранее подготовить массив knight_attacks[64] так, что если конь стоит на поле F6, то knight_attacks[F6] есть битборд, содержащий бит 1 на всех полях, куда может атаковать конь с поля F6 (заметьте, что поля, атакованные конем, не зависят от расстановки фигур на шахматной доске). Та же самая идея работает для короля и для пешек (с небольшими изменениями, так как пешки бьют по диагонали, а без взятия двигаются вперед на одно или два поля).
Однако для дальнобойных фигур простое обращение к массиву (как это сделано выше) не работает, потому что дальнобойные фигуры атакуют только по направлению своего движения и только первую фигуру, которая им встретится в этом направлении. Итак, как же нам это расчитать?
Во-первых, нам понадобится битборд с именем occupied_squares, который есть не что иное, как битборд с единицами, выставленными во всех полях, где стоит любая фигура любого цвета (к примеру, его можно рассматривать, как результат побитового «ИЛИ» (OR) между всеми двенадцатью битбордами для каждого типа фигур, хотя на самом деле мы храним два таких битборда: один для черных и один для белых — и применяем операцию OR между ними при необходимости получить битборд occupied_squares).
На рисунке 1 показан пример шахматной позиции, где занятые поля выделены «X», а незанятые поля отмечены "-".
Заметьте, что не имеет значения, что именно находится на полях, потому что дальнобойная фигура останавливается, когда встречается с фигурой любого вида. Если слон стоит на поле F5 (для ясности он отмечен символом B на рисунке 2), то мы видим, что он напрямую атакует следующий набор полей: {B1, C2, D3, E4, G6, H3, G4, E6, D7}. После того, как мы вычислим битборд атак (если это то, для чего будут использоваться допустимые ходы слона из этой позиции), нам может понадобиться исключить все ходы, которые бьют наши собственные фигуры. Используя упомянутый ранее битборд white_occupied, мы можем применить к нему операцию дополнения (побитовое отрицание) и затем операцию AND с битбордом атак, что сбросит те биты, которые в битборде атак слона соответствуют атакам на наши собственные фигуры, поскольку это недопустимые ходы.
Пока все хорошо. Но как мы определим атакованные биты без перебора всех 4 (или 8 для ферзя) лучей, по которым может двигаться фигура? Это, в общем-то, не так сложно, но не очень эффективно тем, что каждое направление требует отдельной итерации цикла.
Во-первых, мы создадим набор масок для каждого из 8 направлений, по которым может двигаться фигура. Назовем их plus1[64], plus7[64], plus8[64], plus9[64], minus1[64], minus7[64], minus8[64], minus9[64]. Эти битборды содержат бит 1 для любого поля, которое может атаковать слон с поля SQ в некотором заданном направлении. Для нашего примера со слоном на F5 в направлении plus7 (это поля F5-E6-D7-C8) plus7[F5] будет выглядеть так, как это показано на рисунке 3.
Это даст нам все поля, которые может атаковать слон в направлении +7, если бы там не было блокирующих фигур между слоном и краем доски. Но мы знаем, что они могут присутствовать, а, если так, мы должны найти блокирующие фигуры в этом направлении. Для того, чтобы сделать это, мы возьмем вышеприведенный битборд и сделаем AND между ним и битбордом occupied_squares. Если слон блокируется в этом направлении, мы получим непустой битборд, в котором биты 1 будут стоять для каждого поля, где есть фигура, блокирующая движение слона по диагонали к C8. Поскольку нам нужна только первая блокирующая фигура, мы воспользуемся функцией FirstOne(), которая вернет нам индекс первого бита со значением 1. К примеру, если слон был заблокирован на C8 и D7, FirstOne() должна вернуть номер поля D7 (51).
Теперь у нас есть список атакуемых полей по этой диагонали и поле, где дальнобойная фигура блокируется. Все, что нам осталось сделать, — это убрать атакуемые поля после блокирующей фигуры. И это как раз самая простая часть. Следующий пример кода объясняет, как это сделать:
diag_attacks=plus7[F5]; blockers=diag_attacks & occupied_squares; blocking_square=FirstOne(blockers); diag_attacks^=plus7[blocking_square];
Вот все, что нужно сделать для одного луча. Чтобы код был понятней, diag_attacks — это битборд, описанный выше, который содержит атакуемые поля из поля F5 в направлении +7. Blockers есть битборд со всеми фигурами, находящимися на данной диагонали. Мы находим первую блокирующую фигуру и затем делаем исключающее «ИЛИ» между plus7[blocking_square] и diag_attacks, что фактически «отрезает» все атакуемые поля, следующие за ней. (Попробуем разобраться. Если слон с F5 блокируется на E6, то plus7[E6] в этом случае будет выглядеть следующим образом: биты с единицами будут только на D7 и C8. Так как биты D7/C8 ненулевые в обоих битбордах, то после исключающего «ИЛИ» между битбордами, эти (и только эти) биты сбрасываются.)
Мы повторяем это для всех четырех направлений с той лишь разницей, что для минусовых направлений мы не используем FirstOne(), так как нам нужно находить последнюю блокирующую фигуру. Вмето этого мы переключаемся на LastOne(). Теперь код для подсчета атак слона во всех четырех направлениях выглядит так:
diag_attacks=plus7[F5]; blockers=diag_attacks & occupied_squares; blocking_square=FirstOne(blockers); bishop_attacks=diag_attacks^plus7[blocking_square]; diag_attacks=plus9[F5]; blockers=diag_attacks & occupied_squares; blocking_square=FirstOne(blockers); bishop_attacks|=diag_attacks^plus9[blocking_square]; diag_attacks=minus7[F5]; blockers=diag_attacks & occupied_squares; blocking_square=LastOne(blockers); bishop_attacks|=diag_attacks^minus7[blocking_square]; diag_attacks=minus9[F5]; blockers=diag_attacks & occupied_squares; blocking_square=LastOne(blockers); bishop_attacks|=diag_attacks^minus9[blocking_square];
Это выливается в большое количество операций с AND и OR и необходимостью маскирования, плюс использование функций FirstOne()/LastOne() для обнаружения блокирующего поля. Это весьма дорого, но раз уж с булевыми операторами большая часть работы делается параллельно, это все же может себя оправдать. Однако есть лучший путь, который позволяет избавиться от вызовов FirstOne()/LastOne() и который обрабатывает всю диагональ/горизонталь/вертикаль за один шаг, а не за два, как в этом методе.
Также надо заметить, что функции FirstOne()/LastOne() очень дорогие, если выполнены как процедуры на C, потому что нахождение первого или последнего бита — нетривиальная задача, требующая много времени при вышеприведенном вычислении атак. К счастью, современные микропроцессоры имеют аппаратные инструкции для подсчета этих значений (Intel имеет инструкции BSF/BSR [bit-scan forward, bit-scan reverse] в архитектуре X86), что делает эти функции крайне быстрыми. Другие типы архитектуры тоже предлагают подобные инструкции.
3. Вращаемые битборды
После того, как в сентябре 1994 г. появилась версия Crafty, использующая битборды, я начал проводить семинары в UAB (Crafty — шахматная программа, написанная Робертом Хайатом, UAB — Университет Алабамы в Бирмингеме — прим. перевод.), чтобы изучать 64-битный подход и разработать новые способы повышения эффективности. Одно из первых обсуждений сводилось к тому, насколько легко генерировать движение дальнобойной фигуры вдоль горизонтали.
Если вы возьмете любое поле на некоторой горизонтали (горизонтальный ряд полей на шахматной доске), то движение дальнобойной фигуры достаточно легко получить, потому что горизонталь определяется 8 битами в битборде occupied_squares. Если сдвинуть этот битборд вправо так, что в его младших разрядах окажутся 8 бит нашей горизонтали, а затем сделать AND с числом 255, то мы получим 8 бит, которые соответствуют полям данной горизонтали.
Имея это в виду, рассмотрим массив битбордов rank_attacks[64][256]. Для инициализации этого массива возьмем любое поле, например A1. Можно заметить, что его горизонталь имеет только 256 различных состояний в зависимости от того, какие поля заняты, а какие нет. Если перед началом игры заранее просчитать, на какие поля может ходить ладья из A1, принимая во внимание все 256 различных комбинаций единичных битов на этой горизонтали, мы можем получать атакуемые на этой горизонтали поля, просто обращаясь к битборду rank_attacks[A1][contents], где contents — это 8-битное представление состояния данной горизонтали. Все, что нам надо сделать, — это вычислить набор битбордов для каждого из 64 полей и всех 256 различных состояний горизонталей, на которых находятся эти поля (да, если подумать, то горизонталь может иметь только 128 состояний, потому что мы _знаем_, что на одном из полей находится ладья, но легче игнорировать это упрощение). Тут надо заметить, что, хотя горизонталь и имеет 8 битов состояния, два крайних бита (LSB и MSB) ничего не меняют, поскольку атакуются независимо от того, есть ли на них фигура или нет. В результате мы убираем их из дальнейших вычислений для того, чтобы сократить размер таблицы для каждой горизонтали на 75%. Таким образом, мы уменьшаем размер массива rank_attacks до rank_attacks[64][64]. Все остальные подобные массивы будут использовать то же самое упрощение.
Пока неплохо, мы можем получить половину атак ладьи простым обращением к памяти с массивом rank_attacks. Но что насчет атак по вертикали и двум диагоналям для слонов? Там биты не являются смежными в битборде occupied_squares, и это делает нашу идею неприменимой ни для чего, кроме горизонталей.
В ходе обсуждения этого на семинаре мы заметили, что при использовании специализированного шахматного оборудования, мы бы, вероятно, выделили регистр для хранения 64-битного значения occupied_squares, но тогда мы могли бы выделить и три других «псевдорегистра», которые позволят нам обращаться к occupied_squares разными способами. К примеру, один будет вращать все содержимое occupied_squares на 90 градусов так, что теперь биты на одной вертикали станут смежными; и мы сможем использовать это для нахождения атак по вертикали точно так же, как мы это делали с заранее подсчитанными атаками по горизонталям. А еще мы можем выделить два регистра, которые будут вращать битборд occupied_squares влево и вправо на 45 градусов так, что диагональные биты в этих вращаемых битбордах станут смежными. Рисунок 4 иллюстрирует, как поля пронумерованы в обычном битборде для шахматной доски.
Вспомним, что A1 — это нулевой по счету бит (MSB), а H8 — 63-ий бит (LSB) в битборде occupied_squares. Перво-наперво, мы вращаем его влево на 90 градусов, чтобы сделать вертикальные биты смежными (обратите внимание, что нижний левый угол остается нулевым по счету битом в 64-битном битборде, а верхний правый угол всегда будет иметь порядковый номер 63), как показано на рисунке 5.
Затем мы вращаем оригинал влево на 45 градусов, как показано на рисунке 6.
В этом повернутом битборде нижнее поле (A1) становится нулевым по счету битом, а следующие за ним становятся по порядку. Так, например, A2 становится битом 1, B1 становится битом 2 и так далее до H8, который становится битом 63.
Заметьте, что в вышеприведенном битборде биты на диагонали от H1 к A8 и на всех диагоналях, которые ей параллельны, теперь являются смежными. Это не так удобно, как в первых двух битбордах; там мы могли легко расчитать, насколько нужно сдвинуть данную горизонталь или вертикаль к правому концу числа, чтобы его можно было использовать как индекс массива; и мы также знали, что для извлечения восьми нужных бит нам надо сделать AND с числом 255. В случае с диагоналями мы имеем разную длину для каждой диагонали, что означает разное значение сдвига и маски для устранения лишних битов. Решение этой проблемы будет описано позднее.
Теперь мы вращаем оригинальный битборд на 45 градусов вправо, чтобы сделать смежными биты на других диагоналях, как в битборде на рисунке 7.
Теперь, когда у нас есть все это, становится очевидным, что нам надо добавить еще три массива битбордов для атак в дополнение к уже рассмотренному rank_attacks[64][64]. Добавляются file_attacks[64][64], diaga1h8_attacks[64][64] и diagh1a8_attacks[64][64], и, если мы научимся вращать оригинальный битборд occupied_squares, мы сможем использовать ту же самую схему индексации, что даст нам возможность заменить сложную процедуру обновления на два обращения к таблице для слонов или ладей и четыре для ферзей.
Позднее, после долгих обсуждений о способах вращения битборда occupied_squares, простое решение было найдено. Вместо того, чтобы хранить единственный битборд occupied_squares и при необходимости вращать его (что мы полагаем почти невозможным ввиду неэффективности), мы можем хранить четыре битборда для занятых полей: обычный и повернутые на 90 градусов, 45 градусов влево и 45 градусов вправо. Это действительно довольно легко, потому что в процедуре перемещения фигуры MakeMove() мы можем найти подобный код для обновления битборда occupied_squares:
occupied_squares^=set_mask[from]|set_mask[to];
Это простой механизм для обычных ходов (взятия, рокировка и взятие на проходе обрабатываются немного иначе), потому что мы знаем, что бит стартового поля «from» в occupied_squares обязан иметь значение 1 (в противном случае на этом поле не было бы фигуры для перемещения); и мы также знаем, что бит конечного поля «to» в битборде occupied_squares обязан иметь нулевое значение (в противном случае это было бы взятие). Итак, с помощью исключающего «ИЛИ» бит стартового поля сбрасывается, а бит конечного поля устанавливается.
Все элементы массива битбордов set_mask[64] имеют только 1 установленный бит в соответствующей позиции. Например, в set_mask[0] установлен самый левый бит (нулевой бит), тогда как в set_mask[63] установлен самый младший бит (63-ий бит). Чтобы работать с вращаемыми битбордами, мы создали три новых набора таких масок: set_mask_rl90[64], set_mask_rr45[64] и set_mask_rl45[64]. Каждый из них принимает номер поля в качестве индекса, а возвращает битборд, в котором установлен соответствующий бит во вращаемом битборде occupied_squares. К примеру, в set_mask_rl90[0] на самом деле установлен седьмой бит, так как, если вы посмотрите на рисунок, в битборде rotated_left бит 0 становится седьмым.
Это и было решение, нужное нам для того, чтобы заставить все работать. Вместо того, чтобы вращать битборд occupied_squares, мы теперь храним четыре битборда occupied_squares одновременно и можем использовать два из них для слонов/ладей или четыре для ферзей в любой момент, когда потребуется получить атаки для этих типов фигур.
Для слонов есть одна хорошая оптимизация, которая может быть использована, хотя это дорого относительно памяти. Вспомните, что для ладей мы сдвигали соответствующую горизонталь или вертикаль в правый конец числа, затем мы делали AND с 255, чтобы получить содержимое этой горизонтали или вертикали. Это работало, так как каждая горизонталь или вертикаль содержит восемь бит. Но в случае с диагоналями каждая отличается по длине от своего соседа.
Чтобы упростить этот алгоритм, мы будем делать AND 255 и в случае с диагоналями, что, очевидно, даст нам нужную диагональ, но с несколькими лишними битами из соседней диагонали (диагоналей). Если интересующая нас диагональ имеет только три бита (всего 8 уникальных состояний), мы получаем каждое из этих 8 состояний, скомбинированных с 32 состояниями лишних битов. Иными словами, у нас есть состояния трех нужных нам битов, которые повторены 32 раза. Таким образом, не имеет значения, что содержится в лишних 5 битах, мы все равно получим правильный битборд атак для нашей трехбитной диагонали.
4. Вычисление attacks_from[64] с использованием вращаемых битбордов
Для расчета атак мы используем 4 различных массива: один для атак по горизонтали, один для атак по вертикали и по одному для двух диагоналей, которые проходят через поле. Мы назвали эти массивы rank_attacks[64][64], file_attacks[64][64], diaga1h8_attacks[64][64] и diagh1a8_attacks[64][64].
Для инициализации этих массивов (это делается при запуске приложения, и с этого момента массивы остаются неизменными) мы просто предположили, что на поле стоит дальнобойная фигура, которая может двигаться в рассматриваемом направлении (например, ферзь). Затем для каждого поля мы ввели rank_attacks[square][rank_contents] — битборд, который показывает, на какие поля горизонтали ладья/ферзь, стоящая на поле «square», может двигаться в случае, когда поля этой горизонтали заняты соответственно восьми битам числа «rank_contents». К примеру, возьмем ранее рассмотренный битборд occupied_squares, но вместо слона на поле F5, как в предыдущем примере, мы поставим туда ладью (рисунок 8). Предположим, что мы пытаемся инициализировать rank_attacks[37][100] (37 — это поле F5, а 100 соответствует занятым полям на этой горизонтали — 01100100). Мы инициализируем этот элемент rank_attacks, как показано на рисунке 9. Это полностью соответствует тем полям, которые может атаковать ладья/ферзь на 5-ой горизонтали, если фигура стоит на F5, а горизонталь занята тремя фигурами, как сказано выше.
Что ж, неплохо. Проделав это, мы можем быстро получать атаки ладьи вдоль горизонтали. Но теперь нам надо расчитать атаки не по горизонтали, а вдоль вертикали. Для этого мы берем битборд occupied_rl90, который есть точная копия предыдущего occupied_squares, но повернут на 90 градусов, как показано на рисунке 10.
Когда мы извлекаем третью «горизонталь», мы на самом деле получаем информацию о занятости на вертикали F (возможно, имеется в виду третья сверху горизонталь — прим. перевод.). В ход опять идут предварительно расчитанные битборды атак, но на этот раз мы берем attacks_file[37][251] (еще раз, 37 означает поле F5, а занятые поля на этой вертикали образуют 11111011), значение которого мы определили, как показано на рисунке 11.
Теперь, взяв оба этих значения — атаки вдоль горизонтали и атаки вдоль вертикали — и сделав OR между ними, мы получаем полный набор атакованных полей для ладьи, стоящей на поле F5, для частного случая с заданными позициями по горизонтали и вертикали. В случае с ферзем мы точно так же используем два битборда для диагональных атак и два вращаемых по диагонали occupied_squares, чтобы получить тем же способом атаки по диагоналям, а в конце делаем OR между диагональными и вертикальными/горизонтальными атаками. Заметьте, что здесь нет никаких циклов. Алгоритм для дальнобойной фигуры выглядит следующим образом:
BITBOARD attacks=0;
if (BishopMover(piece)) {
get diaga1 status (shift/AND); /* 6 bits */
attacks|=diaga1h8_attacks[square][status];
get diagh1 status (shift/AND); /* 6 bits */
attacks|=diagh1a8_attacks[square][status];
}
if (RookMover(piece)) {
get rank status (shift/AND); /* 6 bits */
attacks|=rank_attacks[square][status];
get file status (shift/AND); /* 6 bits */
attacks|=file_attacks[square][status];
}И все, мы закончили, полностью. Два условия BishopMover() и RookMover() возвращают «ИСТИНУ», если фигура ходит по диагонали, как слон (слон или ферзь), или движется подобно ладье (ладья или ферзь). В Crafty это закодировано в типе фигуры, где P=1, N=2, K=3, B=5, R=6 и Q=7. При анализе этих чисел проверяется результат piece_type&4, и если результат ненулевой, это дальнобойная фигура. Далее, если результат piece_type&1 отличен от нуля, эта фигура ходит по диагонали, а если результат piece_type&2 ненулевой, то фигура может двигаться вдоль горизонталей/вертикалей.
5. Расчет attacks_to[64]
Битборд attacks_to[] был определен Слейтом и Аткином, как битборд с одним битом для каждого поля, с которого производится атака на данное поле. К примеру, attacks_to[28] (28 = E4) может выглядеть, как показано на рисунке 12, если предположить, что E4 атакуется черной ладьей на E8 и черным конем на F6, а защищается белой ладьей на E1 и белой пешкой на D3 (E4 отмечено буквой T, от «target»).
На этой картинке «T» — это атакуемое поле, на самом деле ему соответствует бит 0 в битборде. Четыре бита X (биты 1) показывают четыре поля, с которых стоящими на них фигурами производятся атаки на поле E4. Если мы хотим знать, как много черных фигур атакует E4, мы можем просто сделать AND этого битборда с битбордом occupied_squares для черных фигур. Результат будет иметь биты 1 на каждом поле, занятом черной фигурой, которая атакует E4. Аналогично с атакующими E4 белыми фигурами, мы точно так же делаем AND с битбордом occupied_squares для белых фигур.
Вопросы стоят следующие: (а) Как мы можем расчитать такой битборд и (б) насколько это трудоемко? Используя вышеприведенный метод генерации битбордов атак (вспомним, что генерация битбордов атак для недальнобойных фигур тривиальна, так как все атакуемые фигурой поля, в отличие от дальнобойных фигур, могут быть расчитаны на старте приложения и в дальнейшем не меняются), мы расчитаем атаку слона на E4, а затем сделаем AND с битбордом для белых/черных слонов и ферзей, что даст нам 1 бит для каждого слона/ферзя, независимо от их цвета, которые атакуют целевое поле. Мы запоминаем результат и делаем то же самое для ладьи и битбордов ладей/ферзей. Затем мы берем битборд атак коня, делаем AND с битбордом для белых/черных коней и повторяем это для королей и пешек. В итоге у нас есть пять битбордов, которые, если сделать OR между ними, покажут все поля, с которых производится атака на E4.
Теперь, когда мы можем получить набор полей, которые может атаковать фигура (используется при генерации хода) и набор полей, с которых производится атака на некоторое поле (используется, к примеру, для определения, находится ли король под шахом), мы можем использовать эту информацию в шахматной программе.
6. Использование битбордов в шахматном движке
Важно заметить, что обозначенный алгоритм дает битборд с полным комплектом ходов некоторой фигуры, не используя при этом никаких циклов. Однако в шахматной программе эти перемещения приходится разбивать на набор отдельных ходов «откуда/куда» для их оценки, и этот процесс в итоге определенно будет циклом, хотя и очень простым. Поле «откуда» известно, так что мы просто используем функцию FirstOne() для превращения первого бита в целое число, соответствующее полю «куда», а затем сбрасываем этот бит. Цикл продолжается пока все биты не будут сброшены. Ниже приведен настоящий код, делающий именно это для белого ферзя: (учтите, что в Crafty ход хранится в 21 бите. Младшие 6 бит указывают на поле «FROM» (откуда), следующие 6 — на поле «TO» (куда), еще 3 — это MOVING_PIECE (передвигаемая фигура), а последние 3 — это фигура PROMOTE_TO, в которую превращаются проведенные пешки.)
piecebd=WhiteQueens;
while (piecebd) {
from=LastOne(piecebd);
moves=AttacksQueen(from);
temp=from+(queen<<12);
while (moves) {
to=LastOne(moves);
move_list[i++]=temp+to<<6;
Clear(to,moves);
}
Clear(from,piecebd);
}На первый взгляд, это может показаться довольно неэффективным, но при изучении шахматной программы и задачи оценки хода обнаруживается, что ходы, требующие оценки, — это прежде всего взятия. Чтобы сгенерировать только ходы со взятиями, нужно просто получить вышеуказанный битборд атак и затем сделать AND с битбордом, содержащим все поля, занятые фигурами противника, — после этого останутся только те биты, которые соответствуют взятиям. Следовательно, при генерации взятий, которые являются самой большой частью шахматного древа, в цикле перебираются только некоторые, приводящие к взятию вражеской фигуры, ходы; тут нет перебора пустых полей между дальнобойной фигурой и фигурой, которую она бьет, и нет никаких особых проверок того, достигли мы края доски или нет. В итоге, это оказывается существенным выигрышем в сравнении с традиционным подходом. Ниже приведен тот же код для белого ферзя, но для получения исключительно взятий.
piecebd=WhiteQueens;
while (piecebd) {
from=LastOne(piecebd);
moves=AttacksQueen(from) & BlackPieces;
temp=from+(queen<<12);
while (moves) {
to=LastOne(moves);
move_list[i++]=temp+to<<6;
Clear(to,moves);
}
Clear(from,piecebd);
}Он прост и понятен, и если у королевы нет ни одного хода со взятием вражеской фигуры, то внутренний цикл никогда не выполнится вообще. Если вы захотите, можете передать вашему генератору ходов битборд «целей». Чтобы сгенерировать все ходы, передайте целевой битборд, который есть простое дополнение occupied_squares для осуществляющей ход стороны, и в результате будут сгенерированы все ходы (за исключением взятий ваших собственных фигур).
Как перед этим показано, довольно просто при необходимости получить битборды attacks_to[]. Это не имеет высокой вычислительной сложности, легко реализуется и предоставляет функционал (attacks_to[sq]), если/когда он нужен. Наиболее частое применение для этого типа информации — это ответ на вопрос «находится ли король под шахом?», что еще проще сделать, чем описано ранее. Для каждого типа фигур (слон/ферзь, ладья/ферзь, конь, король и пешка) мы генерируем битборд атак и потом делаем AND для каждого из них с битбордом вражеской фигуры (нас не волнует, если наши фигуры атакуют нашего собственного короля, важны только фигуры оппонента), и, если результат ненулевой, мы сразу же возвращаем «ИСТИНУ», говорящую «да, король атакован и под шахом».
Это также может быть использовано для реализации статического блока расчета разменов, используемого при оценке ходов. Для некоторого поля, где требуется расчитать последовательность разменов, мы сначала берем attacks_to[sq], что дает каждую фигуру, напрямую атакующую это поле. Находим наименее значимую вражескую фигуру, которая атакует это поле; для этого мы делаем AND между attacks_to и каждым из шести битбордов для вражеских фигур, начиная с пешек и двигаясь по возрастанию стоимости фигуры вплоть до короля. Когда в результате AND получается ненулевой результат, мы узнаем стоимость фигуры, которая должна будет первой атаковать целевое поле. Мы сбрасываем эту атакующую фигуру из attacks_to, так как она уже использована, после чего делаем AND получившегося attacks_to с шестью битбордами для наших фигур, чтобы получить защитника с наименьшей стоимостью. Повторяем до тех пор, пока attacks_to не станет пустым.
Однако что насчет дальнобойных фигур, которые атакуют целевое поле так, что одна находится позади другой? Это тоже несложно расчитать. Мы знаем фигуру, которую мы только что «использовали» путем сбрасывания ее из битборда attacks_to, так что можем определить является ли она дальнобойной или нет (например, пешка, слон, ладья или ферзь, сзади которых стоят другие фигуры, могут образовывать «батарею»). Нам надо лишь сделать еще одну операцию AND, чтобы выяснить, есть ли в этом направлени другая фигура за той, которую мы только что использовали. Если это так, и она подходящего типа (слон/ферзь для диагоналей, ладья/ферзь для горизонталей/вертикалей), мы просто делаем OR этой фигуры с attacks_to, в результате чего она теперь атакует целевое поле, не имея помехи перед собой. (мы используем теперь уже знакомые битборды plusN[]/minusN[], а ответ на вопрос, как это сделать, оставляем в качестве упражнения читателю.)
Обратите внимание, мы рассматривали лишь вопрос, атакует фигура поле или нет, ничего более. Это можно применить к королю, к более значимой фигуре или перегрузить для защиты двух полей в одно и то же время. Следовательно, ошибки возможны. Однако для одного поля алгоритм работает достаточно точно. Например, в случае, когда у нас три фигуры в батарее (скажем, ферзь и две ладьи), стоящий впереди ферзь может стать проблемой, так как при анализе размена мы должны быть уверены, что первым будет использован именно он. Данный алгоритм гарантирует это, поскольку ладьи не будут отражены в attacks_to до тех пор, пока ферзь не будет убран.
7. Заключение
Есть множество преимуществ использования битбордов, но на сегодняшний день наиболее важным является «плотность данных». Обратите внимание, что все 64 бита важны, даже если многие заканчиваются нулями, так как они отражают статус некоторого поля. Это означает, что поскольку CPU перемещает эти 64-битные битборды, он не тратит внутреннюю пропускную способность на перемещение неиспользуемых данных, что случается, когда обычная шахматная программа работает на 64-битной машине. Там большинство 64-битных слов не используются, они просто являются дополнительной ненужной информацией.
Для текущих 64-битных архитектур (Alpha, HP, MIPS — вот немногие из них) и для новых 64-битных архитектур, таких как процессор Intel Merced, использование битбордов имеет огромный смысл, поскольку тут битборды получают максимум преимуществ от размера внутреннего регистра процессора и шины. К примеру, большинство обычных битовых операций (AND, OR, XOR, сдвиг и так далее) на 32-битных машинах используют по меньшей мере две инструкции — одна для каждой половины 64-битного битборда. На 64-битной архитектуре с той же тактовой частотой эти операции выполняются в два раза быстрее, потому что они требуют только одну инструкцию для обработки. Это выигрыш в производительности, которым нельзя пренебрегать, потому что он абсолютно даровой.
Множество программ сейчас используют битборды для некоторых функций, таких как расчет пешечной структуры (потому что это удобный и компактный способ представления пешек в качестве одной переменной), определения, находится ли король под шахом или нет (так как всего одной операцией AND битборды позволяют очень просто решить, может ли фигура атаковать короля), и для других целей. «Chess 4.0» начала революцию битбордов, являясь первой программой, использующей их исключительно для представления доски, а программы, подобные Crafty (есть и многие другие. Слишком много, чтобы всех перечислить), продолжили это развитие. Однако, вероятно, основные улучшения в производительности при использовании битбордов пришли из проекта Crafty, когда в качестве альтернативы обычному последовательному обновлению, нашедшему место в «Chess 4.0», была придумана концепция «вращаемых битбордов», что дало существенный прирост в производительности без потери возможностей. В настоящее время самым животрепещущим вопросом остается «как еще можно использовать битборды в шахматной программе, чтобы еще более увеличить ее производительность?». Есть и большая опасность злоупотребления битбордами. Как предупреждает старая поговорка, «для человека с молотком все выглядит как гвоздь» («заставь дурака Богу молиться, он и лоб расшибет» — прим. перевод.) Однако очень важно, чтобы мы (хотя бы раз) попытались заколотить все вокруг, чтобы увидеть, будет ли «молоток» работать, или лучше подыскать другой инструмент для некоторых задач.
Автор: Роберт Хайат
Оригинал: http://www.cis.uab.edu/info/faculty/hyatt/bitmaps.html
От переводчика
Данная статья предполагает наличие у читателя некоторых начальных знаний о битбордах и о том, как с помощью них представляется шахматная доска. Однако информации об этом достаточно много, есть много хороших переводов и на русский язык, так что ознакомиться не составит труда. Я переводил эту статью, так как, к сожалению, не нашел ни одного хорошего перевода именно методов вращаемых и магических битбордов.
В качестве ознакомления рекомендую посмотреть следующие ссылки:
www.frayn.net/beowulf/theory.html#bitboards
www.craftychess.com
Я взял на себя смелость перевести английское слово «bitboard», как «битборд», так как общепринятого шахматного термина мне найти не удалось, а близкое по смыслу русское «битовое поле» является неоднозначным и громоздким.
В английском языке слова «bitmap» и «bitboard» являются синонимами, тогда как русские понятия «битовое поле» и «битовая карта» существенно отличаются по смыслу. В обоих случаях я использую слово «битборд».
В программировании побитовые операции привычней звучат на английском языке, поэтому я оставил английские варианты: AND, OR и т. д., но для ясности также привел и русский вариант при первом вхождении такого слова.