depth first
Best-First and Depth-First Minimax Search in Practice
Most practitioners use a variant of the Alpha-Beta algorithm, a simple depth-first procedure, 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 algorithm 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.rnrnThis 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 tha
Category: white paper from http://citeseer.ist.psu.edu
« previous1 next »
