Difference between revisions of "Late Move Reductions"

From Chessprogramming wiki
Jump to: navigation, search
(Created page with "'''Home * Search * Selectivity * Reductions * Late Move Reductions''' FILE:Bak_OtherRules.jpg|border|right|thumb|333px|link=http://chgs.elevator.u...")
 
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Reductions]] * Late Move Reductions'''
 
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Reductions]] * Late Move Reductions'''
  
−
[[FILE:Bak_OtherRules.jpg|border|right|thumb|333px|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d77d58ae5574bf8bc8|[[Arts#Bak|Samuel Bak]] - Other Rules <ref>[http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d77d58ae5574bf8bc8 Chess in the Art of Samuel Bak], [http://www.chgs.umn.edu/ Center for Holocaust & Genocide Studies], [https://en.wikipedia.org/wiki/University_of_Minnesota University of Minnesota]</ref> ]]  
+
[[FILE:Bak_OtherRules.jpg|border|right|thumb|333px|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d77d58ae5574bf8bc8|[[:Category:Samuel Bak|Samuel Bak]] - Other Rules <ref>[http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d77d58ae5574bf8bc8 Chess in the Art of Samuel Bak], [http://www.chgs.umn.edu/ Center for Holocaust & Genocide Studies], [[University of Minnesota]]</ref> ]]  
  
 
'''Late Move Reductions (LMR)''',<br/>
 
'''Late Move Reductions (LMR)''',<br/>
−
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.  
+
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>[https://web.archive.org/web/20150212051846/http://www.glaurungchess.com/lmr.html An Introduction to Late Move Reductions] by [[Tord Romstad]] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])</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.  
  
 
=Common Conditions=  
 
=Common Conditions=  
 
Most programs do not reduce these types of [[Moves|moves]]:
 
Most programs do not reduce these types of [[Moves|moves]]:
−
* [[Tactical moves]] ([[Captures|captures]] and [[Promotions|promotions]])
+
* [[Tactical Moves]] ([[Captures|captures]] and [[Promotions|promotions]])
 
* Moves while in [[Check|check]]
 
* Moves while in [[Check|check]]
 
* Moves which give check
 
* Moves which give check
Line 21: Line 21:
 
* Moves threatening the King area
 
* Moves threatening the King area
 
* [[Tactics|Tactically]] threatening moves
 
* [[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>
+
* Moves with good past [[Relative History Heuristic|relative history]] <ref> [[Mark Winands]], [[Erik van der Werf]], [[Jaap van den Herik]], [[Jos Uiterwijk]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_18 The Relative History Heuristic]''. [[CG 2004]], [http://erikvanderwerf.tengen.nl/pubdown/relhis.pdf pdf]</ref>
 
* Any [[Pawn Push|Pawn Moves]]  
 
* Any [[Pawn Push|Pawn Moves]]  
 
* Allowing reductions of "bad" [[Captures|captures]] ([[Static Exchange Evaluation|SEE]] < 0)
 
* Allowing reductions of "bad" [[Captures|captures]] ([[Static Exchange Evaluation|SEE]] < 0)
Line 50: Line 50:
 
=Publications=  
 
=Publications=  
 
* [[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]
 
* [[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]
 +
* [[Kunihito Hoki]], [[Masakazu Muramatsu]]  ('''2012'''). ''[https://www.semanticscholar.org/paper/Efficiency-of-three-forward-pruning-techniques-in-Hoki-Muramatsu/206099961f401c8693e071c2b739f164ae5ffa6c Efficiency of three Forward-Pruning Techniques in Shogi: Futility Pruning, Null-move Pruning, and Late Move Reduction (LMR)]''. [https://www.journals.elsevier.com/entertainment-computing Entertainment Computing], Vol. 3, No. 3
 
* [[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]]
 
* [[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]]
  
Line 140: Line 141:
 
* [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=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
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65273 LMR prescription] by [[Evert Glebbeek]], [[CCC]], September 24, 2017
 +
'''2019'''
 +
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=70217 Depth reduced but ELO increased] by [[Tom King]], [[CCC]], March 16, 2019 » [[Playing Strength]]
 +
==2020 ...==
 +
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78397 Elo expected from LMR] by Christian Dean, [[CCC]], October 11, 2021 » [[Playing Strength]]
 +
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79616 Troubles with LMR] by Kurt Peters, [[CCC]], March 31, 2022
  
 
=External Links=  
 
=External Links=  
 
* [https://en.wikipedia.org/wiki/Late_Move_Reductions Late Move Reductions from Wikipedia]
 
* [https://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)
+
* [https://web.archive.org/web/20150212051846/http://www.glaurungchess.com/lmr.html An Introduction to Late Move Reductions] by [[Tord Romstad]] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])
−
* [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://mediocrechess.blogspot.de/2007/03/other-late-move-reduction-lmr.html Mediocre Chess: <nowiki>[Guide]</nowiki> 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://members.home.nl/matador/hr.htm History Reductions in Pro Deo] by [[Ed Schroder|Ed Schröder]] » [[ProDeo]]
 
* [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 - or starters - Advance and Expert] by [[Ed Schroder]], [[CCC]], May 01, 2017</ref> » [[Rebel]]
 
* [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 - or starters - Advance and Expert] by [[Ed Schroder]], [[CCC]], May 01, 2017</ref> » [[Rebel]]
  
 
=References=  
 
=References=  
 
<references />
 
<references />
−
 
 
'''[[Reductions|Up one level]]'''
 
'''[[Reductions|Up one level]]'''
 +
[[Category:Samuel Bak]]

Latest revision as of 11:20, 4 April 2022

Home * Search * Selectivity * Reductions * Late Move Reductions

Samuel Bak - Other Rules [1]

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.

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:

  • 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

See also

Publications

Forum Posts

2004

2005 ...

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

2007

2008

2009

2010 ...

2011

2012

2013

2014

2015 ...

2016

2017

2019

2020 ...

External Links

References

  1. ↑ Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
  2. ↑ History Reductions in Pro Deo by Ed Schröder
  3. ↑ An Introduction to Late Move Reductions by Tord Romstad (Wayback Machine)
  4. ↑ Mark Winands, Erik van der Werf, Jaap van den Herik, Jos Uiterwijk (2004). The Relative History Heuristic. CG 2004, pdf
  5. ↑ Receiver operating characteristic (ROC) from Wikipedia
  6. ↑ LMR - or starters - Advance and Expert by Ed Schroder, CCC, May 01, 2017

Up one level

Retrieved from "https://www.chessprogramming.org/index.php?title=Late_Move_Reductions&oldid=26404"