Представительство на доске (компьютерные шахматы)

Представление доски в компьютерных шахматах — это структура данных в шахматной программе, представляющая позицию на шахматной доске и связанное с ней состояние игры. ^{[ 1 ]} Представление на доске имеет основополагающее значение для всех аспектов шахматной программы, включая генерацию ходов, функцию оценки, выполнение и отмену ходов (т. е. поиск), а также поддержание состояния игры во время игры. Существует несколько различных представлений в совете директоров. Шахматные программы часто используют более одного представления доски в разное время для повышения эффективности. Эффективность выполнения и объем памяти являются основными факторами при выборе представления платы; второстепенными факторами являются усилия, необходимые для написания кода, тестирования и отладки приложения.

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

Состояние Совета

Полное описание шахматной позиции, то есть позиции «состояние», должно содержать следующие элементы:

Расположение каждой фигуры на доске
Чья очередь двигаться
Статус правила ничьей в 50 ходов . Название этого метода иногда немного сбивает с толку, поскольку это 50 ходов каждого игрока и, следовательно, 100 полуходов или ходов. Например, если предыдущие 80 полуходов прошли без взятия или хода пешки, правило пятидесяти ходов вступит в силу еще через двадцать полуходов.
Будет ли какой-либо игрок навсегда дисквалифицирован на рокировку , как на королевском , так и на ферзевом фланге .
Если на проходе . возможен захват

Представление на доске обычно не включает статус тройного повторения правила жеребьевки . Чтобы определить это правило, необходимо вести полную историю игры от последнего необратимого действия (взятия, движения пешки или рокировки), и поэтому она обычно отслеживается в отдельных структурах данных. Без этой информации модели могут повторить позицию, несмотря на наличие выигрышного преимущества, что приведет к чрезмерному количеству ничьих. ^{[ 2 ]}

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

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

Типы

На основе массива

Списки предметов

Некоторые из самых ранних шахматных программ, работавших с чрезвычайно ограниченным объемом памяти, поддерживали последовательные списки (массивы) фигур в удобном для поиска порядке, от самой большой к самой маленькой; С каждой фигурой было связано ее расположение на доске, а также другая информация, например, квадраты, обозначающие ее допустимые ходы. Было несколько списков: один для белых фигур, другой для черных. Списки обычно делились на фигуры и пешки. Это было компактное представление, поскольку большинство клеток доски не занято, но оно было неэффективным, поскольку получение информации об отношении фигур к доске или друг к другу было утомительным. Списки фигур до сих пор используются во многих современных программах вместе с отдельной структурой представления на доске, чтобы обеспечить последовательный доступ к фигурам без поиска на доске.

Квадратный список

Один из самых простых способов представления доски — создание двумерного массива 8x8 (или, что то же самое, одномерного массива из 64 элементов). Каждый элемент массива будет определять, какая фигура занимает данную клетку или, альтернативно, если клетка пуста. Обычное кодирование предполагает, что 0 считается пустым, положительный – белым, а отрицательный – черным, например, белая пешка +1, черная пешка –1, белый конь +2, черный конь –2, белый слон +3 и так далее. Эта схема называется адресацией почтового ящика .

Проблема с этим подходом возникает во время генерации хода. Каждый ход необходимо проверять, чтобы он не заворачивался за край доски, что существенно замедляет процесс. Одним из решений является использование вместо этого массива 12x12, внешние края которого заполнены, скажем, значением 99. Во время генерации хода операция проверки наличия фигуры на поле назначения также будет указывать, находится ли поле назначения за пределами доски. ^{[ 1 ]}^{[ 3 ]}

Лучшего использования памяти можно добиться с помощью массива 10x12, который обеспечивает те же функциональные возможности, что и массив 12x12, за счет перекрытия крайнего левого и крайнего правого краевых файлов (которые помечены как внеплатные). ^{[ 1 ]}^{[ 3 ]} Некоторые шахматные движки используют массивы 16x16 для повышения скорости преобразования номеров в рядах и позволяют использовать некоторые специальные приемы кодирования для атак и т. д.

метод 0x88

Метод 0x88 использует тот факт, что размеры шахматной доски 8x8 представляют собой четную степень двойки (т. е. 8 в квадрате). Доска использует одномерный массив размером 16x8 = 128 с номерами от 0 до 127, а не массив размером 64. По сути, это две доски, расположенные рядом друг с другом: фактическая доска слева, а доска справа будет содержать нелегальная территория. Двоичная структура для ранга и файла координат юридического совета в массиве: 0rrr0fff (R — это 3 бита, используемые для обозначения ранга. F — для файла). Например, 0x71 (двоичный 01110001) будет представлять собой квадрат b8 (в алгебраических обозначениях ). При создании ходов с основной доски можно проверить, что клетка назначения находится на основной доске, прежде чем обращаться к массиву, просто выполняя операцию И для номера клетки с шестнадцатеричным числом 0x88 (двоичный код). 10001000). Ненулевой результат указывает на то, что квадрат находится за пределами основной доски. Кроме того, разница между координатами двух квадратов однозначно определяет, находятся ли эти два квадрата в одной строке, столбце или диагонали (обычный запрос, используемый для определения проверки). ^{[ 1 ]}^{[ 4 ]}

Битборды

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

Преимущество этого представления заключается в возможности использовать параллельные операции с 64-битными объектами вместо итераций для манипулирования и получения информации о состоянии платы. Это позволяет максимально использовать доступное оборудование, особенно с учетом того, что 64-битные процессоры стали массовыми.

