Home * Search * Selectivity * Pruning
UnderTrees.jpg

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

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:

Skipping Moves

likely at All-Nodes:

See also


Publications

1960 ...

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...


Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...

2015 ...


External Links

Pruning Search Trees

Pruning Trees


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