A Shogi Program Based on Monte-Carlo Tree Search

IR IPSJ HANDLE Web Site Open Access

Bibliographic Information

Other Title
  • モンテカルロ木探索によるコンピュータ将棋
  • モンテカルロ モク タンサク ニ ヨル コンピュータ ショウギ

Search this article

Description

本論文では，モンテカルロ木探索によるコンピュータ将棋を実現し，その有効性を検証する．モンテカルロ木探索によるゲームの実現は，ゲームプログラミングの分野において現在最も注目を集めているテーマの1つであるが，将棋では今のところ良い結果を得ることには成功していない．本研究では，コンピュータ囲碁で成功した手法を基に，キラームーブの導入など将棋向けの改良を加えたモンテカルロ木探索によるコンピュータ将棋を実現した．次の一手問題による性能評価では，アマチュア初段程度のプログラムに迫る正答数を得ることに成功し，モンテカルロ木探索が将棋においても有効であることを示した．現在のトップレベルの将棋プログラムはプロに迫るまでとなっており，モンテカルロ木探索のみにより従来の手法を単純に上回る棋力を得ることは難しいと考えられる．しかし，序盤の定跡選択や一部の終盤では従来の手法よりも良い結果を得ることに成功し，モンテカルロ木探索の利用により，現在のコンピュータ将棋の性能をさらに改善できる可能性があることを示した．

Recently, Monte-Carlo Tree Search is attracting much attention in game programming. This method has succeeded in Computer-Go, however it has not yet been able to attain good results in Computer-Shogi. We implemented a Shogi program based on Monte-Carlo Tree Search, using techniques proved in Computer-Go with improvements for Computer-Shogi. In the results of solving problems, the number of correct answers that our program found was almost the same as that of about a 1-dan amateur program. Although the strength of top-level Shogi programs is almost as strong as professional players, our method based on Monte-Carlo Tree Search achieved better performance than existing methods in openings and some positions of the endgame. The results of our experiments showed that Monte-Carlo Tree Search has the possibility of improving the performance of Computer-Shogi.

Journal

  • IPSJ Journal

    IPSJ Journal 50 (11), 2740-2751, 2009-11-15

    一般社団法人情報処理学会

Keywords

Details 詳細情報について

Report a problem

Back to top