11.05.2023 16:06
Elfet 32 5800 Источник

Серия статей про создание AI для игры в русские шашки:

  1. Русские шашки: эффективная генерация ходов в Golang

  2. Русские шашки: представление доски с помощью двух uint64

Введение

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

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

Представления доски

Фрагмент кода, который мы рассмотрим, представляет шашечную доску с помощью двух 64-битных беззнаковых целых чисел (uint64) U и V. Структура Board содержит эти два целых числа:

type Board struct {
	U, V uint64
}

Такое представление значительно сокращает объем памяти, необходимой для хранения состояния доски, что позволяет быстрее генерировать и оценивать ход.

Упаковка битов

Основная идея этого представления - "упаковка битов". Упаковка битов - это техника, при которой несколько частей информации хранятся в одном двоичном числе путем выделения определенного количества битов для каждой части информации.

В данной реализации каждая фигура на доске представлена всего 3 битами, что позволяет хранить до 8 различных типов фигур:

const (
	Empty     Piece = 0b000
	WhiteMan  Piece = 0b001
	BlackMan  Piece = 0b010
	WhiteKing Piece = 0b011
	BlackKing Piece = 0b100
)

Представление доски с двумя uint64

В нашем представлении шашечной доски два целых числа uint64, U и V, хранят состояние доски и некоторую дополнительную информацию:

  1. U хранит фигуры в первых 16 позициях на доске и текущий ход (белые или черные) в старшем бите (MSB).

  2. V хранит фигуры в последних 16 позициях на доске, а также количество ходов, в которых участвуют только короли (в 5 наименее значимых битах с 59-го по 63-й).

Методы манипулирования представлением доски

Предоставленный код включает несколько методов для манипулирования и взаимодействия с представлением доски, таких как:

  1. Get(i Pos) - Получает фигуру в заданной позиции i.

  2. Set(i Pos, c Piece) - устанавливает фигуру в данной позиции i в значение c.

  3. OnlyKingMoves() - Возвращает количество ходов, в которых участвуют только короли.

  4. inc() - Увеличивает количество ходов, в которых участвуют только короли.

  5. IsDraw() - Определяет, является ли партия ничейной, проверяя количество ходов только королей.

  6. Turn(kingMove bool) - Обновляет ход и увеличивает ходы короля, если необходимо.

  7. Transpose() - Переворачивает доску и инвертирует цвета фигур.

  8. GenerateMoveName(target Board) - генерирует название хода для заданного состояния доски.

Преимущества данного представления

Это компактное и эффективное представление шашечной доски дает множество преимуществ:

  1. Уменьшение использования памяти - Использование только двух целых чисел uint64 значительно уменьшает объем памяти представления доски.

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

  3. Упрощенная работа с доской - Предоставленные методы упрощают работу с представлением доски, снижая сложность кода ИИ.

Заключение

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

Комментарии (32)