Node

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Node

The Dragon's Head and Tail [1]

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.

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

Depth

Name Heinz Hyatt Ambiguity
Horizon Node 0 - *
Frontier Node 1 0 *
Pre Frontier Node 2 1 *
Quiescent Node <= 0
  • ) There seems an ambiguity according to the definition of frontier versus horizon nodes. [3] [4] .

See also

Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...

2015 ...

External Links

References

Up one Level