Board Representation in Chess Engines
Building a Chess Engine - Part 1
This is the first post in my journey to write a chess engine. I decided to call the engine Logos and you can find all the code here.
Note that the code will constantly change as the project progresses. I might also add things later to the board representation. This is the first time I write an engine and my first big project in C++, so I might make some mistakes along the way. If you have any suggestions, I'd like to hear about them.
Board Representation
As laid out in my overview, I start with the board representation of the engine.
Each engine needs to have an internal representation of the board. There are different approaches to do this. One can either keep track of all the pieces and store which square they occupy or one can keep track of all the squares and store which piece, if any, is on the given square. These are called piece-centric or square-centric approaches.
The straight-forward approach would be to create an array where each index corresponds to a specific piece and store which square this piece occupies. The problem with such a naive approach is that many operations which are needed to generate moves take a lot of time.
A common piece-centric approach which allows for quick operations are bitboards, which I'll also be using.
Bitboards
Bitboards are a piece-centric board representation, where each piece type (e.g. white king or black queen) has a bitboard. This is a 64 bit number - so it's 64 0s and 1s - where each square is represented by a 0 or 1. If there is a piece of the specific type on a square, the bitboard has a 1 in its place, otherwise a 0.
This is best illustrated with an example, so let's look at the white pawns in the starting position:
So the bitboard for the white pawns (without leading 0s) is 1111 1111 0000 0000 (which is FF00 in hexadecimal). Note that I index the board from bottom right to top left, so h1 is square 0, g1 is square 1 and a8 is square 63.
The same is done for all other piece type, which results in 12 64-bit numbers that represent the position of all pieces.
Storing all the positions is more involved than storing the squares which each piece occupies. Also, bitboards are sparsely populated, meaning that most digits in the 64 bit numbers are 0. However, bitboards have a big speed advantage when working with them due to bitwise operations.
Bitwise Operations
The reason why bitboards are widely used is that efficient bitwise operations can be used to generate moves and much more. The main operations are AND, OR and XOR which work as follows:
These operations are very quick to execute and since modern CPUs are 64-bit, they can execute such an operation on a bitboard in one step. With these operations, one can apply masks to a bitboard which answer specific questions.
For example, if we want to know if there is a white pawn on e2 in the starting position, we can take the bitboard of the white pawns and AND it with the bitboard that represents the e2-square. This is 2 to the power of 11, since 11 is the index of the e2-square.
The result is not 0, so there is a pawn on the e2 square.
Similarly, we can check if there is a pawn on the e3-square and find that the result of the AND operation is 0, since the two numbers don’t have any 1 in the same place. So there isn't a pawn on the e3-square.
Additional Information
We use bitboards to keep track of all the pieces. But in order to fully describe the state of a chess game, we need more information. Apart from the location of the pieces, we need to know
whose move it is
status of the 50-move-rule
castling rights for both players
if an en passant capture is possible
I store all this information in a Board struct which looks as follows:
In the future, it might be useful to keep track of more variables, but for now I think that this should be sufficient.
Next Steps
Now that there is an internal representation of the board, the engine needs to be able to generate moves. This will be more complicated than the board representation, so there'll be multiple posts about move generation in the coming weeks. There will also be more exciting code to share.
If you have any questions or suggestions for the engine, please let me know.