Using Similar Positions to Search Game Trees
Yasuhito Kawano · 1997
We propose a method that uses information on similar positions to solve Tsume-shogi problems (mating problems in Japanese chess). Two notions, priority and simulation, are defined for this method. A given problem is solved step-by-step according to the priority. Simulation often allows us to omit searching on each step. A program made by the author and based on this method solved a celebrated problem requiring over 600 plies (half-moves) to mate. 1. Introduction It would be useful in board games if the experience learned from one position could be applied to other, similar, positions. However, positions that seem to only slightly differ on the board can actually differ greatly in terms of strategy. This paper proposes a method that uses information on similar positions to solve Tsume-shogi problems (mating problems in Japanese chess, the rules of which are explained in Section 2). The method is based on the notions of priority and simulation. Priority means that we look at certain moves of our opponent earlier than others. Intuitively, we say that a position P simulates another position Q if we can mate on Q according to the mating sequence of P . Roughly speaking, our problem-solving strategy has two steps. First, we restrict ourselves to our opponent's moves of high priority. Second, we check whether the position P where the solution has already been obtained simulates a position Q having a lower priority. If P simulates Q , we can dispense with the search for the latter position.