Difference between revisions of "Pruning"

From Chessprogramming wiki
Jump to: navigation, search
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * Pruning'''
 
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * Pruning'''
  
[[FILE:UnderTrees.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b7047d58ae0c54bf8bab#57f3b7277d58ae2139bf8baf|[[:Category:Samuel Bak|Samuel Bak]] - Under the Trees <ref>Under the Trees, Oil on Canvas, 160 x 200 cm,  [http://chgs.elevator.umn.edu/asset/viewAsset/57f3b7047d58ae0c54bf8bab#57f3b7277d58ae2139bf8baf Return to Vilna Series], [http://www.chgs.umn.edu/ Center for Holocaust & Genocide Studies], [https://en.wikipedia.org/wiki/University_of_Minnesota University of Minnesota]</ref> ]]  
+
[[FILE:UnderTrees.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b7047d58ae0c54bf8bab#57f3b7277d58ae2139bf8baf|[[:Category:Samuel Bak|Samuel Bak]] - Under the Trees <ref>Under the Trees, Oil on Canvas, 160 x 200 cm,  [http://chgs.elevator.umn.edu/asset/viewAsset/57f3b7047d58ae0c54bf8bab#57f3b7277d58ae2139bf8baf Return to Vilna Series], [http://www.chgs.umn.edu/ Center for Holocaust & Genocide Studies], [[University of Minnesota]]</ref> ]]  
  
 
'''Pruning''', (as opposed to [[Reductions|reductions]]) <br/>
 
'''Pruning''', (as opposed to [[Reductions|reductions]]) <br/>
Line 114: Line 114:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=38407 Bad Pruning] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Onno]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=38407 Bad Pruning] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Onno]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=40100 Reducing/Pruning Bad Captures (SEE < 0)] by [[Edsel Apostol]], [[CCC]], August 19, 2011 » [[Static Exchange Evaluation|SEE]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=40100 Reducing/Pruning Bad Captures (SEE < 0)] by [[Edsel Apostol]], [[CCC]], August 19, 2011 » [[Static Exchange Evaluation|SEE]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=40456 Over-aggressive pruning] by FlavusSnow, [[CCC]], September 18, 2011
 
* [http://www.open-chess.org/viewtopic.php?f=5&t=2173 Relationship between move ordering and pruning] by [[Don Dailey]], [[Computer Chess Forums|OpenChess Forum]], December 17, 2012 » [[Move Ordering]]
 
* [http://www.open-chess.org/viewtopic.php?f=5&t=2173 Relationship between move ordering and pruning] by [[Don Dailey]], [[Computer Chess Forums|OpenChess Forum]], December 17, 2012 » [[Move Ordering]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=46503 Adjustable search pruning depending on time control] by [[Jerry Donald]], [[CCC]], December 20, 2012 » [[Time Management]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=46503 Adjustable search pruning depending on time control] by [[Jerry Donald]], [[CCC]], December 20, 2012 » [[Time Management]]
Line 126: Line 127:
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69510 Pruning at PV nodes?] by [[Mahmoud Uthman]], [[CCC]], January 06, 2019 » [[Node Types#PV|PV-Nodes]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69510 Pruning at PV nodes?] by [[Mahmoud Uthman]], [[CCC]], January 06, 2019 » [[Node Types#PV|PV-Nodes]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70165 delaying tactics: prune or extend?] by [[Harm Geert Muller]], [[CCC]], March 10, 2019 » [[Selectivity]], [[Tactics]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70165 delaying tactics: prune or extend?] by [[Harm Geert Muller]], [[CCC]], March 10, 2019 » [[Selectivity]], [[Tactics]]
 +
==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]]
 +
 +
=External Links=
 +
* [https://en.wikipedia.org/wiki/Decision_tree_pruning Pruning from Wikipedia]
  
 
=References=
 
=References=
 
<references />
 
<references />
 
 
'''[[Selectivity|Up one level]]'''
 
'''[[Selectivity|Up one level]]'''
 
[[Category:Samuel Bak]]
 
[[Category:Samuel Bak]]

Revision as of 23:50, 2 February 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