Late move reduction (LMR)

See Mediocre v0.3

A late move (as opposed to an early move :) is a move that gets sorted late in the list of moves we are about to search.

These moves should rarely produce any good results. For example the latest moves of them all, the losing captures, need very specific features of the position to be successful. Things like a sacrifice exposing the enemy king. But in the general case these moves will just be bad.

The idea of the late move reductions is since we predict these moves will not produce any good results we might as well reduce the time we spend on them.

One neat feature with LMR is that it considers the moves that are likely to fail low, i.e. moves that are not good enough, as opposed to null-moves that tries to find moves that fail high. Since these two techniques operates in different ends of the spectrum they are not likely to overlap, which many other reducing techniques are prone to do.

How it works

Here are the lines of code I added to Mediocre, just before the search is about to go into the PVS search.

if(movesSearched >= 4 &&
ply >= 3 &&
Move.capture(moves[i]) == 0 &&
!isInCheck(board))
{
eval=-alphaBeta(board,ply-2,-alpha-1,-alpha,true,depth+1);
}
else eval = alpha +1;

if(eval > alpha) // Continue with PVS search

We start with a few conditions for when we are allowed to reduce moves, more about this below. Then we do a search with a minimal window (since we are only interested if the move fails low or not) using a reduced depth. We reduce the depth with 1 extra ply (a usual search is ply-1). If the eval comes back lower than alpha we are satisfied with this result and can be quite confident that the move was indeed a poor one.

If the search however comes back higher than alpha, something is fishy and we have to continue with the ordinary search at regular depth.

When to reduce

The main idea comes with the first condition; movesSearched >= 4. Basically we start with searching all the likely contenders for best move to full depth, these being the hash move (by far the most common best move), good/equal captures (if there are any), the killer moves and possibly one or two of the best non-captures.

In general 3-4 moves is a good amount of moves searched to full depth before starting to reduce.

Now we need some guidelines as to what we should reduce among the 'late' moves. Here are some type of moves that we probably should avoid reducing:

Checks - and any other moves that the engine extends, if we reduce an extended move, the extension effect is cancelled
Captures - unless they are losing, and maybe not even then
Promotions - atleast if they are queen promotions

These are the obvious ones, there are several other techniques for determining if a move is safe to reduce. Moves that historically failed high might not be good to reduce, neither might moves that raises the static evaluation above alpha or moves that can be determined to cause some sort of threat. These techniques are however a bit more tricky to implement.

This is a rather new technique and there are endless possibilites how to handle the reductions. You could for example try to reduce more than one ply or skip the research when a move comes back above alpha.

For further reading take a look at http://www.glaurungchess.com/lmr.html.

Does it work in Mediocre?

Indeed. And extremely well. Even though I have only tested with a few different setups so far, each and every one of them has given fantastic results. Even the simplest reduction conditions (only captures not being reduced for example) seems to work like a charm.

I will have to do some more testing to see what works best.

I think it is time to call it quits here for tonight. I am not sure if I should go through the evaluation since it is rather huge so it is probably better if you read it off the source code.

Hope you enjoyed my little guide-suite. :)