Битборд - Bitboard

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

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

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

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

Описание

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

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

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

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

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

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

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

Плюсы

В представлениях Bitboard используется параллель побитовый операции доступны почти на всех Процессоры которые выполняются за один цикл, полностью конвейерны и кэшированы и т. д. Почти все процессоры имеют И, ИЛИ ЖЕ, НИ, и XOR. Кроме того, современные процессоры имеют конвейеры команд которые ставят в очередь инструкции для выполнения. Процессор с несколькими исполнительными модулями может выполнять более одной инструкции за цикл, если в конвейере доступно более одной инструкции. Обычные последовательности инструкций с ветвями могут привести к опустошению конвейера, если ветвление предсказано неверно. Многие операции битовой доски требуют меньшего количества условных выражений и, следовательно, увеличивают конвейерную обработку и эффективно используют несколько исполнительных блоков на многих процессорах.

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

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

Минусы

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

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

Кеш и использование памяти

Плюсы

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

Минусы

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

Дополнительное обновление

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

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

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

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

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

Стандарт

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

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

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

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

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

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

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

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

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

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

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

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

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

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

История

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

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

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

Другие игры

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

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

Смотрите также

Примечания

  1. ^ Использование идеальной хеш-функции не требуется для реализации этого метода и дает лишь исчезающе небольшое преимущество по сравнению со стандартными методами хеширования.

Рекомендации

  1. ^ Аткин, Ларри Р .; Сланец, Дэвид Дж. (1983) [1977]. «Шахматы 4.5: шахматная программа Северо-Западного университета». Во Фрей, Питер У. (ред.). Шахматное мастерство в человеке и машине (2-е изд.). Springer Verlag. С. 82–118. CiteSeerX  10.1.1.111.926. ISBN  0-387-90790-4.
  2. ^ Хайнц, Эрнст А. (сентябрь 1997 г.). «Как темная мысль играет в шахматы». Журнал ICCA. 20 (3): 166–176.
  3. ^ Хаятт, Роберт (1999). "Повернутые битборды: новый поворот в старой идее". Архивировано из оригинал 28 апреля 2005 г.
  4. ^ Таннус, Сэм (2007-07-23) [2006]. «Избегание ротации битбордов с прямым поиском». Журнал ICGA (2-е изд.). Дарем, Северная Каролина, США. 30 (2): 85–91. arXiv:0704.3773v2. CiteSeerX  10.1.1.561.3461. Дои:10.3233 / ICG-2007-30204.
  5. ^ Кнут, Дональд (1973). «Раздел 6.4. Алгоритм D (открытая адресация с двойным хешированием)». Искусство программирования. 3.
  6. ^ Шервин, Майкл; Изенберг, Герд (04.12.2006). "Объяснение Magic Bitboards!". Winboard Форум. Назовите это детским садом Bitboards
  7. ^ Хансен, Лассе (14 июня 2006 г.). "Быстрый (э) генератор движения битовой доски". Winboard Форум..
  8. ^ «Некоторые исследования машинного обучения с использованием игры в шашки». Журнал исследований и разработок IBM. 1959.
  9. ^ «Программирование компьютера для игры в шахматы». Российские математические обзоры. 1970.

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

внешняя ссылка

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

Шашки

Шахматы

Статьи

Примеры кода

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

Реализации

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

Отелло

Игра слов