モンテカルロゲーム木探索に基づく限量記号付き制約充足問題の実時間解決

摘要

本論文では，モンテカルロ法を用いた限量記号付き制約充足問題を解く実時間アルゴリズムを提案ずる，限量記号付き制約充足問題は，全称限量化された変数を含む制約充足間題であり，自然や敵の選択に対応しで目的を達成するためのブランを求める問題である，限量記号付き制約充足問題はPSPACE完 全であり，問題のサィズが大きい場合に，完全なプランを事前に探索するには膨大な時間がかかる.そこで本論文では，あらがじめ完全なプランを求めることが不可能な場合に，逐次的に妥当な選択を行う実時間アルゴリズムを提案する．このような問題はゲーム木探索の分野で扱われており，状態を評価する静的評価関数の設計が重要となるが，限量記号付き制約充足問題において，適切な静的評価関数を設計することは困難な課題である．そこで本論文では，ランダムシミュレーションに基づく，評価関数の設計が不要なモンテカルロ法を用いたアルゴリズムを提案する．比較実験により，問題のサイズが大きい場合に，提案アルゴリズムがAlphaBeta法 を用いた既存の実時間アルゴリズムよりも高い勝率を得ることを示した．