Реализация 9x9 битборда

Question

Я хочу реализовать настольную игру 9x9, похожую на шахматы, в которой есть только подвижные фигуры, похожие на ладьи.Производительность очень важна, так как я тоже хочу развивать ИИ.

Я читаю статьи о битбордах, эффективном способе представить движок игры.Об этом есть несколько интересных статей, таких как Реализация шахматной доски в Java и https://www.chessprogramming.org/Bitboards.. Конечно, они относятся к платам 8x8 и очень хорошо применяются к 64-битным процессорам, поскольку это позволяет быстро побитоватьопераций.

В этом случае мне нужна плата 9x9, поэтому я ожидаю использовать как минимум две примитивные данные (64 бита + 32 бита, для представления 81 квадрата, который мне нужен).

// 9x9 board, possible representation (64bits+32bits)
  000000000
  000000000
  000000000
  000000000
  000000000
  000000000
  000000000
  000000000
  000000000
  +15 unused bits

Помимо более сложной логики, которая мне понадобится, стоит ли в этом случае использовать битборды?Я действительно получу хороший прирост в производительности?

Answer 1

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

10100R001

, где 1 - занятый квадрат, 0 - пустой квадрат, и ваша ладья начинается с квадрата 3 (считая отмладший бит, который равен 0).Допустим, вы предварительно вычислили:

ROOK_MOVE[3][101000001] = 000110110
ROOK_CAPTURE[3][101000001] = 001000001

(Наивный подход достаточно хорош здесь, потому что есть только 9 стартовых позиций и 256 мест для оставшихся 8 квадратов.) Затем вы можете сгенерировать четыре законных хода в квадраты 1, 2, 4 и 5. Это не требует ветвления, поскольку вы можете извлекать биты один за другим (например, с помощью метода Кернигана ).Чтобы получить список легальных захватов, вам нужно И вторую маску с фигурами противника на этом ранге.

Я ожидаю, что это будет работать хорошо даже для доски 9x9.Дополнительные функции обработки битов все еще должны быть намного быстрее, чем альтернативные (if s и ветвление).Как уже упоминалось в комментариях, лучший способ выяснить это - протестировать несколько подходов!