Best-first fixed-depth minimax algorithms

AbstractThis article has three main contributions to our understanding of minimax search:First, 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 + transposition 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.Second, 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.Third, a new instance of this framework is presented. It performs better than algorithms that are currently used in most state-of-the-art game-playing programs. We provide experimental evidence to explain why this new algorithm, MTD(f), performs better than other fixed-depth minimax algorithms