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>
PV = 1
CUT = b^<span style="vertical-align: super;">⌈n/2⌉</span> - 1 ALL = b^<span style="vertical-align: super;">⌊n/2⌋</span> - 1
... are already the subexpressions ...
... in [[Michael Levin|Levin's]] famous formula demonstrating the [[Odd-Even Effect|odd-even effect]] of [[Alpha-Beta|alpha-beta]]
L = b^<span style="vertical-align: super;">⌈n/2⌉</span> + b^<span style="vertical-align: super;">⌊n/2⌋</span> - 1
<span id="Table"></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>:
In [[Cray Blitz|CB]], I used this extensively, because you never want to split at a CUT node, and want to prefer an ALL node. [[Young Brothers Wait Concept|YBW]] tries to recognize an ALL node by requiring that at least one move be searched before splitting, since > 90% of CUT nodes are discovered on the first move searched. But waiting on that first move introduces some wait time, and if you knew it was an ALL node from the get-go, you could split before the first move is completed. That was the basic premise behind the iterated search and [[Dynamic Tree Splitting|DTS algorithm]] in Cray Blitz ...
* [[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]]
