Best-First and Depth-First Minimax Search in Practice
  Most practitioners use a variant of the Alpha-Beta algorithm, a simple
depth-first pro- cedure, for searching minimax trees. SSS*, with its best-first
search strategy, reportedly offers the potential for more efficient search.
However, the complex formulation of the al- gorithm and its alleged excessive
memory requirements preclude its use in practice. For two decades, the search
efficiency of "smart" best-first SSS* has cast doubt on the effectiveness of
"dumb" depth-first Alpha-Beta. This paper presents a simple framework for
calling Alpha-Beta that allows us to create a variety of algorithms, including
SSS* and DUAL*. In effect, we formulate a best-first algorithm using
depth-first search. Expressed in this framework SSS* is just a special case of
Alpha-Beta, solving all of the perceived drawbacks of the algorithm. In
practice, Alpha-Beta variants typically evaluate less nodes than SSS*. A new
instance of this framework, MTD(f), out-performs SSS* and NegaScout, the
Alpha-Beta variant of choice by practitioners.
