Null-moves

See Mediocre v0.11b

It is time to describe a very powerful search tool. The null-move.

Minimal search trees

There is a limit to how much you can reduce the search tree using different alpha-beta techniques. These techniques work with move ordering, and different search windows (like stated earlier) to try reduce the nodes needed to be searched. The nodes that are pruned are always verified and have no possible way of beating the current best score.

There is actually is a formula of how much the search tree can be reduced using alpha-beta:

B^(D/2) + B^(D/2) - 1

Where B is the branching factor and D is the depth searched. To get to this minimal tree you need perfect move ordering (always looking at the best move first).

Less than minimal

The minimal tree mentioned above is the limit for how small a search tree can get when every single score is verified as being inferior to the best result, by looking at the exact evaluation.

The only thing we do is cut off nodes (moves) that have no chance of beating the best score since the opponent would never allow it.

However, we could cut off nodes that we have not looked at if they appear to be worse than our best move. This is what null-moves are all about. (and futility pruning, but more about that in a later post)

This would reduce the tree even more, at a certain risk of missing something good. First impressions does not always last. :)

Null-moves

A null-move is another word for 'passing'. It simply means the side to play passes and lets the opponent get a free move (i.e. he is allowed to play two consecutive moves).

Let us start with an example, consider the following position:

Somewhere in the search tree we run into the following line:

1. ... Qc1
2. Qxc1 [any move]

Even if white passes here (plays a null-move) black can not possibly reclaim the material.

The line could look like this:

1. ... Qc1
2. Qxc1 Rc8
3. [pass] Rxc1
4. Rxc1

And even though white passed, he is still up a rook.

Obviously black would never allow this to happen, so even if we intended to search this line to 20 plies, we can stop searching here. That is a huge amount of work saved.

That is the basic theory. One side gets a free move, and if it can still not improve its position, the line would never be allowed to happen in the first place.

Putting it in programming terms

In an engine the above scenario would translate into black not being able to reach up to alpha, even though he got a free move.

To make sure black (the side who gets a free move) can not reach up to alpha we still need to do some searching, but we do this with a reduced depth. Instead of doing an ordinary search after the null move, we do it like this:

eval = -alphaBeta(ply -1 -R, -beta, -beta + 1);

The window is minimal since we are only interested if the opponent can reach up to alpha, it does not matter how much worse he is.

The R is how much we reduce the depth, more about this further down.

If the opponent could improve his position after a null-move, we need to do an ordinary search. The line is not bad enough for him.

However if he could not improve his position, we can prune the entire subtree, being fairly certain this line would never be allowed to happen.

This means alot of researching. But since the null-move search is much faster than the ordinary seach, and now and then we get to cut off a huge chunk of the search tree, this results in massive time savings.

The R

In Mediocre I use R=2, that is if we were planning to search the position to depth 10, we only search it to depth 8 when null-moving. This is lightyears faster than the full search (remember that every extra ply adds exponentially to the calculating time).

R=2 is commonly accepted as a good reduction to search a null-move. R=1 is usually too small, making the null-move search too slow. And R=3 is too large, making the null-move too likely to miss tactics.

Some engines use a dynamic R that is larger if the original search depth is large. However using a plain R=2 seems to work very well.

Sample code from Mediocre

Here is how I implemented this in Mediocre.

Firstly we need to handle recursive null-moves. We can not allow a tree with all null-moves since it would result in no moves being played at all.

There are different ways to do this. One is to not allow more than two null-moves in every branch. Another is to not allow two consecutive null-moves, that is how Mediocre handles it.

I did this by changing the alphaBeta() to use a boolean parameter called allowNull. Like this:

alphaBeta(board, ply, alpha, beta, pv, boolean allowNull)

Ordinary recursive calls sends allowNull=true, while null-move searches sends allowNull=false.

This way there will always be a real move between every null-move.

The code added inside alphaBeta() is located right before we start our ordinary move search loop, but after evaluation and mateChecks, and looks like this:

if(allowNull && !usingPreviousLine)
{
if(!isInCheck(board))
{
board.toMove *= -1; // Making a null-move
eval = -alphaBeta(board, ply-1-R, -beta,
-beta+1, localpv, false);
board.toMove *= -1; // Unmaking the null-move

if(eval >= beta) return eval; // Cutoff
}
}

// Continue with ordinary search

The first line allows a null-move if the last move was a real move, and if we are not using our principal variation from the last iteration. We do not want to do null-moves before we have received a first result from our previous principal variation. (maybe we could, but it messes up the code in the sortMoves(), so atleast Mediore does not)

Then we see if the side moving is in check. If he is we can not allow a null-move since the opponent would simply capture the king with his next move.

Now we make the null-move and search with reduced depth (R=2 as mentioned).

Then unmake the null-move.

If the evaluation is higher than beta we can simply return beta here, since we encountered a variation like in the example above. That is the null-move was not enough to help the other side get a better score.

If we do not get a cutoff, we continue with the ordinary search as if nothing happened.

Missed lines

Since we do not actually check every line fully there is always a risk we miss something important that would have happened deep in the search tree. We are essentially moving our horizon closer when doing a null-move search, making it more likely that deep tactics end up beyond it.

This should be a rather rare occurence though, and the speed gains should counter it since we will be able to search to deeper depths to start when using null-moves.

It is possible to avoid missing lines by a more advanced way of determining when to use null-moves. One case would be not using null-moves if there is likely to be a mate on the board. Another, and perhaps most imortantly, if a zugswang situation is likely.

Zugswang

There is one very real problem that occur in positions where zugswang is a factor. Consider the following position:

If white is to move here he will have to either move Kd6 which results in stalemate, or move away from the pawn which loses it and draws the game by material.

If however white could pass here (play a null-move) black would have to play Kc7 and white answers Ke7 and the pawn queens.

This is called zugswang, meaning a side loses if he moves, but will be ok if he could pass.

A null-move search is made under the assumption that having your opponent pass is a huge advantage, huge enough to recover even from horrible moves.

In zugswang positions getting to pass is actually an advantage, and therefore the logics of the null-move search fail.

Taking this into consideration we should never use null-moves in endings with few pieces (especially pawn endings), where there is always a great risk of a zugswang situation appearing.

Mediocre does not recognize endings yet (the evaluation is too simple currently) so he happily plays null-moves even in the endings. This will change once I improve the evaluation algorithm though.

Moving on

The results from null-moves were so impressing and so much fun I will take a look at futuility pruning as well. Which uses a similar scheme.

I will also implement a history herustic which works a bit like killer moves.

After that it is time for the extreme makeover of the evaluation class.