行動評価関数を用いたモンテカルロ木探索の重点化と見落としの抑制

• Item type: Journal(1)
• 公開日: 2014-11-15
• タイトル: 行動評価関数を用いたモンテカルロ木探索の重点化と見落としの抑制
• タイトル / 言語: en
• タイトル: Knowledge Bias in Monte-Carlo Tree Search and Techniques for Reducing Oversight Mistakes
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：ゲームプログラミング] モンテカルロ木探索，行動評価関数，バイアス，Progressive Widening，見落とし
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 北陸先端科学技術大学院大学
• 著者所属: 北陸先端科学技術大学院大学
• 著者所属(英): en
• 著者所属(英): JAIST
• 著者所属(英): en
• 著者所属(英): JAIST
• 著者名: 池田, 心; ビエノ, シモン
• 著者名(英): Kokolo, Ikeda; Simon, Viennot
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: モンテカルロ木探索は現在囲碁プログラムの主流であり，基本となるアルゴリズムにさまざまに工夫が加えられ用いられている．シミュレーション部分において，行動評価関数などを用いて良い手を高い確率で打つことは，全合法手を等確率で選ぶ場合に比べ効果的であることはよく知られる．この評価関数は木探索部分への利用も可能であり，有望な着手に探索を重点化したり，あるいはそれらのみに探索を着手限定したりといったことも行われる．本論文では，行動評価関数を木探索部分で活用する着手限定と重点化の2つの方法の効果やパラメータの影響，組合せた場合の性能を，囲碁プログラムNomitan，Fuegoを用いた実験により示す．そのうえで，着手限定で生じる“見落とし”を抑制するための3つの方法を提案し，NomitanのFuegoに対する勝率が4,000試合ずつの実験で57.7%から64.5%に向上したことを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Monte-Carlo Tree Search is now the most popular method for the game of Go, and many techniques and variations are used to improve the strength. It is already known that biased Monte-Carlo simulations using a probability model containing static knowledge are more efficient than random simulations. Such probability models can be also used in the tree search policy to bias the search or limit the search to a subset of the legal moves. In this article, first we describe more precisely how static knowledge can be used to improve the tree search policy. Then, we show how to reduce the oversight mistakes caused by the limitation of the number of searched moves. We confirm experimentally the efficiency of the proposed methods, with a large number of games using our Go program Nomitan, against Fuego, an open source program. The winning ratio of our program is increased from 57.7% to 64.5% (4,000 games for each).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 55, 号 11, p. 2377-2388, 発行日 2014-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764