Search algorithms are often categorized by their node expansion strategy. One option is the depth-first strategy, a simple backtracking strategy that traverses the search space in the order in which successor nodes are generated. An alternative is the best-first strategy, which was designed to make it possible to use domain-specific heuristic information. By exploring promising parts of the search space first, best-first algorithms generally are more efficient than depth-first algorithms.

In programs that play minimax games such as chess and checkers, the efficiency of the search is of crucial importance. Given the success of best-first algorithms in other domains, one would expect them to be used for minimax games too. However, all high-performance game-playing programs are based on a depth-first algorithm.

This study takes a closer look at a depth-first
algorithm, Alpha-Beta, and a best-first algorithm, SSS*.
The prevailing opinion on these algorithms is that SSS* offers the
potential for a more efficient search, but that its complicated
formulation and exponential memory requirements render it impractical.
The theoretical part of this work shows that there is a
surprisingly straightforward link between the two algorithms - for all
practical purposes, SSS* is a special case of Alpha-Beta.
Subsequent empirical evidence proves the prevailing opinion on SSS*
to be wrong: it is not a complicated algorithm, it does not need too
much memory, and it is also *not* more efficient than
depth-first search.

Over the years, research on Alpha-Beta has yielded many enhancements, such
as transposition tables and minimal windows with re-searches, that are
responsible for the success of depth-first minimax search.
The enhancements have made it possible to use a depth-first procedure
to expand nodes in a best-first sequence.
Based on these insights, a new algorithm is presented, MTD(*f*),
which out-performs both SSS* and NegaScout, the Alpha-Beta variant of
choice by practitioners.

In addition to best-first search, other ways for improvement of minimax search algorithms are investigated. The tree searched in Alpha-Beta's best case is usually considered to be equal to the minimal tree that has to be searched by any algorithm in order to find and prove the minimax value. We show that in practice this assumption is not valid. For non-uniform trees, the real minimal tree - or rather, graph - that proves the minimax value is shown to be significantly smaller than Alpha-Beta's best case. Thus, there is more room for improvement of full-width minimax search than is generally assumed.

The full thesis (approx. 180 pages) is available as a compressed
postscript file of about 750kb.

A list of errata
is available. If
you find an error, please let me know at plaat@theory.lcs.mit.edu.

If you prefer zip instead of gzip, then click here for thesis.zip. Please send me a note (plaat@theory.lcs.mit.edu) for any other format.

If the net is giving you a hard time, you could try downloading the thesis piece by piece:

- full thesis in one file (750kb)
- part1 (26 kb)
- part2 (78 kb)
- part3 (95 kb)
- part4 (55 kb)
- part5 (59 kb)
- part6 (475 kb)
- part7 (48 kb)