モンテカルロ木探索の性能の分析と改善

点击翻译按钮获取中文摘要

モンテカルロ木探索（MCTS）はゲームにおける代表的な探索の枠組みである．しかし，ゲームの性質とMCTSの性能の関係性については，まだ解明されていない点がある．本年度は，まず，多腕バンディット問題（MAB）における，期待値の最大値の推定量についての研究を行った．MABは確率的な報酬が得られるスロットマシーンが複数存在する時に，より多くの報酬を得られるプレイの仕方を求める問題である．MCTSの代表的なアルゴリズムであるUCTは，MABでの累積的な報酬の最大化を目指したアルゴリズムを木探索に応用したものであるように，MABはMCTSと密接な関わりがある．また，期待値の最大値の推定量は，最善手を判別するために重要である．判別のためには，以後も最善手を選び続けた（最も期待値が高くなるように手を選んだ）場合の報酬の期待値を比較する必要があるためである．本研究では，各確率変数に対し，その期待値が最大である確率の上限に基づき，重みを与え，その重み付き平均で期待値の最大値を推定する手法（SWE）を新たに提案した．理論的な解析を行い，推定値のバイアスが０に収束すること等を示した．加えて，実験を行い，提案手法の有効性を確かめた．様々なMABの設定の下で，提案手法は常に最良ではないものの，多くの設定で良い結果となった．次に，上記の手法SWEのMCTSへの応用を行った．既存手法UCTでは，子の価値の推定を子孫から行ったシミュレーション結果の平均で行う．まず，実験を行い，MABで，サンプルの平均による推定の代わりにSWEを使うことで推定値の精度を改善出来ることを確かめた．そして，UCTにおける，平均による推定の代わりに，SWEよる推定を行う手法を提案した．ゲームでの終盤に近いモデルと，序盤に近いモデルの２種類で，実験を行い，後者のモデルでの提案手法の有効性を示した．