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

馬場 里美  岩崎 敦  横尾 真  

誌名
電子情報通信学会論文誌 D   Vol.J94-D   No.11   pp.1729-1739
発行日: 2011/11/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 特集論文 (ソフトウェアエージェントとその応用論文特集)
専門分野: 理論
キーワード: 
限量記号付き制約充足問題,  モンテカルロ法,  UCT,  実時間アルゴリズム,  

本文: PDF(519.4KB)
>>論文を購入 | 正誤


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