著者

今川 孝久 金子 知適

雑誌

ゲームプログラミングワークショップ2014論文集

巻号頁・発行日

vol.2014, pp.145-150, 2014-10-31

---

UCT は囲碁やGeneral Game Playing などの応用で効果を発揮している探索手法で,多腕バンディット問題のアルゴリズムであるUCB1 をモンテカルロ木探索(MCTS) に応用したものである.多腕バンディット問題には,KL-UCB, Thompson Sampling, UCB1-Tuned などUCB1 より優れるとされる様々なアルゴリズムが提案されてきている. そこで本研究では、UCB1 に変えてそれらのアルゴリズムをMCTS に用いることを提案し,実際の性能についてP-game と呼ばれる仮想的なゲーム木を用いて分析した. 実験の結果,UCB1 よりもKL-UCB, Thompson Sampling, UCB1-Tuned がMCTS においても優れることが,期待通りに確認された.ただし,各アルゴリズムの差よりも各仮想的なゲーム木の性質に因る性能の違いの方が大きいことも同時に確認されている.本稿で用いたP-game は,広く探索アルゴリズムの性能の評価で用いられているが,MCTS の評価に用いる場合は,木の作り方に注意を払う必要がある可能性がある.