25,161
edits
Changes
Node
,Created page with "'''Home * Search * Node''' FILE:Bonatti-caput et cauda draconis.PNG|border|right|thumb|The Dragon's Head and Tail <ref>[https://commons.wikimedia.org/wiki..."
'''[[Main Page|Home]] * [[Search]] * Node'''
[[FILE:Bonatti-caput et cauda draconis.PNG|border|right|thumb|The Dragon's Head and Tail <ref>[https://commons.wikimedia.org/wiki/File:Bonatti-caput_et_cauda_draconis.PNG The Dragon's Head and Tail] refer ascending and descending [https://en.wikipedia.org/wiki/Lunar_node Lunar nodes], Image from [https://en.wikipedia.org/wiki/Guido_Bonatti Guido Bonatti] ('''1550'''). ''[http://hardenberg.jalb.de/display_page.php?elementId=5363 Foroliviensis Mathematici De Astronomia Tractatvs X. : Vniuersum quod iudiciariam rationem Natiuitatum, Aeris, Tempestatum, attinet, comprehendentes. Adiectus est Cl. Ptolemaei liber Fructus, cum commentarijs vtilissimis Georgij Trapezunt]''. pp. 119, from [https://de.wikipedia.org/wiki/Johannes_a_Lasco_Bibliothek Johannes a Lasco Bibliothek] (JALB)</ref> ]]
'''Node''', ([https://en.wikipedia.org/wiki/Vertex_%28graph_theory%29 vertex])<br/>
the fundamental unit in [https://en.wikipedia.org/wiki/Graph_theory graph theory] and, applied to [https://en.wikipedia.org/wiki/Computer_science computer science], basic unit to structure and link devices of a [https://en.wikipedia.org/wiki/Computer_network network] as well as [[Data|data]], such as items of a [[Linked List|linked list]] or [https://en.wikipedia.org/wiki/Tree_%28data_structure%29 tree structure]. This page is about the '''node''' of the [[Search Tree|search tree]] in the game of chess, which represents the alternating white and black to move [[Chess Position|positions]] and keeps its state dependent on the [https://en.wikipedia.org/wiki/Tree_traversal tree traversal]. Inside a [[Depth-First|depth-first]] search, nodes are usually counted at top of the [[Recursion|recursive]] search routine, i.e. for the purpose to determine [[Nodes per second|nodes per second]]. The [[Moves|move]] is the [https://en.wikipedia.org/wiki/Directed_graph directed edge] which connects an ordered pair of nodes or positions.
Nodes are classified by their topological properties inside the search tree, and in context of [[Alpha-Beta|alpha-beta]] and its enhancements, by their [[Node Types|type]] as expected in accordance to the [[Search Tree#MinimalGameTree|minimal tree]] before searching this node, or as determined after searching the node.
=Node Types=
[[Node Types]] of the [[Search Tree#MinimalGameTree|minimal tree]] - enumerated as classified by [[Donald Knuth|Knuth]] and Moore:
# [[Node Types#PV|PV-Node]] Knuth's '''Type 1'''
# [[Node Types#CUT|Cut-Node]] Knuth's '''Type 2''', also called [[Fail-High|fail-high]] node
# [[Node Types#ALL|All-Node]] Knuth's '''Type 3''', also called [[Fail-Low|fail-low]] node
PV-nodes are often treated differently by the search - see [[Principal Variation Search]] or [[Internal Iterative Deepening]] for examples.
=Topology=
* [[Root|Root Node]] - depth = D
* [[Leftmost Node]] - are always PV-nodes <ref>That leftmost nodes are always PV-nodes, does not imply each PV-node is leftmost - since we have to deal with real search trees rather than minimal ones.</ref>
* [[Sibling Node]]
* [[Interior Node]]
* [[Leaf Node]]
* [[Terminal Node]]
=Depth=
{| class="wikitable"
|-
! Name
! Heinz
! Hyatt
! Ambiguity
|-
| [[Horizon Node]]
| style="text-align:right;" | 0
| style="text-align:right;" | -
| style="text-align:center;" | *
|-
| [[Frontier Nodes|Frontier Node]]
| style="text-align:right;" | 1
| style="text-align:right;" | 0
| style="text-align:center;" | *
|-
| [[Pre Frontier Node]]
| style="text-align:right;" | 2
| style="text-align:right;" | 1
| style="text-align:center;" | *
|-
| [[Quiescent Node]]
| style="text-align:center;" colspan="2" | <= 0
|
|}
*) ''There seems an ambiguity according to the definition of frontier versus horizon nodes.'' <ref>[https://www.stmintz.com/ccc/index.php?id=387518 Re: simple node definitions question] post by [[Robert Hyatt]], [[CCC]], September 13, 2004</ref> <ref>[[Ernst A. Heinz]] ('''1998'''). ''[http://people.csail.mit.edu/heinz/dt/node18.html Extended Futility Pruning].'' [[ICGA Journal#21_2|ICCA Journal, Vol. 21, No. 2]], pp. 75-83</ref> .
=See also=
* [[Chess Position]]
* [[Nodes per second]]
* [[Principal variation]]
* [[Score]]
=Forum Posts=
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/926eaf0869b6f176# quiescent vs non-quiescent node counting] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], July 01, 1996
* [https://www.stmintz.com/ccc/index.php?id=14239 Node counting confusion] by [[Don Dailey]], [[CCC]], January 17, 1998
* [https://www.stmintz.com/ccc/index.php?id=20796 Bratko-Kopec Test - Node Counts] by [[Peter McKenzie]], [[CCC]], June 17, 1998 » [[Bratko-Kopec Test]]
* [https://www.stmintz.com/ccc/index.php?id=55179 nodes per ply] by [[Leonid Liberman|Leonid]], [[CCC]], June 10, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=215421 How to count the nodes?] by [[Benny Antonsson]], [[CCC]], February 25, 2002
* [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=387460 simple node definitions question] by Michael Henderson, [[CCC]], September 13, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=23037 To Jeroen and interested minds, re. Tiger node count] by [[Christophe Théron]], [[CCC]], August 15, 2008
==2010 ...==
* [http://www.open-chess.org/viewtopic.php?f=5&t=1004 Node counting] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], January 20, 2011 » [[Rybka]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40269 How do you count nodes?] by [[Edsel Apostol]], [[CCC]], September 04, 2011
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57033 counting nodes vs counting evaluations] by [[Ed Schroder|Ed Schröder]], [[CCC]], July 19, 2015
=External Links=
* [https://en.wikipedia.org/wiki/Node Node from Wikipedia]
* [https://en.wikipedia.org/wiki/Vertex_%28graph_theory%29 Vertex (graph theory) from Wikipedia]
* [https://en.wikipedia.org/wiki/Node_%28computer_science%29 Node (computer science) from Wikipedia]
* [https://en.wikipedia.org/wiki/Node_%28networking%29 Node (networking) from Wikipedia]
* [https://en.wikipedia.org/wiki/Orbital_node Orbital node from Wikipedia]
=References=
<references />
'''[[Search|Up one Level]]'''
[[FILE:Bonatti-caput et cauda draconis.PNG|border|right|thumb|The Dragon's Head and Tail <ref>[https://commons.wikimedia.org/wiki/File:Bonatti-caput_et_cauda_draconis.PNG The Dragon's Head and Tail] refer ascending and descending [https://en.wikipedia.org/wiki/Lunar_node Lunar nodes], Image from [https://en.wikipedia.org/wiki/Guido_Bonatti Guido Bonatti] ('''1550'''). ''[http://hardenberg.jalb.de/display_page.php?elementId=5363 Foroliviensis Mathematici De Astronomia Tractatvs X. : Vniuersum quod iudiciariam rationem Natiuitatum, Aeris, Tempestatum, attinet, comprehendentes. Adiectus est Cl. Ptolemaei liber Fructus, cum commentarijs vtilissimis Georgij Trapezunt]''. pp. 119, from [https://de.wikipedia.org/wiki/Johannes_a_Lasco_Bibliothek Johannes a Lasco Bibliothek] (JALB)</ref> ]]
'''Node''', ([https://en.wikipedia.org/wiki/Vertex_%28graph_theory%29 vertex])<br/>
the fundamental unit in [https://en.wikipedia.org/wiki/Graph_theory graph theory] and, applied to [https://en.wikipedia.org/wiki/Computer_science computer science], basic unit to structure and link devices of a [https://en.wikipedia.org/wiki/Computer_network network] as well as [[Data|data]], such as items of a [[Linked List|linked list]] or [https://en.wikipedia.org/wiki/Tree_%28data_structure%29 tree structure]. This page is about the '''node''' of the [[Search Tree|search tree]] in the game of chess, which represents the alternating white and black to move [[Chess Position|positions]] and keeps its state dependent on the [https://en.wikipedia.org/wiki/Tree_traversal tree traversal]. Inside a [[Depth-First|depth-first]] search, nodes are usually counted at top of the [[Recursion|recursive]] search routine, i.e. for the purpose to determine [[Nodes per second|nodes per second]]. The [[Moves|move]] is the [https://en.wikipedia.org/wiki/Directed_graph directed edge] which connects an ordered pair of nodes or positions.
Nodes are classified by their topological properties inside the search tree, and in context of [[Alpha-Beta|alpha-beta]] and its enhancements, by their [[Node Types|type]] as expected in accordance to the [[Search Tree#MinimalGameTree|minimal tree]] before searching this node, or as determined after searching the node.
=Node Types=
[[Node Types]] of the [[Search Tree#MinimalGameTree|minimal tree]] - enumerated as classified by [[Donald Knuth|Knuth]] and Moore:
# [[Node Types#PV|PV-Node]] Knuth's '''Type 1'''
# [[Node Types#CUT|Cut-Node]] Knuth's '''Type 2''', also called [[Fail-High|fail-high]] node
# [[Node Types#ALL|All-Node]] Knuth's '''Type 3''', also called [[Fail-Low|fail-low]] node
PV-nodes are often treated differently by the search - see [[Principal Variation Search]] or [[Internal Iterative Deepening]] for examples.
=Topology=
* [[Root|Root Node]] - depth = D
* [[Leftmost Node]] - are always PV-nodes <ref>That leftmost nodes are always PV-nodes, does not imply each PV-node is leftmost - since we have to deal with real search trees rather than minimal ones.</ref>
* [[Sibling Node]]
* [[Interior Node]]
* [[Leaf Node]]
* [[Terminal Node]]
=Depth=
{| class="wikitable"
|-
! Name
! Heinz
! Hyatt
! Ambiguity
|-
| [[Horizon Node]]
| style="text-align:right;" | 0
| style="text-align:right;" | -
| style="text-align:center;" | *
|-
| [[Frontier Nodes|Frontier Node]]
| style="text-align:right;" | 1
| style="text-align:right;" | 0
| style="text-align:center;" | *
|-
| [[Pre Frontier Node]]
| style="text-align:right;" | 2
| style="text-align:right;" | 1
| style="text-align:center;" | *
|-
| [[Quiescent Node]]
| style="text-align:center;" colspan="2" | <= 0
|
|}
*) ''There seems an ambiguity according to the definition of frontier versus horizon nodes.'' <ref>[https://www.stmintz.com/ccc/index.php?id=387518 Re: simple node definitions question] post by [[Robert Hyatt]], [[CCC]], September 13, 2004</ref> <ref>[[Ernst A. Heinz]] ('''1998'''). ''[http://people.csail.mit.edu/heinz/dt/node18.html Extended Futility Pruning].'' [[ICGA Journal#21_2|ICCA Journal, Vol. 21, No. 2]], pp. 75-83</ref> .
=See also=
* [[Chess Position]]
* [[Nodes per second]]
* [[Principal variation]]
* [[Score]]
=Forum Posts=
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/926eaf0869b6f176# quiescent vs non-quiescent node counting] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], July 01, 1996
* [https://www.stmintz.com/ccc/index.php?id=14239 Node counting confusion] by [[Don Dailey]], [[CCC]], January 17, 1998
* [https://www.stmintz.com/ccc/index.php?id=20796 Bratko-Kopec Test - Node Counts] by [[Peter McKenzie]], [[CCC]], June 17, 1998 » [[Bratko-Kopec Test]]
* [https://www.stmintz.com/ccc/index.php?id=55179 nodes per ply] by [[Leonid Liberman|Leonid]], [[CCC]], June 10, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=215421 How to count the nodes?] by [[Benny Antonsson]], [[CCC]], February 25, 2002
* [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=387460 simple node definitions question] by Michael Henderson, [[CCC]], September 13, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=23037 To Jeroen and interested minds, re. Tiger node count] by [[Christophe Théron]], [[CCC]], August 15, 2008
==2010 ...==
* [http://www.open-chess.org/viewtopic.php?f=5&t=1004 Node counting] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], January 20, 2011 » [[Rybka]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40269 How do you count nodes?] by [[Edsel Apostol]], [[CCC]], September 04, 2011
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57033 counting nodes vs counting evaluations] by [[Ed Schroder|Ed Schröder]], [[CCC]], July 19, 2015
=External Links=
* [https://en.wikipedia.org/wiki/Node Node from Wikipedia]
* [https://en.wikipedia.org/wiki/Vertex_%28graph_theory%29 Vertex (graph theory) from Wikipedia]
* [https://en.wikipedia.org/wiki/Node_%28computer_science%29 Node (computer science) from Wikipedia]
* [https://en.wikipedia.org/wiki/Node_%28networking%29 Node (networking) from Wikipedia]
* [https://en.wikipedia.org/wiki/Orbital_node Orbital node from Wikipedia]
=References=
<references />
'''[[Search|Up one Level]]'''
