  This paper has three main contributions to our understanding of fixed-depth
minimax search: (A) A new formulation for Stockman's SSS* algorithm, based on
Alpha-Beta, is presented. It solves all the perceived drawbacks of SSS*,
finally transforming it into a practical algorithm. In effect, we show that
SSS* = alpha-beta + ransposition tables. The crucial step is the realization
that transposition tables contain so-called solution trees, structures that are
used in best-first search algorithms like SSS*. Having created a practical
version, we present performance measurements with tournament game-playing
programs for three different minimax games, yielding results that contradict a
number of publications. (B) Based on the insights gained in our attempts at
understanding SSS*, we present a framework that facilitates the construction of
several best-first fixed- depth game-tree search algorithms, known and new. The
framework is based on depth-first null-window Alpha-Beta search, enhanced with
storage to allow for the refining of previous search results. It focuses
attention on the essential differences between algorithms. (C) We present a new
instance of the framework, MTD(f). It is well-suited for use with iterative
deepening, and performs better than algorithms that are currently used in most
state-of-the-art game-playing programs. We provide experimental evidence to
explain why MTD(f) performs better than the other fixed-depth minimax
algorithms.
