Битборд

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

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

Битборды особенно эффективны, когда связанные биты различных связанных состояний на плате укладываются в одно или двойное слово архитектуры ЦП, так что одиночные побитовые операторы, такие как И и ИЛИ, можно использовать для создания или запроса состояний игры.

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

Описание

Дополнительная информация: Битовое поле.

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

Эффективность битбордов усиливается двумя другими свойствами реализации. Во-первых, битборды быстро обновляются, например, биты в исходной и целевой позициях на битборде меняются местами для определения местоположения детали при ее перемещении. Во-вторых, растровые изображения, представляющие статические свойства, такие как все поля, атакованные фигурами каждого типа для каждой позиции на шахматной доске, могут быть предварительно сопоставлены и сохранены в таблице, так что для ответа на вопрос типа «Каковы допустимые ходы коня на поле e4?» " на него можно ответить одной выборкой памяти.

Реализации битовых полей используют преимущества наличия полнословных (32-битных или 64-битных) поразрядных логических операций, таких как AND, OR, NOT и других, в современных архитектурах ЦП, чтобы быть эффективными. Битборды могут быть неэффективны на более ранних 8- и 16-битных мини-компьютерах и микропроцессорных архитектурах.

Проблемы реализации

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

Использование процессора

Плюсы

Представления Bitboard используют параллельные побитовые операции, доступные почти на всех процессорах , которые выполняются за один цикл, полностью конвейеризированы, кэшируются и т. д. Почти все процессоры имеют AND , OR , NOR и XOR . Более того, современные процессоры имеют конвейеры команд , которые ставят инструкции в очередь для выполнения. Процессор с несколькими исполнительными блоками может выполнять более одной инструкции за такт, если в конвейере доступно более одной инструкции. Обычные последовательности команд с ветвями могут привести к опустошению конвейера, если ветвь предсказана неверно. Многие операции с битбордами требуют меньшего количества условных операторов и, следовательно, увеличивают конвейерную обработку и позволяют эффективно использовать несколько исполнительных блоков на многих процессорах.

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

Если размер битовой панели превышает ширину набора команд, для выполнения над ней операции полной ширины потребуется несколько инструкций. Таким образом, программа, использующая 64-битные растровые платы, будет работать быстрее на 64-битном процессоре, чем на 32-битном процессоре.

Минусы

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

Если у процессора нет аппаратных инструкций для «первой единицы» (или « подсчета ведущих нулей ») и « подсчета единиц » (или «подсчета нулей»), реализация будет существенно затруднена, поскольку эти операции крайне неэффективно кодировать как циклы ассемблера.

Использование кэша и памяти

Плюсы

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

Минусы

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

Инкрементное обновление

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

Предварительно рассчитанные растровые изображения и поиск по таблицам

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

Шахматные доски

Очевидным и простым представлением конфигурации фигур на шахматной доске является список (массив) фигур в удобном для поиска порядке (например, от наименьшего к наибольшему по значению), который сопоставляет каждую фигуру с ее местоположением на доске. Аналогично, сопоставление пространств, атакованных каждой фигурой, требует последовательного перебора таких пространств для фигуры. Эта схема называется адресацией почтового ящика . Отдельные списки ведутся для белых и черных фигур, а часто и для белых и черных пешек. Карты обновляются при каждом ходе, что требует линейного поиска (или двух, если фигура была захвачена) по списку фигур. Преимущество почтового ящика — простой код; недостатком является то, что линейный поиск выполняется медленно. Более быстрые, но более сложные структуры данных, которые сопоставляют фрагменты с местоположениями, называются битбордами .

Стандартный

Алгебраические обозначения

В представлениях растровых досок каждый бит 64-битного слова (или двойного слова в 32-битных архитектурах) связан с квадратом шахматной доски. Можно использовать любое отображение битов в квадраты, но по общему соглашению биты связаны с квадратами слева направо и снизу вверх, так что бит 0 представляет квадрат a1, бит 7 — квадрат h1, бит 56 — квадрат a8, а бит 7 — квадрат h1, бит 56 — квадрат a8, а бит 7 — квадрат h1. 63 – это квадрат h8.

Многие различные конфигурации доски обычно представлены отдельными битбордами, включая расположение королей, всех белых пешек, всех черных пешек, а также битбордами для каждого из других типов фигур или комбинаций фигур, таких как все белые фигуры. Два битборда атаки также универсальны: один битборд на клетку для всех фигур, атакующих это поле, и инверсный битборд для всех полей, атакованных фигурой, для каждого поля, содержащего фигуру. Битборды также могут быть константами, например, тот, который представляет первый ранг, который будет иметь единицы в позициях 0–7. Другие локальные или переходные битборды, такие как «все места, прилегающие к королю, атакованные фигурами противника», могут быть сопоставлены по мере необходимости или удобно.

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

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

Вспомогательные представления растровых изображений

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

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

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

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

Прямое хеширование

Рядовые векторы атаки ладей, а также диагональные и антидиагональные векторы атаки слонов могут быть отдельно замаскированы и использованы в качестве индексов в хеш-таблице заранее вычисленных векторов атаки в зависимости от занятости, по 8 битов для ладей и 2-8 битов. каждый для епископов. Полный вектор атаки фигуры получается как объединение каждого из двух однонаправленных векторов, индексированных из хеш-таблицы. Количество записей в хеш-таблице скромное, порядка 8*2^8 или 2 КБ, но требуются два вычисления хеш-функции и два поиска на каждую часть. см. используемую схему хеширования.

