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.

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 recursiveProbCut 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.

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.

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.

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

Home * Search * Selectivity * PruningPruning, (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.^{[2]}## Table of Contents

## Backward pruning

sound pruning, not affecting the search result## 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:## Returning Alpha

or below at expected All-Nodes or expected Cut-Nodes which turn out to become All-Nodes:width[ply]moves in ShannonType-Bprograms, return alpha## Skipping Moves

likely at All-Nodes:Extended Futility Pruning

Deep Futility Pruning

Move Count Based Pruning

## See also

Late Move Reductions aka History Pruning

^{[3]}## Publications

## 1960 ...

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 ...

1977).Tree-searching and tree-pruning techniques. Advances in Computer Chess 1, reprinted in Computer Chess Compendium## 1980 ...

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.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 Alberta1988).Comparing Various Pruning Algorithms on Very Strongly Ordered Game Trees: The Details.Tech. Report #50, Department of Statistics and Computer Science, Vienna University of Technology1989).Comparing Various Pruning Algorithms on Very Strongly Ordered Game Trees. Workshop on New Directions in Game-Tree Search1989).Probabilistic Analysis of Search. Ph.D. thesis, University of Alberta, advisor Tony Marsland1989).Probability-Based Game Tree Pruning. pdf## 1990 ...

1990).Probability-Based Game Tree Pruning. Journal of Algorithms, Vol. 11, No. 11992).Experiments in Forward Pruning with Limited Extensions.ICCA Journal, Vol. 15, No. 21993).The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning. ICCA Journal, Vol. 16, No. 21993).Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs.ICCA Journal, Vol. 16, No. 31994).An Analysis of Forward Pruning. Proceedings AAAI 1994, pdf1995).ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.ICCA Journal, Vol. 18, No. 2, pdf1998).Extended Futility Pruning.ICCA Journal, Vol. 21, No. 31998).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 ...

2000).AEL Pruning.ICGA Journal, Vol. 23, No. 1, pdf2000).Selective Depth-First Search Methods. in Jaap van den Herik, Hiroyuki Iida (eds.) (2000).Games in AI Research. Universiteit Maastricht, pdf preprint2001).Multi-cut Alpha-Beta Pruning in Game Tree Search.Theoretical Computer Science, Vol. 252, pp. 177-196. pdf2003).Enhanced forward pruning.Accepted for publication. pdf2003).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, pdf2006).Properties of Forward Pruning in Game-Tree Search, AAAI 2006, pdf2006).RankCut - A Domain Independent Forward Pruning Method for Games, AAAI 2006, pdf2006).Alpha-Beta with Sibling Prediction Pruning in Chess. Masters thesis, pdf2007).On Forward Pruning in Game-Tree Search. Ph.D. thesis, National University of Singapore, pdf## 2010 ...

2012).Tree Pruning for New Search Techniques in Computer Games. Advances in Artificial Intelligence, Vol. 20132013).Dynamic Move Chains – a Forward Pruning Approach to Tree Search in Computer Chess. arXiv:1403.0778## Forum Posts

## 1995 ...

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

## 2000 ...

## 2005 ...

## 2010 ...

## 2015 ...

## External Links

## Pruning Search Trees

^{[4]}» Rebel## Pruning Trees

## References

## What links here?

Up one level