 21 views
 31 downloads
Nearly Optimal Minimax Tree Search?

 Author(s) / Creator(s)

Technical report TR9419. Knuth and Moore presented a theoretical lower bound on the number of leaves that any fixeddepth minimax treesearch algorithm traversing a uniform tree must explore, the socalled minimal tree Since reallife minimax trees aren't uniform, the exact size of this tree isn't known for most applications. Further, most games have transpositions, implying that there exists a minimal graphwhich 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 AlphaBeta search is capable of building a tree that is close in size to that of the minimal graph. Hence, it appears gameplaying 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 leftmost 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 leftmost minimal graph. Hence, it appears that gameplaying programs are not searching as efficiently as is widely believed. Understanding the leftmost and real minimal search graphs leads to some new ideas for enhancing AlphaBeta search. One of them, enhanced transposition cutoffs, is shown to significantly reduce search tree size.  TRIDID TR9419

 Date created
 1994

 Subjects / Keywords

 Type of Item
 Report

 License
 Attribution 3.0 International