Building a Chess AI, Part 1 – Game State

I’ve been saying for years that when I get a bit of spare time I’d like to build a chess AI, or chess engine as it is more commonly known. So a few months ago I set out to do just that and this post is an overview of the project’s first major milestone: modelling game state.

If you’re interested in seeing the full code, check out tomcant/chess-rs on GitHub.

I had a few high-level goals for the project:

  1. Play legal chess.
  2. Play sensible chess.
  3. Beat me.

The first goal may seem a bit obvious, but this was the hardest and most time-consuming task. Codifying all the nuances of the rules was painstaking and error-prone, but once this was done, playing semi-sensible chess didn’t require too much more effort. And while the engine can beat me, playing good chess may have to be a future aspiration for the project!

Whilst performance wasn’t a specific goal, I chose to use Rust because it allows me to express high-level concepts with C-like performance, due to its zero-cost abstractions.

Broadly speaking, the various building blocks of a chess engine (or any two player zero-sum board game) are as follows:

This post will focus on the first topic, but I plan to write about the rest in upcoming posts.

Foundations

Before getting into the nuts and bolts of game state, I want to highlight a few foundational concepts that can be seen throughout the code: colours, pieces and squares.

Colours

We need to represent the players. This will be used to keep track of whose turn it is:

enum Colour {
    White,
    Black,
}

Pieces

From white pawns to the black king, pieces are abbreviated as follows:

enum Piece {
    WP, WN, WB, WR, WQ, WK,
    BP, BN, BB, BR, BQ, BK,
}

A piece intrinsically has a colour, so it should be cheap to extract this information:

impl Piece {
    fn colour(&self) -> Colour {
        match self {
            WP | WN | WB | WR | WQ | WK => Colour::White,
            _ => Colour::Black,
        }
    }
}

Squares

From 0 to 63, a1 to h8, squares are value objects composed of unsigned 8-bit integers:

struct Square(u8);

It will be useful to be able to extract a square’s zero-based index, file or rank:

impl Square {
    fn index(&self) -> u8 { self.0 }
    fn file(&self) -> u8 { self.0 & 7 }
    fn rank(&self) -> u8 { self.0 >> 3 }
}

We’ll see how these foundational concepts evolve as the needs of the engine develop, but for now this provides a good enough base to start thinking about how to represent the board.

Board Representation

The decisions made this early on have a far-reaching impact on the overall performance of the engine, so it’s worth spending time here to ensure the representation is efficient. For example, it might seem intuitive to use an 8x8 array, but this would have a huge negative impact on performance. Having to loop over the array and repeatedly check bounds to ensure pieces don’t go off the board would really slow down move generation.

Bitboards

A much more efficient approach is to use bitboards. This takes advantage of the fact that the number of squares on a chessboard and the number of bits in a 64-bit data type are the same, making 64-bit variables a very convenient place to store chess pieces!

Each bit represents the state of one square. Exactly how the bits map to each square is an implementation detail that changes from engine to engine, but I think it’s common to see the following layout:

h8
g8
f8
e8
d8
e1
d1
c1
b1
a1
63
62
61
60
59
⋯
4
3
2
1
0

It’s confusing to visualise the squares with h8 at the start, but it feels right that a1 is the least significant bit. This means that if there’s a 1-bit in the 0th index, then there’s a piece on a1. It can also be helpful to visualise this as an actual chessboard:

8
56
57
58
59
60
61
62
63
7
48
49
50
51
52
53
54
55
6
40
41
42
43
44
45
46
47
5
32
33
34
35
36
37
38
39
4
24
25
26
27
28
29
30
31
3
16
17
18
19
20
21
22
23
2
8
9
10
11
12
13
14
15
1
0
1
2
3
4
5
6
7
a
b
c
d
e
f
g
h

The Rust u64 unsigned integer type will be perfect for this use case. For example, suppose we have a bitboard with the white king on its start square, e1:

let white_king: u64 = 1 << 4;

The value 1 << 4 equates to the binary pattern 10000, preceded by 59 zeros: a single bit set in the 4th index, which is e1. Now consider the white rooks on a1 and h1:

let white_rooks: u64 = (1 << 0) | (1 << 7);

This looks like 10000001, preceded by 56 zeros, where the 0th and 7th bits are set. The actual value of white_rooks in this case is 129, or 2^0 + 2^7, but for the purpose of thinking about the chessboard we needn’t worry about actual values.

Consider the black rooks on a8 and h8:

let black_rooks: u64 = (1 << 56) | (1 << 63);

This equates to 9295429630892703744, so it’s much simpler to think in terms of indices!

Adding a piece to the board is just a bitwise OR operation to set the desired bit index:

black_rooks |= (1 << 3); // Put a black rook on d1

Removing a piece is a bitwise AND operation with the complement of the desired bit:

black_rooks &= !(1 << 3); // Remove the black rook on d1

We can check for the presence of a piece using another bitwise AND operation:

if black_rooks & (1 << 63) != 0 {
    // There's a black rook on h8
}

