Nearly Optimal Minimax Tree Search?
  Knuth and Moore presented a theoretical lower bound on the number of leaves
that any fixed-depth minimax tree-search algorithm traversing a uniform tree
must explore, the so-called minimal tree. Since real-life minimax trees are not
uniform, the exact size of this tree is not known for most applications.
Further, most games have transpositions, implying that there exists a minimal
graph which is smaller than the minimal tree. For three games (chess, Othello
and checkers) we compute the size of the minimal tree and the minimal graph.
Empirical evidence shows that in all three games, enhanced Alpha-Beta search is
capable of building a tree that is close in size to that of the minimal graph.
Hence, it appears game-playing programs build nearly optimal search trees.
However, the conventional definition of the minimal graph is wrong. There are
ways in which the size of the minimal graph can be reduced: by maximizing the
number of transpositions in the search, and generating cutoffs using branches
that lead to smaller search trees. The conventional definition of the minimal
graph is just a left-most approximation. Calculating the size of the real
minimal graph is too computationally intensive. However, upper bound
approximations show it to be significantly smaller than the left-most minimal
graph. Hence, it appears that game-playing programs are not searching as
efficiently as is widely believed. Understanding the left-most and real minimal
search graphs leads to some new ideas for enhancing Alpha-Beta search. One of
them, enhanced transposition cutoffs, is shown to significantly reduce search
tree size.
