General Game Playing における一般性の高い類似盤面利用手法の検討

General Game Playing(GGP) とは、初見の様々なゲームを上手くプレイすることができるプログラムの実現を目標とした問題カテゴリである。ゲーム固有の知識や技術に頼ることができないため、正確な評価関数を必要としないモンテカルロ機探索（MCTS）の活用が主流となっている。一方で、汎用の実装が求められるため、シミュレーション回数を容易に多くすることができない。この問題に対して、我々は、MCTS で展開するノードに探索経験から一致または類似する盤面の情報を付加することで、シミュレーション回数を増やすのと同等の効果を狙う手法を提案した。過去の検証の結果、類似盤面の活用によって一部のゲームでは勝率を上げることができた。本論文では、拡張する盤面と探索経験から取得する類似盤面のツリー上の距離を計測することで、本研究の手法が有効となるゲームの特徴を捉えた。そして、事前の準備時間で簡易的なシミュレーションを行い、扱うゲームによって類似盤面の利用をするか否かを判断することで、勝率を安定化させる仕組みを検討した。

General Game Playing (GGP) is a problem category that aims to achieve programs that can play a variety of games only with the rule definitions. Since it is not possible to rely on game-specific knowledge and techniques, Monte Carlo Tree Search (MCTS), which does not require an exact evaluation function, is widely used. On the other hand, the number of simulations cannot be easily increased due to the need for general-purpose implementation. With regard to this problem, we proposed a method to increase the number of apparent simulations by adding matched or similar board information from exploration experience to the expanded node in MCTS. Results of past verifications showed that using similar board information increased the win rate in some games. In this paper, we explored the characteristics of games for which our approach is effective by measuring the distance on the tree between the extended node and the similar board information obtained from the exploration experience. We also proposed a switching algorithm for our approach using a small number of simulations in the preparation period, which successfully stabilized the win rate.