Quiescence Search and Move Ordering

Building a Chess Engine - Part 8

I'm currently building a chess engine and in this series of posts, I write about the progress I made and how I implemented the various different parts needed to get a working engine. If you're new and don't know where to start, I'd recommend reading this post which gives a general overview of how chess engines work.

When I implemented the search in my engine, I simply let it calculate up to a fixed depth and evaluate the resulting positions. The big problem with this approach is that the final positions might not be stable (e.g. positions with hanging pieces) and therefore the evaluation might not be suitable. To avoid such problems, chess engines usually use a technique called quiescence search.

Quiescence search

To avoid evaluating "volatile" positions, quiescence search calculates deeper until a quiet position is reached. What exactly counts as a quiet position varies in different engines. For my first implementation, I decided to search deeper in positions where a king is in check and also to look at every possible capture in the position.

One problem with this approach is that there are often many senseless captures in a position, like a queen taking a protected pawn. So again, one has to either set a depth limit or prune moves that seem bad on the surface. As always, this is a tradeoff between performance and searching possible sacrifices. For now I just limited the depth of the quiescence search. This means that some volatile positions still get evaluated, but at a higher depth than from the normal search.

This added depth also slows down the search, so I implemented basic move ordering to improve the performance.

Move ordering

One important technique to improve the performance of alpha-beta pruning is to order the moves based on how strong they seem to be. Of course, before searching one doesn't know exactly how strong a move will be, but a guess can be made based on various factors. When looking at a strong move first, the engine already knows that a strong option exists, so it can discard less promising lines earlier.

I only implemented a very naive version of move ordering. I moved captures that win material (at least on first sight) to the top of the move list and did nothing else. Even this simple ordering improved the search performance in a few test positions by about 40% which was amazing to see. I'll experiment more with optimisations like this once the first version of the engine is done.

Next goals

As mentioned last time, I now only want to implement the UCI protocol before I create a bot on Lichess to play against the engine. I haven't looked at the details of the protocol yet, but I hope that it won't take longer than 1-2 weeks to implement.

After the first version is done, I'll work on various optimisations of the engine, but probably less regularly than I'm working on it right now.