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

In complex games with a high branching factor, global alphabeta search is computationally infeasible. One way to overcome this problem is by using selective goal-directed search algorithms. These goal-directed searches can use relevancy zones to determine which part of the board influences the goal. In this paper, we propose a general method that uses these relevancy zones for searching for compound goals. A compound goal is constructed from less complex atomic goals, using the standard connectives. In contrast to other approaches that treat goals separately in the search phase, compound goal search obtains exact results. ispartof: pages:113-128 ispartof: Lecture Notes in Computer Science vol:3846 pages:113-128 ispartof: 4th International Conference on Computers and Games location:Ramat-Gan, Israel date:5 Jul - 7 Jul 2004 status: published