Битборд — это специализированная структура данных битового массива, обычно используемая в компьютерных системах, которые играют в настольные игры , где каждый бит соответствует игровому полю или фигуре. Это позволяет параллельным битовым операциям устанавливать или запрашивать состояние игры или определять ходы или ходы в игре.
Биты в одной битборде связаны друг с другом правилами игры, часто образуя игровую позицию, когда они взяты вместе. Другие битборды обычно используются в качестве масок для преобразования или ответа на запросы о позициях. Битборды применимы к любой игре, ход которой представлен состоянием или присутствием фигур на дискретных пространствах игровой доски, путем сопоставления состояний пространства битам в структуре данных. Битборды являются более эффективным альтернативным представлением доски традиционному представлению почтового ящика , где каждая фигура или пространство на доске является элементом массива.
Битборды особенно эффективны, когда соответствующие биты различных связанных состояний на плате вписываются в одно слово или двойное слово архитектуры ЦП, так что для построения или запроса состояний игры можно использовать отдельные побитовые операторы, такие как AND и OR.
Среди реализаций компьютерных игр, использующих битборды, можно назвать шахматы , шашки , отелло и словесные игры . Схема была впервые использована в программах для шашек в 1950-х годах, а с середины 1970-х годов стала фактическим стандартом для представления игровых досок в компьютерных автоматах.
Битборд, специализированное битовое поле, представляет собой формат, который упаковывает несколько связанных булевых переменных в одно машинное слово, обычно представляющее позицию на игровом поле или состояние игры. Каждый бит представляет собой пробел; когда бит положителен, свойство этого пробела является истинным. Битборды позволяют компьютеру отвечать на некоторые вопросы о состоянии игры с помощью одной побитовой операции. Например, если шахматная программа хочет узнать, есть ли у белого игрока пешки в центре доски (четыре центральных квадрата), она может просто сравнить битборд для пешек игрока с одним для центра доски, используя побитовую операцию И. Если центральных пешек нет, то результатом будут все нулевые биты (т. е. равные нулю). Несколько битбордов могут представлять различные свойства пробелов на доске, а специальные или временные битборды (например, временные переменные) могут представлять локальные свойства или содержать промежуточные сопоставленные результаты.
Эффективность битбордов усиливается двумя другими свойствами реализации. Во-первых, битборды быстро обновляются пошагово, например, переворачивая биты в исходных и конечных позициях битборда для расположения фигуры при ее перемещении. Во-вторых, битовые карты, представляющие статические свойства, такие как все поля, атакованные каждым типом фигуры для каждой позиции на шахматной доске, могут быть предварительно собраны и сохранены в таблице, так что ответ на вопрос типа «каковы допустимые ходы коня на поле e4?» может быть получен с помощью одной выборки из памяти.
Реализации Bitfield используют наличие полных слов (32-битных или 64-битных) побитовых логических операций, таких как AND, OR, NOT и других на современных архитектурах ЦП, чтобы быть эффективными. Bitboards могут быть неэффективны на более ранних 8- и 16-битных архитектурах мини-компьютеров и микропроцессоров.
В результате необходимого сжатия и кодирования содержимого массивных таблиц и вероятности ошибок транскрипции или кодирования, программы bitboard утомительны для разработчиков программного обеспечения как в плане написания, так и в плане отладки. Для построения таблиц обычно требуются вспомогательные генеративные методы, не являющиеся частью приложения.
Представления Bitboard используют параллельные побитовые операции, доступные почти на всех ЦП , которые завершаются за один цикл и полностью конвейеризированы и кэшированы и т. д. Почти все ЦП имеют AND , OR , NOR и XOR . Кроме того, современные ЦП имеют конвейеры инструкций , которые ставят инструкции в очередь для выполнения. Процессор с несколькими исполнительными блоками может выполнять более одной инструкции за цикл, если в конвейере доступно более одной инструкции. Обычные последовательности инструкций с ветвлениями могут привести к опустошению конвейера, если ветвь неверно предсказана. Многие операции bitboard требуют меньшего количества условных операторов и, следовательно, увеличивают конвейеризацию и эффективно используют несколько исполнительных блоков на многих ЦП.
У ЦП есть разрядность, на которую они рассчитаны, и они могут выполнять побитовые операции за один цикл в этой ширине. Таким образом, на 64-битном или более ЦП 64-битные операции могут выполняться в одной инструкции. Может быть поддержка инструкций большей или меньшей разрядности. Многие 32-битные ЦП могут иметь некоторые 64-битные инструкции, и они могут занимать более одного цикла или иным образом быть ограниченными по сравнению с их 32-битными инструкциями.
Если битборд больше ширины набора инструкций, для выполнения операции полной ширины на нем потребуется несколько инструкций. Поэтому программа, использующая 64-битные битборды, будет работать быстрее на 64-битном процессоре, чем на 32-битном процессоре.
Представления битбордов имеют гораздо более длинный код, как исходный, так и объектный. Длинные последовательности битовых манипуляций технически сложны для написания и отладки. Сами битборды разрежены, иногда содержат только один бит из 64, поэтому реализации битбордов требуют много памяти. Обе эти проблемы могут увеличить промахи кэша или вызвать пробуксовку кэша.
Если процессор не имеет аппаратных инструкций для «первой единицы» (или « подсчета ведущих нулей ») и « подсчета единиц » (или «подсчета нулей»), реализация будет существенно затруднена, поскольку эти операции крайне неэффективно кодировать в виде циклов на языке ассемблера.
Битборды требуют больше памяти, чем структуры данных доски списка частей, но более эффективны в исполнении, поскольку многие операции цикла и сравнения сводятся к одной (или небольшому количеству) побитовой операции (операциям). Например, в почтовом ящике определение того, атакует ли часть пространство, требует генерации и цикла по допустимым ходам части и сравнения конечного пространства с пространством . В битбордах допустимые ходы части хранятся в битовой карте, и эта карта объединяется с битовой картой для пространства . Ненулевой результат означает, что часть атакует пространство .
Для некоторых игр написание движка bitboard требует изрядного количества исходного кода, включая таблицы данных, которые будут длиннее, чем компактная реализация mailbox/enumeration. Для мобильных устройств (например, сотовых телефонов) с ограниченным количеством регистров или кэша инструкций процессора это может вызвать проблему. Для полноразмерных компьютеров это может привести к промахам кэша между кэшем первого и второго уровня. Это лишь потенциальная проблема, а не серьезный недостаток, поскольку у большинства машин будет достаточно кэша инструкций, чтобы это не было проблемой.
Некоторые виды битбордов выводятся из других с помощью сложного процесса кросс-корреляции, например, карты атак в шахматах. Реформирование всех этих карт при каждом изменении состояния игры (например, при ходе) может быть непомерно дорогим, поэтому производные битовые карты обновляются инкрементально, процесс, требующий сложного и точного кода. Это выполняется намного быстрее, поскольку нужно менять только битовые карты, связанные с измененными пространствами, а не все битовые карты на доске. Без инкрементального обновления битовое представление может оказаться не более эффективным, чем старое представление почтового ящика, где обновление по сути локально и инкрементально.
Некоторые виды растровых изображений, не зависящие от конфигурации доски, можно предварительно вычислить и извлечь с помощью поиска по таблице, а не сопоставлять после хода или изменения состояния доски, например, поля, атакованные конем или королем, расположенные на каждой из 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]
Magic bitboards — это экстраполяция компромисса времени и пространства прямого хэширования поиска векторов атаки. Они используют преобразование полного вектора атаки в качестве индекса в хэш-таблицу. Magic — неправильное название, и оно просто относится к созданию и использованию идеальной хэш-функции в сочетании с трюками для уменьшения потенциального размера хэш-таблицы, которую необходимо хранить в памяти, что составляет 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 году.
Десять лет спустя были введены методы прямого поиска, использующие замаскированные ранги, файлы и диагонали для индексации таблицы векторов атак в зависимости от состояний занятости битов под маской. Одна из таких схем, использующая идеальную хэш-функцию для устранения коллизий хэшей, была названа «магическими битбордами». Тем не менее, большой размер и высокая скорость доступа к таким таблицам вызывали проблемы с занятостью памяти и конфликтами кэша и не обязательно были более эффективными, чем подход с вращающимися битбордами. Сегодня игровые программы остаются разделенными, причем лучшая схема зависит от приложения.
Помимо шахмат, многие другие игры выигрывают от использования битбордов.
Назовите это Kindergarten Bitboards