Home * Search * Node
Bonatti-caput_et_cauda_draconis.jpg

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


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


Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...

2015 ...


External Links


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