Difference between revisions of "Futility Pruning"

From Chessprogramming wiki
Jump to: navigation, search
m
 
(13 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Pruning]] * Futility Pruning'''
 
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Pruning]] * Futility Pruning'''
  
[[FILE:EschersRelativity.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/back-bmp/LW389.jpg|[[Arts#Escher|M. C. Escher]], Relativity, 1953 <ref>[http://www.mcescher.com/Gallery/gallery-back.htm Picture gallery "Back in Holland 1941 - 1954"] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref> ]]  
+
[[FILE:EschersRelativity.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/back-bmp/LW389.jpg|[[:Category:M. C. Escher|M. C. Escher]], Relativity, 1953 <ref>[http://www.mcescher.com/Gallery/gallery-back.htm Picture gallery "Back in Holland 1941 - 1954"] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref> ]]  
  
 
'''Futility Pruning''',<br/>
 
'''Futility Pruning''',<br/>
Line 11: Line 11:
 
* moves that give [[Check|check]]  
 
* moves that give [[Check|check]]  
  
Futility pruning is not used when the [[Side to move|side to move]] is in [[Check|check]] , or when either [[Alpha|alpha]] or [[Beta|beta]] are close to the [[Checkmate#MateScore|mate value]], since it would leave the program blind to certain [[Checkmate|checkmates]]. [[Tord Romstad]] reported that in his early program [[Gothmog]] one more condition was necessary - namely that futility pruning requires checking for the existence of at least one legal move <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=43669&p=166791 Serious bug in Gothmog 0.2.6!] by [[Tord Romstad]], [[Computer Chess Forums|Winboard Forum]], August 04, 2003</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=339076 Re: Unexpected problem with futility pruning?] by [[Tord Romstad]], [[CCC]], December 29, 2003</ref> to avoid returning erroneous stalemate scores. As replied by [[Omid David]]: then simply return alpha (to fail [[Fail-Low|low]] but [[Fail-Hard|hard]]).
+
Futility pruning is not used when the [[Side to move|side to move]] is in [[Check|check]] , or when either [[Alpha|alpha]] or [[Beta|beta]] are close to the [[Checkmate#MateScore|mate value]], since it would leave the program blind to certain [[Checkmate|checkmates]]. [[Tord Romstad]] reported that in his early program [[Gothmog]] one more condition was necessary - namely that futility pruning requires checking for the existence of at least one legal move <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=43669&p=166791 Serious bug in Gothmog 0.2.6!] by [[Tord Romstad]], [[Computer Chess Forums|Winboard Forum]], August 04, 2003</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=339076 Re: Unexpected problem with futility pruning?] by [[Tord Romstad]], [[CCC]], December 29, 2003</ref> to avoid returning erroneous stalemate scores. As replied by [[Eli David|Omid David]]: then simply return alpha (to fail [[Fail-Low|low]] but [[Fail-Hard|hard]]).
 
<span id="Extendedfutilitypruning"></span>
 
<span id="Extendedfutilitypruning"></span>
 
=Extended Futility Pruning=  
 
=Extended Futility Pruning=  
Line 37: Line 37:
 
* [[Razoring]]
 
* [[Razoring]]
 
* [[Reverse Futility Pruning]]
 
* [[Reverse Futility Pruning]]
 +
* [[Sibling Prediction Pruning]]
  
 
=Publications=
 
=Publications=
 
* [[Jonathan Schaeffer]] ('''1986'''). ''Experiments in Search and Knowledge''. Ph.D. Thesis, [[University of Waterloo]]. Reprinted as Technical Report TR 86-12, Department of Computing Science, [[University of Alberta]]
 
* [[Jonathan Schaeffer]] ('''1986'''). ''Experiments in Search and Knowledge''. Ph.D. Thesis, [[University of Waterloo]]. Reprinted as Technical Report TR 86-12, Department of Computing Science, [[University of Alberta]]
 
* [[Chun Ye]], [[Tony Marsland]] ('''1992'''). ''Experiments in Forward Pruning with Limited Extensions.'' [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
 
* [[Chun Ye]], [[Tony Marsland]] ('''1992'''). ''Experiments in Forward Pruning with Limited Extensions.'' [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
* [[Ernst A. Heinz]] ('''1998'''). ''[http://people.csail.mit.edu/heinz/dt/node18.html Extended Futility Pruning].'' [[ICGA Journal#21_2|ICCA Journal, Vol. 21, No. 2]].
+
* [[Ernst A. Heinz]] ('''1998'''). ''[http://people.csail.mit.edu/heinz/dt/node18.html Extended Futility Pruning].'' [[ICGA Journal#21_2|ICCA Journal, Vol. 21, No. 2]]
 +
* [[Jeroen Carolus]] ('''2006'''). ''Alpha-Beta with Sibling Prediction Pruning in Chess''. Masters thesis, [http://homepages.cwi.nl/%7Epaulk/theses/Carolus.pdf pdf]
 +
* [[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
  
 
=Forum Posts=
 
=Forum Posts=
Line 56: Line 59:
 
* [https://www.stmintz.com/ccc/index.php?id=143506 question about futility pruning and positional evaluation] by Bert van den Akker, [[CCC]], December 07, 2000  » [[Evaluation]]
 
* [https://www.stmintz.com/ccc/index.php?id=143506 question about futility pruning and positional evaluation] by Bert van den Akker, [[CCC]], December 07, 2000  » [[Evaluation]]
 
* [https://www.stmintz.com/ccc/index.php?id=186225 Futility Cutoff futile?] by [[Stuart Cracraft]], [[CCC]], August 29, 2001
 
* [https://www.stmintz.com/ccc/index.php?id=186225 Futility Cutoff futile?] by [[Stuart Cracraft]], [[CCC]], August 29, 2001
 +
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=34982 Futility + WAC] by [[Stefan Knappe]], [[Computer Chess Forums|Winboard Forum]], November 07, 2001 »  [[Matador]], [[Win at Chess]]
 
* [https://www.stmintz.com/ccc/index.php?id=271983 Re: Futility Pruning] by [[Vincent Diepeveen]], [[CCC]], December 20, 2002
 
* [https://www.stmintz.com/ccc/index.php?id=271983 Re: Futility Pruning] by [[Vincent Diepeveen]], [[CCC]], December 20, 2002
 
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=43088 To Stefan Knappe] by [[Rahman Paidar]], [[Computer Chess Forums|Winboard Forum]], June 21, 2003 » [[Stefan Knappe]]
 
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=43088 To Stefan Knappe] by [[Rahman Paidar]], [[Computer Chess Forums|Winboard Forum]], June 21, 2003 » [[Stefan Knappe]]
 
* [https://www.stmintz.com/ccc/index.php?id=326340 futility pruning?] by [[Daniel Shawul]], [[CCC]], November 09, 2003
 
* [https://www.stmintz.com/ccc/index.php?id=326340 futility pruning?] by [[Daniel Shawul]], [[CCC]], November 09, 2003
 
* [https://www.stmintz.com/ccc/index.php?id=339041 Unexpected problem with futility pruning ?] by Geoff, [[CCC]], December 29, 2003
 
* [https://www.stmintz.com/ccc/index.php?id=339041 Unexpected problem with futility pruning ?] by Geoff, [[CCC]], December 29, 2003
 +
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=46383 Question for Tom Likens] by [[Matt McKnight]], [[Computer Chess Forums|Winboard Forum]], February 07, 2004 » [[Djinn]]
 
* [https://www.stmintz.com/ccc/index.php?id=380679 Extended futility pruning not working] by Cesar Contreras, [[CCC]], August 03, 2004
 
* [https://www.stmintz.com/ccc/index.php?id=380679 Extended futility pruning not working] by Cesar Contreras, [[CCC]], August 03, 2004
 
* [https://www.stmintz.com/ccc/index.php?id=391540 Futility] by [[Stuart Cracraft]], [[CCC]], October 14, 2004
 
* [https://www.stmintz.com/ccc/index.php?id=391540 Futility] by [[Stuart Cracraft]], [[CCC]], October 14, 2004
Line 85: Line 90:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=42749 How to get futility pruning to work?] by [[Robert Purves]], [[CCC]], March 05, 2012
 
* [http://www.talkchess.com/forum/viewtopic.php?t=42749 How to get futility pruning to work?] by [[Robert Purves]], [[CCC]], March 05, 2012
 
* [http://www.talkchess.com/forum/viewtopic.php?t=43165 futility pruning, razoring question] by [[Marco Belli]], [[CCC]], April 04, 2012 » [[Razoring]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=43165 futility pruning, razoring question] by [[Marco Belli]], [[CCC]], April 04, 2012 » [[Razoring]]
* [http://www.talkchess.com/forum/viewtopic.php?t=43513 A search enhancement?] by [[Dan Homan|Daniel Homan]], [[CCC]], April 30, 2012 » [[Futility Pruning#MoveCountBasedPruning|Move Count Based Pruning]]
+
* [http://www.talkchess.com/forum/viewtopic.php?t=43513 A search enhancement?] by [[Daniel Homan]], [[CCC]], April 30, 2012 » [[Futility Pruning#MoveCountBasedPruning|Move Count Based Pruning]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=54761 LMP in PV nodes] by [[Peter Österlund]], [[CCC]], December 27, 2014 »  [[Node Types#PV|PV-Node]], [[Texel]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=54761 LMP in PV nodes] by [[Peter Österlund]], [[CCC]], December 27, 2014 »  [[Node Types#PV|PV-Node]], [[Texel]]
 
==2015 ...==
 
==2015 ...==
Line 95: Line 100:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=61093 Futility prunning] by [[Daniel Anulliero]], [[CCC]], August 11, 2016 » [[Reverse Futility Pruning]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=61093 Futility prunning] by [[Daniel Anulliero]], [[CCC]], August 11, 2016 » [[Reverse Futility Pruning]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=61682 Futility Pruning] by [[David Cimbalista]], [[CCC]], October 11, 2016
 
* [http://www.talkchess.com/forum/viewtopic.php?t=61682 Futility Pruning] by [[David Cimbalista]], [[CCC]], October 11, 2016
'''2017'''
+
'''2017 ...'''
 
* [http://www.talkchess.com/forum/viewtopic.php?t=63344 Futility pruning ?] by [[Mahmoud Uthman]], [[CCC]], March 04, 2017 » [[Reverse Futility Pruning]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=63344 Futility pruning ?] by [[Mahmoud Uthman]], [[CCC]], March 04, 2017 » [[Reverse Futility Pruning]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=63368 futile futility pruning attempt] by [[Folkert van Heusden]], [[CCC]], March 07, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=63368 futile futility pruning attempt] by [[Folkert van Heusden]], [[CCC]], March 07, 2017
 
* [http://www.open-chess.org/viewtopic.php?f=5&t=3099 Futility pruning...] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], April 07, 2017
 
* [http://www.open-chess.org/viewtopic.php?f=5&t=3099 Futility pruning...] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], April 07, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=63852 increasing futility prunning depth] by [[Alexandru Mosoi]], [[CCC]], April 28, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=63852 increasing futility prunning depth] by [[Alexandru Mosoi]], [[CCC]], April 28, 2017
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=64343 Tuning Futility Margin] by [[Tamás Kuzmics]], [[CCC]], June 19, 2017
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=68081 A question about futility prunning] by [[Vivien Clauzon]], [[CCC]], July 26, 2018
 +
==2020 ...==
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74403 Futility Pruning Issues] by Cheney, [[CCC]], July 07, 2020
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77451 Futility Pruning and its Relation to Quiescence Search] by [[Jakob Progsch]], [[CCC]], June 06, 2021 » [[Quiescence Search]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77644 Futility reductions] by [[Jost Triller]], [[CCC]], July 05, 2021
  
 
=External Links=  
 
=External Links=  
 
==Pruning==
 
==Pruning==
* [http://www.top-5000.nl/authors/rebel/chess840.htm#FUTILITY Search Techniques in REBEL (Futility Pruning)] from [http://www.top-5000.nl/authors/rebel/chess840.htm How Rebel Plays Chess] by [[Ed Schroder|Ed Schröder]], [http://members.home.nl/matador/Inside%20Rebel.pdf pdf]
+
* [https://www.madchess.net/2020/02/08/madchess-3-0-beta-4478cb8-late-move-pruning/ MadChess 3.0 Beta 6f3d17a (Late Move Pruning)] by [[Erik Madsen]], February 8, 2020 » [[Futility Pruning#MoveCountBasedPruning|LMP]], [[MadChess]]
 
* [http://home.hccnet.nl/h.g.muller/deepfut.html Deep Futility Pruning] by [[Harm Geert Muller]]
 
* [http://home.hccnet.nl/h.g.muller/deepfut.html Deep Futility Pruning] by [[Harm Geert Muller]]
 
==Misc==
 
==Misc==
Line 110: Line 121:
 
* [https://en.wikipedia.org/wiki/Futility Futility from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Futility Futility from Wikipedia]
 
* [https://en.wikipedia.org/wiki/The_Wreck_of_the_Titan:_Or,_Futility The Wreck of the Titan: Or, Futility - Wikipedia]
 
* [https://en.wikipedia.org/wiki/The_Wreck_of_the_Titan:_Or,_Futility The Wreck of the Titan: Or, Futility - Wikipedia]
* [[Videos#PorcupineTree|Porcupine Tree]] - [https://en.wikipedia.org/wiki/Futile_(EP) Futile], [https://de.wikipedia.org/wiki/Zeche_Bochum Zeche] [https://en.wikipedia.org/wiki/Bochum Bochum], November 18, 2003, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
+
* [[:Category:Porcupine Tree|Porcupine Tree]] - [https://en.wikipedia.org/wiki/Futile_(EP) Futile], [https://de.wikipedia.org/wiki/Zeche_Bochum Zeche] [https://en.wikipedia.org/wiki/Bochum Bochum], November 18, 2003, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 
: {{#evu:https://www.youtube.com/watch?v=C7mL-DNCuJc|alignment=left|valignment=top}}
 
: {{#evu:https://www.youtube.com/watch?v=C7mL-DNCuJc|alignment=left|valignment=top}}
  
 
=References=  
 
=References=  
 
<references />
 
<references />
 
 
'''[[Pruning|Up one Level]]'''
 
'''[[Pruning|Up one Level]]'''
 
[[Category:M. C. Escher]]
 
[[Category:M. C. Escher]]
 +
[[Category:Porcupine Tree]]

Latest revision as of 08:48, 8 July 2021

Home * Search * Selectivity * Pruning * Futility Pruning

M. C. Escher, Relativity, 1953 [1]

Futility Pruning,
in its pure form implemented at the frontier nodes (depth == 1) with one ply left to the horizon. It discards the moves that have no potential of raising alpha, which in turn requires some estimate of a potential value of a move. This is calculated by adding a futility margin (representing the largest conceivable positional gain) to the evaluation of the current position. If this does not exceed alpha then the futility pruning is triggered to skip this move (which further means setting a flag like f_prune = 1 to indicate not all moves were tried).

Conditions

For tactical stability, even in such a node we ought to search the following moves:

  • captures (either all or less typically only those that are capable of raising the score above alpha + margin)
  • moves that give check

Futility pruning is not used when the side to move is in check , or when either alpha or beta are close to the mate value, since it would leave the program blind to certain checkmates. Tord Romstad reported that in his early program Gothmog one more condition was necessary - namely that futility pruning requires checking for the existence of at least one legal move [2] [3] to avoid returning erroneous stalemate scores. As replied by Omid David: then simply return alpha (to fail low but hard).

Extended Futility Pruning

Ernst A. Heinz advocated using so-called extended futility pruning [4]. It means employing similar algorithm at pre frontier nodes at depth == 2, only with the greater margin. If at depth 1 the margin does not exceed the value of a minor piece, at depth 2 it should be more like the value of a rook.

Move Count Based Pruning

A further variation of Extended Futility Pruning combining the ideas of Fruit's History Leaf Pruning and Late Move Reductions is called Move Count Based Pruning or Late Move Pruning (LMP) as implemented in Stockfish [5].

Deep Futility Pruning

Deep Futility Pruning was proposed by Harm Geert Muller [6]. It is applied at depths of 1<d<=3+R, i.e. with two moves to go:

if ( CurEval <= Alpha - PVal[FirstPiece(Opponent)] - PVal[SecondPiece(Opponent)] - 2*PosMargin )
   prune

See also

Publications

Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...

2015 ...

2016

2017 ...

2020 ...

External Links

Pruning

Misc

futile - Wiktionary

References

Up one Level