  Search algorithms are often categorized by their node expansion strategy. One
option is the depth-first strategy, a simple backtracking strategy that
traverses the search space in the order in which successor nodes are generated.
An alternative is the best-first strategy, which was designed to make it
possible to use domain-specific heuristic information. By exploring promising
parts of the search space first, best-first algorithms are usually more
efficient than depth-first algorithms.
  In programs that play minimax games such as chess and checkers, the
efficiency of the search is of crucial importance. Given the success of
best-first algorithms in other domains, one would expect them to be used for
minimax games too. However, all high-performance game-playing programs are
based on a depth-first algorithm.
  This study takes a closer look at a depth-first algorithm, AB, and a
best-first algorithm, SSS. The prevailing opinion on these algorithms is that
SSS offers the potential for a more efficient search, but that its complicated
formulation and exponential memory requirements render it impractical. The
theoretical part of this work shows that there is a surprisingly
straightforward link between the two algorithms -- for all practical purposes,
SSS is a special case of AB. Subsequent empirical evidence proves the
prevailing opinion on SSS to be wrong: it is not a complicated algorithm, it
does not need too much memory, and it is also not more efficient than
depth-first search.