Волшебные битборды

Волшебные битборды — это экстраполяция компромисса во времени и пространстве при прямом хешировании векторов атак. Они используют преобразование полного вектора атаки в качестве индекса в хеш-таблицу. «Магия» — неправильное название и просто относится к созданию и использованию идеальной хеш-функции в сочетании с приемами, позволяющими уменьшить потенциальный размер хеш-таблицы, которую необходимо хранить в памяти, которая составляет 8*2^64 или 144 эксабайта. . Первое наблюдение заключается в том, что внешние поля или первая и восьмая ряды вместе с колонками «a» и «h» не имеют значения для занятости вектора атаки: фигура атакует эти поля или нет (в зависимости от других блокирующих фигур) независимо от того, занятости, поэтому их можно исключить из рассмотрения, оставив только 6x6 или 36 квадратов (~бит в соответствующей хэш-функции). Как и в случае с другими схемами, требующими идеальной хеш-функции, для генерации хеш-функции необходим исчерпывающий процесс перебора, частично алгоритмический, частично методом проб и ошибок. Но остается неразрешимая проблема: это очень активные таблицы, и их размер (в большинстве случаев менее миллиона записей) огромен по сравнению с размерами кэша нижнего уровня современных архитектур чипов, что приводит к переполнению кэша. Таким образом, волшебные битборды во многих приложениях не обеспечивают прироста производительности по сравнению с более скромными схемами хеширования или вращаемыми битбордами.

История

Метод растрового изображения настольной игры, судя по всему, был изобретен в середине 1950-х годов Артуром Сэмюэлем и использовался в его шашечной программе. Для более сложной игры в шахматы, похоже, этот метод был независимо заново открыт позже командой «Каисса» в Советском Союзе в конце 1960-х годов. и снова авторами программы « Шахматы » Северо-Западного университета США в начале 1970-х годов. 64-битная длина слова суперкомпьютеров 1970-х годов, таких как машины Амдала и Крея, способствовала разработке растровых представлений, которые удобно отображали 64 клетки шахматной доски в биты слова.

Повернутые битборды для сопоставления ходов скользящих фигур были изобретены профессором Робертом Хаяттом, автором шахматных движков Cray Blitz и Crafty, где-то в середине 1990-х годов и переданы команде программистов Dark Thought. Позже они были реализованы в Crafty and Dark Thought, но первое опубликованное описание появилось только в 1997 году.

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

Другие игры

Битборды полезны для многих других игр, помимо шахмат.

• В Connect Four они позволяют очень эффективно тестировать четыре последовательных диска, всего с помощью двух операций сдвига + И в каждом направлении.
• В « Игре жизни Конвея» они являются возможной альтернативой массивам.
• Отелло/Реверси (см. статью Реверси ).

См. также

• Представительство в совете (шахматы)

Дальнейшее чтение

• http://people.csail.mit.edu/heinz/dt/node2.html

Внешние ссылки

Калькуляторы

• 64-битное представление и манипулирование

Шашки

• Учебник по шашкам Bitboard от Джонатана Кройцера

шахматы

Статьи

• Битборды — Wiki по шахматному программированию
• Область программирования проекта «Беовульф»
• Ларами, Франсуа-Доминик. Шахматное программирование. Часть 2: Структуры данных.
• Верхелст, Пол. Представления на шахматной доске
• Хаятт, Роберт. Представления на доске шахматной программы
• Фрейн, Колин. Как реализовать битборды в шахматном движке (теория шахматного программирования)
• Пепичелли, Глен. Битовые поля, битборды и многое другое - (Пример битбордов на языке Java и обсуждение того, почему эта оптимизация работает с виртуальной машиной Java (издатель www.OnJava.com: O'Reilly 2005))
• Генерация Magic Move-Bitboard в компьютерных шахматах. Прадьюмна Каннан

Примеры кода

• [1] Автор движка Frenzee опубликовал несколько исходных примеров.
• [2] 155-строчная программа Java Connect-4, демонстрирующая использование растровых панелей.

Реализации

Открытый исходный код

• Беовульф Unix, Linux, Windows. Повернутые битборды.
• Crafty См. статью Crafty. Написано на чистом C. В старых версиях повернуты битборды, теперь используются волшебные битборды.
• GNU Chess См. статью GNU Chess.
• Stockfish UCI занимает второе место в рейтинге Elo по состоянию на 2010 год. Шахматная система
• Gray Matter C++, повернутые битборды.
• Лицензия KnightCap GPL. ЭЛО 2300.
• Пепито К. Битборд, автор Карлос дель Качо. Доступны двоичные файлы для Windows и Linux, а также исходный код.
• Симонтаччи Повернутые битборды.

Закрытый исходный код

• DarkThought Домашняя страница

Отелло

• Полное обсуждение движков Othello ( Reversi ) с исходным кодом, включая растровый файл Othello на языке C и ассемблер.
• Edax (вычисления) См. статью Edax. Движок Othello ( Reversi ) с исходным кодом на основе битборда.

Словесные игры

• Обзор использования битовой доски в играх в слова.