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

• Item type: Symposium(1)
• 公開日: 2022-11-04
• タイトル: General Game Playing における一般性の高い類似盤面利用手法の検討
• タイトル / 言語: en
• タイトル: Towards a universally effective utilization of board similarities in General Game Playing
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: General Game Playing
• キーワード / 主題Scheme: Other
• キーワード / 主題: MCTS
• キーワード / 主題Scheme: Other
• キーワード / 主題: 類似盤面検出
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 明治大学大学院理工学研究科情報科学専攻
• 著者所属(英): en
• 著者所属(英): Department of Information Sciences Graduate School of Science and Technology, Meiji University
• 著者名: 上宮, 佳晃; 横山, 大作
• 著者名(英): Yoshiaki, Uemiya; Daisaku, Yokoyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: General Game Playing(GGP) とは、初見の様々なゲームを上手くプレイすることができるプログラムの実現を目標とした問題カテゴリである。ゲーム固有の知識や技術に頼ることができないため、正確な評価関数を必要としないモンテカルロ機探索（MCTS）の活用が主流となっている。一方で、汎用の実装が求められるため、シミュレーション回数を容易に多くすることができない。この問題に対して、我々は、MCTS で展開するノードに探索経験から一致または類似する盤面の情報を付加することで、シミュレーション回数を増やすのと同等の効果を狙う手法を提案した。過去の検証の結果、類似盤面の活用によって一部のゲームでは勝率を上げることができた。本論文では、拡張する盤面と探索経験から取得する類似盤面のツリー上の距離を計測することで、本研究の手法が有効となるゲームの特徴を捉えた。そして、事前の準備時間で簡易的なシミュレーションを行い、扱うゲームによって類似盤面の利用をするか否かを判断することで、勝率を安定化させる仕組みを検討した。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌情報: ゲームプログラミングワークショップ2022論文集; 巻 2022, p. 104-111, 発行日 2022-11-04
• 出版者 / 言語: ja
• 出版者: 情報処理学会