Существенным преимуществом битбордов является то, что они позволяют предварительно сопоставлять и сохранять карты мест, атакованных фигурами каждого типа на каждой клетке доски, и сохранять их в таблице, так что возможные ходы фигуры можно получить за одну выборку памяти. карты атаки для поля, на котором находится фигура, что, исключая места, занятые дружественными фигурами (одна побитовая операция), дает допустимые ходы фигуры. Но ходы скользящих фигур (ладей, слонов, ферзей) неопределенны, поскольку ходы этих фигур зависят от расположения других фигур на доске. Поэтому для представления их ходов были разработаны специальные и сложные структуры данных.

Повернутые битборды

Повернутые битборды — это метод генерации ходов для скользящих частей, который использует повернутые копии битбордов для размещения пробелов (битов) в файле или диагонали в соседних битах, аналогичных битам, представляющим ранг. Эти биты можно извлечь и использовать в качестве индекса в таблице для получения карты пространств, атакованных этими частями. Битборд поворачивается на 90° для индексации файлов и на 45° или -45° для диагональной индексации. Вращение шахматной доски концептуально сложно, а вращение битовой доски вычислительно неэлегантно, но преобразование позволяет избежать последовательного перебора ходов фигуры или длительной последовательности смещения и маскировки битовой доски карты атаки фигуры, чтобы принять во внимание конфигурацию доски.

Прямой поиск

Замаскированные ранги, файлы и диагонали скользящих частей можно использовать с помощью хэш-функции для прямой индексации таблицы заранее вычисленных векторов атак на основе битов занятости в маскированной части. Одна из таких схем, в которой используется идеальная хэш-функция вместе с приемами, позволяющими минимизировать потенциальный размер таблицы, которая должна храниться в памяти, называется «волшебными битбордами».

Таблица транспонирования

Таблица транспонирования представляет собой кэш ранее просмотренных позиций и связанных с ними оценок в дереве игры , созданном программой компьютерной игры. Для быстрого поиска по таблице можно использовать хеш-функцию, например хеширование Zobrist , для ускорения поиска совпадающих досок. ^{[ 5 ]}

Другие методы

Были предложены и другие методы, такие как представление на компактной шахматной доске (CCR). ^{[ нужна ссылка ]} но ни один из них не получил признания.

CCR использует 4 бита на квадрат для представления занятости квадрата. ^{[ Примечания 1 ]} весь ранг может быть представлен в 32 битах, а плата - в 8 регистрах (с дополнительным для оставшейся информации о позиции). Код занятости поля можно набрать из регистра и добавить в счетчик программы для индексации таблицы переходов , переходя непосредственно к коду для генерации ходов для типа фигуры на этом поле (если таковые имеются). Хотя программа длиннее, чем для традиционных методов генерации ходов, проверки края доски не требуются, а ходы за пределы доски невозможны, что увеличивает скорость генерации ходов.

Недостатками CCR являются: 1) зависимость от размера 32-битного слова; 2) наличие не менее 9 свободных регистров API; 3) необходимость ассемблерного программирования на CISC-архитектуре для доступа к регистрам; 4) непереносимость ассемблерного приложения.

Примечания

^ Существует 6 типов фигур: король, ферзь, ладья, слон, конь, пешка для каждой из черных и белых фигур плюс незанятое поле, всего 13 состояний, представленных в 4 или 2 битах. ⁴=16 возможных кодов.

Ссылки

^ Jump up to: ^а ^б ^с ^д Хаятт, Роберт . «Представления на доске шахматной программы» . Архивировано из оригинала 12 февраля 2013 года . Проверено 15 января 2012 г.
^ mnj12 (07 июля 2021 г.), mnj12/chessDeepLearning , получено 7 июля 2021 г. {{citation}}: CS1 maint: числовые имена: список авторов ( ссылка )
^ Jump up to: ^а ^б Фрей, Питер В., изд. (1983) [1977], «Введение в компьютерные шахматы», Chess Skill In Man and Machine , Springer – Verlag, стр. 55–56.
^ Метод 0x88. Брюс Морленд
^ Альберт Линдси Зобрист, Новый метод хеширования с применением для игр , Tech. Представитель 88, факультет компьютерных наук, Университет Висконсина, Мэдисон, Висконсин (1969).

[6] Существует 6 типов фигур: король, ферзь, ладья, слон, конь, пешка для каждой из черных и белых фигур плюс незанятое поле, всего 13 состояний, представленных в 4 или 2 битах. ⁴=16 возможных кодов.

[Hyatt-1] Jump up to: ^а ^б ^с ^д Хаятт, Роберт . «Представления на доске шахматной программы» . Архивировано из оригинала 12 февраля 2013 года . Проверено 15 января 2012 г.

[2] 12 (07 июля 2021 г.), mnj12/chessDeepLearning , получено 7 июля 2021 г. {{citation}}: CS1 maint: числовые имена: список авторов ( ссылка )

[Frey1977-3] Jump up to: ^а ^б Фрей, Питер В., изд. (1983) [1977], «Введение в компьютерные шахматы», Chess Skill In Man and Machine , Springer – Verlag, стр. 55–56.

[4] Метод 0x88. Брюс Морленд

[5] Альберт Линдси Зобрист, Новый метод хеширования с применением для игр , Tech. Представитель 88, факультет компьютерных наук, Университет Висконсина, Мэдисон, Висконсин (1969).

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ Примечания 1 ]