深さに応じたバイアスによるモンテカルロ木探索の効率化

スポンサーリンク

概要

論文の詳細を見る
ゲームにおける着手選択の方法として,モンテカルロシミュレーションに基づいた手法が注目されている.このシミュレーションの制御には UCT アルゴリズムが効果的であることが知られているが,これは k-armed バンデット問題に対する UCB1 アルゴリズムをゲーム木の各節点に適用したアルゴリズムである.しかし,木構造に対する探索アルゴリズムの特徴として,深い子節点に対して十分効果的な探索を行うには膨大な計算量が必要となってしまう.本研究では,UCT アルゴリズムにおける子節点の展開をその節点の深さに応じて経験的な評価関数を用いて制限することにより,実行の効率化を図った.その結果,従来の UCT アルゴリズムに対して同じ計算時間でより深い節点まで探索を行えることを確認し,着手の強さに向上がみられることが確認された.
2011-05-10

著者

関連論文

もっと見る

スポンサーリンク