Представление доски в компьютерных шахматах — это структура данных в шахматной программе, представляющая позицию на шахматной доске и связанное с ней состояние игры. [1] Представление доски имеет основополагающее значение для всех аспектов шахматной программы, включая генерацию ходов, функцию оценки, выполнение и отмену ходов (т. е. поиск), а также поддержание состояния игры во время игры. Существует несколько различных представлений доски. Шахматные программы часто используют более одного представления доски в разное время для эффективности. Эффективность выполнения и объем памяти являются основными факторами при выборе представления доски; вторичными соображениями являются усилия, необходимые для кодирования, тестирования и отладки приложения.
Ранние программы использовали списки частей и списки квадратов, оба основаны на массивах. Большинство современных реализаций используют более сложный, но и более эффективный подход битовых массивов, называемый битбордами , которые отображают биты 64-битного слова или двойного слова в квадраты доски.
Полное описание шахматной позиции, т.е. «состояние» позиции, должно содержать следующие элементы:
Представление доски обычно не включает статус правила тройного повторения ничьей . Чтобы определить это правило, необходимо сохранить полную историю игры с последнего необратимого действия (взятие, перемещение пешки или рокировка), и поэтому обычно отслеживается в отдельных структурах данных. Без этой информации модели могут повторять позицию, несмотря на выигрышное преимущество, что приводит к чрезмерному количеству ничьих. [2]
Состояние доски может также содержать вторичную производную информацию, например, какие фигуры атакуют поле; для полей, содержащих фигуры, какие поля атакуются или охраняются этой фигурой; какие фигуры связаны; и другое удобное или временное состояние.
Состояние доски связано с каждым узлом дерева игры, представляя позицию, достигнутую ходом, независимо от того, был ли этот ход сыгран на доске или сгенерирован как часть поиска программы. Оно концептуально локально для узла, но может быть определено глобально и постепенно обновляться от узла к узлу по мере обхода дерева.
Некоторые из самых ранних шахматных программ, работающих с крайне ограниченным объемом памяти, поддерживали последовательные списки (массивы) фигур в удобном для поиска порядке, например, от наибольшей к наименьшей; с каждой фигурой было связано ее местоположение на доске, а также другая информация, такая как поля, представляющие ее допустимые ходы. Было несколько списков, один набор для белых фигур, а другой для черных фигур. Списки обычно делились на фигуры и пешки. Это было компактное представление, поскольку большинство полей доски не заняты, но неэффективное, поскольку получение информации об отношении фигур к доске или друг к другу было утомительным. Списки фигур все еще используются многими современными программами в сочетании с отдельной структурой представления доски, чтобы предоставить последовательный доступ к фигурам без поиска по доске.
Один из самых простых способов представления доски — создание двумерного массива 8x8 (или, что эквивалентно, одномерного массива из 64 элементов). Каждый элемент массива будет определять, какая фигура занимает данную клетку, или, в качестве альтернативы, является ли клетка пустой. Распространенная кодировка — считать 0 пустым, положительное — белым, а отрицательное — черным, например, белая пешка +1, черная пешка −1, белый конь +2, черный конь −2, белый слон +3 и т. д. Эта схема называется адресацией почтового ящика .
Проблема с этим подходом возникает во время генерации ходов. Каждый ход должен быть проверен, чтобы убедиться, что он не заходит за край доски, что значительно замедляет процесс. Одним из решений является использование массива 12x12 вместо этого, с внешними краями, заполненными, скажем, значением 99. Во время генерации ходов операция проверки наличия фигуры на поле назначения также укажет, находится ли поле назначения за пределами доски. [1] [3]
Лучшего использования памяти можно добиться с помощью массива 10x12, который обеспечивает те же функциональные возможности, что и массив 12x12, путем перекрытия файлов самого левого и самого правого края (которые помечены как находящиеся вне доски). [1] [3] Некоторые шахматные движки используют массивы 16x16 для повышения скорости преобразования номеров рядов и линий и позволяют использовать некоторые специальные приемы кодирования для атак и т. д.
Метод 0x88 использует тот факт, что размеры шахматной доски 8x8 являются четной степенью двойки (т. е. 8 в квадрате). Доска использует одномерный массив размером 16x8 = 128, пронумерованный от 0 до 127, а не массив размером 64. По сути, это две доски рядом друг с другом, фактическая доска слева, а доска справа будет содержать нелегальную территорию. Двоичная разметка для ранга и вертикали законной координаты доски в массиве 0rrr0fff(где r — это 3 бита, используемые для представления ранга. f — для вертикали). Например, 0x71 (двоичное 01110001) будет представлять квадрат b8 (в алгебраической нотации ). При генерации ходов с основной доски можно проверить, находится ли конечный квадрат на основной доске, прежде чем обращаться к массиву, просто выполнив операцию AND над номером квадрата и шестнадцатеричным 0x88 (двоичным 10001000). Ненулевой результат указывает на то, что квадрат находится за пределами основной доски. Кроме того, разница между координатами двух квадратов однозначно определяет, находятся ли эти два квадрата в одной строке, столбце или диагонали (обычный запрос, используемый для проверки определения). [1] [4]
Более эффективным, но и более сложным представлением доски, чем структуры на основе массива, является bitboard . Bitboard — это 64-битная последовательность битов (0 или 1), которая указывает на отсутствие или наличие (ложь или истина) некоторого состояния каждого пространства на доске. Затем положение доски может быть представлено с помощью серии bitboard. Например, серия bitboard для каждого типа фигуры, для каждой стороны, может представлять положение доски.
Преимущество этого представления заключается в возможности использовать параллельные битовые операции над 64-битными сущностями вместо итерации для манипулирования и получения информации о состоянии платы. Это позволяет максимально использовать имеющееся оборудование, особенно с учетом того, что 64-битные процессоры стали мейнстримом.
Существенным преимуществом битбордов является то, что они позволяют предварительно собирать и хранить в таблице карты для полей, атакуемых каждым типом фигуры на каждом поле доски, так что возможные ходы фигуры могут быть извлечены за одну выборку памяти карты атаки для поля, на котором находится фигура, которая, исключая поля, занятые дружественными фигурами (одна битовая операция), дает допустимые ходы фигуры. Но ходы скользящих фигур (ладей, слонов, ферзей) неопределенны, поскольку ходы этих фигур зависят от конфигурации других фигур на доске. Поэтому были разработаны специальные и сложные структуры данных для представления их ходов.
Повернутые битборды — это метод генерации ходов для скользящих фигур, который использует повернутые копии битборда для размещения пробелов (битов) в строке или диагонали в смежных битах, аналогичных битам, представляющим ранг. Эти биты можно извлечь и использовать в качестве индекса в таблице для получения карты пробелов, атакуемых этими фигурами. Битборд поворачивается на 90° для индексации файла и на 45° или -45° для диагональной индексации. Поворот шахматной доски концептуально сложен, а поворот битборда вычислительно неэлегантен, но преобразование позволяет избежать последовательного перечисления ходов фигур или длинной последовательности сдвига и маскировки битборда карты атаки фигуры для учета конфигурации доски.
Маскированные ряды, ряды и диагонали скользящих частей могут быть использованы с помощью хэш-функции для прямой индексации таблицы предварительно вычисленных векторов атак на основе битов занятости в замаскированной части. Одна из таких схем, которая использует идеальную хэш-функцию вместе с трюками для минимизации потенциального размера таблицы, которая должна храниться в памяти, называется «магическими битбордами».
Таблица транспозиции — это кэш ранее просмотренных позиций и связанных с ними оценок в игровом дереве , сгенерированном программой компьютерной игры. Для быстрого поиска в таблице может использоваться хэш-функция, например хэширование Зобриста , чтобы ускорить поиск соответствующих досок. [5]
Были предложены и другие методы, такие как компактное представление шахматной доски (CCR), [ требуется ссылка ], но ни один из них не получил признания.
CCR использует 4 бита на квадрат для представления занятости квадрата, [Примечание 1] весь ряд может быть представлен 32 битами, а доска — 8 регистрами (с дополнительным одним для информации об оставшейся позиции). Код занятости квадрата может быть набран из регистра и добавлен в счетчик программы для индексации таблицы переходов , переходя напрямую к коду для генерации ходов для типа фигуры на этом квадрате (если таковые имеются). Хотя программа длиннее, чем для обычных методов генерации ходов, не требуется никаких проверок края доски, и никакие ходы за пределы доски невозможны, что увеличивает скорость генерации ходов.
Недостатками CCR являются: 1) зависимость от 32-битного размера слова; 2) наличие не менее 9 свободных регистров для API; 3) необходимость программирования ассемблера на архитектуре CISC для доступа к регистрам; 4) непереносимость ассемблерного приложения.
{{citation}}: CS1 maint: numeric names: authors list (link)