A Minimax Algorithm Better than Alpha-Beta? No and Yes
Arie de Bruin, Aske Plaat, Jonathan Schaeffer, Wim Pijls · 1995
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* = a-b + 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. (B) Based on the insights gained in our attempts at understanding SSS*, we present a framework that facilitates the construction of several best-first fixeddepth game-tree search algorithms, known and new. The framework is based on depth-first null-window Alpha-Beta search, enhanced with stora...