Download the full-sized PDF of Nearly Optimal Minimax Tree Search?Download the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Computing Science, Department of


This file is in the following collections:

Technical Reports (Computing Science)

Nearly Optimal Minimax Tree Search? Open Access


Author or creator
Plaat, Aske
Schaeffer, Jonathan
Pijls, Wim
de Bruin, Arie
Additional contributors
minimax tree search
Type of item
Computing Science Technical Report
Computing science technical report ID
Technical report TR94-19. 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 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 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.
Date created
License information
Creative Commons Attribution 3.0 Unported

Citation for previous publication

Link to related item

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 222844
Last modified: 2015:10:12 21:20:43-06:00
Filename: TR94-19.pdf
Original checksum: 6d42930de99f072890599daaff02dff0
Well formed: true
Valid: true
Page count: 21
Activity of users you follow
User Activity Date