Search Tree

Home * Search * Tree

Piet Mondrian - Gray Tree, 1912

The Search Tree as part of the game tree is a dynamical, hierarchical data-structure, a directed graph of nodes, also called vertices or states, connected by directed edges, also called arcs, 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.

Alpha-Beta Tree

An Alpha-Beta Search Tree

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.

• Root Node
• Leftmost Node
• Sibling Node
• Interior Node
• Leaf Node
• Terminal Node
• Branching Factor

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. Ndb5
1. 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.

                (A)
               / | \
             /   |   \
           /     |     \
         /       |       \
       /         |         \
     [A]        [C]        [C]
    / | \        |          |
   /  |  \       |          |
 (A) (C) (C)    (A)        (A)
 /|\  |   |     /|\        /|\
[ACC][A] [A]   [CCC]      [CCC]

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.

                (P)
               / | \
             /   |   \
           /     |     \
         /       |       \
       /         |         \
     [P]        [C]        [C]
    / | \        |          |
   /  |  \       |          |
 (P) (C) (C)    (A)        (A)
 /|\  |   |     /|\        /|\
[PCC][A] [A]   [CCC]      [CCC]

See also

• Conspiracy Numbers
• Graph History Interaction
• NegaScout or Principal Variation Search
• Path-Dependency
• Repetitions
• Scout
• Search Space
• Transposition

Publications

• 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
• Chun-Hung Tzeng, Paul W. Purdom (1983). A Theory of Game Trees. AAAI-83
• Andrew N. Walker (1984). Uniqueness in Game Trees. ICCA Journal, Vol. 7, No. 4
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1996). Exploiting Graph Properties of Game Trees. AAAI-96 » Enhanced Transposition Cutoff
• Wim Pijls, Arie de Bruin (1998). Game Tree Algorithms and Solution Trees. CG 1998
• Rémi Coulom (2002). Treemaps for Search-Tree Visualization. 7th Computer Olympiad Workshop, pdf
• Yngvi Björnsson, Jónheiður Ísleifsdóttir (2006). Tools for debugging large game trees. 11th Game Programming Workshop, Hakone, Japan » Debugging
• Jónheiður Ísleifsdóttir (2007). GTQL: A Query Language for Game Trees. M.Sc. thesis, Reykjavík University
• Jónheiður Ísleifsdóttir, Yngvi Björnsson. (2008). GTQ: A Language and Tool for Game-Tree Analysis. CG 2008, pdf

Forum Posts

• Measuring closeness to a minimal tree by Ian Kennedy, CCC, April 06, 2003
• how to print tree non-recursively by Daniel Shawul, CCC, February 24, 2012 » Recursion, Iteration
• Probabilistic approach to optimize search tree by Sergei S. Markoff, CCC, September 22, 2012

External Links

• Tree (graph theory) from Wikipedia
• Tree (set theory) from Wikipedia
• Tree (data structure) from Wikipedia
• Tree decomposition from Wikipedia
• Tree traversal from Wikipedia
• AVL tree from Wikipedia named after its inventors Georgy Adelson-Velsky, Evgenii Landis
• Expectiminimax tree from Wikipedia
• Dancing tree from Wikipedia
• Decision tree from Wikipedia
• Red-black tree from Wikipedia
• Jan Garbarek Group - Once I Dreamt A Tree Upside Down, 37th international jazz festival in Burghausen, 22.03.06 YouTube Video

Jan Garbarek, Manu Katché, Rainer Brüninghaus, Eberhard Weber

References

Up one Level