ベイジアンアプローチに基づくモンテカルロ木探索アルゴリズムの将棋への適用と評価

• 横山, 大作

• 喜連川, 優

書誌事項

タイトル別名

• An Application and Evaluation of Monte-Carlo Tree Search Algorithm for Shogi Player Based on Bayesian Approach

抄録

我々は，Bayesian Approachに基づいた新しいモンテカルロ木探索アルゴリズム（MCTS）を提案し，将棋に対して適用を試みた．提案手法は，(1)乱数を付加した評価関数によるゲーム木探索をシミュレーション試行として用いること，(2)評価値を確率分布として扱い，Bayesian Approachに基づいてゲーム木中を伝搬させること，という2点から構成される．これは，将棋に代表される，従来のMCTSが有効に利用できないtacticalなゲームへの適用を想定した手法である．問題領域特有の探索技法を多数利用しているトップレベルのコンピュータプレイヤを用いて実装を行い，大量の自己対戦による性能評価を行った結果，十分なリソースを利用可能であれば，提案手法によって従来のゲーム木探索を越える性能を実現できることが示された．また，提案手法の詳細な性能特性評価を通して，提案手法の設計指針に関する理解が得られた．

We propose a new Monte-Carlo Tree Search (MCTS) algorithm based on Bayesian Approach to improve performance of game-tree search. It consists of two main concepts; (1) using multiple game-tree search with a randomized evaluation function as simulations, (2) treating evaluated values as probability distribution and propagating it through the game-tree using the Bayesian Approach concept. Proposed method is focusing on applying to tactical games such as Shogi, in which MCTS is not currently effective. We apply the method for shogi using a top-level computer player application which is constructed with many domain-specific search techniques. Through large amount of self-play evaluations, we conclude our method can achieve good win ratio against an ordinary game-tree search based player when enough computing resource is available. We also precisely examine performance behaviors of the method, and depict designing directions.

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 55 (11), 2389-2398, 2014-11-15

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

キーワード

• [特集：ゲームプログラミング] ゲーム木探索アルゴリズム，モンテカルロ木探索，将棋，Bayesian Approach

詳細情報

• CRID: 1050564287859067776
• NII論文ID: 110009843045
• NII書誌ID: AN00116647
• ISSN: 18827764
• Web Site: http://id.nii.ac.jp/1001/00106958/
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles
  • KAKEN