Node
Node, (vertex)
the fundamental unit in graph theory and, applied to computer science, basic unit to structure and link devices of a network as well as data, such as items of a linked list or tree structure. This page is about the node of the search tree in the game of chess, which represents the alternating white and black to move positions and keeps its state dependent on the tree traversal. Inside a depth-first search, nodes are usually counted at top of the recursive search routine, i.e. for the purpose to determine nodes per second. The move is the 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 and its enhancements, by their type as expected in accordance to the minimal tree before searching this node, or as determined after searching the node.
Contents
Node Types
Node Types of the minimal tree - enumerated as classified by Knuth and Moore:
- PV-Node Knuth's Type 1
- Cut-Node Knuth's Type 2, also called fail-high node
- All-Node Knuth's Type 3, also called fail-low node
PV-nodes are often treated differently by the search - see Principal Variation Search or Internal Iterative Deepening for examples.
Topology
- Root Node - depth = D
- Leftmost Node - are always PV-nodes [2]
- Sibling Node
- Interior Node
- Leaf Node
- Terminal Node
Depth
| Name | Heinz | Hyatt | Ambiguity |
|---|---|---|---|
| Horizon Node | 0 | - | * |
| Frontier Node | 1 | 0 | * |
| Pre Frontier Node | 2 | 1 | * |
| Quiescent Node | <= 0 | ||
See also
Forum Posts
1995 ...
- quiescent vs non-quiescent node counting by Robert Hyatt, rgcc, July 01, 1996
- Node counting confusion by Don Dailey, CCC, January 17, 1998
- Bratko-Kopec Test - Node Counts by Peter McKenzie, CCC, June 17, 1998 » Bratko-Kopec Test
- nodes per ply by Leonid, CCC, June 10, 1999
2000 ...
- How to count the nodes? by Benny Antonsson, CCC, February 25, 2002
- ALL node definition by Alvaro Cardoso, CCC, February 21, 2003
- simple node definitions question by Michael Henderson, CCC, September 13, 2004
- To Jeroen and interested minds, re. Tiger node count by Christophe Théron, CCC, August 15, 2008
2010 ...
- Node counting by BB+, OpenChess Forum, January 20, 2011 » Rybka
- How do you count nodes? by Edsel Apostol, CCC, September 04, 2011
- counting nodes vs counting evaluations by Ed Schröder, CCC, July 19, 2015
2020 ...
- Counting nodes correctly by Steven Griffin, CCC, July 07, 2020
External Links
- Node from Wikipedia
- Vertex (graph theory) from Wikipedia
- Node (computer science) from Wikipedia
- Node (networking) from Wikipedia
- Orbital node from Wikipedia
References
- ↑ The Dragon's Head and Tail refer ascending and descending Lunar nodes, Image from Guido Bonatti (1550). 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 Johannes a Lasco Bibliothek (JALB)
- ↑ 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.
- ↑ Re: simple node definitions question post by Robert Hyatt, CCC, September 13, 2004
- ↑ Ernst A. Heinz (1998). Extended Futility Pruning. ICCA Journal, Vol. 21, No. 2, pp. 75-83
