Search

Technical report TR98-07. The thinking-process used by computers for chess and other two-person games differs significantly from the one used by humans. While humans consider at most a few alternatives when deciding what to play, computers exhaustively search all the possible moves. In the half century since minimax was first suggested as a strategy for adversary game search, various search algorithms have been developed. The standard approach has been to use improvements to the Alpha-Beta algorithm to explore all continuations to some fixed depth (continuation length or search horizon). In practice, however, the algorithms are not used that way, instead heuristics vary the search horizon, exploring some continuations more deeply than others. In an indirect way, this resembles the human thinking process. Continuations that are thought to be of special interest are expanded beyond the nominal depth, while others may be terminated prematurely. The latter case is referred to as forward pruning. In this paper we discuss some important aspects of forward-pruning, especially regarding risk-management, and propose ways of improving risk-assessment. Finally, we introduce two new pruning methods based on some of the principles discussed here, and present experimental results applying the methods in an established chess program. | TRID-ID TR98-07