Chance Node Sensitivity and its Applications to Multi-player Imperfect Information Games

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

 

西野 順二 電気通信大学情報・通信工学専攻 助教

［背景］ゲーム情報学の進歩によるアルゴリズムの高度化
［問題］多人数不完全情報ゲームの解法に向けた特徴の探求
［貢献］多人数不完全情報ゲームと局面の新たな特徴量の提案

 多人数不完全情報ゲームは人や企業の関わりとして営まれる社会活動の自然なモデルである．しかしながらチェスや囲碁に代表される二人完全情報ゲームについての研究が進む一方で多人数不完全情報ゲームはそのカバーするモデルの広さのため分類も多様で未解決の課題も多い．ゲームの不完全性は，他者の手札の配布状態など認識上同一視される複数の状態の重ね合わせとして情報集合により与えられる．このため最適な戦略は探索的手法を用いても唯1つに定めることができない．ゲームの多人数性は二人完全情報ゼロ和ゲームで有効であったmin-max定理にもとづくゲーム木探索を不可能としているため，情報の不完全性同様に一般的な方法による最良の行動決定を困難にしている．このため，個々のゲームとその状態の特性に適合する戦略の決定が求められるが，多人数不完全情報ゲームとその局面の特性を明らかに示す有効な分析方法が不足していた．

 本研究では種々の多人数不完全情報ゲームやその局面の特質を分析するための指標として偶然手番感度を提案した．偶然手番感度とは，展開型ゲームのある局面における戦略（手）に対する期待利得について情報集合中の状態の広がりに対する分散と定義する．ある手の利得が相手手札の状態など未知情報の影響によってどの程度変化するかを評価した指標である．

 応用実験として代表的な多人数不完全情報ゲームで日本国内でポピュラーかつ競技者の多いカードゲームである大貧民とその縮小ゲームである単貧民について計測を行った．単貧民はゲームの進行を単数カードにのみ絞った大貧民で，2人から5人に各2から5枚のカードを配布するとし，合計12枚までのすべての配布状況について完全情報ゲームとして多人数ゲーム探索を網羅的に行なった．求めた各最良手について，生成した配布状況をプレイヤからみた不完全情報ゲームとして再統合し各手の偶然手番感度を求め，多くの場合で感度ゼロ，すなわち他者の配布状態を考慮せずに最適着手が決定することを確かめた．また53枚を用いる実際のサイズのコンピュータ大貧民の中間局面において，各手の評価値と偶然手番感度をモンテカルロ探索によって求めた．その結果偶然手番感度は 0.4であり，すなわち手の配布の影響では順位が 0.4しか変わらないことを確かめ，大貧民がゲーム全体として偶然手番感度の低いゲームであることを示した．また，偶然手番感度が低いことから終盤探索の利用やGPGPUによる並列化などアルゴリズムの有効性を評価できることを示した．

 これらによって多人数不完全情報ゲームとその局面の新たな指標として提案した偶然手番感度の有効性を確かめることができた．

 

 （2013年6月15日受付）

取得年月日：2013年3月 学位種別：博士（工学） 大学： 電気通信大学

本論文はゲームにおける偶然手番の影響を計る新たな特徴指標としてChance Node Sensitivity （偶然手番感度）を提案し，コンピュータ大貧民などの不完全情報ゲームを題材に測定を行った研究である．この指標を用いると，大貧民ではカードの配布を知るよりも，自身の手札による探索が有用であり，他者の手札を推定することの重要性が低いことが示された．

まだまだ手つかずで未開拓の分野に1つの道を残すことができ嬉しく思います．コンピュータ大貧民大会に参加し優勝したことから始めた多人数不完全情報ゲームの研究で学位の取得にまで到達できました．ご指導いただいた西野哲朗教授に感謝いたします．