Bitboard представляет собой специализированная битовый массив структура данных обычно используется в компьютерных системах , которые играют настольные игры , где каждый бит соответствует настольной игре пространства или части. Это позволяет параллельным побитовым операциям устанавливать или запрашивать состояние игры, а также определять ходы или ходы в игре.
Биты на одной и той же битовой доске связаны друг с другом правилами игры, часто вместе формируя игровую позицию. Другие битовые доски обычно используются в качестве масок для преобразования или ответа на запросы о позициях. Битовые доски применимы к любой игре, прогресс которой представлен состоянием или наличием фигур на дискретных пространствах игровой доски, путем сопоставления состояний пространств с битами в структуре данных. Битовые доски - более эффективная альтернатива традиционному представлению почтового ящика , где каждая часть или пространство на доске является элементом массива.
Битовые доски особенно эффективны, когда связанные биты различных связанных состояний на плате помещаются в одно слово или двойное слово архитектуры ЦП, так что одиночные побитовые операторы, такие как AND и OR, могут использоваться для построения или запроса состояний игры.
К числу реализаций компьютерных игр, использующих битовые доски, относятся шахматы , шашки , отелло и игры в слова . Схема была впервые использована в программах для шашек в 1950-х годах, а с середины 1970-х годов стала фактическим стандартом для представления игровых досок в компьютерных автоматах.
Описание
Битовая доска, специализированное битовое поле, представляет собой формат, в котором несколько связанных логических переменных упаковываются в одно и то же машинное слово, обычно представляющее позицию в настольной игре или состояние игры. Каждый бит представляет собой пробел; когда бит положительный, свойство этого пространства истинно. Битовые доски позволяют компьютеру ответить на некоторые вопросы о состоянии игры с помощью одной поразрядной операции. Например, если шахматная программа хочет знать, есть ли у белого игрока пешки в центре доски (четыре центральных квадрата), она может просто сравнить битовую доску для пешек игрока с пешкой в центре доски, используя побитовое И операция. Если центральных пешек нет, то результатом будут все нулевые биты (то есть равные нулю). Множественные битовые доски могут представлять различные свойства пространств над доской, а специальные или временные битовые доски (например, временные переменные) могут представлять локальные свойства или содержать промежуточные сопоставленные результаты.
Эффективность битовых досок увеличивается за счет двух других свойств реализации. Во-первых, битовые доски быстро инкрементно обновляются, например, переворачивают биты в исходной и целевой позициях на битовой доске для определения местоположения части при ее перемещении. Во-вторых, растровые изображения, представляющие статические свойства, такие как все пробелы, атакованные каждым типом фигур для каждой позиции на шахматной доске, могут быть предварительно сопоставлены и сохранены в таблице, чтобы ответить на вопрос типа «каковы допустимые ходы коня на пространстве e4? " можно ответить одной выборкой из памяти.
Реализации битового поля используют преимущества присутствия полнословных (32-битных или 64-битных) побитовых логических операций, таких как AND, OR, NOT и другие, на современных архитектурах ЦП для повышения эффективности. Битовые доски могут быть неэффективными на более ранних 8- и 16-разрядных архитектурах миникомпьютеров и микропроцессоров.
Проблемы реализации
В результате необходимого сжатия и кодирования содержимого больших таблиц и вероятности ошибок транскрипции или кодирования, программы битовой доски утомительны для разработчиков программного обеспечения, чтобы писать или отлаживать. Для построения таблиц обычно требуются вспомогательные методы генерации, не являющиеся частью приложения.
Использование процессора
Плюсы
В представлениях битовой доски используются параллельные побитовые операции, доступные почти на всех процессорах, которые завершаются за один цикл, полностью конвейеризированы и кэшированы и т. Д. Почти все процессоры имеют операции AND , OR , NOR и 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]
Примером использования bitboards будет определить , является ли кусок ан приз : bitboards для «все дружественные части охраняя <место>» и «все противоборствующие части нападая <пробел>» позволит соответствие части , чтобы легко определить , является ли цель кусок на <пробел> является ценным .
Одним из недостатков стандартных битбордов является сопоставление векторов атаки скользящих фигур (ладья, слон, ферзь), потому что у них есть неопределенное количество областей атаки в зависимости от других занятых областей. Это требует нескольких длинных последовательностей масок, сдвигов и дополнений для каждой части.
Вспомогательные представления битовой доски
В знак признания размера кода и вычислительной сложности генерации битовых панелей для векторов атаки скользящих элементов были разработаны альтернативные структуры данных битовой доски для их сопоставления. На битовые изображения коней, королей, пешек и других конфигураций доски не влияет использование вспомогательных битовых досок для скользящих фигур.
Повернутые битовые доски
Повернутые битовые доски - это дополнительные структуры данных битовой доски, которые позволяют табулировать векторы атаки скользящей фигуры, одну для векторов атаки файлов ладей и по одной для диагональных и антидиагональных векторов атаки слонов (ранговые атаки ладей могут быть проиндексированы со стандартных битовых досок) . С этими битовыми панелями поиск в одной таблице заменяет длинные последовательности побитовых операций.
Эти битовые доски поворачивают конфигурацию размещения платы на 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] Для более сложной игры в шахматы, похоже, этот метод был независимо повторно открыт позже командой Kaissa в Советском Союзе в конце 1960-х годов [9], а также авторами программы « Шахматы » Северо-Западного университета США. начало 1970-х гг. 64-битная длина слова суперкомпьютеров 1970-х годов, таких как машины Амдала и Крея, облегчила разработку представлений битовой доски, которые удобно отображали 64-квадраты шахматной доски в биты слова.
Повернутые битовые доски для сопоставления движений скользящих фигур были изобретены профессором Робертом Хаяттом, автором шахматных движков Cray Blitz и Crafty, где-то в середине 1990-х годов и совместно с командой программистов Dark Thought. Позже они были реализованы в Crafty и Dark Thought, но первое опубликованное описание появилось только в 1997 году.
Десятилетием позже были введены методы прямого поиска с использованием маскированных рангов, файлов и диагоналей для индексации таблицы векторов атак в зависимости от состояния занятости битов под маской. Одна такая схема, использующая идеальную хеш-функцию для устранения хэш-коллизий, получила название «волшебные битовые доски». Тем не менее, большой размер и высокая скорость доступа к таким таблицам вызвали проблемы с занятостью памяти и конфликтами в кэше, и не обязательно были более эффективными, чем подход с вращающейся битовой платой. Сегодня игровые программы остаются разделенными, и лучшая схема зависит от приложения.
Другие игры
Битборды выигрывают во многих других играх, помимо шахмат.
- В Connect Four они позволяют очень эффективно тестировать четыре последовательных диска всего двумя операциями shift + AND в каждом направлении.
- В «Игре жизни» Конвея они являются возможной альтернативой массивам.
- Отелло / Реверси (см. Статью Реверси ).
Смотрите также
Заметки
- ^ Использование идеальной хеш-функции не требуется для реализации этого метода и дает лишь исчезающе малое преимущество по сравнению со стандартными методами хеширования.
Рекомендации
- ^ Аткин, Ларри Р .; Slate, Дэвид Дж. (1983) [1977]. «Шахматы 4.5: шахматная программа Северо-Западного университета». Во Фрей, Питер У. (ред.). Шахматное мастерство в человеке и машине (2-е изд.). Springer Verlag . С. 82–118. CiteSeerX 10.1.1.111.926 . ISBN 0-387-90790-4.
- ^ Хайнц, Эрнст А. (сентябрь 1997 г.). «Как темная мысль играет в шахматы» . Журнал ICCA . 20 (3): 166–176.
- ^ Хаятт, Роберт (1999). «Повернутые битборды: новый поворот в старой идее» . Архивировано из оригинала на 2005-04-28.
- ^ Таннус, Сэм (2007-07-23) [2006]. «Избегайте ротации битовых панелей с прямым поиском». Журнал ICGA (2-е изд.). Дарем, Северная Каролина, США. 30 (2): 85–91. arXiv : 0704.3773v2 . CiteSeerX 10.1.1.561.3461 . DOI : 10.3233 / МКГ-2007-30204 .
- ^ Кнут, Дональд (1973). «Раздел 6.4. Алгоритм D (открытая адресация с двойным хешированием)». Искусство программирования . 3 .
- ^ Шервин, Майкл; Изенберг, Герд (04.12.2006). "Объяснение Magic Bitboards!" . Форум Winboard .
Назовите это детским садом Bitboards
- ^ Хансен, Лассе (14 июня 2006 г.). "Быстрый (эр) генератор движения битовой доски" . Форум Winboard ..
- ^ «Некоторые исследования машинного обучения с использованием игры в шашки». Журнал исследований и разработок IBM . 1959 г.
- ^ «Программирование компьютера для игры в шахматы». Российские математические обзоры . 1970 г.
дальнейшее чтение
- http://people.csail.mit.edu/heinz/dt/node2.html
Внешние ссылки
Калькуляторы
- 64-битное представление и манипулирование
Шашки
- Учебник по шашкам для битбордов от Джонатана Кройцера
Шахматы
Статьи
- Битовые доски - Chessprogramming wiki
- Программная область проекта Беовульф
- Ларами, Франсуа-Доминик. Шахматное программирование, часть 2: структуры данных.
- Верхелст, Пол. Представления на шахматной доске
- Хаятт, Роберт. Представления на доске шахматной программы
- Фрейн, Колин. Как реализовать битборды в шахматном движке (теория шахматного программирования)
- Пепичелли, Глен. Битовые поля, битовые доски и не только - (Пример битовых битов на языке Java и обсуждение того, почему эта оптимизация работает с виртуальной машиной Java (www.OnJava.com, издатель: O'Reilly 2005))
- Генерация Magic Move-Bitboard в компьютерных шахматах. Прадьюмна Каннан
Примеры кода
- [1] Автор движка Frenzee опубликовал несколько исходных примеров.
- [2] Программа на языке Java Connect-4 из 155 строк, демонстрирующая использование битовых досок.
Реализации
Открытый источник
- Беовульф Unix, Linux, Windows. Повернутые битовые доски.
- Crafty См. Статью Crafty. Написано на прямом C. В старых версиях используются вращающиеся битовые доски, теперь используются волшебные битовые доски.
- GNU Chess См. Статью о GNU Chess.
- Шахматный движок Stockfish UCI занимает второе место в рейтинге Эло по состоянию на 2010 год.
- Gray Matter C ++, повернутые битовые доски.
- KnightCap GPL. ЭЛО 2300.
- Пепито К. Битборд, Карлос дель Качо. Доступны двоичные файлы Windows и Linux, а также исходный код.
- Simontacci Повернутые битовые доски.
Закрытый источник
- Домашняя страница DarkThought
Отелло
- Полное обсуждение движков Othello ( Reversi ) с некоторым исходным кодом, включая битовую доску Othello на C и ассемблер.
- Edax (вычисления) См. Статью Edax. Движок Отелло ( Реверси ) с исходным кодом на основе битовой доски.
Игра слов
- Обзор использования битовой доски в словесных играх.