Since calculating 1 << index will be such a common operation, it makes sense to add a method to Square to do this for us:

impl Square {
    fn u64(&self) -> u64 {
        1 << self.0
    }
}

An obvious invariant to be guarded by the board representation is that a square can only be occupied by one piece at a time. It follows that all bitboards must have mutually exclusive bits set, which makes it safe to write the following:

let white_pieces: u64 =
      white_pawns
    | white_knights
    | white_bishops
    | white_rooks
    | white_queens
    | white_king;

let black_pieces: u64 =
      black_pawns
    | .
    | .

This goes to show how memory efficient bitboards are, since the whole state of the board is encoded with just 12 integers. Compare this with an array based approach, which would use a minimum of 64 values to do the same thing.

With the basic operations outlined above we can define a model of the board that allows us to add/remove pieces and inspect the state of individual squares. This will provide the basis for the rest of the engine to query and mutate the state of the game.

Implementing Bitboards

I defined a Board structure to store the 12 piece bitboards:

struct Board {
    pieces: [u64; 12],
    colours: [u64; 2],
}

Additionally, tracking pieces by colour will make it easy to determine the occupancy of all squares, since we can just merge the 2 colour bitboards:

impl Board {
    fn occupancy(&self) -> u64 {
        self.colours[Colour::White] | self.colours[Colour::Black]
    }
}

This gives us a new bitboard with the locations of all pieces, making it easy to check if a given square has a piece on it:

impl Board {
    fn has_piece_at(&self, square: Square) -> bool {
        self.occupancy() & square.u64() != 0
    }
}

Determining which piece is more complicated because we can’t avoid looping over the piece bitboards:

impl Board {
    fn piece_at(&self, square: Square) -> Option<Piece> {
        Piece::pieces().find(|&&piece| {
            self.pieces[piece] & square.u64() != 0
        })
    }
}

Adding and removing pieces simply follows the bitwise logic described above:

impl Board {
    fn put_piece(&mut self, piece: Piece, square: Square) {
        self.pieces[piece] |= square.u64();
        self.colours[piece.colour()] |= square.u64();
    }

    fn remove_piece(&mut self, square: Square) {
        let Some(piece) = self.piece_at(square) else {
            return;
        };
        self.pieces[piece] &= !square.u64();
        self.colours[piece.colour()] &= !square.u64();
    }
}

These few methods provide enough functionality to start working with the board in a meaningful way. We’ll go on to use this structure as the foundation for move generation.

The Bigger Picture

If you’re familiar with FEN, you’ll know that the board is only part of the story. FEN is a format used to describe the state of a game at a single point in time. For example, consider the start position as a FEN string:

                    the                  colour
                   board                 to move   en-passant square
                     |                      |      |
                     |                      |      |
                     v                      v      v
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1 <-- move counters
        ^                         ^            ^
        |                         |            |
        |                         |            |
      black                     white       castling
      pieces                    pieces       rights

The model we have so far only includes the board, so we’re missing a few things:

I didn’t feel like all this belonged inside Board (which FEN sort of indicates), so I created a separate structure to keep it alongside the board, instead:

struct Position {
    board: Board,
    colour_to_move: Colour,
    castling_rights: CastlingRights,
    en_passant_square: Option<Square>,
    half_move_clock: u8,
    full_move_counter: u8,
}

This structure reflects the FEN string above. I think moving forwards there could be a need to expand upon this and store more information for use in search optimisation (transposition tables and zobrist hashing), but this should be good enough for now.

Castling Rights

The last thing worth mentioning is the CastlingRights type, which stores the sides of the board each colour has the right to castle on:

struct CastlingRights(u8);

The wrapped u8 ranges from 0 to 15 using a combination of the following values:

enum CastlingRight {
    WhiteKing = 1,
    WhiteQueen = 2,
    BlackKing = 4,
    BlackQueen = 8,
}

When both colours can castle on either side, the castling rights are 15 (1 + 2 + 4 + 8). Using powers of two like this, we can work with castling rights in the same way as a bitboard:

impl CastlingRights {
    fn none() -> Self {
        Self(0)
    }

    fn has(&self, right: CastlingRight) -> bool {
        self.0 & right as u8 != 0
    }

    fn add(&mut self, right: CastlingRight) {
        self.0 |= right as u8;
    }

    fn remove(&mut self, right: CastlingRight) {
        self.0 &= !(right as u8);
    }
}

This allows us to write the following:

let mut rights = CastlingRights::none();

rights.add(BlackQueen);

assert!(rights.has(BlackQueen));

rights.remove(BlackQueen);

Similarly to bitboards, this is an efficient way to model castling rights because querying and mutating the state with bitwise operations is fast. We’ll see how the engine uses the structure more meaningfully in a future post, when making and unmaking moves in a Position.

Next Up: Move Generation

This post covered how the engine models game state, which was the first milestone for the project. In the next post I’ll write about move generation: finding all the available moves in a position. This will require expanding on the use of bitboards to calculate which squares are under attack, and we’ll see a couple of approaches for effectively testing move generation.

♟️