偶然手番感度とその多人数不完全情報ゲームへの応用

摘要

多人数不完全情報ゲームは人や企業の関わりとして営まれる社会活動の自然なモデルである。しかしながらチェスや囲碁に代表される二人完全情報ゲームについての研究が進む一方で多人数不完全情報ゲームはそのカバーするモデルの広さのため分類も多様で未解決の課題も多い。ゲームの不完全性は、認識上同一視される複数の状態の重ね合わせとしての情報集合により与えられる。このため最適な戦略も探索等を用いてもただ一つに定めることはできずその融合方法も課題である。ゲームの多人数性は二人完全情報ゼロ和ゲームで有効であったmin-max定理にもとづくゲーム木探索による最適行動の決定を不可能としているため、情報の不完全性同様に一般的な方法による最良の行動決定を困難にしている。このため、個々のゲームとその状態の特性に適合する戦略の決定が求められるが、多人数不完全情報ゲームとその局面の特性を明らかに示す有効な分析方法が不足していた。本論文は個々の多人数不完全情報ゲームやその局面の特質を分析するための指標として偶然手番感度を提案する。偶然手番感度は展開型ゲームのある局面における戦略（手）に対する期待利得の情報集合に含まれる複数の状態変化に対する分散で定義し、その手の利得がどの程度変化しうるかを評価した指標である。偶然手番感度を用いて不完全情報ゲームにおけるひとつの戦略が情報集合に含まれる複数の状態に対して頑健であるかどうかを判断することができ、効果的な戦略の決定に役立つことを明らかにした。まず多人数不完全情報ゲームについて述べその戦略決定に関連する既存の手法を概観する。つぎに偶然手番感度を定義を行った。ある要素数Dの情報集合Iにおける手mに付与される期待利得giについて偶然手番感度を1=Dsum(gi??avg(gi))2と定義する。これにより、各情報集合に含まれるノードの実現確率pに対する総合利得sum(pigi)の変動を計ることができる。これは、展開型で記述した不完全情報ゲームに対するベイジアン均衡解を求めるときの利得について、情報集合における着手価値の変動可能性を指標となる。この偶然手番感度について、様々なゲームでの値の調査を行い、局面の状態を表していることを確かめた。代表的な多人数不完全情報ゲームとして日本国内でポピュラーで競技者の多いカードゲーム大貧民とその縮小ゲームである単貧民について計測実験を行った。単貧民はゲームの進行を単数カードにのみ絞った大貧民である。2人から5人に各2から5枚のカードを配布するとし、合計12枚までのすべての配布状況について完全情報ゲームとしてmax-n paranoid探索を行った。求めた各最良手について、生成した配布状況をプレイヤからみた不完全情報ゲームとして再統合して情報集合とし各手の偶然手番感度を求め、ほぼゼロとなることを確かめた。また53枚を用いるコンピュータ大貧民の中間局面において、各手の評価値をモンテカルロ探索によって求め偶然手番感度のシミュレーションを行ないその最頻値はゲイン幅4に対して0.4であり、大貧民がゲーム全体として偶然手番感度の低いゲームであることを示した。さらに、大貧民が偶然手番感度の低いゲームであることを利用し、偶然手番における相手情報を推定しながらモンテカルロ探索を行う大貧民プレイヤと推定をせずに多量のランダムシミュレーションからなるプレイヤの強度比較を行った。結果として単純なシミュレーション回数を十分に上げると偶然手番での推定に匹敵することを示した。これらの応用として、終盤データベースを利用した大貧民の戦略決定では、とくに終盤で偶然手番感度が極めて低くなることから単貧民に縮約した終盤情報のみを使用すればよいことを明らかにした。合計が10枚以下の最終局面について、単貧民化を行って探索した終盤データベースを作成しこれを検索することで終盤での高速な戦略決定を可能とした。さらに偶然手番感度と並列化の関係について、感度の低い場面では状態特定の必要性が下がることから、単一局面の評価を繰り返し行えば良くGPGPUなどを用いた並列化も有効であることを示した。GPGPU は高並列ではあるが高速化しやすいアルゴリズムの制約がある。不完全情報ゲームでは状態が未知のため探索木等による戦略決定ができないため情報集合に含まれる状態をモンテカルロサンプリングによって仮定したうえで戦略決定を行う。モンテカルロサンプリングも含め並列化するサンプリング並列化と単一のサンプル内でのシミュレーションを並列化するリーフ並列化を比較した。計算回数の比が10 程度でリーフ並列化がサンプリング並列化と同程度の最良戦略を発見できることを示した。GPGPU では200以上の並列化も標準的であり、サンプリング負担の少ないリーフ並列化が10倍程度で計算でき実用的であることを示した。以上により、これまで示されていなかった不完全多人数ゲームの局面およびゲーム全体を分析する指標として偶然手番感度を提案し、日本でポピュラーな多人数不完全情報ゲームである大貧民を対象に実験を行い有効性を示した。