25,161
edits
Changes
Created page with "'''Home * Search * Selectivity * Pruning''' FILE:UnderTrees.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b7047d58ae0c5..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * Pruning'''
[[FILE:UnderTrees.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b7047d58ae0c54bf8bab#57f3b7277d58ae2139bf8baf|[[Arts#Bak|Samuel Bak]] - Under the Trees <ref>Under the Trees, Oil on Canvas, 160 x 200 cm, [http://chgs.elevator.umn.edu/asset/viewAsset/57f3b7047d58ae0c54bf8bab#57f3b7277d58ae2139bf8baf Return to Vilna Series], [http://www.chgs.umn.edu/ Center for Holocaust & Genocide Studies], [https://en.wikipedia.org/wiki/University_of_Minnesota University of Minnesota]</ref> ]]
'''Pruning''', (as opposed to [[Reductions|reductions]]) <br/>
a name for every heuristic that removes completely certain branches of the [[Search Tree|search tree]], assuming they have no bearing to the search result. [[Alpha-Beta]] may be considered as backward pruning, because we found a refutation after searching <ref>Better Alpha-Beta algorithm than pruning, to don't confuse it with the mentioned forward pruning</ref>. Forward pruning always involves some risks to overlook something, with influence on the root score. Some pruning techniques rely on a specialized, but reduced search, others rely only on static move properties. [[Type B Strategy|Shannon Type B]] programs only consider some plausible mores, but all other moves are pruned.
=Backward pruning=
sound pruning, not affecting the search result
* [[Mate Distance Pruning]]
=Forward pruning techniques=
Forward pruning techniques are either applied at expected [[Node Types#CUT|Cut-Nodes]] or [[Node Types#ALL|All-Nodes]] and return either beta as [[Lower Bound|lower bound]] or alpha as [[Upper Bound|upper bound]]. The none [[Recursion|recursive]] [[ProbCut]] is applied at both types of none [[Node Types#PV|PV-nodes]]. Rather than immediately returning alpha at strong expected [[Node Types#ALL|All-Nodes]] after a reduced or [[Quiescence Search|quiescence search]], pruning techniques near the horizon skip moves, which are very unlikely to exceed alpha, or in case of the quiescence search itself, all (most) [[Quiet Moves|quiet moves]] as well as losing [[Captures|captures]].
==Returning Beta==
at expected [[Node Types#CUT|Cut-Nodes]]:
* [[Null Move Pruning]] - if reduced nullmove search fails high, return beta
* [[Multi-Cut]] - if a reduced, specialized search has C cut-offs from N tried moves, return beta
* [[Enhanced Forward Pruning]], also applicable at expected [[Node Types#ALL|All-Nodes]]
* [[ProbCut]]
* [[Reverse Futility Pruning]]
* [[Quiescence Search#StandPat|Standing Pat in Quiescence Search]]
==Returning Alpha==
or below at expected [[Node Types#ALL|All-Nodes]] or expected [[Node Types#CUT|Cut-Nodes]] which turn out to become All-Nodes:
* after trying '''width[ply]''' moves in [[Claude Shannon|Shannon]] '''Type-B''' programs, return alpha
* [[Sibling Prediction Pruning]] - return alpha, or depending on the implementation, only skip the move
* [[ProbCut]]
* [[Uncertainty Cut-Offs]]
==Skipping Moves==
likely at [[Node Types#ALL|All-Nodes]]:
* [[Bobby#StrategicQuiescenceSearch|Bobby's Strategic Quiescence Search]]
* [[Futility Pruning]]
: [[Futility Pruning#Extendedfutilityprunning|Extended Futility Pruning]]
: [[Futility Pruning#DeepFutilityPruning|Deep Futility Pruning]]
: [[Futility Pruning#MoveCountBasedPruning|Move Count Based Pruning]]
* [[AEL-Pruning]]
* [[Delta Pruning]] in [[Quiescence Search]]
* [[History Leaf Pruning]]
* [[Parity Pruning]]
=See also=
* [[Extensions]]
* [[Razoring]]
* [[Reductions]]
: [[Late Move Reductions]] aka History Pruning <ref>[https://www.stmintz.com/ccc/index.php?id=434817 Re: What is History Pruning?] by [[Tord Romstad]], [[CCC]], July 03, 2005</ref>
* [[Nimzo#Pruning|Pruning in Nimzo 2.2.1]]
* [[Quiescence Search]]
* [[Type B Strategy|Shannon Type B Strategy]]
=Publications=
==1960 ...==
* [[Richard Greenblatt]], [[Donald Eastlake]], [https://en.wikipedia.org/wiki/Steve_Crocker Stephen D. Crocker] ('''1967'''). ''The Greenblatt Chess Program''. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted ('''1988''') in [[Computer Chess Compendium]], [http://archive.computerhistory.org/projects/chess/related_materials/text/2-4.Greenblatt_Chess_Program/The_Greenblatt_Chess_Program.Greenblatt_Eastlake_Crocker.1967.Fall_Joint_Computer_Conference.062303060.sm.pdf pdf] from [[The Computer History Museum]] or as [http://dspace.mit.edu/handle/1721.1/6176 pdf or ps] from [http://libraries.mit.edu/dspace-mit/ DSpace] at [[Massachusetts Institute of Technology|MIT]]
==1970 ...==
* [[John Birmingham]], [[Peter Kent]] ('''1977'''). ''Tree-searching and tree-pruning techniques''. [[Advances in Computer Chess 1]], reprinted in [[Computer Chess Compendium]]
==1980 ...==
* [[Peter W. Frey]] ('''1983'''). ''The Alpha-Beta Algorithm: Incremental Updating, Well-Behaved Evaluation Functions, and Non-Speculative Forward Pruning''. Computer Game-Playing (ed. [[Max Bramer]]), pp. 285-289. Ellis Horwood Limited Publishers, Chichester.
* [[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]]
* [[Hermann Kaindl]], [[Marcus Wagner]], [[Helmut Horacek]] ('''1988'''). ''Comparing Various Pruning Algorithms on Very Strongly Ordered Game Trees: The Details.'' Tech. Report #50, Department of Statistics and Computer Science, [[Vienna University of Technology]]
* [[Hermann Kaindl]], [[Marcus Wagner]], [[Helmut Horacek]] ('''1989'''). ''Comparing Various Pruning Algorithms on Very Strongly Ordered Game Trees''. [[WCCC 1989#Workshop|Workshop on New Directions in Game-Tree Search]]
* [[Liwu Li]] ('''1989'''). ''[https://doi.org/10.7939/R3VX06F26 Probabilistic Analysis of Search]''. Ph.D. thesis, [[University of Alberta]], advisor [[Tony Marsland]]
* [[Liwu Li]], [[Tony Marsland]] ('''1989'''). ''Probability-Based Game Tree Pruning''. [http://webdocs.cs.ualberta.ca/~tony/OldPapers/joa89.pdf pdf]
==1990 ...==
* [[Liwu Li]], [[Tony Marsland]] ('''1990'''). ''[http://www.sciencedirect.com/science/article/pii/019667749090027C Probability-Based Game Tree Pruning]''. [ftp://ftp.math.utah.edu/pub/tex/bib/toc/jalg.html#11(1):March:1990 Journal of Algorithms, Vol. 11, No. 1]
* [[Chun Ye]], [[Tony Marsland]] ('''1992'''). ''Experiments in Forward Pruning with Limited Extensions.'' [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
* [[Yi-Fan Ke]], [[Tai-Ming Parng]] ('''1993'''). ''The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning''. [[ICGA Journal#16_2|ICCA Journal, Vol. 16, No. 2]]
* [[Chrilly Donninger]]. ('''1993'''). ''Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs.'' [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]
* [[Stephen J.J. Smith]], [[Dana Nau|Dana S. Nau]] ('''1994'''). ''An Analysis of Forward Pruning''. Proceedings [[AAAI]] 1994, [http://www.aaai.org/Papers/AAAI/1994/AAAI94-213.pdf pdf]
* [[Michael Buro]] ('''1995'''). ''ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.'' [[ICGA Journal#18_2|ICCA Journal, Vol. 18, No. 2]], [http://www.cs.ualberta.ca/~mburo/ps/probcut.pdf pdf]
* [[Ernst A. Heinz]] ('''1998'''). ''[http://people.csail.mit.edu/heinz/dt/node18.html Extended Futility Pruning].'' [[ICGA Journal#21_3|ICCA Journal, Vol. 21, No. 3]]
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''1998'''). ''Multi-Cut Pruning in Alpha-Beta Search''. [[CG 1998]], pp. 15-24. See also [[Yngvi Björnsson]], [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search''. Theoretical Computer Science, Vol. 252, pp. 177-196 for an expanded version.
==2000 ...==
* [[Ernst A. Heinz]] ('''2000'''). ''AEL Pruning.'' [[ICGA Journal#23_1|ICGA Journal, Vol. 23, No. 1]], [http://www.top-5000.nl/ps/AEL%20pruning.pdf pdf]
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2000'''). ''Selective Depth-First Search Methods''. in [[Jaap van den Herik]], [[Hiroyuki Iida]] (eds.) ('''2000'''). ''Games in AI Research''. [[Maastricht University|Universiteit Maastricht]], [http://www.cs.ualberta.ca/%7Etony/RecentPapers/nec97w.pdf pdf preprint]
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search.'' Theoretical Computer Science, Vol. 252, pp. 177-196. [http://www.ru.is/faculty/yngvi/pdf/BjornssonM01a.pdf pdf]
* [[Mark Winands]], [[Jaap van den Herik]], [[Jos Uiterwijk]], [[Erik van der Werf]] ('''2003'''). ''Enhanced forward pruning.'' Accepted for publication. [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf]
* [[Qian Liang]] ('''2003'''). ''The Evolution of Mulan: Some Studies in Game-Tree Pruning and Evaluation Functions in the Game of Amanons''. M.Sc. thesis, Electronic Engineering, [https://en.wikipedia.org/wiki/University_of_New_Mexico The University of New Mexico], [http://www.santafe.edu/~moore/QianThesis.pdf pdf]
* [[Yew Jin Lim]], [[Wee Sun Lee]] ('''2006'''). ''Properties of Forward Pruning in Game-Tree Search'', AAAI 2006, [http://www.yewjin.com/storage/papers/riskmanagement.pdf pdf]
* [[Yew Jin Lim]], [[Wee Sun Lee]] ('''2006'''). ''RankCut - A Domain Independent Forward Pruning Method for Games'', AAAI 2006, [http://www.yewjin.com/storage/papers/rankcut.pdf pdf]
* [[Jeroen Carolus]] ('''2006'''). ''Alpha-Beta with Sibling Prediction Pruning in Chess''. Masters thesis, [http://homepages.cwi.nl/%7Epaulk/theses/Carolus.pdf pdf]
* [[Yew Jin Lim]] ('''2007'''). ''On Forward Pruning in Game-Tree Search''. Ph.D. thesis, [https://en.wikipedia.org/wiki/National_University_of_Singapore National University of Singapore], [http://www.yewjin.com/storage/papers/PhDThesisLimYewJin.pdf pdf]
==2010 ...==
* [[Kieran Greer]] ('''2012'''). ''[http://www.hindawi.com/journals/aai/2013/357068/ Tree Pruning for New Search Techniques in Computer Games]''. Advances in Artificial Intelligence, Vol. 2013
* [[Kieran Greer]] ('''2013'''). ''Dynamic Move Chains – a Forward Pruning Approach to Tree Search in Computer Chess''. [http://arxiv.org/abs/1403.0778 arXiv:1403.0778]
=Forum Posts=
==1995 ...==
* [https://www.stmintz.com/ccc/index.php?id=73649 Forward pruning] by [[Frank Phillips]], [[CCC]], October 16, 1999
: [https://www.stmintz.com/ccc/index.php?id=73701 Re: Forward pruning] by [[Andrew Williams]], [[CCC]], October 16, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=144854 Alpha beta fail soft, pruning & hash bounds?] by [[Steve Maughan]], [[CCC]], December 14, 2000 » [[Fail-Soft]], [[Bound]]
* [https://www.stmintz.com/ccc/index.php?id=148308 Correct values if all moves are pruned?] by [[Severi Salminen]], [[CCC]], January 05, 2001
* [https://groups.google.com/d/msg/rec.games.chess.computer/iECalt6Tzug/GWNOLzFQyk8J An interesting forward pruning experiment - with pseudo description] by [[Vincent Diepeveen]], [[Computer Chess Forums|rgcc]], February 08, 2003
* [https://www.stmintz.com/ccc/index.php?id=296689 Testing the reliability of forward pruning] by [[Russell Reagan]], [[CCC]], May 15, 2003 » [[Engine Testing]]
* [https://www.stmintz.com/ccc/index.php?id=351949 Forward Pruning...] by [[Joshua Haglund]], [[CCC]], February 29, 2004
* [https://www.stmintz.com/ccc/index.php?id=352384 Forward pruning and some related techniques] by [[Sergei Markoff]], [[CCC]], March 02, 2004
* [https://www.stmintz.com/ccc/index.php?id=359342 Bayesian Forward Pruning] by [[Dann Corbit]], [[CCC]], April 09, 2004
* [https://www.stmintz.com/ccc/index.php?id=389135 Forward/HB/Null move pruning ideas] by [[Sergei Markoff]], [[CCC]], September 25, 2004
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=457846 About history pruning...] by Svein Bjørnar Myrvang, [[CCC]], October 26, 2005
* [https://www.stmintz.com/ccc/index.php?id=480380 Fail-low pruning] by Tommi Rimpiläinen, [[CCC]], January 17, 2006
* [https://www.stmintz.com/ccc/index.php?id=489978 History pruning] by [[Frank Phillips]] from [[CCC]], February 27, 2006
* [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.talkchess.com/forum/viewtopic.php?t=13791 avoidrep-pruning] by [[Gerd Isenberg]], [[CCC]], May 15, 2007 » [[Repetitions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=19316 Toga/Glaurung/Strelka Prunings/Reductions] by [[Edsel Apostol]], [[CCC]], January 31, 2008 » [[Toga]], [[Glaurung]], [[Strelka]], [[Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=22359 Fruit 2.1 pruning] by [[Chua Kong Sian|kongsian]], [[CCC]], July 15, 2008 » [[Fruit]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=37012 What program first used hard pruning?] by [[Larry Kaufman]], [[CCC]], December 10, 2010
* [http://www.open-chess.org/viewtopic.php?f=5&t=807 Hard pruning history] by [[Mark Watkins]], [[Computer Chess Forums|Open Chess Programming Forum]], December 10, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=37514 Using SEE to prune in main search] by [[Tom King]], [[CCC]], January 08, 2011 » [[Static Exchange Evaluation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=38407 Bad Pruning] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Onno]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40100 Reducing/Pruning Bad Captures (SEE < 0)] by [[Edsel Apostol]], [[CCC]], August 19, 2011 » [[Static Exchange Evaluation|SEE]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2173 Relationship between move ordering and pruning] by [[Don Dailey]], [[Computer Chess Forums|OpenChess Forum]], December 17, 2012 » [[Move Ordering]]
* [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]]
* [http://www.talkchess.com/forum/viewtopic.php?t=47423 Pruning in QS] by [[Harm Geert Muller]], [[CCC]], March 06, 2013 » [[Quiescence Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=49342 Pruning in today's top engines] by Gordon Robertson, [[CCC]], September 13, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=49429 stalemate detection and pruning] by [[Jon Dart]], [[CCC]], September 22, 2013 » [[Stalemate]]
* [http://www.talkchess.com/forum/viewtopic.php?t=51075 pruning statistics] by [[Jon Dart]], [[CCC]], January 27, 2014 » [[Search Statistics]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57843 Verification of pruning techniques] by [[Shawn Chidester]], [[CCC]], October 04, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=60868 EMR & EMP] by [[Michael Sherwin]], [[CCC]], July 19, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=66135 Transposition table based pruning idea] by [[Jerry Donald]], [[CCC]], December 25, 2017 » [[Transposition Table]]
=External Links=
==Pruning Search Trees==
* [http://www.top-5000.nl/authors/rebel/chess840.htm#SELECTIVE%20SEARCH Selective Search Techniques in REBEL (introduction)] from [http://www.top-5000.nl/authors/rebel/chess840.htm Programmer Corner] by [[Ed Schroder|Ed Schröder]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=44686 Nullmove vs classic selective search] by [[Ed Schroder|Ed Schröder]], [[CCC]], August 04, 2012</ref> » [[Rebel]]
==Pruning Trees==
* [https://en.wikipedia.org/wiki/Pruning Pruning (Plants) from Wikipedia]
* [https://en.wikipedia.org/wiki/Fruit_tree_pruning Fruit tree pruning from Wikipedia] » [[Fruit]]
* [https://en.wikipedia.org/wiki/Shredding_%28tree-pruning_technique%29 Shredding (tree-pruning technique) from Wikipedia] » [[Shredder]]
* [http://www.extension.umn.edu/distribution/horticulture/dg0628.html Pruning Trees and Shrubs]
* [http://aces.nmsu.edu/pubs/_h/h-156/welcome.html Tree Pruning Techniques] from [https://en.wikipedia.org/wiki/New_Mexico_State_University New Mexico State University]
=References=
<references />
'''[[Selectivity|Up one level]]'''
[[FILE:UnderTrees.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b7047d58ae0c54bf8bab#57f3b7277d58ae2139bf8baf|[[Arts#Bak|Samuel Bak]] - Under the Trees <ref>Under the Trees, Oil on Canvas, 160 x 200 cm, [http://chgs.elevator.umn.edu/asset/viewAsset/57f3b7047d58ae0c54bf8bab#57f3b7277d58ae2139bf8baf Return to Vilna Series], [http://www.chgs.umn.edu/ Center for Holocaust & Genocide Studies], [https://en.wikipedia.org/wiki/University_of_Minnesota University of Minnesota]</ref> ]]
'''Pruning''', (as opposed to [[Reductions|reductions]]) <br/>
a name for every heuristic that removes completely certain branches of the [[Search Tree|search tree]], assuming they have no bearing to the search result. [[Alpha-Beta]] may be considered as backward pruning, because we found a refutation after searching <ref>Better Alpha-Beta algorithm than pruning, to don't confuse it with the mentioned forward pruning</ref>. Forward pruning always involves some risks to overlook something, with influence on the root score. Some pruning techniques rely on a specialized, but reduced search, others rely only on static move properties. [[Type B Strategy|Shannon Type B]] programs only consider some plausible mores, but all other moves are pruned.
=Backward pruning=
sound pruning, not affecting the search result
* [[Mate Distance Pruning]]
=Forward pruning techniques=
Forward pruning techniques are either applied at expected [[Node Types#CUT|Cut-Nodes]] or [[Node Types#ALL|All-Nodes]] and return either beta as [[Lower Bound|lower bound]] or alpha as [[Upper Bound|upper bound]]. The none [[Recursion|recursive]] [[ProbCut]] is applied at both types of none [[Node Types#PV|PV-nodes]]. Rather than immediately returning alpha at strong expected [[Node Types#ALL|All-Nodes]] after a reduced or [[Quiescence Search|quiescence search]], pruning techniques near the horizon skip moves, which are very unlikely to exceed alpha, or in case of the quiescence search itself, all (most) [[Quiet Moves|quiet moves]] as well as losing [[Captures|captures]].
==Returning Beta==
at expected [[Node Types#CUT|Cut-Nodes]]:
* [[Null Move Pruning]] - if reduced nullmove search fails high, return beta
* [[Multi-Cut]] - if a reduced, specialized search has C cut-offs from N tried moves, return beta
* [[Enhanced Forward Pruning]], also applicable at expected [[Node Types#ALL|All-Nodes]]
* [[ProbCut]]
* [[Reverse Futility Pruning]]
* [[Quiescence Search#StandPat|Standing Pat in Quiescence Search]]
==Returning Alpha==
or below at expected [[Node Types#ALL|All-Nodes]] or expected [[Node Types#CUT|Cut-Nodes]] which turn out to become All-Nodes:
* after trying '''width[ply]''' moves in [[Claude Shannon|Shannon]] '''Type-B''' programs, return alpha
* [[Sibling Prediction Pruning]] - return alpha, or depending on the implementation, only skip the move
* [[ProbCut]]
* [[Uncertainty Cut-Offs]]
==Skipping Moves==
likely at [[Node Types#ALL|All-Nodes]]:
* [[Bobby#StrategicQuiescenceSearch|Bobby's Strategic Quiescence Search]]
* [[Futility Pruning]]
: [[Futility Pruning#Extendedfutilityprunning|Extended Futility Pruning]]
: [[Futility Pruning#DeepFutilityPruning|Deep Futility Pruning]]
: [[Futility Pruning#MoveCountBasedPruning|Move Count Based Pruning]]
* [[AEL-Pruning]]
* [[Delta Pruning]] in [[Quiescence Search]]
* [[History Leaf Pruning]]
* [[Parity Pruning]]
=See also=
* [[Extensions]]
* [[Razoring]]
* [[Reductions]]
: [[Late Move Reductions]] aka History Pruning <ref>[https://www.stmintz.com/ccc/index.php?id=434817 Re: What is History Pruning?] by [[Tord Romstad]], [[CCC]], July 03, 2005</ref>
* [[Nimzo#Pruning|Pruning in Nimzo 2.2.1]]
* [[Quiescence Search]]
* [[Type B Strategy|Shannon Type B Strategy]]
=Publications=
==1960 ...==
* [[Richard Greenblatt]], [[Donald Eastlake]], [https://en.wikipedia.org/wiki/Steve_Crocker Stephen D. Crocker] ('''1967'''). ''The Greenblatt Chess Program''. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted ('''1988''') in [[Computer Chess Compendium]], [http://archive.computerhistory.org/projects/chess/related_materials/text/2-4.Greenblatt_Chess_Program/The_Greenblatt_Chess_Program.Greenblatt_Eastlake_Crocker.1967.Fall_Joint_Computer_Conference.062303060.sm.pdf pdf] from [[The Computer History Museum]] or as [http://dspace.mit.edu/handle/1721.1/6176 pdf or ps] from [http://libraries.mit.edu/dspace-mit/ DSpace] at [[Massachusetts Institute of Technology|MIT]]
==1970 ...==
* [[John Birmingham]], [[Peter Kent]] ('''1977'''). ''Tree-searching and tree-pruning techniques''. [[Advances in Computer Chess 1]], reprinted in [[Computer Chess Compendium]]
==1980 ...==
* [[Peter W. Frey]] ('''1983'''). ''The Alpha-Beta Algorithm: Incremental Updating, Well-Behaved Evaluation Functions, and Non-Speculative Forward Pruning''. Computer Game-Playing (ed. [[Max Bramer]]), pp. 285-289. Ellis Horwood Limited Publishers, Chichester.
* [[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]]
* [[Hermann Kaindl]], [[Marcus Wagner]], [[Helmut Horacek]] ('''1988'''). ''Comparing Various Pruning Algorithms on Very Strongly Ordered Game Trees: The Details.'' Tech. Report #50, Department of Statistics and Computer Science, [[Vienna University of Technology]]
* [[Hermann Kaindl]], [[Marcus Wagner]], [[Helmut Horacek]] ('''1989'''). ''Comparing Various Pruning Algorithms on Very Strongly Ordered Game Trees''. [[WCCC 1989#Workshop|Workshop on New Directions in Game-Tree Search]]
* [[Liwu Li]] ('''1989'''). ''[https://doi.org/10.7939/R3VX06F26 Probabilistic Analysis of Search]''. Ph.D. thesis, [[University of Alberta]], advisor [[Tony Marsland]]
* [[Liwu Li]], [[Tony Marsland]] ('''1989'''). ''Probability-Based Game Tree Pruning''. [http://webdocs.cs.ualberta.ca/~tony/OldPapers/joa89.pdf pdf]
==1990 ...==
* [[Liwu Li]], [[Tony Marsland]] ('''1990'''). ''[http://www.sciencedirect.com/science/article/pii/019667749090027C Probability-Based Game Tree Pruning]''. [ftp://ftp.math.utah.edu/pub/tex/bib/toc/jalg.html#11(1):March:1990 Journal of Algorithms, Vol. 11, No. 1]
* [[Chun Ye]], [[Tony Marsland]] ('''1992'''). ''Experiments in Forward Pruning with Limited Extensions.'' [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
* [[Yi-Fan Ke]], [[Tai-Ming Parng]] ('''1993'''). ''The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning''. [[ICGA Journal#16_2|ICCA Journal, Vol. 16, No. 2]]
* [[Chrilly Donninger]]. ('''1993'''). ''Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs.'' [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]
* [[Stephen J.J. Smith]], [[Dana Nau|Dana S. Nau]] ('''1994'''). ''An Analysis of Forward Pruning''. Proceedings [[AAAI]] 1994, [http://www.aaai.org/Papers/AAAI/1994/AAAI94-213.pdf pdf]
* [[Michael Buro]] ('''1995'''). ''ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.'' [[ICGA Journal#18_2|ICCA Journal, Vol. 18, No. 2]], [http://www.cs.ualberta.ca/~mburo/ps/probcut.pdf pdf]
* [[Ernst A. Heinz]] ('''1998'''). ''[http://people.csail.mit.edu/heinz/dt/node18.html Extended Futility Pruning].'' [[ICGA Journal#21_3|ICCA Journal, Vol. 21, No. 3]]
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''1998'''). ''Multi-Cut Pruning in Alpha-Beta Search''. [[CG 1998]], pp. 15-24. See also [[Yngvi Björnsson]], [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search''. Theoretical Computer Science, Vol. 252, pp. 177-196 for an expanded version.
==2000 ...==
* [[Ernst A. Heinz]] ('''2000'''). ''AEL Pruning.'' [[ICGA Journal#23_1|ICGA Journal, Vol. 23, No. 1]], [http://www.top-5000.nl/ps/AEL%20pruning.pdf pdf]
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2000'''). ''Selective Depth-First Search Methods''. in [[Jaap van den Herik]], [[Hiroyuki Iida]] (eds.) ('''2000'''). ''Games in AI Research''. [[Maastricht University|Universiteit Maastricht]], [http://www.cs.ualberta.ca/%7Etony/RecentPapers/nec97w.pdf pdf preprint]
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search.'' Theoretical Computer Science, Vol. 252, pp. 177-196. [http://www.ru.is/faculty/yngvi/pdf/BjornssonM01a.pdf pdf]
* [[Mark Winands]], [[Jaap van den Herik]], [[Jos Uiterwijk]], [[Erik van der Werf]] ('''2003'''). ''Enhanced forward pruning.'' Accepted for publication. [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf]
* [[Qian Liang]] ('''2003'''). ''The Evolution of Mulan: Some Studies in Game-Tree Pruning and Evaluation Functions in the Game of Amanons''. M.Sc. thesis, Electronic Engineering, [https://en.wikipedia.org/wiki/University_of_New_Mexico The University of New Mexico], [http://www.santafe.edu/~moore/QianThesis.pdf pdf]
* [[Yew Jin Lim]], [[Wee Sun Lee]] ('''2006'''). ''Properties of Forward Pruning in Game-Tree Search'', AAAI 2006, [http://www.yewjin.com/storage/papers/riskmanagement.pdf pdf]
* [[Yew Jin Lim]], [[Wee Sun Lee]] ('''2006'''). ''RankCut - A Domain Independent Forward Pruning Method for Games'', AAAI 2006, [http://www.yewjin.com/storage/papers/rankcut.pdf pdf]
* [[Jeroen Carolus]] ('''2006'''). ''Alpha-Beta with Sibling Prediction Pruning in Chess''. Masters thesis, [http://homepages.cwi.nl/%7Epaulk/theses/Carolus.pdf pdf]
* [[Yew Jin Lim]] ('''2007'''). ''On Forward Pruning in Game-Tree Search''. Ph.D. thesis, [https://en.wikipedia.org/wiki/National_University_of_Singapore National University of Singapore], [http://www.yewjin.com/storage/papers/PhDThesisLimYewJin.pdf pdf]
==2010 ...==
* [[Kieran Greer]] ('''2012'''). ''[http://www.hindawi.com/journals/aai/2013/357068/ Tree Pruning for New Search Techniques in Computer Games]''. Advances in Artificial Intelligence, Vol. 2013
* [[Kieran Greer]] ('''2013'''). ''Dynamic Move Chains – a Forward Pruning Approach to Tree Search in Computer Chess''. [http://arxiv.org/abs/1403.0778 arXiv:1403.0778]
=Forum Posts=
==1995 ...==
* [https://www.stmintz.com/ccc/index.php?id=73649 Forward pruning] by [[Frank Phillips]], [[CCC]], October 16, 1999
: [https://www.stmintz.com/ccc/index.php?id=73701 Re: Forward pruning] by [[Andrew Williams]], [[CCC]], October 16, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=144854 Alpha beta fail soft, pruning & hash bounds?] by [[Steve Maughan]], [[CCC]], December 14, 2000 » [[Fail-Soft]], [[Bound]]
* [https://www.stmintz.com/ccc/index.php?id=148308 Correct values if all moves are pruned?] by [[Severi Salminen]], [[CCC]], January 05, 2001
* [https://groups.google.com/d/msg/rec.games.chess.computer/iECalt6Tzug/GWNOLzFQyk8J An interesting forward pruning experiment - with pseudo description] by [[Vincent Diepeveen]], [[Computer Chess Forums|rgcc]], February 08, 2003
* [https://www.stmintz.com/ccc/index.php?id=296689 Testing the reliability of forward pruning] by [[Russell Reagan]], [[CCC]], May 15, 2003 » [[Engine Testing]]
* [https://www.stmintz.com/ccc/index.php?id=351949 Forward Pruning...] by [[Joshua Haglund]], [[CCC]], February 29, 2004
* [https://www.stmintz.com/ccc/index.php?id=352384 Forward pruning and some related techniques] by [[Sergei Markoff]], [[CCC]], March 02, 2004
* [https://www.stmintz.com/ccc/index.php?id=359342 Bayesian Forward Pruning] by [[Dann Corbit]], [[CCC]], April 09, 2004
* [https://www.stmintz.com/ccc/index.php?id=389135 Forward/HB/Null move pruning ideas] by [[Sergei Markoff]], [[CCC]], September 25, 2004
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=457846 About history pruning...] by Svein Bjørnar Myrvang, [[CCC]], October 26, 2005
* [https://www.stmintz.com/ccc/index.php?id=480380 Fail-low pruning] by Tommi Rimpiläinen, [[CCC]], January 17, 2006
* [https://www.stmintz.com/ccc/index.php?id=489978 History pruning] by [[Frank Phillips]] from [[CCC]], February 27, 2006
* [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.talkchess.com/forum/viewtopic.php?t=13791 avoidrep-pruning] by [[Gerd Isenberg]], [[CCC]], May 15, 2007 » [[Repetitions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=19316 Toga/Glaurung/Strelka Prunings/Reductions] by [[Edsel Apostol]], [[CCC]], January 31, 2008 » [[Toga]], [[Glaurung]], [[Strelka]], [[Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=22359 Fruit 2.1 pruning] by [[Chua Kong Sian|kongsian]], [[CCC]], July 15, 2008 » [[Fruit]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=37012 What program first used hard pruning?] by [[Larry Kaufman]], [[CCC]], December 10, 2010
* [http://www.open-chess.org/viewtopic.php?f=5&t=807 Hard pruning history] by [[Mark Watkins]], [[Computer Chess Forums|Open Chess Programming Forum]], December 10, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=37514 Using SEE to prune in main search] by [[Tom King]], [[CCC]], January 08, 2011 » [[Static Exchange Evaluation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=38407 Bad Pruning] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Onno]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40100 Reducing/Pruning Bad Captures (SEE < 0)] by [[Edsel Apostol]], [[CCC]], August 19, 2011 » [[Static Exchange Evaluation|SEE]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2173 Relationship between move ordering and pruning] by [[Don Dailey]], [[Computer Chess Forums|OpenChess Forum]], December 17, 2012 » [[Move Ordering]]
* [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]]
* [http://www.talkchess.com/forum/viewtopic.php?t=47423 Pruning in QS] by [[Harm Geert Muller]], [[CCC]], March 06, 2013 » [[Quiescence Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=49342 Pruning in today's top engines] by Gordon Robertson, [[CCC]], September 13, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=49429 stalemate detection and pruning] by [[Jon Dart]], [[CCC]], September 22, 2013 » [[Stalemate]]
* [http://www.talkchess.com/forum/viewtopic.php?t=51075 pruning statistics] by [[Jon Dart]], [[CCC]], January 27, 2014 » [[Search Statistics]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57843 Verification of pruning techniques] by [[Shawn Chidester]], [[CCC]], October 04, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=60868 EMR & EMP] by [[Michael Sherwin]], [[CCC]], July 19, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=66135 Transposition table based pruning idea] by [[Jerry Donald]], [[CCC]], December 25, 2017 » [[Transposition Table]]
=External Links=
==Pruning Search Trees==
* [http://www.top-5000.nl/authors/rebel/chess840.htm#SELECTIVE%20SEARCH Selective Search Techniques in REBEL (introduction)] from [http://www.top-5000.nl/authors/rebel/chess840.htm Programmer Corner] by [[Ed Schroder|Ed Schröder]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=44686 Nullmove vs classic selective search] by [[Ed Schroder|Ed Schröder]], [[CCC]], August 04, 2012</ref> » [[Rebel]]
==Pruning Trees==
* [https://en.wikipedia.org/wiki/Pruning Pruning (Plants) from Wikipedia]
* [https://en.wikipedia.org/wiki/Fruit_tree_pruning Fruit tree pruning from Wikipedia] » [[Fruit]]
* [https://en.wikipedia.org/wiki/Shredding_%28tree-pruning_technique%29 Shredding (tree-pruning technique) from Wikipedia] » [[Shredder]]
* [http://www.extension.umn.edu/distribution/horticulture/dg0628.html Pruning Trees and Shrubs]
* [http://aces.nmsu.edu/pubs/_h/h-156/welcome.html Tree Pruning Techniques] from [https://en.wikipedia.org/wiki/New_Mexico_State_University New Mexico State University]
=References=
<references />
'''[[Selectivity|Up one level]]'''
