[4B3-GS-1] 基礎・理論 (2)

[4B3-GS-1-04] MCTSの木の再利用における減衰係数の自動調整

〇横川 滉太¹、森山 甲一¹、武藤 敦子¹、松井 藤五郎²、犬塚 信博¹ (1. 名古屋工業大学、2. 中部大学)

キーワード：モンテカルロ木探索

近年、様々な分野において木探索アルゴリズムは利用されており、Monte-Calro Tree Search(MCTS)はその1つである。
MCTSはランダムな探索を繰り返し、その結果を基に評価値を推定し、木を徐々に拡張して最良となるノードを選択する最良優先探索アルゴリズムである。
しかし、MCTSは毎回木を初期化するため、探索に無駄が生じるという問題点がある。
MCTSの改良法の一つである木の再利用は遷移先のノードをルートノードとする木を次の探索に持ち越すことで探索の効率を向上させる手法である。
確率的遷移を含む環境では評価値等の情報を完全に再利用することが問題になる場合があるため減衰係数を用いて情報を減衰させるが、適切な減衰係数は環境によって異なるため事前に知ることは難しいという問題がある。
そこで本研究では、環境から得られる情報を用いて減衰係数の自動調整を行う。
実験としてGeneral Video Game Playing AI(GVGAI)のフレームワークを利用して、６０種のゲームを提案手法を実装したゲームプレイングAIでプレイし評価する。
結果、従来手法より勝率がわずかだが向上した。