Pruning

From Chessprogramming wiki
Revision as of 17:45, 7 March 2019 by GerdIsenberg (talk | contribs)
Jump to: navigation, search

Home * Search * Selectivity * Pruning

Samuel Bak - Under the Trees [1]

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 [2]. 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.

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:

Extended Futility Pruning
Deep Futility Pruning
Move Count Based Pruning

See also

Late Move Reductions aka History Pruning [3]

Publications

1960 ...

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

Forum Posts

1995 ...

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

2000 ...

2005 ...

2010 ...

2015 ...

External Links

Pruning Search Trees

Pruning Trees

References

  1. Under the Trees, Oil on Canvas, 160 x 200 cm, Return to Vilna Series, Center for Holocaust & Genocide Studies, University of Minnesota
  2. Better Alpha-Beta algorithm than pruning, to don't confuse it with the mentioned forward pruning
  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

Up one level