Threat Analysis to Reduce the Effects of the Horizon Problem in Shogi

Grimbergen, R. (2002)

in: The Pan-Yellow-Sea International Workshop on Information Technologies for the Network Era (PYIWIT2002), pp. 180--185, Saga, Japan

Abstract

In two-player perfect information games, a combination of pruning and extension techniques is used to deal with the horizon problem. These techniques must be tuned carefully for each individual game. In this paper we define a general framework from which pruning and extension decisions can be derived. This framework is based on the notion of threats, i.e. the problems that an intelligent game-playing agent has to handle during search. We have used the framework for pruning and extension decisions in shogi (Japanese chess). Results for a partial implementation of this framework indicate that it will improve the playing strength of a shogi program.