Late Move Reductions (LMR),
or its version known as History Pruning and History Reductions[1] , save search by reducing moves that are ordered closer to the end of likely fail-low nodes. Typically, most schemes search the first few moves (say 3-4) at full depth, then if no move fails high, many of the remaining moves are reduced in search depth. The technique has been used for many years in various forms, but it became very popular in 2005 after Fruit and Glaurung[2] 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.
Classical implementation reduces by one ply only. Yet modern programs, most notably Stockfish, allow reductions of more than one ply and increase them for later moves. Reduction depth changes according to expected node type (being typically smaller in pv nodes), depth and move number. Here some sample formulas can be viewed:
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.
Re-searches
Classical implementation assumes a re-search at full depth if the reduced depth search returns a score above alpha.
or its version known as History Pruning and History Reductions [1] , save search by reducing moves that are ordered closer to the end of likely fail-low nodes. Typically, most schemes search the first few moves (say 3-4) at full depth, then if no move fails high, many of the remaining moves are reduced in search depth. The technique has been used for many years in various forms, but it became very popular in 2005 after Fruit and Glaurung [2] 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.
Table of Contents
Common Conditions
Most programs do not reduce these types of moves:Less Common Conditions
Less common conditions on moves not to reduce:Reduction Depth
Classical implementation reduces by one ply only. Yet modern programs, most notably Stockfish, allow reductions of more than one ply and increase them for later moves. Reduction depth changes according to expected node type (being typically smaller in pv nodes), depth and move number. Here some sample formulas can be viewed:Re-searches
Classical implementation assumes a re-search at full depth if the reduced depth search returns a score above alpha.Test Results
Some test results related to LMR can be found onSee also
Publications
Forum Posts
2004
2005 ...
- Reductions and null move refutations by Tord Romstad, Winboard Forum, April 18, 2005 » Null Move Pruning
- What is History Pruning? by David Dahlem, CCC, July 03, 2005
- History based pruning question by Alvaro Jose Povoa Cardoso, CCC, August 26, 2005
- About history pruning... by Svein Bjørnar Myrvang, CCC, October 26, 2005
- What is "history pruning"? by Vladimir Medvedev, Winboard Forum, November 07, 2005
2006- History pruning by Frank Phillips, CCC, February 27, 2006
- late move reductions by Robert Hyatt, CCC, March 01, 2006
- history pruning/ late move pruning by Tom King, Winboard Programming Forum, March 02, 2006
- LMR question by Uri Blass, Winboard Programming Forum, July 13, 2006
2007Re: late move reductions by Alessandro Scotti, CCC, March 01, 2006 » Kiwi
PHR (Peak History Reduction) idea by Daniel Mehrmann, CCC, March 01, 2006 » Homer, Relative History Heuristic
- LMR in micro-Max by Harm Geert Muller, CCC, April 07, 2007 » Micro-Max
- Fruit and History Reductions by Ed Schröder, CCC, July 19, 2007 » Fruit
- LMR other conditions by Mark Lefler, CCC, July 23, 2007
- Improving history tables by Michael Sherwin, CCC, July 25, 2007
- LMR: history or not? by Alessandro Scotti, CCC, December 13, 2007 » Hamsters
2008- Extreme late move reductions? by Gary, CCC, March 05, 2008
- LMR? by Martin Giepmans, CCC, April 12, 2008 » Anatoli
- Adaptative LMR and TT by Fermin Serrano, CCC, December 23, 2008
20092010 ...
- The problem with LMR in suprtactical positions by Oliver Brausch, CCC, January 05, 2010
- Researching if LMR-affected search improves Alpha? by John Merlino, CCC, January 22, 2010
- Problems with LMR in late endgames by Luca Hemmerich, CCC, March 01, 2010
- LMR algorithm by kenny stanley, CCC, March 15, 2010
- LMR Conditions by kenny stanley, CCC, March 23, 2010
- LMR at root of search tree - worthwhile? by Tom King, CCC, May 21, 2010
- EPR, even better than LMR! by Michael Sherwin, CCC, May 27, 2010
- Re: "Automated Discovery of Search Extensions" by Ed Schröder, OpenChess Forum, June 26, 2010
- lmr at PV nodes? by Tom King, CCC, July 23, 2010
- move count based pruning by Tom King, CCC, September 02, 2010
- LMR differences in long vs short games by Jacob Børs Lind, CCC, November 08, 2010
- fulitiy + lmr; funny results by Volker Böhm, CCC, December 28, 2010
2011- lmr in PV by Larry Kaufman, CCC, January 03, 2011
2012- Should reduction depend on depth? by Larry Kaufman, CCC, January 14, 2012 » Komodo
- Possible LMR improvement using AB_FOOL by Ed Schroder, CCC, April 24, 2012
- LMR Research by Matthew R. Brades, CCC, July 02, 2012
- Adjustable search pruning depending on time control by Jerry Donald, CCC, December 20, 2012 » Time Management
2013- ROC analysis of Late Move Reductions by Gerard van Ewijk, CCC, March 22, 2013 [5]
- Is LMR Sound by Henk van den Belt, CCC, May 29, 2013
- Is LMR safe within NULL move reduction by Henk van den Belt, CCC, May 30, 2013
- LMR at CUT nodes can be arbitrarily bad! by Michel Van den Bergh, CCC, June 20, 2013 » Node Types, Python
- How much to reduce ? by Henk van den Belt, CCC, October 03, 2013 » R
20142015 ...
- About LMR , again :-) by Daniel Anulliero, CCC, March 01, 2015
- LMR tuning by Shawn Chidester, CCC, May 11, 2015
- Interpretation of LMR by Alexandru Mosoi, CCC, May 29, 2015
- What's Your Engine's Maximum LMR Reduction? by Steve Maughan, CCC, June 08, 2015
- New "smoothing" issue by Robert Hyatt, CCC, July 20, 2015
- On LMR, and statically predicting moves by Matthew Lai, CCC, August 25, 2015
- LMR by another name by Steven Edwards, CCC, September 02, 2015 » Spector
- Ratio reduction by Steven Edwards, CCC, September 20, 2015 » Symbolic
2016- late move reduction by Folkert van Heusden, CCC, January 21, 2016
- Extensions in the days of LMR? by Martin Fierz, CCC, March 22, 2016 » Extensions
- LMR problems by Alvaro Cardoso, CCC, May 16, 2016
- Reductions by Harm Geert Muller, CCC, May 22, 2016 » R
- Disappointing LMR Results by David Cimbalista, CCC, August 04, 2016
- Null Move in LMR by Laurie Tunnicliffe, CCC, August 10, 2016 » Null Move Pruning
2017External Links
Late Move Reductions
Misc
References
What links here?
Up one level