Changes

Jump to: navigation, search

Pruning

441 bytes added, 10:33, 21 August 2020
no edit summary
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * Pruning'''
[[FILE:UnderTrees.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b7047d58ae0c54bf8bab#57f3b7277d58ae2139bf8baf|[[Arts#: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> ]]
'''Pruning''', (as opposed to [[Reductions|reductions]]) <br/>
==Returning Alpha==
or below at expected [[Node Types#ALL|All-Nodes]] or expected [[Node Types#CUT|Cut-Nodes]] which turn out to become All-Nodes:
* after trying '''width[ply]''' moves in [[Claude ShannonType B Strategy|Shannon]] '''Type-B''' ]] programs, return alpha
* [[Sibling Prediction Pruning]] - return alpha, or depending on the implementation, only skip the move
* [[ProbCut]]
=Publications=
==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 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 ...==
* [[John Birmingham]], [[Peter Kent]] ('''1977'''). ''Tree-searching and tree-pruning techniques''. [[Advances in Computer Chess 1]], reprinted in [[Computer Chess Compendium]]
* [[Yi-Fan Ke]], [[Tai-Ming Parng]] ('''1993'''). ''The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning''. [[ICGA Journal#16_2|ICCA Journal, Vol. 16, No. 2]]
* [[Chrilly Donninger]]. ('''1993'''). ''Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs.'' [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]
* [[Stephen J.J. Smith]], [[Dana Nau|Dana S. Nau]] ('''1994'''). ''An Analysis of Forward Pruning''. Proceedings [[AAAI]] 1994, [http://www.aaai.org/Papers/AAAI/1994/AAAI94-213.pdf pdf]
* [[Michael Buro]] ('''1995'''). ''ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.'' [[ICGA Journal#18_2|ICCA Journal, Vol. 18, No. 2]], [http://www.cs.ualberta.ca/~mburo/ps/probcut.pdf pdf]
* [[Ernst A. Heinz]] ('''1998'''). ''[http://people.csail.mit.edu/heinz/dt/node18.html Extended Futility Pruning].'' [[ICGA Journal#21_3|ICCA Journal, Vol. 21, No. 3]]
* [[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.
==2000 ...==
* [[Ernst A. Heinz]] ('''2000'''). ''AEL Pruning.'' [[ICGA Journal#23_1|ICGA Journal, Vol. 23, No. 1]], [http://www.top-5000.nl/ps/AEL%20pruning.pdf pdf]
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2000'''). ''Selective Depth-First Search Methods''. in [[Jaap van den Herik]], [[Hiroyuki Iida]] (eds.) ('''2000'''). ''Games in AI Research''. [[Maastricht University|Universiteit Maastricht]], [http://www.cs.ualberta.ca/%7Etony/RecentPapers/nec97w.pdf pdf preprint]
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search.'' Theoretical Computer Science, Vol. 252, pp. 177-196. [http://www.ru.is/faculty/yngvi/pdf/BjornssonM01a.pdf pdf]
* [[Yew Jin Lim]] ('''2007'''). ''On Forward Pruning in Game-Tree Search''. Ph.D. thesis, [https://en.wikipedia.org/wiki/National_University_of_Singapore National University of Singapore], [http://www.yewjin.com/storage/papers/PhDThesisLimYewJin.pdf pdf]
==2010 ...==
* [[Kunihito Hoki]], [[Masakazu Muramatsu]] ('''2012'''). ''[https://www.semanticscholar.org/paper/Efficiency-of-three-forward-pruning-techniques-in-Hoki-Muramatsu/206099961f401c8693e071c2b739f164ae5ffa6c Efficiency of three Forward-Pruning Techniques in Shogi: Futility Pruning, Null-move Pruning, and Late Move Reduction (LMR)]''. [https://www.journals.elsevier.com/entertainment-computing Entertainment Computing], Vol. 3, No. 3
* [[Kieran Greer]] ('''2012'''). ''[http://www.hindawi.com/journals/aai/2013/357068/ Tree Pruning for New Search Techniques in Computer Games]''. Advances in Artificial Intelligence, Vol. 2013
* [[Kieran Greer]] ('''2013'''). ''Dynamic Move Chains – a Forward Pruning Approach to Tree Search in Computer Chess''. [http://arxiv.org/abs/1403.0778 arXiv:1403.0778]
* [[Naoyuki Sato]], [[Kokolo Ikeda]] ('''2016'''). ''[https://ieeexplore.ieee.org/document/7860427 Three types of forward pruning techniques to apply the alpha beta algorithm to turn-based strategy games]''. [https://dblp.uni-trier.de/db/conf/cig/cig2016.html CIG 2016]
=Forum Posts=
* [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/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.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=60868 EMR & EMP] by [[Michael Sherwin]], [[CCC]], July 19, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=66135 Transposition table based pruning idea] by [[Jerry Donald]], [[CCC]], December 25, 2017 » [[Transposition Table]]
* [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]]
==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=74425 Questions on Razoring and Code Structure for Pruning] by Cheney, [[CCC]], July 09, 2020 » [[Razoring]]
=External Links=
==Pruning Search Trees==* [http://www.top-5000.nl/authors/rebel/chess840.htm#SELECTIVE%20SEARCH Selective Search Techniques in REBEL (introduction)] from [http://www.top-5000.nl/authors/rebel/chess840.htm Programmer Corner] by [[Ed Schroder|Ed Schröder]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=44686 Nullmove vs classic selective search] by [[Ed Schroder|Ed Schröder]], [[CCC]], August 04, 2012</ref> » [[Rebel]]==Pruning Trees==* [https://en.wikipedia.org/wiki/Decision_tree_pruning Pruning Pruning (Plants) from Wikipedia]* [https://en.wikipedia.org/wiki/Fruit_tree_pruning Fruit tree pruning from Wikipedia] » [[Fruit]]* [https://en.wikipedia.org/wiki/Shredding_%28tree-pruning_technique%29 Shredding (tree-pruning technique) from Wikipedia] » [[Shredder]]* [http://www.extension.umn.edu/distribution/horticulture/dg0628.html Pruning Trees and Shrubs]* [http://aces.nmsu.edu/pubs/_h/h-156/welcome.html Tree Pruning Techniques] from [https://en.wikipedia.org/wiki/New_Mexico_State_University New Mexico State University]
=References=
<references />
 
'''[[Selectivity|Up one level]]'''
[[Category:Samuel Bak]]
Retrieved from "https://www.chessprogramming.org/Special:MobileDiff/1273...20850"

Navigation menu