In the game of chess, nodes represent the alternating white and black to move chess positions, and directed edges represent the alternating white and black moves.

Opposed to the wooden plants, which are due to their similar structure metaphor of the search tree, where the root is inside the bottom ground, the root of a search tree is most often illustrated from the top down to the leaves at the bottom. Due to our text-flow from top to bottom (after left to right), this might considered as endianness of the search tree illustration.

The root of the search tree is the position we like to evaluate to find the best move. Leaves are either terminal nodes (mate, stalemate) or nodes which has been assigned a heuristic value, where the desired depth from the root is accomplished.

Because of transpositions due to different move sequences, nodes inside the tree may occur from various ancestors - even within a different number of moves.

The search tree may contain various cycles, since both sides may repeat a former position with the minimum of two reversible moves each, or four plies. Cycles are usually eliminated and not searched twice, which results in searching a directed acyclic graph (DAG).

Tree walk

Whether the search tree has to reside in memory the whole search, depends on which algorithm is used to traverse and expand it. So called Depth-First search algorithms, like Alpha-Beta, starts at the root and explores as far as possible along each branch before backtracking, and only has to keep one path from the root to the current position in memory. Best-First approaches build a search-tree by visiting and expanding the most promising nodes first.

Minimal Search Trees

Minimal Search Trees require optimal move ordering in Alpha-Beta or its enhancements. Of course, this goal requires an oracle, since we don't know the best moves in advance - otherwise we wouldn't search at all. Thus rarely the expected Node Types don't behave as expected, but Cut-Nodes don't fail high, because their All-Node child fails high instead. Anyway, due to Iterative Deepening with Transposition Table, Move Ordering is already quite good, so this occurs quite rarely. Often, if the first move on an expected Cut-Node fails to cut, there are still other moves which do the cut.

Minimal Alpha-Beta Tree

A perfectly ordered Tree, All-Nodes (A) need to consider all successors, Cut-Nodes (C) only the one which already refutes the opponent move.

A minimal, perfectly ordered search tree, with Knuth'sNode Types. Only the PV-Nodes (P) are searched with an open alpha-beta window. Cut-Nodes as children or sibling of PV-Nodes require a Scout-search, to prove the nodes are greater or equal to beta. An All-Node as successor of Cut-Nodes has to consider all moves to prove no move will cause a beta-cutoff.

Donald Michie (1966). Game Playing and Game Learning Automata. Advances in Programming and Non-Numerical Computation, Leslie Fox (ed.), pp. 183-200. Oxford, Pergamon. » Includes Appendix: Rules of SOMAC by John Maynard Smith, introduces Expectiminimax tree^{[3]}

Home * Search * TreeSearch Treeas part of the game tree is a dynamical, hierarchical data-structure, a directed graph of nodes, also called vertices or states, connected by directededges, also calledarcs, or state transitions.In the game of chess, nodes represent the alternating white and black to move chess positions, and directed edges represent the alternating white and black moves.

Opposed to the wooden plants, which are due to their similar structure metaphor of the search tree, where the root is inside the bottom ground, the root of a search tree is most often illustrated from the top down to the leaves at the bottom. Due to our text-flow from top to bottom (after left to right), this might considered as endianness of the search tree illustration.

^{[1]}## Table of Contents

## Alpha-Beta Tree

^{[2]}## Topology

The root of the search tree is the position we like to evaluate to find the best move. Leaves are either terminal nodes (mate, stalemate) or nodes which has been assigned a heuristic value, where the desired depth from the root is accomplished.## Transpositions

Because of transpositions due to different move sequences, nodes inside the tree may occur from various ancestors - even within a different number of moves.A common sample from the Sveshnikov Variation in the Sicilian:

1. e4 c5 2. Nf3 d6 3. d4 cxd 4. Nxd4 Nf6 5. Nc3 Nc6 6. Bg5 e5 7. Ndb51. e4 c5 2. Nc3 e6 3. Nf3 Nc6 4. d4 cxd 5. Nxd4 Nf6 6. Ndb5 d6 7. Bf4 e5 8 Bg5## Cycles

The search tree may contain various cycles, since both sides may repeat a former position with the minimum of two reversible moves each, or four plies. Cycles are usually eliminated and not searched twice, which results in searching a directed acyclic graph (DAG).## Tree walk

Whether the search tree has to reside in memory the whole search, depends on which algorithm is used to traverse and expand it. So called Depth-First search algorithms, like Alpha-Beta, starts at the root and explores as far as possible along each branch before backtracking, and only has to keep one path from the root to the current position in memory. Best-First approaches build a search-tree by visiting and expanding the most promising nodes first.## Minimal Search Trees

Minimal Search Trees require optimal move ordering in Alpha-Beta or its enhancements. Of course, this goal requires an oracle, since we don't know the best moves in advance - otherwise we wouldn't search at all. Thus rarely the expected Node Types don't behave as expected, but Cut-Nodes don't fail high, because their All-Node child fails high instead. Anyway, due to Iterative Deepening with Transposition Table, Move Ordering is already quite good, so this occurs quite rarely. Often, if the first move on an expected Cut-Node fails to cut, there are still other moves which do the cut.## Minimal Alpha-Beta Tree

A perfectly ordered Tree, All-Nodes (A) need to consider all successors, Cut-Nodes (C) only the one which already refutes the opponent move.## Minimal PV Tree

A minimal, perfectly ordered search tree, with Knuth's Node Types. Only the PV-Nodes (P) are searched with an open alpha-beta window. Cut-Nodes as children or sibling of PV-Nodes require a Scout-search, to prove the nodes are greater or equal to beta. An All-Node as successor of Cut-Nodes has to consider all moves to prove no move will cause a beta-cutoff.## See also

## Publications

1966).Game Playing and Game Learning Automata.Advances in Programming and Non-Numerical Computation, Leslie Fox (ed.), pp. 183-200. Oxford, Pergamon. » Includes Appendix:Rules of SOMACby John Maynard Smith, introduces Expectiminimax tree^{[3]}1984).Uniqueness in Game Trees. ICCA Journal, Vol. 7, No. 41996).Exploiting Graph Properties of Game Trees.13th National Conference on Artificial Intelligence (AAAI-96), Vol. 1, pp. 234-239, ISBN 978-0-262-51091-2. pdf, ps, see Enhanced Transposition Cutoff1998).Game Tree Algorithms and Solution Trees. CG 19982002).Treemaps for Search-Tree Visualization. pdf2006).Tools for debugging large game trees. 11th Game Programming Workshop, Hakone, Japan » Debugging2007).GTQL: A Query Language for Game Trees. M.Sc. thesis, Reykjavík University, pdf2008).GTQ: A Language and Tool for Game-Tree Analysis. CG 2008, pdf## Forum Posts

## External Links

^{[4]}Once I Dreamt A Tree Upside Down, 37th international jazz festival in Burghausen, 22.03.06 YouTube VideoJan Garbarek, Manu Katché, Rainer Brüninghaus, Eberhard Weber

## References

1962).An algorithm for the organization of information. Proceedings of the USSR Academy of Sciences 146: 263–266. (Russian) English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263, 1962## What links here?

Up one Level