25,161
edits
Changes
no edit summary
'''[[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#: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/>
* 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 [[Eli David|Omid David]]: then simply return alpha (to fail [[Fail-Low|low]] but [[Fail-Hard|hard]]).
<span id="Extendedfutilitypruning"></span>
=Extended Futility Pruning=
* [[Razoring]]
* [[Reverse Futility Pruning]]
* [[Sibling Prediction Pruning]]
=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]]
* [[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]]* [[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=
* [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=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=54761 LMP in PV nodes] by [[Peter Österlund]], [[CCC]], December 27, 2014 » [[Node Types#PV|PV-Node]], [[Texel]]
==2015 ...==
* [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
'''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=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.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=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
=External Links=
==Pruning==
* [httphttps://www.top-5000madchess.nlnet/authors2020/rebel02/chess84008/madchess-3-0-beta-4478cb8-late-move-pruning/ MadChess 3.htm#FUTILITY Search Techniques in REBEL 0 Beta 6f3d17a (Futility Late Move Pruning)] from by [http://www.top-5000.nl/authors/rebel/chess840.htm How Rebel Plays Chess[Erik Madsen]] by , February 8, 2020 » [[Ed SchroderFutility Pruning#MoveCountBasedPruning|Ed SchröderLMP]], [http://members.home.nl/matador/Inside%20Rebel.pdf pdf[MadChess]]
* [http://home.hccnet.nl/h.g.muller/deepfut.html Deep Futility Pruning] by [[Harm Geert Muller]]
==Misc==
* [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]
* [[Videos#PorcupineTree: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}}
=References=
<references />
'''[[Pruning|Up one Level]]'''
[[Category:M. C. Escher]]
[[Category:Porcupine Tree]]
