Best-First Fixed-Depth Game-Tree Search in Practice

Abstract

We present a new paradigm for minimax search algorithms: MT, a memory-enhanced version of Pearl's Test procedure. By changing the way MT is called, a number of practical best-first search algorithms can be simply constructed. Reformulating SSS* as an instance of MT eliminates all its perceived implementation drawbacks. Most assessments of minimax search performance are based on simulations that do not address two key ingredients of high performance game-playing programs: iterative deepening and memory usage. Instead, we use experimental data gathered from tournament checkers, Othello and chess programs. The use of iterative deepening and memory makes our results differ significantly from the literature. One new instance of our framework, MTD(f), out-performs our best Alpha-Beta searcher on leaf nodes, total nodes and execution time. To our knowledge, these are the first reported results that compare both depth-first and bestfirst algorithms given the same amount of memory.