A New Paradigm for Minimax Search
  This paper introduces a new paradigm for minimax game-tree search algo-
rithms. MT is a memory-enhanced version of Pearls Test procedure. By changing
the way MT is called, a number of best-first game-tree search algorithms can be
simply and elegantly constructed (including SSS*). Most of the assessments of
minimax search algorithms have been based on simulations. However, these
simulations generally do not address two of the key ingredients of high
performance game-playing programs: iterative deepening and memory usage. This
paper presents experimental data from three game-playing programs (checkers,
Othello and chess), covering the range from low to high branching factor. The
improved move ordering due to iterative deepening and memory usage results in
significantly different results from those portrayed in the literature. Whereas
some simulations show Alpha-Beta expanding almost 100% more leaf nodes than
other algorithms [12], our results showed variations of less than 20%. One new
instance of our framework (MTD-f) out-performs our best alpha- beta searcher
(aspiration NegaScout) on leaf nodes, total nodes and execution time. To our
knowledge, these are the first reported results that compare both depth-first
and best-first algorithms given the same amount of memory
