An Introduction to Late Move Reductions

Introduction

Most of the commonly used selective search techniques in computer chess and other abstract board games work by reducing the amount of work at nodes where the search fails high. Recursive null move pruning, multi-cut pruning and ProbCut all belong to this category. All of these techniques also share another characteristic: They use reduced depth searches to compute an estimate for the score of the node (or just a lower bound for the score), and prune the sub-tree below the node if this estimated score is above beta.

A problem of all the above-mentioned techniques is that although they work well by themselves, they do not complement each other very well. In computer chess, recursive null move pruning has proved to be extremely effective, but remarkably few programmers have reported success with adding multi-cut or ProbCut on top of recursive null move pruning. The most likely reason for this is that all three techniques tend to be successful at the same nodes. At nodes where ProbCut would have achieved a cutoff, the null move search will moste often produce a cutoff before ProbCut is even applied.

When attempting to further improve a standard PVS search with recursive null move pruning, it is therefore tempting to look for techniques which reduce the amount of work at fail low nodes. Until now, little work has been published in this area. Late move reductions are one of the few known techniques. The origins of this technique is lost in antiquity, and nobody seems to know who the inventor was. It was rather obscure until year 2004, when it was popularised by Sergei Markoff and myself in discussions at the Computer Chess Club. Since then, late move reductions have been successfully implemented by a big number of chess programmers, especially after they were added to the very strong open source program Fruit near the end of 2005.

The nomenclature is still not standardized. Several different names are used for the technique. In addition to "late move reductions", which is the name I prefer to use myself, I have seen them described as "ordering-based reductions", "fail low reductions" and "history pruning". The last name is by far the most common, and in my opinion by far the most unfortunate. The reasons for this will be explained below.

The Basic Idea

Late move reductions are based on the simple observation that in a program with reasonably good move ordering, a beta cutoff will usually occur either at the first node, or not at all. We make use of this observation by searching the first few moves at every node with full depth, and searching the remaining moves with reduced depth unless they look particularly forcing or interesting in some other way. If one of the reduced moves surprise us by returning a score above alpha, the move is re-searched with full depth. The following pseudo code displays the outline of a PVS search with recursive null move pruning and late move reductions included (the actual late move reduction code is displayed in boldface):

const int FullDepthMoves = 4;
const int ReductionLimit = 3;

int search(int alpha, int beta, int depth) {
  int value, moves_searched;
  move_t move;

  if(depth == 0) return qsearch(alpha, beta, depth);
  
  // Null move search:
  if(ok_to_do_nullmove_at_this_node()) {
    make_nullmove();
    value = -search(-beta, -beta, -(beta-1), depth-4);
    unmake_nullmove();
    if(value >= beta) return value;
  }
  
  moves_searched = 0;
  while((move = pick_move()) && alpha < beta) {
    make_move(move);

    if(moves_searched == 0) // First move, use full-window search
      value = -search(-beta, -alpha, depth-1);
    else {
      if(moves_searched >= FullDepthMoves && depth >= ReductionLimit &&
         ok_to_reduce(move))
        // Search this move with reduced depth:
        value = -search(-(alpha+1), -alpha, depth-2);
      else value = alpha+1;  // Hack to ensure that full-depth search
                             // is done.
      if(value > alpha) {
        value = -search(-(alpha+1), -alpha, depth-1);
        if(value > alpha && value < beta)
          value = -search(-beta, -alpha, depth-1);
      }
    }
    unmake_move(move);
    if(value > alpha) alpha = value;

    moves_searched++;
  }
  return alpha;
}

Enhancements and Variations

The most obvious thing missing in the pseudo code above is the ok_to_reduce() function. Blindly reducing all moves after the first three or four will almost certainly have catastrophic results. We need some extra conditions for identifying tactically and positionally interesting moves, and avoid reducing these too often. Obviously, checks (and more generally, moves which are extended) should never be reduced. Most programs also avoid reducing captures and promotions. Beyond this, the conditions vary widely between different programs. Some of the more popular conditions are the following:

The first of these conditions are the origin of the name "history pruning". I do not like this name, because it implies that the history condition is essential, and because it obscures the fact that we are talking about reductions rather than pruning. There are programs which successfully use late move reductions without relying on history counters at all.

Not all programs with late move reductions follow the exact pattern of the pseudo code in the previous section. One of the most common deviations is to omit the re-search of reduced moves which return a score above alpha. The majority of programs do seem to use re-searches, but they are not essential. For instance, Fruit 2.0 used late move reductions without re-search. History re-search was only added in Fruit 2.1.

Some chess program authors have also experimented with reductions by more than one ply, with varying degrees of success.

Does it Work?

Like most other tricks, the effectivity of late move reductions depends to a great extent on the program. For some programs it gives 100 Elo points or more, for others it is just a tiny improvement, or none at all. There are also programs where it just does not work at all, and the program plays better without late move reductions. The only way to find out whether they work for you is to try.

It seems clear, however, that they have some potential, even on the highest level. I know that late move reductions are used in at least two of the current top commercial programs, and I have strong suspicions about a third. For all I know, the number could be even bigger.

I think that late move reductions is still a very crude and unpolished technique, and that it can and will be improved considerably in the future.

Sample Code

Two popular open source chess programs using late move reductions are Fruit (available from the download section at the WBEC site) and Glaurung. These two engines differ considerably in their implementational details. Fruit's reductions are based on history counters and node types, while Glaurung's are based on evaluation data and a simple form of dynamic threat detection.