Late Move Reductions
Home * Search * Selectivity * Reductions * Late Move Reductions
Late Move Reductions (LMR),
or its version known as History Pruning and History Reductions [2] , 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 [3] 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
Most programs do not reduce these types of moves:
- Depth < 3 (sometimes depth < 2)
Most programs reduce these types of moves less:
- Moves while in check
- Moves which give check
- Killer Moves
- Moves in a PV-Node in a PVS search
- Moves when improving
Most programs reduce these types of moves more:
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 [4]
- 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
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:
- Weiss reduces by 0.20 + ln(depth) * ln(move number) / 3.35 for captures and promotions and 1.35 + ln(depth) * ln(move number) / 2.75 for quiet moves.
- Ethereal reduces by 0.7844 + ln(depth) * ln(moves played) / 2.4696 for quiet moves and 3 (or 2 if the move gave check) for captures and promotions
- 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. In recent years, Stockfish had success with adjusting re-search depth based on result from reduced search.
Test Results
Some test results related to LMR can be found on
See also
- Parallelism and Selectivity in Game Tree Search | Video, Talk by Tord Romstad
- Bobby's Strategic Quiescence Search
- History Heuristic
- History Leaf Pruning
- Move Count Based Pruning (Late Move Pruning)
- Null Move Pruning
- Relative History Heuristic
- SEX Algorithm
Publications
- David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1
- Kunihito Hoki, Masakazu Muramatsu (2012). Efficiency of three Forward-Pruning Techniques in Shogi: Futility Pruning, Null-move Pruning, and Late Move Reduction (LMR). Entertainment Computing, Vol. 3, No. 3
- Daniel S. Abdi (2013). Analysis of pruned minimax trees. pdf » Alpha-Beta, Null Move Pruning
Forum Posts
2004
- Forward pruning and some related techniques by Sergei Markoff, CCC, March 02, 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
- Re: late move reductions by Alessandro Scotti, CCC, March 01, 2006 » Kiwi
- PHR (Peak History Reduction) idea by Daniel Mehrmann, CCC, March 01, 2006 » Home, Relative History Heuristic
- 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
2007
- 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
2009
- About LMR & History reductions by Joona Kiiski, CCC, February 24, 2009
- LMR by Robert Hyatt, CCC, March 05, 2009
- LMR and 'tactically connected' moves by Harm Geert Muller, CCC, March 10, 2009
- LMR revisited by Robert Hyatt, CCC, April 01, 2009
- LMR and null move selectivity by Don Dailey, CCC, April 20, 2009
- LMR by Bas Hamstra, CCC, September 30, 2009
- May I Ask What You Think Of This? by Christopher Conkie, CCC, October 20, 2009
- Did people try replacing LMR by pruning by Uri Blass, CCC, December 31, 2009
2010 ...
- 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
2014
- Null move and LMR by Laurie Tunnicliffe, CCC, March 12, 2014 » Null Move Pruning
- LMR & TT interaction by Natale Galioto, CCC, April 29, 2014 » Transposition Table
- A question about Stockfish and LMR or other pruning... by Forrest Hoch, CCC, November 20, 2014
2015 ...
- 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
2017
- LMR and PVS by thevinenator, OpenChess Forum, February 10, 2017 » Principal Variation Search
- Late move reductions ? by Mahmoud Uthman, CCC, March 22, 2017
- Check extension vs LMR by Harm Geert Muller, CCC, April 04, 2017 » Check Extensions
- LMR - or starters - Advance and Expert by Ed Schroder, CCC, May 01, 2017
- LMR and killer by Harm Geert Muller, CCC, September 14, 2017 » Killer Heuristic
- LMR prescription by Evert Glebbeek, CCC, September 24, 2017
2019
- Depth reduced but ELO increased by Tom King, CCC, March 16, 2019 » Playing Strength
2020 ...
- Elo expected from LMR by Christian Dean, CCC, October 11, 2021 » Playing Strength
- Troubles with LMR by Kurt Peters, CCC, March 31, 2022
External Links
- Late Move Reductions from Wikipedia
- An Introduction to Late Move Reductions by Tord Romstad (Wayback Machine)
- Mediocre Chess: [Guide] Late move reduction (LMR) by Jonatan Pettersson, March 26, 2007 » Mediocre
- History Reductions in Pro Deo by Ed Schröder » ProDeo
- LMR advanced from Rebel 13 by Ed Schroder [6] » Rebel
References
- ↑ Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
- ↑ History Reductions in Pro Deo by Ed Schröder
- ↑ An Introduction to Late Move Reductions by Tord Romstad (Wayback Machine)
- ↑ Mark Winands, Erik van der Werf, Jaap van den Herik, Jos Uiterwijk (2004). The Relative History Heuristic. CG 2004, pdf
- ↑ Receiver operating characteristic (ROC) from Wikipedia
- ↑ LMR - or starters - Advance and Expert by Ed Schroder, CCC, May 01, 2017