A Shogi Program Based on Monte-Carlo Tree Search

Sato, Y., Takahashi, D. and Grimbergen, R. (2010).

ICGA Journal, Vol.33, no.2, pp. 80--92.

Abstract

Recently, Monte-Carlo Tree Search (MCTS) has been attracting a lot of attention in game programming research. This method has been very successful in computer Go, but 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 1-dan amateur. These results did not carry over to actual playing strength as the match results against a conventional shogi program with a strength of about 1-dan 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 current methods. Therefore, we believe that MCTS can be a useful tool to improve the overall performance of a shogi program.