Transposition Tables and Improvements
Building a Chess Engine - Part 11
It has been a while since I wrote anything about my chess engine Logos, as I was quite busy and decided to focus more on my usual posts. But now I’ve finally found time to work on it again.
If you haven’t seen one of these posts before, I’m writing my own chess engine and I’m documenting the process. You can find my older posts about the engine here.
As always, you can challenge the bot on Lichess.
Performance improvements
As usual, I felt that there was a lot of room for performance improvements. Over the past few months, there were many different things I tried to improve the search speed of the engine. These changes included rewriting the move generation for pawns, saving the attacked squares together with the board to improve the speed of king move generation and to redo the detection of checks. Here is how the performance changed compared to last time:
I also reduced the memory usage of my search by freeing allocated memory correctly.
The whole move generation can probably still be massively improved, but for now I want to focus on some different and more exciting parts of the engine.
Transposition tables
Another big feature I implemented was transposition tables. There are usually many different ways to reach a given position, so it makes a lot of sense to store the evaluations of positions for cases when they get encountered again. This can eliminate entire subtrees from the search process.
For the transposition table, we need to identify the different positions. To do this, I use the Zobrist hash I wrote about in the last post. These hashes are used to identify the position in the transposition table and are stored together with the evaluation and the depth at which this evaluation was reached.
When we want to search a position, we first check if this position is already in the transposition table with a greater or equal depth than the current search (otherwise we would take a less accurate result from the table). If that’s the case, we can simply skip the search and use the value from the transposition table.
Converting endgames
After watching some games from the Lichess bot, I realised that there were some problems with the play of the engine.
The biggest issue was the play in completely winning endgames, like king and rook versus a lone king. The basic problem is that if the engine doesn’t search until checkmate, it simply wants to shuffle the pieces around their best squares and doesn’t make any progress.
The solution was surprisingly simple namely that I added an extra piece square table for the king in the endgame.
As pieces get traded from the board, I weigh the endgame table more and more heavily compared to the middle game table. The engine is now centralising its own king and also driving the opponent’s king to the edge of the board, which is usually enough to convert these easily winning endgames.
My implementation is pretty basic and I only focus on piece count, not which constellation of pieces are remaining. In general, there are many things in the evaluation that can (and hopefully will) be improved, but I’ll leave that until I implemented more pruning techniques to achieve deeper searches.
Time management
In the past, my Lichess bot was only searching to a fixed depth, depending on the remaining time. This often lead to the engine blitzing out moves in endgames, where the search is faster due to less pieces and therefore less legal moves.
The big problem with searching depending on the time remaining is that it’s impossible to accurately predict how long a search will take and one can’t really use results from a search that was ended early, as the best moves may not have been considered.
To solve this, engines use a technique called iterative deepening, where the position gets first searched at depth 1, then 2, 3 and so on. This would be very wasteful on its own, but using the results from lower depths to order the moves and saving the results in the transposition table helps a lot to reduce the search time. The big advantage with this technique is that if the search is cancelled after a certain time period, there are always useful results to fall back on.
So the engine should now use its time a bit better, but my implementation is still far away from any decent time management implementation.
Other minor fixes and future plans
There were many other small issues I fixed, like occasional crashes of the Lichess bot and a faulty implementation of the 50 move rule. I also rewrote the code for the search to make future improvements easier, which is the next thing I want to focus on.
I still haven’t implemented any pruning techniques in my search, apart from alpha beta pruning. So the engine still can’t search to a high depth. This is what I want to tackle next and it (hopefully) won’t take another 8 months until the next update.
Once again, it’d be great if you played a game against Logos.