Late Move Reductions

Home * Search * Selectivity * Reductions * Late Move Reductions

Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota ↩︎

Late Move Reductions (LMR),
save search by reducing moves that are ordered closer to the end. Typically, most schemes search the first few moves (say 1-2) at full depth, then if no move fails high, many of the remaining moves are reduced in search depth, and only re-searched if the reduced search fails high. The technique has been used for many years in various forms, but it became very popular in 2005 after Fruit and Glaurung ¹ used open source implementations based on the History Heuristic. LMR can often reduce the effective branching factor to less than 2, depending on the reduction conditions.

Contents

Common Conditions
Uncommon Conditions
Reduction Depth
Re-searches
Test Results
See also
Publications
Forum Posts
1. 2004
2. 2005 ...
3. 2010 ...
4. 2015 ...
5. 2020 ...
External Links
References

Common Conditions

Most programs do not reduce these types of moves:

Depth < 3 (sometimes depth < 2)

Uncommon Conditions

Uncommon conditions on moves not to reduce:

Tactical Moves (captures and promotions)
Moves while in check
Moves which give check
Moves that cause a search extension
Anytime in a PV-Node in a PVS search
Passed Pawn Moves
Killer Moves
Moves threatening the King area
Tactically threatening moves
Moves with good past relative history ²
Any Pawn Moves
Allowing reductions of "bad" captures (SEE < 0)
Moves of a threatened piece to safety (often detected via a Null Move search)

Reduction Depth

Modern programs, most notably Stockfish, allow reductions of more than one ply and adjust them based on contextual information.

Base Reduction

The base reduction depth changes according to depth and the number of moves that have been searched. In the simplest case, the base reduction is linear with respect to the product of the logarithm of depth and move number. For example:

Obsidian reduces by 0.99 + ln(depth) * ln(moves) / 3.14

Here some extra sample formulas can be viewed:

Weiss reduces by 0.20 + ln(depth) * ln(moves) / 3.35 for captures and promotions and 1.35 + ln(depth) * ln(moves) / 2.75 for quiet moves.
Ethereal reduces by 0.7844 + ln(depth) * ln(moves) / 2.4696 for quiet moves and 3 (or 2 if the move gave check) for captures and promotions.
Equisetum reduces by 0.57 + (pow(depth, 0.10) * pow(moves, 0.16)) / 2.49 for all moves.
Halogen reduces by -0.7851 + 1.041 * log(depth + 1) + 2.126 * log(moves + 1) - 0.6481 * log(depth + 1) * log(moves + 1)
Senpai reduces by one ply for the first 6 moves and by depth / 3 for remaining moves.
Fruit Reloaded uses formula: uint8(sqrt(double(depth-1)) + sqrt(double(moves-1))); for non-PV nodes. In PV-nodes it reduces by 2/3 of this value.

Heuristic Reductions

In addition to a well-tuned base reduction formula, modern programs also reduce conditionally based on specific sets of heuristics. Some common examples include:

Reduce less while in check.
Reduce less on moves which give check.
Reduce less on Killer Moves.
Reduce less in the PV-Nodes of a PVS search.
Reduce less when improving.
Reduce more in an expected Cut-node.
Reduce more when hash move is a capture.
Reduce more/less based on the history value of the move.

Reduction Range

Nominal reduction values can sometimes reach below zero or exceed depth. Therefore, it is common to clamp reduction to ensure correctness. The range at which reductions are clamped is an area of further refinements.

Re-searches

Classical implementation assumes a re-search at full depth if the reduced depth search returns a score above alpha. In recent years, Stockfish had success with adjusting re-search depth based on result from reduced search.