Home * Search * 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.
The Dragon's Head and Tail [1]

Node Types

Node Types of the minimal tree - enumerated as classified by Knuth and Moore:

1. PV-Node Knuth's Type 1
2. Cut-Node Knuth's Type 2, also called fail-high node
3. 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 (* see note below
• Sibling Node
• Interior Node
• Leaf Node
• Terminal Node

*) 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.

Zero	based depth by	Heinz		vs.	Hyatt	ambiguity
	Horizon Node	0		-		(* ambiguity
	Frontier Node	1		0		(* ambiguity
	Pre Frontier Node	2		1		(* ambiguity
	Quiescent Node	<= 0

*) There seems an ambiguity according to the definition of frontier versus horizon nodes. ^{[2] [3]} .

See also

• Chess Position
• Nodes per second
• Principal variation
• Score

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

2005 ...

• 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

2015 ...

• counting nodes vs counting evaluations by Ed Schröder, CCC, July 19, 2015

External Links

• Node from Wikipedia
• Vertex (graph theory) from Wikipedia
• Node (computer science) from Wikipedia
• Node (networking) from Wikipedia
• Orbital node from Wikipedia

References

1. ^ 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)
2. ^ Re: simple node definitions question post by Robert Hyatt, CCC, September 13, 2004
3. ^ Ernst A. Heinz (1998). Extended Futility Pruning. ICCA Journal, Vol. 21, No. 2, pp. 75-83

What links here?

Up one Level