Битборды

Самый простой способ представить шахматную доску — использовать растровые доски. С ними легко работать, и они значительно облегчают предварительные вычисления. Битборд — это 64-битное число, каждый бит которого представляет отдельный квадрат на шахматной доске. Бит равен 1, если соответствующая клетка занята, и 0 в противном случае. Например, битборд пешки для белых в начале игры равен 65280 или в двоичном формате:

Обычно доска представлена ​​14 досками: по 7 для каждой стороны, по 1 для каждого типа фигур (ладья, слон и т. д.) и по 1 для всех фигур вместе взятых.

Я только что объяснил размещение битбордов, но битборды имеют множество применений. Например, вы можете представить поля, атакованные одним конем, с помощью битборда. Поля, атакованные конем, соответствуют 1, а не атакованные поля соответствуют 0.

Одной из важных операций на битборде является битовое сканирование. Эта операция находит младший значащий бит, равный 1, а затем (необязательно) переключает этот бит на 0. Эта операция выполняется много раз в ходе генерации/оценки хода и поэтому должна выполняться как можно быстрее. Поэтому мы используем последовательности ДеБрюйна. Идея состоит в том, что если мы умножим два двоичных числа, это приведет к сначала сдвигу двоичного числа, а затем к добавлению некоторой (нерелевантной) последовательности чисел в конце. Величина сдвига определяется младшим битом или битом, положение которого мы хотим найти! Используя эту информацию, мы можем выполнить побитовое сканирование числа: 1) умножить его на «специальное» число, в котором каждая последовательная последовательность из 6 бит уникальна. 2) проверьте последние биты и посмотрите, где в исходном (специальном) номере они находились.

Предварительный расчет (короли, кони и пешки)

Лучший способ вычислить ходы для любой фигуры — не сделать это, а уже сделать это. Идея предварительных вычислений лежит в основе генерации перемещений битовой панели. В относительно простом случае с конями мы можем просто просмотреть каждую клетку на доске, поместить туда коня и вычислить, на какие клетки он может переместиться. Наконец, мы сохраняем эти результаты на битборде. Идея аналогична для королей и пешек, хотя необходимо предпринять некоторые дополнительные шаги. Для королей мы должны удалять поля, атакованные фигурами противника (это, к сожалению, нужно делать во время выполнения и может быть дорогостоящим). Что касается пешек, мы должны учитывать фигуры, блокирующие путь пешек и т. д.

Волшебство!

Задача предварительного расчета становится намного сложнее для скользящих фигур (ладей, слонов и ферзей). Это связано с тем, что они могут быть заблокированы, и поэтому каждый случай блокировки приходится рассматривать индивидуально. Поскольку части блока хранятся на битовой доске, если мы хотим выполнить предварительные вычисления, нам нужна справочная таблица размером 2⁶⁴ (1/0 для каждого квадрата). Однако не все эти биты важны; единственные значимые биты — это те, которые находятся ближе всего к нашему скользящему элементу, поэтому теоретически может быть число, которое сдвигает эти значимые биты вперед. Затем мы могли бы сделать ключами нашей таблицы поиска только первые биты, в результате чего таблица поиска будет гораздо более разумного размера (обычно около 4000 записей). Мы можем найти эти магические числа, просто проверяя случайные числа, пока не найдем то, которое работает. (Скорость не является проблемой, поскольку эти числа рассчитываются только один раз при запуске или предварительно вычисляются и сохраняются.)

Юридическая генерация (чеки и булавки)

В настоящее время у нас нет системы борьбы с псевдозаконными действиями, такими как те, которые могут привести к тому, что король окажется под контролем. Существует два типа этих псевдозаконных ходов: ходы, сделанные королем, и ходы других фигур, обнажающих короля (кегли). В первом типе мы должны использовать простой (и, к сожалению, медленный) подход: пройти через каждую фигуру противника и сохранить атакуемые ею клетки на битовой доске. Затем мы можем убрать любое из этих полей из-под атак короля. У булавок есть гораздо более элегантный (и быстрый) ответ. Связки могут быть вызваны только скользящими фигурами противника (слонами/ладьями/ферзями), поэтому мы рассматриваем короля как каждую из них, а затем смотрим, какую из фигур противника он может атаковать, перепрыгивая через свои фигуры. Таким образом мы получаем все возможные «пиннеры». Затем мы можем пересечь атаки рентгеновского короля (сгенерированные на предыдущем шаге) с атаками каждого пиннера, чтобы получить возможные поля, на которых могут находиться закрепленные фигуры. Каждый из них имеет форму одного луча. Для каждого из этих лучей мы проверяем, есть ли ровно одна дружественная фигура (связанная фигура) и нет вражеских фигур. Если да, то эта фигура закреплена, и мы можем пересекать ее атаки соответствующим лучом.

Псевдоюридический против юридического

Вышеупомянутые усилия могут сильно повлиять на скорость генерации ходов, и, как вы позже увидите, большинство сгенерированных ходов не обрабатываются полностью. Следовательно, генерация псевдозаконных ходов может оказаться более эффективной при реальном поиске. Другими словами, во время поиска большинство ходов, которые могли бы привести к шаху, уже оказываются невыгодными и отсекаются, в результате чего их все равно не обрабатывают. Это означает, что создание легальных ходов не требуется.