25,161
edits
Changes
Created page with "'''Home * Search * Node * Node Types''' FILE:Img2725NodeTypes.gif|border|right|thumb|440px|link=http://www.netlib.org/utk/lsi/pcwLSI/text/node351.html..."
'''[[Main Page|Home]] * [[Search]] * [[Node]] * Node Types'''
[[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 Ronald W. Moore ('''1975'''). ''An analysis of alpha-beta pruning.'' Artificial Intelligence, 6:293–326, 1975. Reprinted in [http://www-cs-faculty.stanford.edu/%7Eknuth/aa.html Selected Papers on Analysis of Algorithms] by Donald E. Knuth, Published 2000, by Addison-Wesley ISBN: 1-57585-211-5</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]].
<span id="PV"></span>
=PV-Nodes=
PV-nodes (Knuth's '''Type 1''') are nodes that have a score that ends up being inside the [[Window|window]]. So if the bounds passed are <span style="background-color: rgb(229, 229, 229)">[a,b]</span>, with the score returned <span style="background-color: rgb(229, 229, 229)">s, a<s<b</span>. These nodes have all moves searched, and the value returned is [[Exact Score|exact]] (i.e., not a [[Bound|bound]]), which propagates up to the [[Root|root]] along with a [[Principal Variation|principal variation]].
* [[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 node|Siblings]] of a PV-node are expected Cut-nodes
<span id="CUT"></span>
=Cut-Nodes=
Cut-nodes (Knuth's '''Type 2'''), otherwise known as [[Fail-High|fail-high]] nodes, are nodes in which a [[Beta-Cutoff|beta-cutoff]] was performed. So with [[Bound|bounds]] <span style="background-color: rgb(229, 229, 229)">[a,b], s>=b</span>. A minimum of one move at a Cut-node needs to be searched. The score returned is a [[Lower Bound|lower bound]] (might be greater) on the [[Exact Score|exact score]] of the node
* In [[Principal Variation Search]] Cut-nodes are searched with [[Null Window|null windows]]
* The child of a Cut-node is an All-node
* The parent of a Cut-node is either a PV- or All-node
* The [[Ply|ply]] distance of a Cut-node to its PV-ancestor is odd
<span id="ALL"></span>
=All-Nodes=
All-nodes (Knuth's '''Type 3'''), otherwise known as [[Fail-Low|fail-low]] nodes, are nodes in which no move's score exceeded alpha. With [[Bound|bounds]] <span style="background-color: rgb(229, 229, 229)">[a,b], s<=a</span>. Every move at an All-node is searched, and the score returned is an [[Upper Bound|upper bound]], the [[Exact Score|exact score]] might be less.
* In [[Principal Variation Search]] All-nodes are searched with [[Null Window|null windows]]
* The children of an All-node are Cut-nodes
* The parent of an All-node is a Cut-node
* The [[Ply|ply]] distance of an All-node to its PV-ancestor is even
=Node Types in PVS=
==Onno==
[[Onno]] by [[Onno Garms]] determines expected node types, beside other things, to perform [[Internal Iterative Deepening|IID]] not only at PV-nodes but also at expected Cut-nodes. Onno Garms gave the following rules <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=399511&t=38408 Re: On internal iterative deeping] by [[Onno Garms]], [[CCC]], March 17, 2011</ref>
* The root node is a PV-node
* The first child of a PV-node is a PV-node
* The further children are searched by a [[Scout|scout search]] as CUT-nodes
* [[Principal Variation Search|PVS]] re-search is done as PV-node
* The first node of [[Onno#Search|bad pruning]] is a CUT-node
* The node after a [[Null Move|null move]] is a CUT-node
* The first node of [[Null Move Pruning#ZugzwangVerification|null move verification]] is a CUT-node
* [[Internal Iterative Deepening|Internal iterative deepening]] does not change the node type
* The first child of a CUT-node is an ALL-node
* Further children of a CUT-node are CUT-nodes
* Children of ALL-nodes are CUT-nodes
==Summary==
Following summary was given by [[Pradu Kannan]] similar to Onno's definition as an attempt to predict the node type before searching the node by assuming reasonably good [[Move Ordering|move ordering]] on PV-nodes and Cut-nodes <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=399059&t=38408 Re: On internal iterative deeping] by [[Don Dailey]], [[CCC]], March 15, 2011</ref>:
* The root node is a PV-node
* The first child of a PV-node is a PV-node
* Children of PV-nodes that are searched with a zero-window [[Scout|scout search]] are Cut-nodes
* Children of PV-nodes that have to be re-searched because the scout search failed high, are PV-nodes
* The first child of a Cut-node, and other candidate cutoff moves (nullmove, killers, captures, checks, ...) is an All-node
* A Cut-node becomes an All-node once the first and all candidate cutoff moves are searched
* Children of All-nodes are Cut-nodes
<span id="LeafNodes"></span>
=Number of Leaf Nodes=
==Formulas==
As emphasized by [[Daniel Shawul]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48205 CUT/ALL nodes ratio] by [[Daniel Shawul]], [[CCC]], June 06, 2013</ref>, the formulas for the number of [[Leaf Node|leaf nodes]] of a certain Node type with uniform [[Depth|depth]] '''n''' and [[Branching Factor|branching factor]] '''b''', using [https://en.wikipedia.org/wiki/Floor_and_ceiling_functions floor and ceiling] of n/2 (cut the ceiling, all the floor) ...
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 ...
L = PV + CUT + ALL
... 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>
==Table==
Assuming a constant [[Branching Factor|branching factor]] of 40, this results in following number of leaves:
{| class="wikitable"
|+ 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
|}
=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 ...
=See also=
* [[Alpha-Beta]]
* [[Enhanced Forward Pruning]]
* [[Internal Iterative Deepening]]
* [[Move Ordering]]
* [[Odd-Even Effect]]
* [[Principal Variation Search]]
* [[Young Brothers Wait Concept]]
=Selected Publications=
* [[Donald Knuth|Donald E. Knuth]] and Ronald W. Moore ('''1975'''). ''An analysis of alpha-beta pruning.'' Artificial Intelligence, 6:293–326, 1975. Reprinted in [http://www-cs-faculty.stanford.edu/%7Eknuth/aa.html Selected Papers on Analysis of Algorithms] by Donald E. Knuth, Published 2000, by Addison-Wesley ISBN: 1-57585-211-5
* [[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
* [[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)
* [[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] » [[Enhanced Forward Pruning]]
=Forum Posts=
==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 variation]], [[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]]
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?t=4384 Move ordering at different (Knuth) node types] by [[Tom Likens]], [[Computer Chess Forums|Winboard Forum]], February 21, 2006 » [[Move Ordering]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4710 PV based decisions] by [[Mark Lefler]], [[Computer Chess Forums|Winboard Forum]], April 27, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6392 NMP on ALL nodes] by [[Onno Garms]], [[Computer Chess Forums|Winboard Forum]], April 15, 2007 » [[Null Move Pruning]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6558 Slight enhancement to PVS] by [[Pradu Kannan]], [[Computer Chess Forums|Winboard Forum]], June 10, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=24198 Nodes type clarification] by [[Mathieu Pagé]], [[CCC]], October 05, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=27122 Different handling of ALL / CUT nodes] by [[Gregory Strong]], [[CCC]], March 22, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=38317 CUT" vs "ALL" nodes] by [[Larry Kaufman]], [[CCC]], March 7, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38408 On internal iterative deepening] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Internal Iterative Deepening]], [[Onno]]
* [http://www.talkchess.com/forum/viewtopic.php?t=43041 When does a cut-node became an all-node?] by [[Alcides Schulz]], [[CCC]], March 27, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=48205 CUT/ALL nodes ratio] by [[Daniel Shawul]], [[CCC]], June 06, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48356 LMR at CUT nodes can be arbitrarily bad!] by [[Michel Van den Bergh]], [[CCC]], June 20, 2013 » [[Late Move Reductions]], [[Python]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50907 Pruning in PV nodes] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], January 14, 2014 » [[Reductions]], [[Root]]
* [http://www.talkchess.com/forum/viewtopic.php?t=51422 Node Types and Thoughts On Their Application] by [[Cheney Nattress]], [[CCC]], February 26, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53049 Null move pruning on PV nodes] by [[Eric Oldre]], [[CCC]], July 22, 2014 » [[Null Move Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54761 LMP in PV nodes] by [[Peter Österlund]], [[CCC]], December 27, 2014 » [[Futility Pruning#MoveCountBasedPruning|Move Count Based Pruning]], [[Texel]]
==2015 ...==
* [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]]
=External Links=
* [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
=References=
<references />
'''[[Node|Up one Level]]'''
[[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 Ronald W. Moore ('''1975'''). ''An analysis of alpha-beta pruning.'' Artificial Intelligence, 6:293–326, 1975. Reprinted in [http://www-cs-faculty.stanford.edu/%7Eknuth/aa.html Selected Papers on Analysis of Algorithms] by Donald E. Knuth, Published 2000, by Addison-Wesley ISBN: 1-57585-211-5</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]].
<span id="PV"></span>
=PV-Nodes=
PV-nodes (Knuth's '''Type 1''') are nodes that have a score that ends up being inside the [[Window|window]]. So if the bounds passed are <span style="background-color: rgb(229, 229, 229)">[a,b]</span>, with the score returned <span style="background-color: rgb(229, 229, 229)">s, a<s<b</span>. These nodes have all moves searched, and the value returned is [[Exact Score|exact]] (i.e., not a [[Bound|bound]]), which propagates up to the [[Root|root]] along with a [[Principal Variation|principal variation]].
* [[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 node|Siblings]] of a PV-node are expected Cut-nodes
<span id="CUT"></span>
=Cut-Nodes=
Cut-nodes (Knuth's '''Type 2'''), otherwise known as [[Fail-High|fail-high]] nodes, are nodes in which a [[Beta-Cutoff|beta-cutoff]] was performed. So with [[Bound|bounds]] <span style="background-color: rgb(229, 229, 229)">[a,b], s>=b</span>. A minimum of one move at a Cut-node needs to be searched. The score returned is a [[Lower Bound|lower bound]] (might be greater) on the [[Exact Score|exact score]] of the node
* In [[Principal Variation Search]] Cut-nodes are searched with [[Null Window|null windows]]
* The child of a Cut-node is an All-node
* The parent of a Cut-node is either a PV- or All-node
* The [[Ply|ply]] distance of a Cut-node to its PV-ancestor is odd
<span id="ALL"></span>
=All-Nodes=
All-nodes (Knuth's '''Type 3'''), otherwise known as [[Fail-Low|fail-low]] nodes, are nodes in which no move's score exceeded alpha. With [[Bound|bounds]] <span style="background-color: rgb(229, 229, 229)">[a,b], s<=a</span>. Every move at an All-node is searched, and the score returned is an [[Upper Bound|upper bound]], the [[Exact Score|exact score]] might be less.
* In [[Principal Variation Search]] All-nodes are searched with [[Null Window|null windows]]
* The children of an All-node are Cut-nodes
* The parent of an All-node is a Cut-node
* The [[Ply|ply]] distance of an All-node to its PV-ancestor is even
=Node Types in PVS=
==Onno==
[[Onno]] by [[Onno Garms]] determines expected node types, beside other things, to perform [[Internal Iterative Deepening|IID]] not only at PV-nodes but also at expected Cut-nodes. Onno Garms gave the following rules <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=399511&t=38408 Re: On internal iterative deeping] by [[Onno Garms]], [[CCC]], March 17, 2011</ref>
* The root node is a PV-node
* The first child of a PV-node is a PV-node
* The further children are searched by a [[Scout|scout search]] as CUT-nodes
* [[Principal Variation Search|PVS]] re-search is done as PV-node
* The first node of [[Onno#Search|bad pruning]] is a CUT-node
* The node after a [[Null Move|null move]] is a CUT-node
* The first node of [[Null Move Pruning#ZugzwangVerification|null move verification]] is a CUT-node
* [[Internal Iterative Deepening|Internal iterative deepening]] does not change the node type
* The first child of a CUT-node is an ALL-node
* Further children of a CUT-node are CUT-nodes
* Children of ALL-nodes are CUT-nodes
==Summary==
Following summary was given by [[Pradu Kannan]] similar to Onno's definition as an attempt to predict the node type before searching the node by assuming reasonably good [[Move Ordering|move ordering]] on PV-nodes and Cut-nodes <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=399059&t=38408 Re: On internal iterative deeping] by [[Don Dailey]], [[CCC]], March 15, 2011</ref>:
* The root node is a PV-node
* The first child of a PV-node is a PV-node
* Children of PV-nodes that are searched with a zero-window [[Scout|scout search]] are Cut-nodes
* Children of PV-nodes that have to be re-searched because the scout search failed high, are PV-nodes
* The first child of a Cut-node, and other candidate cutoff moves (nullmove, killers, captures, checks, ...) is an All-node
* A Cut-node becomes an All-node once the first and all candidate cutoff moves are searched
* Children of All-nodes are Cut-nodes
<span id="LeafNodes"></span>
=Number of Leaf Nodes=
==Formulas==
As emphasized by [[Daniel Shawul]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48205 CUT/ALL nodes ratio] by [[Daniel Shawul]], [[CCC]], June 06, 2013</ref>, the formulas for the number of [[Leaf Node|leaf nodes]] of a certain Node type with uniform [[Depth|depth]] '''n''' and [[Branching Factor|branching factor]] '''b''', using [https://en.wikipedia.org/wiki/Floor_and_ceiling_functions floor and ceiling] of n/2 (cut the ceiling, all the floor) ...
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 ...
L = PV + CUT + ALL
... 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>
==Table==
Assuming a constant [[Branching Factor|branching factor]] of 40, this results in following number of leaves:
{| class="wikitable"
|+ 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
|}
=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 ...
=See also=
* [[Alpha-Beta]]
* [[Enhanced Forward Pruning]]
* [[Internal Iterative Deepening]]
* [[Move Ordering]]
* [[Odd-Even Effect]]
* [[Principal Variation Search]]
* [[Young Brothers Wait Concept]]
=Selected Publications=
* [[Donald Knuth|Donald E. Knuth]] and Ronald W. Moore ('''1975'''). ''An analysis of alpha-beta pruning.'' Artificial Intelligence, 6:293–326, 1975. Reprinted in [http://www-cs-faculty.stanford.edu/%7Eknuth/aa.html Selected Papers on Analysis of Algorithms] by Donald E. Knuth, Published 2000, by Addison-Wesley ISBN: 1-57585-211-5
* [[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
* [[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)
* [[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] » [[Enhanced Forward Pruning]]
=Forum Posts=
==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 variation]], [[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]]
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?t=4384 Move ordering at different (Knuth) node types] by [[Tom Likens]], [[Computer Chess Forums|Winboard Forum]], February 21, 2006 » [[Move Ordering]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4710 PV based decisions] by [[Mark Lefler]], [[Computer Chess Forums|Winboard Forum]], April 27, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6392 NMP on ALL nodes] by [[Onno Garms]], [[Computer Chess Forums|Winboard Forum]], April 15, 2007 » [[Null Move Pruning]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6558 Slight enhancement to PVS] by [[Pradu Kannan]], [[Computer Chess Forums|Winboard Forum]], June 10, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=24198 Nodes type clarification] by [[Mathieu Pagé]], [[CCC]], October 05, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=27122 Different handling of ALL / CUT nodes] by [[Gregory Strong]], [[CCC]], March 22, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=38317 CUT" vs "ALL" nodes] by [[Larry Kaufman]], [[CCC]], March 7, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38408 On internal iterative deepening] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Internal Iterative Deepening]], [[Onno]]
* [http://www.talkchess.com/forum/viewtopic.php?t=43041 When does a cut-node became an all-node?] by [[Alcides Schulz]], [[CCC]], March 27, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=48205 CUT/ALL nodes ratio] by [[Daniel Shawul]], [[CCC]], June 06, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48356 LMR at CUT nodes can be arbitrarily bad!] by [[Michel Van den Bergh]], [[CCC]], June 20, 2013 » [[Late Move Reductions]], [[Python]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50907 Pruning in PV nodes] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], January 14, 2014 » [[Reductions]], [[Root]]
* [http://www.talkchess.com/forum/viewtopic.php?t=51422 Node Types and Thoughts On Their Application] by [[Cheney Nattress]], [[CCC]], February 26, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53049 Null move pruning on PV nodes] by [[Eric Oldre]], [[CCC]], July 22, 2014 » [[Null Move Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54761 LMP in PV nodes] by [[Peter Österlund]], [[CCC]], December 27, 2014 » [[Futility Pruning#MoveCountBasedPruning|Move Count Based Pruning]], [[Texel]]
==2015 ...==
* [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]]
=External Links=
* [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
=References=
<references />
'''[[Node|Up one Level]]'''
