25,161
edits
Changes
no edit summary
[[FILE:Img2725NodeTypes.gif|border|right|thumb|440px|link=http://www.netlib.org/utk/lsi/pcwLSI/text/node351.html|Node Types <ref>[http://www.netlib.org/utk/lsi/pcwLSI/text/node351.html Analysis of Alpha-Beta Pruning] from the [http://www.netlib.org/utk/lsi/pcwLSI/text/BOOK.html Parallel Computing Works] ebook</ref> ]]
'''Node Types''' are classifications of [[Node|nodes]] as expected inside a [[Search Tree#MinimalGameTree|minimal alpha-beta tree]], or as determined by the search. These types were first formulated by [[Donald Knuth]] and Ronald Moore when describing the [[Alpha-Beta|alpha-beta algorithm]] <ref>[[Donald Knuth|Donald E. Knuth]] and , [http://www.informatik.uni-trier.de/~ley/pers/hd/m/Moore:Ronald_W= Ronald W. Moore ] ('''1975'''). ''[http://www.scribd.com/doc/28194932/An-Analysis-of-Alpha-Beta-Pruning An analysis of alpha-beta pruning].'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6:, No. 4, pp 293–326, 1975. Reprinted in [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/%7Eknuth~uno/aa.html Selected Papers on Analysis of Algorithms] by Donald E''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN. Knuth, Published 2000shtml CSLI lecture notes series] 102, by Addison-Wesley ISBN: 1-5758557586-211212-53</ref> and further analyzed by [[Judea Pearl]] <ref>[[Judea Pearl]] ('''1982'''). ''The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality''. [[ACM#Communications|Communications of the ACM]], Vol. 25, No. 8, pp. 559-564</ref>. While Knuth used the terms Type 1, 2, and 3, [[Tony Marsland]] and [[Fred Popowich]] introduced the more descriptive terms '''PV-''', '''Cut-''' and '''All-nodes''' <ref>[[Mark Winands]], [[Jaap van den Herik]], [[Jos Uiterwijk]], [[Erik van der Werf]] ('''2003'''). ''Enhanced forward pruning.'' [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf]</ref> <ref>[[Tony Marsland]], [[Fred Popowich]] ('''1985'''). ''Parallel Game-Tree Search.'' [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 7, No. 4, pp. 442-452. [http://webdocs.cs.ualberta.ca/~tony/OldPapers/parallel.pdf 1984 pdf] (Draft)</ref>.
Node types as established by the search are stored inside the [[Transposition Table|transposition table]], indicating whether the [[Score|score]] is either [[Exact Score|exact]], [[Lower Bound|lower]] or [[Upper Bound|upper bounded]]. Expected node types, as determined by tree topology, probing the transposition table, or comparing scores of a [[Evaluation|static evaluation]] considering threats, or even a reduced search or [[Quiescence Search|quiescence search]], with the [[Bound|bounds]], may be considered by various ([[Parallel Search|parallel]]) search algorithms and in decisions concerning [[Selectivity|selectivity]].
* [[Root|Root Node]] and the [[Leftmost Node|Leftmost Nodes]] are always PV-nodes
* In [[Principal Variation Search]], PV-nodes are defined by <span style="background-color: rgb(229, 229, 229)">beta-alpha>1</span>
* All [[Sibling nodeNode|Siblings]] of a PV-node are expected Cut-nodes
<span id="CUT"></span>
Assuming a constant [[Branching Factor|branching factor]] of 40, this results in following number of leaves:
{| class="wikitable"|+ number {Number of leaves with depth n and b = 40 |-! depth! worst case! best case! PV ! CUT ! ALL |-! n | style="text-align:center;" | b<span style="vertical-align: super;">n</span>| style="text-align:center;" | b<span style="vertical-align: super;">⌈n/2⌉</span> + b<span style="vertical-align: super;">⌊n/2⌋</span> - 1| style="text-align:right;" | 1 | style="text-align:center;" | b<span style="vertical-align: super;">⌈n/2⌉</span> - 1| style="text-align:center;" | b<span style="vertical-align: super;">⌊n/2⌋</span> - 1|-! 0 | style="text-align:right;" | 1 | style="text-align:right;" | 1 | style="text-align:right;" | 1 | style="text-align:right;" | 0 | style="text-align:right;" | 0 |-! 1 | style="text-align:right;" | 40 | style="text-align:right;" | 40 | style="text-align:right;" | 1 | style="text-align:right;" | 39 | style="text-align:right;" | 0 |-! 2 | style="text-align:right;" | 1,600 | style="text-align:right;" | 79 | style="text-align:right;" | 1 | style="text-align:right;" | 39 | style="text-align:right;" | 39 |-! 3 | style="text-align:right;" | 64,000 | style="text-align:right;" | 1,639 | style="text-align:right;" | 1 | style="text-align:right;" | 1,599 | style="text-align:right;" | 39 |-! 4 | style="text-align:right;" | 2,560,000 | style="text-align:right;" | 3,199 | style="text-align:right;" | 1 | style="text-align:right;" | 1,599 | style="text-align:right;" | 1,599 |-! 5 | style="text-align:right;" | 102,400,000 | style="text-align:right;" | 65,569 | style="text-align:right;" | 1 | style="text-align:right;" | 63,999 | style="text-align:right;" | 1,599 |-! 6 | style="text-align:right;" | 4,096,000,000 | style="text-align:right;" | 127,999 | style="text-align:right;" | 1 | style="text-align:right;" | 63,999 | style="text-align:right;" | 63,999 |-! 7 | style="text-align:right;" | 163,840,000,000 | style="text-align:right;" | 2,623,999 | style="text-align:right;" | 1 | style="text-align:right;" | 2,559,999 | style="text-align:right;" | 63,999 |-! 8 | style="text-align:right;" | 6,553,600,000,000 | style="text-align:right;" | 5,119,999 | style="text-align:right;" | 1 | style="text-align:right;" | 2,559,999 | style="text-align:right;" | 2,559,999 |Leaves}}
=Quotes=
[[Robert Hyatt]] on the distinction between [[Node Types#ALL|ALL-]] and [[Node Types#CUT|CUT-nodes]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=398061&t=38317 Re: "CUT" vs "ALL" nodes] by [[Robert Hyatt]], [[CCC]], March 08, 2011</ref>:
=See also=
* [[Alpha-Beta]]
* [[Stephen F. Wheeler#Alpha-Beta Benchmark|Alpha-Beta Benchmark]] by [[Stephen F. Wheeler]]
* [[Enhanced Forward Pruning]]
* [[Internal Iterative Deepening]]
=Selected Publications=
* [[Donald Knuth|Donald E. Knuth]] and , [http://www.informatik.uni-trier.de/~ley/pers/hd/m/Moore:Ronald_W= Ronald W. Moore ] ('''1975'''). ''[http://www.scribd.com/doc/28194932/An-Analysis-of-Alpha-Beta-Pruning An analysis of alpha-beta pruning].'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6:, No. 4, pp 293–326, 1975. Reprinted in [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/%7Eknuth~uno/aa.html Selected Papers on Analysis of Algorithms] by Donald E''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN. Knuth, Published 2000shtml CSLI lecture notes series] 102, by Addison-Wesley ISBN: 1-5758557586-211212-53
* [[Igor Roizen]] ('''1981'''). ''On the Average Number of Terminal Nodes examined by Alpha-Beta''. Technical Report UCLA-ENG-CSL-8108, [https://en.wikipedia.org/wiki/University_of_California,_Los_Angeles University of California at Los Angeles], Cognitive Systems Laboratory
* [[Judea Pearl]] ('''1982'''). ''The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality''. [[ACM#Communications|Communications of the ACM]], Vol. 25, No. 8, pp. 559-564
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=285939 ALL node definition] by [[Alvaro Cardoso]], [[CCC]], February 21, 2003
* [https://www.stmintz.com/ccc/index.php?id=354012 Fruit - Question for Fabien] by [[Dan Honeycutt]], [[CCC]], March 11, 2004 » [[Fruit]], [[Transposition Table]], [[Principal variationVariation]], [[Principal Variation Search]]
: [https://www.stmintz.com/ccc/index.php?id=354016 Re: Fruit - Question for Fabien] by [[Fabien Letouzey]], [[CCC]], March 11, 2004
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=171&start=143 Re: Attack table] by [[Zach Wegner]], [[Computer Chess Forums|Winboard Forum]], October 22, 2004 » [[Attack and Defend Maps]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59682 Recognizing PV nodes] by [[Martin Fierz]], [[CCC]], March 29, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62890 What is wrong with doing Nulls & ttcuts in a pv node ?] by [[Mahmoud Uthman]], [[CCC]], January 21, 2017 » [[Null Move Pruning]], [[Node Types#PV|PV-Nodes]], [[Transposition Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65477 cut nodes] by [[Folkert van Heusden]], [[CCC]], October 18, 2017 » [[Node Types#CUT|Cut-Nodes]]* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69510 Pruning at PV nodes?] by [[Mahmoud Uthman]], [[CCC]], January 06, 2019 » [[Pruning]], [[#PV|PV-Nodes]]
=External Links=
=References=
<references />
'''[[Node|Up one Level]]'''
[[Category:Hyatt Quotes]]
