Search Tree

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Tree

Piet Mondrian - Gray Tree, 1912 [1]

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

Deep-prune.gif

An Alpha-Beta Search 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. 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

Publications

Forum Posts

External Links

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

References

  1. ↑ Gray Tree from Wikipedia
  2. ↑ Lecture notes for April 22, 1997 Alpha-Beta Search by David Eppstein
  3. ↑ see Swap-off by Helmut Richter
  4. ↑ Georgy Adelson-Velsky and Evgenii Landis (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

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=Search_Tree&oldid=24168"