board view with two uint64s

A series of articles about the creation AI for playing Russian checkers:

1. Russian Checkers: Efficient Move Generation in Golang

2. Russian Checkers: Board Representation with Two uint64s

Introduction

In game development, especially board games such as checkers, board presentation is a critical component of game performance. The board is, in fact, the state of the game: it stores all the information about the position of the pieces, about whose turn it is, and other important data of the game. The efficiency of board presentation affects the speed and efficiency of AI move generation, which in turn affects the gameplay.

One common way to represent a board is to use a two-dimensional array, where each cell is a square on the board. While this approach is intuitive, it is not the most efficient, especially for games with complex rules or large board sizes. For such games, we need a more efficient method of presenting the board. “Bitpacking” comes to the rescue, a technique that uses bitwise operations to store and manipulate game state information. In this blog post, we’ll look at an implementation of a game of checkers that uses bitpacking to represent the playing field using two uint64s.

Board views

The code snippet we’ll look at represents a checkerboard using two 64-bit unsigned integers (uint64) U and V. The Board structure contains these two integers:

type Board struct {
	U, V uint64
}

This representation greatly reduces the amount of memory required to store board state, allowing for faster move generation and evaluation.

Bit packing

The main idea of ​​this representation is “packing bits”. Bit packing is a technique in which multiple pieces of information are stored in a single binary number by allocating a specific number of bits to each piece of information.

In this implementation, each piece on the board is represented by only 3 bits, which allows you to store up to 8 different types of pieces:

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

Board view with two uint64s

In our checkerboard representation, two uint64 integers, U and V, store the state of the board and some additional information:

1. U stores the pieces in the first 16 positions on the board and the current move (white or black) in the most significant bit (MSB).

2. V stores the pieces in the last 16 positions on the board, as well as the number of moves involving only kings (in the 5 least significant bits from 59th to 63rd).

Methods for Manipulating the Board View

The code provided includes several methods for manipulating and interacting with the board view, such as:

1. Get(i Pos) – Gets the figure at the given position i.

2. Set(i Pos, c Piece) – Sets the piece at the given position i to c.

3. OnlyKingMoves() – Returns the number of moves in which only kings participate.

4. inc() – Increases the number of turns that involve only kings.

5. IsDraw() – Determines if a game is a draw by checking the number of moves for kings only.

6. Turn(kingMove bool) – Updates the turn and increases the king’s moves if needed.

7. Transpose() – Flips the board and inverts the colors of the pieces.

8. GenerateMoveName(target Board) – generates a move name for a given board state.

Benefits of this view

This compact and efficient representation of the checkerboard offers many benefits:

1. Reduced Memory Usage – Using only two uint64 integers greatly reduces the board view’s memory footprint.

2. Faster move generation – Efficient bit manipulation operations allow for faster move generation and evaluation, which is critical to AI performance.

3. Simplified board experience – The methods provided make it easier to work with the board view by reducing the complexity of the AI ​​code.

Conclusion

In conclusion, the bit-packed board representation presented in this blog post offers a powerful way to optimize the generation of checker AI moves. By using only two uint64 integers to store the state of the board and applying efficient bit manipulation operations, the AI ​​can evaluate and generate moves faster, resulting in a stronger and more competitive checkers player.