Board representation

Before introduce the world of the move generation we have another topic to touch: the representation of the game status, which includes the board, the side to move, castling status, etc...

Board representation is commonly considered a crucial choice in a chess engine. This decision is going to influence especially the move generator and the position evaluation heuristics we will cover in the next posts.

A deep discussion about the board representation is above the goal of this post series. Hence for our little chess engine I've decided to adopt the clearest solution for an high level language like Python: a simple list of 64 elements that maps one-one with the squares. Each element contains a character that represent a chess piece or a space for an empty square.

In base.py I've put some utility functions and the class BaseBoard that represents our chess board with the game status. The move maker is usually implemented either by one of the following ways:

• copy: copy the board to a new object and apply the move (this lets the board object be immutable)
• make/undo: directly apply the move to the board, keeping track of the changes to restore the previous state if required.

A good programming practice suggests to limit the usage of mutable objects but we are not going to follow it. As we have to track the list of the moves anyway, I chose the make/undo way. I think actually the majority of chess engines do it, at least almost all the ones I've studied. The move() method applies a move, the undo() method takes it back.

move() (source) needs to face several special cases:

• pawn double push.
• en passant capture.
• pawn promotion.
• king castling.
• king castling status changes if any of the rooks or the king makes a move.

These are some of the most annoying parts of a chess engine and are highly error prone. I strongly suggest to test all these functions properly covering all special cases (test_board.py).

BaseBoard constructor takes a single parameter: a FEN string. From Wikipedia:

Forsyth–Edwards Notation (FEN) is a standard notation for describing a particular board position of a chess game. The purpose of FEN is to provide all the necessary information to restart a game from a particular position.

All major chess software let import/export game status using the FEN notation. It is highly recommended to provide the engine with functions to import and export FEN strings so to interface it with other software.

Several of the test I wrote are tuples (start status, action, end status). Using FEN made things easier.

Move generator

Once the board is represented we can shift to the move generator (movegen.py). Each piece in Chess has its own list of moves, therefore for each piece is necessary to write a specific function to generate the moves.

Generating moves and generating legal moves are two things we can keep separated to make the stuff simpler. Indeed the move generator I wrote for our Python chess engine generates pseudolegal moves and it checks for the legality in a next step. This is actually a very common choice made by many several chess engines. A pseudolegal move normally ignores the possibility of leaving the own king capturable by the other side but checks all the other conditions required for a move to be legal:

• moves are generated following the piece rules
• moves do not bring pieces outside the board
• pieces do not capture piece of the same side
• if a pawn moves to the last rank then it promotes

Sliding pieces like Queen, Bishop and Rook, can be grouped in a single category. All of them have a set of directions they can follow until they reach an edge of the board or another piece. To handle these pieces I've made two tables, one for straight rays and one for diagonal rays. For each square and for each direction the tables contain the list of reachable squares ordered by distance. The move generator picks a square until it encounters another piece and then switches to the next direction. A capture is generated if the encountered piece belongs to the other side.

Knight and King have a fixed list of moves for each square. The generator for these pieces is simpler, it makes use of other tables that contain a list of moves for each source square and it just need to filter out the destinations not occupied by pieces of the same side.

Castling is a special case and it's handled by hand. (Some notes about castling)

Last but not least we have the pawns. Pawns have just special cases: they "normally" move forward by one, if they are on the second rank then they can do a double push, they capture with a diagonal move, they promote on the last rank, there is the en passant capture... too much... no table here, just logic.

Some notes about castling

Castling is a special move in Chess. Castling can be done only if either the King or the Rook involved have not moved yet in the game. We need to keep the status of the possibility of Castling (FEN strings indeed have a castling status field).

Another important thing is that during castling, the square jumped by the King cannot be under attack by the other side. For this reason I wrote a can_attack function that returns True or False if a side attacks a square. This function is required by the move generator to generate castling moves. In order to check the attacked squares, this function requires the move generator. This means we have a cyclic dependency: we need the move generator to generate moves.

can_attack is also used to check if the king of the side to move is checked and if the king of the other side is checked (that means it is an illegal board position - remember our move generator is pseudlegal, so we need such a function).

Precomputed tables

As discussed before, the move generator can take advantage of some tables to simplify the computation. In gentables.py I put some of the ugly functions used to compute these tables and generate a valid python file that contains them. So we don't need to compute the tables each time we load the program.

The movetables.py is the generated file. You can create it running the run script from the program root:

./run gentables > movetables.py

Testing and PERFT

Board representation, move maker, move generator and board legality check are all very sensitive parts and it's quite common to encounter bugs on these functions. Some developers actually fix bugs in these functions after months of development!

To avoid these issues I wrote many tests that you can check in the code. Another very useful tool to make tests is the PERFT (PERFormance Test). PERFT is used by many chess engines to measure the speed of the move generator, actually it can be used to find bugs too.

PERFT consists in an exhaustive search of all the legal moves that can be reached from a starting position limiting the number of moves by a given depth, the return value is the number of nodes generated. For instance running PERFT on the start position of chess with depth 1 returns 20, all white moves. Similarly with depth 2 returns 400, for each of the 20 white moves the black side can reply with other 20 moves.

Many web sites have collections of PERFT values for several positions. We can use these information to check the results given by our engine. The run executable in the root folder of the project lets run the test.

The Python engine is not supposed to be fast, verifying the speed of the move generator is not fair. Still I was curious to compare it against my old C++ version of smash:

~/dev/smash_old/bin$ echo perft 4 | ./smash
OK Result: 197281 Time: 0.2s.

~/dev/smash$ time ./run perft 4
197281

real  0m44.808s
user  0m44.200s
sys   0m0.145s

That means about two hundred times slower... But don't worry and read the next section before throwing Python away!

Some scientific points

The only factor that is heavily influenced by the choice of the board representation is the program speed.

As we've discussed in the previous post, we can forget about exploring all the possible move combinations, it is just absurd, even with a super computer and a long time spent in front of its super monitor. Therefore we should focus on reduce the number of move to consider. Still the same chess engine, with a faster core, can analyze more nodes and will probably play better compared to the slower version.

Our experiments want to focus on the scientific part of the engine development: we want to understand which are the breaking algorithms/data structures/strategies in the chess engine evolution. We don't want to care about the bits. Selective search is a more interesting aspect from this point of view. This is the reason why I won't write much about all the board representations, with their bonus and malus.

In the next posts we are going to make a chess engine, improving it introducing new interesting strategies and algorithms.