| This thesis continues an ongoing study of algorithms for selective depth-first expansion of game trees (for two-person zero-sum perfect-information board games). The question we are primarily concerned with is: how should game-playing programs spend their search effort to maximize the quality of their move decisions?; This is a challenging problem. Early attempts at selective expansion of game trees were not particularly successful, and were replaced by brute-force full-width searches once technological advances in both hardware and software made such approaches feasible. However, such brute-force methods are not sufficient on their own to produce world-class game-playing programs. Therefore, many new algorithms have been proposed for exploring game trees more selectively. On the one hand, there are algorithms that traverse the game trees in a best-first fashion but, unfortunately, these algorithms are neither time nor space efficient and have thus not found a wide use in practice. On the other hand, selective depth-first based search algorithms show more promise.; This work introduces several algorithmic enhancements to state-of-the-art depth-first game-tree search. First of all, we show how speculative pruning can, if applied in a controlled manner, improve the search efficiency of existing game-tree search algorithms—without compromising the returned minimax value. Secondly, a novel domain-independent method for speculative pruning of game trees is presented, and its promise demonstrated in two different search domains. The method has been adapted by some of the world's leading chess-playing programs with good success. Finally, we introduce a method for automatically learning search-control parameters in two-person games, either from online play or by offline analyzes of game positions. |
