1. Introduction

In recent years, a number of games have been solved using computers, including Qubic [Patashnik 1980], Connect-4 [Allen 1989; Allis 1988] and Go-Moku [Allis et al. 1993]. All these games were solved using knowledge-based methods. These methods are successful because all these games have a low decision complexity [Allis et al. 1991], that is, the right move is often easy to find. Not all games profit to the same extent. For instance, in checkers, chess and go a multitude of moves often seem fairly equal. Brute-force search is often the most viable means of playing or solving this type of game. This observation is supported by the fact that the best programs for both chess [Hsu 1990] and checkers [Schaeffer 1992] rely heavily on search.

Search methods are not only useful for playing games: they are ubiquitous in many aspects of problem solving. Some of these algorithms are among the best understood in computer science. However, not all search algorithms are equally well studied; in particular, exhaustive search in large state spaces is still in its infancy. Partly this is because the hardware has only recently progressed to a point where interesting problems are within reach.