Difference between revisions of "Pruning"

From Chessprogramming wiki
Jump to: navigation, search
(One intermediate revision by the same user not shown)
Line 52: Line 52:
 
=Publications=  
 
=Publications=  
 
==1960 ...==
 
==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]]
+
* [[Richard Greenblatt]], [[Donald Eastlake]], [[Stephen D. Crocker]] ('''1967'''). ''The Greenblatt Chess Program''. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, 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 ...==  
 
==1970 ...==  
 
* [[John Birmingham]], [[Peter Kent]] ('''1977'''). ''Tree-searching and tree-pruning techniques''. [[Advances in Computer Chess 1]], reprinted in [[Computer Chess Compendium]]
 
* [[John Birmingham]], [[Peter Kent]] ('''1977'''). ''Tree-searching and tree-pruning techniques''. [[Advances in Computer Chess 1]], reprinted in [[Computer Chess Compendium]]
Line 129: Line 129:
 
==2020 ...==
 
==2020 ...==
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72981 Pruning / reduction depending on king safety] by [[Vivien Clauzon]], [[CCC]], February 02, 2020 » [[King Safety]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72981 Pruning / reduction depending on king safety] by [[Vivien Clauzon]], [[CCC]], February 02, 2020 » [[King Safety]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74425 Questions on Razoring and Code Structure for Pruning] by Cheney, [[CCC]], July 09, 2020 » [[Razoring]]
  
 
=External Links=
 
=External Links=

Revision as of 09:33, 21 August 2020

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

2020 ...

External Links

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

Up one level