Threat Stacks to Guide Pruning and Search Extensions in Shogi

Grimbergen, R. (2002)

in: Workshop Notes of the International Workshop on Entertainment Computing (IWEC2002), pp.61--68, Makuhari, Japan.

Abstract

In most cases, game programs have to decide their next move under strict time constraints. Iterative deepening is the most common method to make sure a move is played that is the result of a completed search to a certain depth. To produce a reasonable move at each iteration a combination of pruning techniques and search extensions is used. Often, the decisions for pruning and extending the search are based on game-specific knowledge. In this paper we propose to store the game-specific knowledge into threat stacks and use general rules regarding the content of these threat stacks for pruning and extension decisions. Preliminary results in shogi show that if threat stacks are used instead of a standard quiescence search, an improvement of the tactical performance can be expected.