Home * Search * Selectivity * Pruning

		Pruning, (as opposed to reductions) a name for every heuristic that removes completely certain branches of the 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 [1]. 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. Shannon Type B programs only consider some plausible mores, but all other moves are pruned.
Samuel Bak - Under the Trees [2]

Backward pruning

sound pruning, not affecting the search result

• Mate Distance Pruning

Forward pruning techniques

Forward pruning techniques are either applied at expected Cut-Nodes or All-Nodes and return either beta as lower bound or alpha as upper bound. The none recursive ProbCut is applied at both types of none PV-nodes. Rather than immediately returning alpha at strong expected All-Nodes after a reduced or 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 as well as losing captures.

Returning Beta

at expected 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 All-Nodes
• ProbCut
• Reverse Futility Pruning
• Standing Pat in Quiescence Search

Returning Alpha

or below at expected All-Nodes or expected Cut-Nodes which turn out to become All-Nodes:

• after trying width[ply] moves in 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 All-Nodes:

• Bobby's Strategic Quiescence Search
• Futility Pruning
  Extended Futility Pruning
  Deep Futility Pruning
  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 ^[3]
• Pruning in Nimzo 2.2.1
• Quiescence Search
• Shannon Type B Strategy

Publications

1960 ...

• Richard Greenblatt, Donald Eastlake, 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, pdf from The Computer History Museum or as pdf or ps from DSpace at 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. Workshop on New Directions in Game-Tree Search
• Liwu Li (1989). Probabilistic Analysis of Search. Ph.D. thesis, University of Alberta, advisor Tony Marsland
• Liwu Li, Tony Marsland (1989). Probability-Based Game Tree Pruning. pdf

1990 ...

• Liwu Li, Tony Marsland (1990). Probability-Based Game Tree Pruning. Journal of Algorithms, Vol. 11, No. 1
• Chun Ye, Tony Marsland (1992). Experiments in Forward Pruning with Limited Extensions. ICCA Journal, Vol. 15, No. 2
• Yi-Fan Ke, Tai-Ming Parng (1993). The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning. ICCA Journal, Vol. 16, No. 2
• Chrilly Donninger. (1993). Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs. ICCA Journal, Vol. 16, No. 3
• Stephen J.J. Smith, Dana S. Nau (1994). An Analysis of Forward Pruning. Proceedings AAAI 1994, pdf
• Michael Buro (1995). ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm. ICCA Journal, Vol. 18, No. 2, pdf
• Ernst A. Heinz (1998). Extended Futility Pruning. 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, Vol. 23, No. 1, 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. Universiteit Maastricht, 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. pdf
• Mark Winands, Jaap van den Herik, Jos Uiterwijk, Erik van der Werf (2003). Enhanced forward pruning. Accepted for publication. 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, The University of New Mexico, pdf
• Yew Jin Lim, Wee Sun Lee (2006). Properties of Forward Pruning in Game-Tree Search, AAAI 2006, pdf
• Yew Jin Lim, Wee Sun Lee (2006). RankCut - A Domain Independent Forward Pruning Method for Games, AAAI 2006, pdf
• Jeroen Carolus (2006). Alpha-Beta with Sibling Prediction Pruning in Chess. Masters thesis, pdf
• Yew Jin Lim (2007). On Forward Pruning in Game-Tree Search. Ph.D. thesis, National University of Singapore, pdf

2010 ...

• Kieran Greer (2012). 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. arXiv:1403.0778

Forum Posts

1995 ...

• Forward pruning by Frank Phillips, CCC, October 16, 1999
  Re: Forward pruning by Andrew Williams, CCC, October 16, 1999

2000 ...

• Alpha beta fail soft, pruning & hash bounds? by Steve Maughan, CCC, December 14, 2000 » Fail-Soft, Bound
• Correct values if all moves are pruned? by Severi Salminen, CCC, January 05, 2001
• An interesting forward pruning experiment - with pseudo description by Vincent Diepeveen, rgcc, February 08, 2003
• Testing the reliability of forward pruning by Russell Reagan, CCC, May 15, 2003 » Engine Testing
• Forward Pruning... by Joshua Haglund, CCC, February 29, 2004
• Forward pruning and some related techniques by Sergei Markoff, CCC, March 02, 2004
• Bayesian Forward Pruning by Dann Corbit, CCC, April 09, 2004
• Forward/HB/Null move pruning ideas by Sergei Markoff, CCC, September 25, 2004

2005 ...

• About history pruning... by Svein Bjørnar Myrvang, CCC, October 26, 2005
• Fail-low pruning by Tommi Rimpiläinen, CCC, January 17, 2006
• History pruning by Frank Phillips from CCC, February 27, 2006
• history pruning/ late move pruning by Tom King, Winboard Programming Forum, March 02, 2006
• avoidrep-pruning by Gerd Isenberg, CCC, May 15, 2007 » Repetitions
• Toga/Glaurung/Strelka Prunings/Reductions by Edsel Apostol, CCC, January 31, 2008 » Toga, Glaurung, Strelka, Reductions
• Fruit 2.1 pruning by kongsian, CCC, July 15, 2008 » Fruit

2010 ...

• What program first used hard pruning? by Larry Kaufman, CCC, December 10, 2010
• Hard pruning history by Mark Watkins, Open Chess Programming Forum, December 10, 2010
• Using SEE to prune in main search by Tom King, CCC, January 08, 2011 » Static Exchange Evaluation
• Bad Pruning by Onno Garms, CCC, March 13, 2011 » Onno
• Reducing/Pruning Bad Captures (SEE < 0) by Edsel Apostol, CCC, August 19, 2011 » SEE
• Relationship between move ordering and pruning by Don Dailey, OpenChess Forum, December 17, 2012 » Move Ordering
• Adjustable search pruning depending on time control by Jerry Donald, CCC, December 20, 2012 » Time Management
• Pruning in QS by Harm Geert Muller, CCC, March 06, 2013 » Quiescence Search
• Pruning in today's top engines by Gordon Robertson, CCC, September 13, 2013
• stalemate detection and pruning by Jon Dart, CCC, September 22, 2013 » Stalemate
• pruning statistics by Jon Dart, CCC, January 27, 2014 » Search Statistics

2015 ...

• Verification of pruning techniques by Shawn Chidester, CCC, October 04, 2015
• EMR & EMP by Michael Sherwin, CCC, July 19, 2016
• Transposition table based pruning idea by Jerry Donald, CCC, December 25, 2017 » Transposition Table

External Links

Pruning Search Trees

• Selective Search Techniques in REBEL (introduction) from Programmer Corner by Ed Schröder ^[4] » Rebel

Pruning Trees

• Pruning (Plants) from Wikipedia
• Fruit tree pruning from Wikipedia » Fruit
• Shredding (tree-pruning technique) from Wikipedia » Shredder
• Pruning Trees and Shrubs
• Tree Pruning Techniques from New Mexico State University

References

1. ^ Better Alpha-Beta algorithm than pruning, to don't confuse it with the mentioned forward pruning
2. ^ Under the Trees, Oil on Canvas, 160 x 200 cm, Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
3. ^ Re: What is History Pruning? by Tord Romstad, CCC, July 03, 2005
4. ^ Nullmove vs classic selective search by Ed Schröder, CCC, August 04, 2012

What links here?

Up one level