完全情報化による不完全情報ゲームの数理的解析

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

本年度は従来の予定通り，完全情報化された不完全情報ゲームの計算量解析を行った．本年度の主な成果は以下の二つである．1.一般化七並べゲームの必勝判定に対する高速解法の提案及び計算量解析:多人数不完全情報ゲームであるトランプゲーム七並べを完全情報化したゲームに対してグラフ的一般化を行い，その計算量解析を行った．本年度はこのグラフ的一般化を行ったゲームに対して，二人完全情報下で行う場合に対して組合せゲーム理論の手法を用いた解析を行い，従来のこのゲームやその一般化ゲームにおける必勝者判定やその必勝戦略を求める線形時間アルゴリズムを提案した．また，七並べでよく遊ばれるローカルルールを含めた七並べに関しても解析を行った．結果として，使用するローカルルールによっては必勝者判定を行うことがNP困難やPSPACE困難といった計算困難性があることなど完全情報七並べに対する種々の性質を解明した．2.オラクルを用いた不完全情報ゲームの解析：単貧民ゲームを題材として，不完全情報ゲームをオラクルを用いて解析する手法を提案し，その有効性を検証した．手札に関する情報が全くない場合，確定的な意味で「必勝戦略」を得ることは難しい．このため，本研究では相手の手札に関する部分的な情報を提供するオラクルの存在を許したモデルを定義し，そのオラクル存在下で必勝戦略が得られるかどうかについて考察した．結果として，相手がどの札を持っているかなどの情報がない状況でも，ゲームの構造パラメータを得るオラクルさえあれば完全情報単貧民と同様の必勝戦略をとることができるなど，オラクルの強さと必勝戦略発見可能性に関する様々な結果が得られた．