GAME-TREE SEARCH ALGORITHM BASED ON REALIZATION PROBABILITY

Article type: Research Article

Authors: Tsuruoka, Yoshimasa^{; 1} | Yokoyama, Daisaku^{; 2} | Chikayama, Takashi^{; 3}

Affiliations: Tokyo, Japan

Note: [1] Japan Science and Technology Corporation. Email: [email protected]

Note: [2] Department of Frontier Informatics, School of Frontier Sciences, The University of Tokyo. Email: [email protected]

Note: [3] Department of Frontier Informatics, School of Frontier Sciences, The University of Tokyo. Email: [email protected]

Abstract: In games like chess, the node-expansion strategy significantly affects the performance of a game-playing program. In this article we propose a new game-tree search algorithm that uses the realization probabilities of nodes for deciding upon the range of the search. The realization probability of a node represents the probability that the moves leading to the node will actually be played. Our algorithm expands nodes as long as the realization probability of a node is greater than the thresh-old. Therefore, it spends little computational resource on unrealistic moves, resulting in a more effective search. We have implemented this algorithm in a Shogi-playing program. Experimental results show that the proposed algorithm achieves state-of-the-art performance on a standard test suite for computer Shogi. Moreover, its performance gain is equivalent to a speed-up of more than two.

DOI: 10.3233/ICG-2002-25304

Journal: ICGA Journal, vol. 25, no. 3, pp. 145-152, 2002