Quiescent search and the horizon effect

See Mediocre (dl8)

While there might still be a bug or two in the code so far I will go ahead and implement the Quiescent search.

The horizon effect

I have mentioned the horizon effect in previous posts and it is a problem for every chess engine. I will try to illustrate it with an example.

Consider the position. Now we want the engine to determine if white can capture the pawn on a2. It is obvious to us the move is not ok. We would get:

1. Rxa2 Rxa2
2. Rxa2 Rxa2

And white is down a rook.

Now we are going to look at the engine thinking with different depths. In the following lines the '|' character symbolizes the 'horizon' for what the engine can see.

1 ply depth
Rxa2 | Rxa2 Rxa2 Rxa2

The engine would evaluate the position as equal since all he sees is the pawn capture. And he would make the move.

2 ply depth
Rxa2 Rxa2 | Rxa2 Rxa2

The engine would evaluate the position as being down a rook. And not make the move.

3 ply depth
Rxa2 Rxa2 Rxa2 | Rxa2

The evaluation would be equal again, and he would think he gained a pawn. So he would make the move.

4 ply depth
Rxa2 Rxa2 Rxa2 Rxa2 |

He sees the whole capture sequence and realizes he will be down a rook after capturing the pawn. He would not make the move.

This example is an obvious kind of horizon playing a big role in what moves the engine makes. There are trickier examples though, like the next one.

It is black to move and he is going to lose a piece, so he has to make the best out of the sitation. Here are the lines he will choose at depth 3 and 4.

3 ply depth

1. ... Bxh2
2. Kxh2 Nc5

He sees that he is going to lose a piece no matter what he does, so by taking the pawn he thinks he atleast gained some material. Since he can not see passed the horizon he does not realize that he still will lose one of the knights.

4 ply depth

1. ... Nbc5
2. cxd7 Nxd7
3. h4

With the extra ply depth he sees that capturing the pawn on h2 still loses one of the knights and he ops for a more sound line.

Note that depending on move ordering he might go for the knight move in the three ply search as well, since that also gains a pawn. But the fact that it even considers taking on h2 (Mediocre currently takes on h2) illustrates what a big problem the horizon effect is.

There are countless more examples, like the engine being about to lose his queen and sacrifices piece after piece to keep the queen loss out of his horizon. I think you got the point now though. :)

The 'quiet' solution

The more depth you add to the search, the less of a problem the horizon effect is. If you make a 20 ply search it does not matter too much if the engine thinks he will gain a pawn at the end of the line, since he has plenty of time to change his plan when it comes within his horizon. An error 20 plies away is rarely forced by the first move in the line.

But a 20 ply search takes ages to calclulate even for the best engines out there, so we need a different approach to solve the problem.

The solution is called Quiescent search.

The idea is to search every position until it is 'quiet'. By quiet we mean no captures can be made, so nothing game breaking should be happening in the near future. Some quiescence searches consider checks as well, but I will only consider captures.

We do this by doing an ordinary search to a certain ply, but instead of evaluating the position when we reached the depth, we continue calculating every move that is a capture.

We can do this without it costing too much extra calculation since the way quiescent search works (more about this below) we get a search tree that looks something like the image. This is a bit simplified since I only used a branching factor of about 5 (branching factor is the number of possible moves in each position) for the ordinary moves, a real position has a branching factor of about 30-35.

The bottom line is compared to the ordinary search, quiescent search takes a minor part of the calculation time into consideration, but improves the playing strength immensely.

With a working quiescent search even an engine playing with only 1-ply ordinary depth can play quite descent chess, or atleast not lose pieces too easily.

The implementation

It works almost like alpha-beta and goes something like (pseudo code this time):

quis(board, alpha, beta)

eval = evaluatePosition();
if(value >= beta)
return beta;

if(value > alpha)
alpha = value;

generateCaptures();
forEveryCapture
{
makeMove(nextCapture);
eval = -quis(tempBoard, -beta,-alpha);
unmakeMove();

if(eval >= beta)
return beta;

if(value > alpha)
alpha = eval;
}

return alpha;

We start with evaluating the position as it is. If we get a cutoff we end the search here, this happen quit a bit, meaning we never even enter the actual quiescence search. If we get a better move than our last best move, we remember the value and continue the search.

For every capture we keep searching until all captures are made or we get a cutoff. If we find a capture that improves our last best move, we remember it.

This is basically how it works. Now on to a possible problem.

The importance of move order

I have mentioned before that move ordering is important for the alpha-beta search, since searching the best moves first will enable the engine to cutoff many bad lines without looking at them.

When it comes to quiescent search this is even more important.

Since quiescent search does not have a set depth it searches to, a bad ordering of the moves may result in extremely deep lines that completely ruins any kind of efficiency. This is called a quiescent search explosion.

But if we search the best capture first, we can cut off the other captures fast, just like in alpha-beta.

It is hard to know which capture will be the best in every position so we have to make our best guess.

The sorting scheme I will be using is called MVV/LVA (Most Valuable Victim/Least Valuable Attacker). It does what the name implies, sorts the moves to get the low value pieces capture high value pieces first. So PxQ is the first capture that will be checked, next comes NxQ, BxQ and so on down to QxP which will be the last capture we evaluate.

By sorting like this we make sure we are not calculating obvious losses early in the search.

Of course we can not know if the captured pieces are protected. A queen capturing an unprotected pawn is often a good move, but a majority of the time the pieces will be protected.

A limitation

The quiescent search I am going to use will not be able to detect mates. This is not a problem though since the ordinary search will be able to take care of that.

It is possible to tweak the quiescent search to call alpha-beta again if the king is in check (or any other suspicion of a mate being near), but as I said I will not do this.

Looking ahead

When quiescent search is implemented I expect the engine to vastly increase its playing strength. I might go ahead and add a few guidelines in the evaluation just to make it play less 'weird', and then start putting it to the test with a number of games to try to finding some hidden bugs.