Debugging Move Generation and Optimization

Building a Chess Engine - Part 4

I spent the last week finishing the move generation, debugging it and making some changes that where needed to make everything work. The changes aren't too exciting since they "just" make everything work without implementing something completely new. So in this post I'll summarize the many changes that happened over the past week.

Attacks

Castling was still missing from my move generation, so this was the first thing I wanted to implement. To do this, one needs to check if the squares the king castles through are attacked. To do this, I wrote a new class to compute the attacked squares.

This is very similar to the normal move generation. The differences are only that one doesn't need to remove attacks on squares occupied by friendly pieces. Also the pawn attacks are much easier to compute than all possible pawn moves.

The castling itself is straightforward to implement. I used the leading bit in the move encoding to indicate if the move was castling and moved the king and rook accordingly.

Unmaking moves

To calculating different moves from one starting position, one could make a copy of the starting position for each move that can be played. But this takes a lot of time and memory, so chess engines usually "unmake" moves when calculating different branches from a position. This means that they calculate one variation, then backtrack their steps and start with the next variation when they reached the starting position.

The implementation is a bit tricky since moves aren't reversible. You can't tell if it was a capture (in the for engines usual UCI notation), which piece was captured and other information like castling rights and the en-passant square also can't be deduced. So I first added the following struct to keep track of this information:

Information to reverse moves

This struct will then be populated with the information of a board before a move is played and afterwards it's used to revert the move. I used it in the following way:

Making and unmaking moves

Debugging move generation

To find mistakes in the move generation, one can use the perft function. This computes all legal moves in a position up to a given depth. Then one can either look at some reference tables or use Stockfish to compute the legal moves for any position.

I first looked at the legal moves from the starting position and compared it to a table with the correct number of moves. After I got the correct number of moves for the first couple of moves, I looked at specific positions with Stockfish. When I noticed that the number of moves was incorrect, I drilled down to find the specific instance where the error happens.

The bugs where mostly typos or scenarios I didn't consider. For example, I didn't remove the castling rights after a rook got captured on its starting square. Also some bugs where harder to find because the engine introduced a mistake into the position. Take a look at the following example where my engine displayed amazing creativity:

White to move

One of the moves the engine came up with was castling short which is fine, but when the engine actually played the move, it lead to the following position:

The position after a creative castling manoeuvre

A mixture of typos and castling logic lead to the black rook landing on c6.

This bug was somewhat hard to identify because it looked like my engine played a legal move and if I looked at the position after castling correctly, everything was fine.

Performance optimizations

When I first ran the perft from the starting position, I was very surprised with how slow my move generation was. The speed was only around 200k nodes per second. As a comparison, Stockfish has around 900k nodes per second on my laptop which includes the evaluation and search function. So I knew I needed to do quite a bit of optimizations, just to test the move generation at an acceptable speed.

The first thing I did was rewriting the popLSB function since it's used quite often and I knew that there is a better way to remove the final bit. Here is what it looks like now:

New popLSB function

Next I noticed that the slowest part of the engine is the move generation for sliding pieces. First I rewrote the function to reverse a bitboard which lead to a huge speedup.

New function to reverse a bitboard

This approach is so much faster because the old function always looped through all 64 bits. Now we only look at the 1s and since bitboards are generally very sparsely populated, there are way fewer iterations.

Then I also made some changes to the generation of the sliding moves to reduce the size of the bitboards which needed to be reversed. Finally I used more pointers to the current board which was also a little speedup. Here is how the speed of the engine improved with these changes:

Speedup of the engine with these optimizations

The generation of sliding moves is still the slowest part and I'll look into magic bitboards in the future. But for now I think that the performance should be good enough to implement the evaluation and search. So you can look forward to some more exciting changes in the next week.