A Shogi Program Based on Monte-Carlo Tree Search

Article type: Research Article

Authors: Sato, Yoshikuni¹ | Takahashi, Daisuke² | Grimbergen, Reijer³

Affiliations: Tsukuba and Tokyo, Japan

Note: [1] Graduate School of Systems and Information Engineering, University of Tsukuba. Mail: ysato@hpcs.cs.tsukuba.ac.jp

Note: [2] Graduate School of Systems and Information Engineering, University of Tsukuba.

Note: [3] School of Computer Science, Tokyo University of Technology

Abstract: Recently, Monte-Carlo Tree Search (MCTS) has been attracting a great deal of attention in game-programming research. This method has been quite successful in computer Go, but so far results in other games have not been so impressive. In this paper, we present an implementation of MCTS in shogi which combines techniques used in computer Go with a number of shogi-specific enhancements. We tested this implementation on a standard test set of tactical positions. The number of correct answers indicates that the strength of the Monte-Carlo based shogi program is about that of a 1-dan amateur. The results did not carry over to actual playing strength as the match results against a conventional shogi program with a strength of about a 1-dan player showed. Therefore, it seems unlikely that a pure MCTS-based shogi program will surpass the level of the best conventional shogi programs. However, we also observed that our MCTS program could solve certain opening and endgame positions that are considered hard to solve with the current methods. Therefore, we believe that MCTS can be a useful method to improve the overall performance of a shogi program.

DOI: 10.3233/ICG-2010-33203

Journal: ICGA Journal, vol. 33, no. 2, pp. 80-92, 2010