Late Move Reductions

**[[Home]] * [[Search]] * [[Selectivity]] * [[Reductions]] * Late Move Reductions**
|| [[image:OtherRules.jpg width="333" height="224" link="http://www.chgs.umn.edu/museum/responses/bak/chess.html"]] ||~   || **Late Move Reductions (LMR)**,
or its version known as **History Pruning** and **History Reductions** <ref>[[http://members.home.nl/matador/hr.htm|History Reductions in Pro Deo]] by [[Ed Schroder|Ed Schröder]]</ref> , save search by reducing [[Moves|moves]] that are [[Move Ordering|ordered]] closer to the end of likely [[Node Types#ALL|fail-low nodes]]. Typically, most schemes search the first few moves (say 3-4) at full [[Depth|depth]], then if no move [[Fail-High|fails high]], many of the remaining moves are reduced in search [[Depth|depth]]. The technique has been used for many years in various forms, but it became very popular in 2005 after [[Fruit]] and [[Glaurung]] <ref>[[http://www.glaurungchess.com/lmr.html|An Introduction to Late Move Reductions]] by [[Tord Romstad]]</ref> used open source implementations based on the [[History Heuristic]]. LMR can often reduce the [[Branching Factor#EffectiveBranchingFactor|effective branching factor]] to less than 2, depending on the reduction conditions. ||
|| [[Arts#Bak|Samuel Bak]] - Other Rules <ref>[[http://www.chgs.umn.edu/museum/responses/bak/chess.html|Chess in the Art of Samuel Bak]], [[http://www.chgs.umn.edu/|Center for Holocaust & Genocide Studies]], [[http://en.wikipedia.org/wiki/University_of_Minnesota|University of Minnesota]]</ref> ||~   ||^   ||
[[toc]]
=Common Conditions= 
Most programs do not reduce these types of [[Moves|moves]]:
* [[Tactical moves]] ([[Captures|captures]] and [[Promotions|promotions]])
* Moves while in [[Check|check]]
* Moves which give check
* Moves that cause a search [[Extensions|extension]]
* Anytime in a [[Node Types#PV|PV-Node]] in a [[Principal Variation Search|PVS]] search
* [[Depth]] < 3 (sometimes depth < 2)

=Less Common Conditions= 
Less common conditions on moves not to reduce:
* [[Passed Pawn]] Moves
* [[Killer Heuristic|Killer Moves]]
* Moves threatening the King area
* [[Tactics|Tactically]] threatening moves
* Moves with good past [[Relative History Heuristic|relative history]] <ref>[[Mark Winands]], [[Erik van der Werf]], [[Jaap van den Herik]], and [[Jos Uiterwijk]] (**2006**). //The Relative History Heuristic//. Computers and Games, Lecture Notes in Computer Science (LNCS 3846) (eds. [[Jaap van den Herik]], [[Yngvi Björnsson]], and [[Nathan S. Netanyahu]]), pp. 262-272. [[http://www.cs.unimaas.nl/m.winands/documents/relhis.pdf|pdf]]</ref>
* Any [[Pawn Push|Pawn Moves]] 
* Allowing reductions of "bad" [[Captures|captures]] ([[Static Exchange Evaluation|SEE]] < 0)
* Moves of a  [[Null Move Pruning#ThreatDetection|threatened piece]] to safety (often detected via a [[Null Move Pruning|Null Move search]])

=Reduction Depth= 
Classical implementation reduces by one [[Ply|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 Types|node type]] (being typically smaller in pv nodes), [[Depth|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.

=Test Results= 
Some test results related to LMR can be found on
* [[Late Move Reduction Test Results]]

=See also= 
* [[Tord Romstad#Video|Parallelism and Selectivity in Game Tree Search | Video]], Talk by [[Tord Romstad]]
* [[Bobby#StrategicQuiescenceSearch|Bobby's Strategic Quiescence Search]]
* [[History Heuristic]]
* [[History Leaf Pruning]]
* [[Futility Pruning#MoveCountBasedPruning|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//. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]
* [[Daniel Shawul|Daniel S. Abdi]] (**2013**). //Analysis of pruned minimax trees//. [[https://dl.dropboxusercontent.com/u/55295461/analysis/pruning.pdf|pdf]] » [[Alpha-Beta]], [[Null Move Pruning]]

=Forum Posts= 
==2004== 
* [[http://www.stmintz.com/ccc/index.php?id=352384|Forward pruning and some related techniques]] by [[Sergei Markoff]], [[CCC]], March 02, 2004
==2005 ...== 
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=2300&p=10549|Reductions and null move refutations]] by [[Tord Romstad]], [[Computer Chess Forums|Winboard Forum]], April 18, 2005 » [[Null Move Pruning]]
* [[http://www.stmintz.com/ccc/index.php?id=434809|What is History Pruning?]] by [[David Dahlem]], [[CCC]], July 03, 2005
* [[http://www.stmintz.com/ccc/index.php?id=445457|History based pruning question]] by [[Alvaro Cardoso|Alvaro Jose Povoa Cardoso]], [[CCC]], August 26, 2005
* [[http://www.stmintz.com/ccc/index.php?id=457846|About history pruning...]] by Svein Bjørnar Myrvang, [[CCC]], October 26, 2005
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=3795|What is "history pruning"?]] by [[Vladimir Medvedev]], [[Computer Chess Forums|Winboard Forum]], November 07, 2005
**2006** 
* [[http://www.stmintz.com/ccc/index.php?id=489978|History pruning]] by [[Frank Phillips]], [[CCC]], February 27, 2006
* [[http://www.stmintz.com/ccc/index.php?id=490705|late move reductions]] by [[Robert Hyatt]], [[CCC]], March 01, 2006
> [[http://www.stmintz.com/ccc/index.php?id=490712|Re: late move reductions]] by [[Alessandro Scotti]], [[CCC]], March 01, 2006 » [[Kiwi]]
> [[http://www.stmintz.com/ccc/index.php?id=490779|PHR (Peak History Reduction) idea]] by [[Daniel Mehrmann]], [[CCC]], March 01, 2006 » [[Homer]], [[Relative History Heuristic]]
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4435&p=23839|history pruning/ late move pruning]] by [[Tom King]], [[Computer Chess Forums|Winboard Programming Forum]], March 02, 2006
* [[http://www.open-aurec.com/wbforum/viewtopic.php?t=5194|LMR question]] by [[Uri Blass]], [[Computer Chess Forums|Winboard Programming Forum]], July 13, 2006
**2007**
* [[http://www.talkchess.com/forum/viewtopic.php?t=12936|LMR in micro-Max]] by [[Harm Geert Muller]], [[CCC]], April 07, 2007 » [[Micro-Max]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=15219|Fruit and History Reductions]] by [[Ed Schroder|Ed Schröder]], [[CCC]], July 19, 2007 » [[Fruit]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=15304|LMR other conditions]] by [[Mark Lefler]], [[CCC]], July 23, 2007
* [[http://www.talkchess.com/forum/viewtopic.php?t=15337|Improving history tables]] by [[Michael Sherwin]], [[CCC]], July 25, 2007
* [[http://www.talkchess.com/forum/viewtopic.php?t=18345|LMR: history or not?]] by [[Alessandro Scotti]], [[CCC]], December 13, 2007 » [[Hamsters]]
**2008**
* [[http://www.talkchess.com/forum/viewtopic.php?p=178438|Extreme late move reductions?]] by [[Gary Linscott|Gary]], [[CCC]], March 05, 2008
* [[http://www.talkchess.com/forum/viewtopic.php?t=20636|LMR?]] by [[Martin Giepmans]], [[CCC]], April 12, 2008  » [[Anatoli]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=25599|Adaptative LMR and TT]] by [[Fermin Serrano]], [[CCC]], December 23, 2008
**2009**
* [[http://www.talkchess.com/forum/viewtopic.php?t=26703|About LMR & History reductions]] by [[Joona Kiiski]], [[CCC]], February 24, 2009
* [[http://www.talkchess.com/forum/viewtopic.php?t=26877|LMR]] by [[Robert Hyatt]], [[CCC]], March 05, 2009
* [[http://www.talkchess.com/forum/viewtopic.php?t=26944|LMR and 'tactically connected' moves]] by [[Harm Geert Muller]], [[CCC]], March 10, 2009
* [[http://www.talkchess.com/forum/viewtopic.php?t=27277|LMR revisited]] by [[Robert Hyatt]], [[CCC]], April 01, 2009
* [[http://www.talkchess.com/forum/viewtopic.php?t=27530|LMR and null move selectivity]] by [[Don Dailey]], [[CCC]], April 20, 2009
* [[http://www.talkchess.com/forum/viewtopic.php?t=29944|LMR]] by [[Bas Hamstra]], [[CCC]], September 30, 2009
* [[http://www.talkchess.com/forum/viewtopic.php?t=30245|May I Ask What You Think Of This?]] by [[Christopher Conkie]], [[CCC]], October 20, 2009
* [[http://www.talkchess.com/forum/viewtopic.php?t=31369|Did people try replacing LMR by pruning]] by [[Uri Blass]], [[CCC]], December 31, 2009
==2010 ...== 
* [[http://www.talkchess.com/forum/viewtopic.php?t=31494|The problem with LMR in suprtactical positions]] by [[Oliver Brausch]], [[CCC]], January 05, 2010
* [[http://www.talkchess.com/forum/viewtopic.php?t=31933|Researching if LMR-affected search improves Alpha?]] by [[John Merlino]], [[CCC]], January 22, 2010
* [[http://talkchess.com/forum/viewtopic.php?t=32984|Problems with LMR in late endgames]] by [[Luca Hemmerich]], [[CCC]], March 01, 2010
* [[http://www.talkchess.com/forum/viewtopic.php?t=33265|LMR algorithm]] by kenny stanley, [[CCC]], March 15, 2010
* [[http://www.talkchess.com/forum/viewtopic.php?t=33434|LMR Conditions]] by kenny stanley, [[CCC]], March 23, 2010
* [[http://www.talkchess.com/forum/viewtopic.php?t=34437|LMR at root of search tree - worthwhile?]] by [[Tom King]], [[CCC]], May 21, 2010
* [[http://www.talkchess.com/forum/viewtopic.php?t=34557|EPR, even better than LMR!]] by [[Michael Sherwin]], [[CCC]], May 27, 2010
* [[http://www.open-chess.org/viewtopic.php?f=5&t=248#p2538|Re: "Automated Discovery of Search Extensions"]] by [[Ed Schroder|Ed Schröder]], [[Computer Chess Forums|OpenChess Forum]], June 26, 2010
* [[http://www.talkchess.com/forum/viewtopic.php?t=35558|lmr at PV nodes?]] by [[Tom King]], [[CCC]], July 23, 2010
* [[http://www.talkchess.com/forum/viewtopic.php?t=35955|move count based pruning]] by [[Tom King]], [[CCC]], September 02, 2010
* [[http://www.talkchess.com/forum/viewtopic.php?t=36633|LMR differences in long vs short games]] by [[Jacob Børs Lind]], [[CCC]], November 08, 2010
* [[http://www.talkchess.com/forum/viewtopic.php?t=37337|fulitiy + lmr; funny results]] by [[Volker Böhm]], [[CCC]], December 28, 2010
**2011**
* [[http://www.talkchess.com/forum/viewtopic.php?t=37424|lmr in PV]] by [[Larry Kaufman]], [[CCC]], January 03, 2011
**2012**
* [[http://www.talkchess.com/forum/viewtopic.php?t=41995|Should reduction depend on depth?]] by [[Larry Kaufman]], [[CCC]], January 14, 2012 » [[Komodo]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=43434|Possible LMR improvement using AB_FOOL]] by [[Ed Schroder]], [[CCC]], April 24, 2012
* [[http://www.talkchess.com/forum/viewtopic.php?t=44272|LMR Research]] by [[Matthew R. Brades]], [[CCC]], July 02, 2012
* [[http://www.talkchess.com/forum/viewtopic.php?t=46503|Adjustable search pruning depending on time control]] by [[Jerry Donald]], [[CCC]], December 20, 2012 » [[Time Management]]
**2013**
* [[http://www.talkchess.com/forum/viewtopic.php?t=47577|ROC analysis of Late Move Reductions]] by Gerard van Ewijk, [[CCC]], March 22, 2013 <ref>[[http://en.wikipedia.org/wiki/Receiver_operating_characteristic|Receiver operating characteristic (ROC) from Wikipedia]]</ref>
* [[http://www.talkchess.com/forum/viewtopic.php?t=48144|Is LMR Sound]] by [[Henk van den Belt]], [[CCC]], May 29, 2013
* [[http://www.talkchess.com/forum/viewtopic.php?t=48154|Is LMR safe within NULL move reduction]] by [[Henk van den Belt]], [[CCC]], May 30, 2013
* [[http://www.talkchess.com/forum/viewtopic.php?t=48356|LMR at CUT nodes can be arbitrarily bad!]] by [[Michel Van den Bergh]], [[CCC]], June 20, 2013 » [[Node Types]], [[Python]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=49558|How much to reduce ?]] by [[Henk van den Belt]], [[CCC]], October 03, 2013 » [[Depth Reduction R|R]]
**2014**
* [[http://www.talkchess.com/forum/viewtopic.php?t=51578|Null move and LMR]] by [[Laurie Tunnicliffe]], [[CCC]], March 12, 2014 » [[Null Move Pruning]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=52169|LMR & TT interaction]] by [[Natale Galioto]], [[CCC]], April 29, 2014 » [[Transposition Table]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=54392|A question about Stockfish and LMR or other pruning...]] by Forrest Hoch, [[CCC]], November 20, 2014
==2015 ...==
* [[http://www.talkchess.com/forum/viewtopic.php?t=55526|About LMR , again :-)]] by [[Daniel Anulliero]], [[CCC]], March 01, 2015
* [[http://www.talkchess.com/forum/viewtopic.php?t=56312|LMR tuning]] by [[Shawn Chidester]], [[CCC]], May 11, 2015
* [[http://www.talkchess.com/forum/viewtopic.php?t=56524|Interpretation of LMR]] by [[Alexandru Mosoi]], [[CCC]], May 29, 2015
* [[http://www.talkchess.com/forum/viewtopic.php?t=56631|What's Your Engine's Maximum LMR Reduction?]] by [[Steve Maughan]], [[CCC]], June 08, 2015
* [[http://www.talkchess.com/forum/viewtopic.php?t=57035|New "smoothing" issue]] by [[Robert Hyatt]], [[CCC]], July 20, 2015
* [[http://www.talkchess.com/forum/viewtopic.php?t=57381|On LMR, and statically predicting moves]] by [[Matthew Lai]], [[CCC]], August 25, 2015
* [[http://www.talkchess.com/forum/viewtopic.php?t=57486|LMR by another name]] by [[Steven Edwards]], [[CCC]], September 02, 2015 » [[Spector]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=57697|Ratio reduction]] by [[Steven Edwards]], [[CCC]], September 20, 2015 » [[Symbolic]]
**2016**
* [[http://www.talkchess.com/forum/viewtopic.php?t=58996|late move reduction]] by [[Folkert van Heusden]], [[CCC]], January 21, 2016
* [[http://www.talkchess.com/forum/viewtopic.php?t=59598|Extensions in the days of LMR?]] by [[Martin Fierz]], [[CCC]], March 22, 2016 » [[Extensions]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=60194|LMR problems]] by [[Alvaro Cardoso]], [[CCC]], May 16, 2016
* [[http://www.talkchess.com/forum/viewtopic.php?t=60240|Reductions]] by [[Harm Geert Muller]], [[CCC]], May 22, 2016 » [[Depth Reduction R|R]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=61031|Disappointing LMR Results]] by [[David Cimbalista]], [[CCC]], August 04, 2016
* [[http://www.talkchess.com/forum/viewtopic.php?t=61086|Null Move in LMR]] by [[Laurie Tunnicliffe]], [[CCC]], August 10, 2016 » [[Null Move Pruning]]
**2017**
* [[http://www.open-chess.org/viewtopic.php?f=5&t=3084|LMR and PVS]] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], February 10, 2017 » [[Principal Variation Search]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=63521|Late move reductions ?]] by [[Mahmoud Uthman]], [[CCC]], March 22, 2017
* [[http://www.talkchess.com/forum/viewtopic.php?t=63649|Check extension vs LMR]] by [[Harm Geert Muller]], [[CCC]], April 04, 2017 » [[Check Extensions]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=63870|LMR - [for starters] - [Advance] and [Expert] ]] by [[Ed Schroder]], [[CCC]], May 01, 2017
* [[http://www.talkchess.com/forum/viewtopic.php?t=65169|LMR and killer]] by [[Harm Geert Muller]], [[CCC]], September 14, 2017 » [[Killer Heuristic]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=65273|LMR prescription]] by [[Evert Glebbeek]], [[CCC]], September 24, 2017

=External Links= 
==Late Move Reductions==
* [[http://en.wikipedia.org/wiki/Late_Move_Reductions|Late Move Reductions from Wikipedia]]
* [[http://www.glaurungchess.com/lmr.html|An Introduction to Late Move Reductions]] by [[Tord Romstad]] (dead link)
* [[http://mediocrechess.blogspot.de/2007/03/other-late-move-reduction-lmr.html|Mediocre Chess: [Guide] Late move reduction (LMR)]] by [[Jonatan Pettersson]], March 26, 2007 » [[Mediocre]]
* [[http://members.home.nl/matador/hr.htm|History Reductions in Pro Deo]] by [[Ed Schroder|Ed Schröder]] » [[Pro Deo]]
* [[http://rebel13.nl/rebel13/blog/lmr%20advanced.html|LMR advanced]] from [[http://rebel13.nl/index.html|Rebel 13]] by [[Ed Schroder]] <ref>[[http://www.talkchess.com/forum/viewtopic.php?t=63870|LMR - [for starters] - [Advance] and [Expert] ]] by [[Ed Schroder]], [[CCC]], May 01, 2017</ref> » [[Rebel]]
==Misc==
* [[Videos#WolfgangSchmid|Wolfgang Schmid]] - The Latest Kick, [[http://www.bix-stuttgart.de/|Bix Jazzclub Stuttgart]], Summer 2010, [[https://en.wikipedia.org/wiki/YouTube|YouTube]] Video
> [[media type="custom" key="24626870"]]

=References= 
<references />
=What links here?= 
[[include page="Late Move Reductions" component="backlinks" limit="220"]]
**[[Reductions|Up one level]]**