展開型ゲーム

展開型ゲーム（てんかいがたゲーム、英: Extensive-form game）とは、ゲームの表現形式のひとつであり、ゲームの木と呼ばれるグラフの形式で表現されたものである。ゲームの表現形式には展開型と標準型（または戦略型）と特性関数型（または提携型）の3種がある。ある非協力ゲームは展開型でも標準型でも表現できるが、展開型の方が情報量が多い。特性関数型は特に協力ゲームの表現に使われる。

展開型ゲームは、ゲームの木、プレイヤー分割、偶然手番の確率分布族、情報分割、利得関数の5つの要素で記述できる。

ゲームの木

ゲームの木は点で示されるノードと2点を結ぶ有向線分である枝とから成る。ノードは状態とも呼ばれ、ゲームのひとつの局面を表す。枝は一人のプレイヤーの意志または偶然による選択により、あるノードから別のノードへ遷移できることを示すもので選択肢(alternative)とも呼ばれる。ノードは分岐点と頂点に分けられる。頂点はそこから枝が出ていないノード、すなわちゲームが終了した局面を示す点であり、各プレイヤーの利得(pay off)が与えられている。利得は利得関数とも呼ばれ、プレイヤーの数だけの成分数を持つベクトル量として表せる。分岐点は頂点以外のノードであり、手番(move)とも呼ばれる。各手番では一人のプレイヤーの意志または偶然により、その手番から出ている選択肢のひとつが選択されてその先の手番に遷移する。偶然により選択がなされる手番を偶然手番と呼ぶ。またプレイヤー甲の意志で選択がなされる手番を甲の手番と呼ぶ。プレイヤー分割とは手番の集合を各プレイヤーの手番に分割したものである。偶然手番の確率分布族とは偶然手番での確率分布を定めたものである。そこに遷移する選択肢がひとつもない分岐点を底点と呼び、これはゲームの初期状態、つまり出発局面である。

以下に「奇数偶数ゲーム」（MorraまたはOdd-or-evenと呼ばれる）を例としてゲームの木を示す。これは、双方が偶数か奇数のどちらかを示し、示された数の和が偶数ならAの勝ちで奇数ならBの勝ちとするゲームである（外部リンクの英語版wikipedia参照）。

• 
  図1A.不完全情報ゲームの木の例。点線で囲んだものが情報集合のひとつ。
• 
  図1B.図1Aの標準型表現。同時手番ゲームの例。
• 
  図2A.完全情報ゲームの木の例。
• 
  図2B.図2Aの標準型表現。Bの戦略はAの第1手に対応して4通り。Bの第2戦略は必勝戦略である。

例示

各局面が、枝を選択するプレイヤー(偶然も含む)の他にどのようなもので定まるかの具体例をいくつか挙げる。チェスやダイヤモンドゲーム、連珠、リバーシなどでは各局面は盤面の各位置の駒の種類（空白も含む）で完全に定まる。将棋ではさらに各プレイヤーの持ち駒も含めれば完全に定まる。チェスや将棋では頂点は詰みやステイルメイトの局面であり、そこでの各プレイヤーの利得は例えば勝者が+1で敗者が-1と表せる。リバーシでは頂点は盤面全てに石が置かれた局面であり、利得は盤面にある各プレイヤーの駒（石）の個数である。碁では利得は、いわゆる地の数である。カードゲームでは各プレイヤーの手札と獲得した札、および場に晒されている場札および山札で局面が定まる。例えばコントラクトブリッジやホイストでは頂点は各プレイヤーの手札が無くなった局面であり、そこでの利得はそれまでに取ったトリック数である。カードゲームの利得には他にも、各プレイヤーが獲得していた札の枚数や点数、獲得した札の組み合わせで定まる点数などルールにより多様なものがある。

情報分割

情報分割(information partition)とは手番の集合を情報集合(information set)に分割したものである。プレイヤー甲の情報集合とは甲の手番から成る集合であり、ひとつの情報集合の中のある手番に居るとき、甲はその情報集合の中のどの手番に居るのかを知ることができない。

例えば多くのカードゲームでは各プレイヤーは自分の手札と場札しか知ることができず、他のプレイヤーの手札と山札は知ることができない。つまり自分がプレイしようとする時に、現在の局面はある複数の局面の中のどれかひとつであることしかわからない。このとき、自分の手札と場札はわかるが他の札の状態はわからないので、現在の局面には知らない札の組み合わせの数だけの可能性がある。これらの可能な局面つまり手番の全ての集合が情報集合になる。チェスなど多くのボードゲームのように自分の手番の状態を全て知ることができるゲームは、全ての情報集合がただひとつの手番を持つゲームと定義でき、このようなゲームを完全情報ゲーム(Game with perfect information)と呼ぶ。完全情報ゲームではないゲームを不完全情報ゲーム(Game with imperfect information)という。麻雀、七並べ、大富豪、ＵＮＯなどは相手の手札が見えないので不完全情報ゲームである。

同時手番ゲーム

ジャンケンのように各プレイヤーが同時に指すゲームを同時手番ゲームと呼ぶが、これは各プレイヤーが順番に指すが全員が指し終えるまでは他のプレイヤーの指し手が隠されている不完全情報ゲームと同値である。先に例示した「奇数偶数ゲーム」も同時手番ゲームの例である。

完全記憶ゲーム

全プレイヤーが自分の過去の選択肢を全て記憶しているゲームを完全記憶ゲーム(Game with perfect recall)と呼ぶ。完全情報ゲームは完全記憶ゲームである。完全記憶であり不完全情報であるゲームの木の例を図3に示す。また不完全記憶ゲームの木の例を図4に示す。図4のプレイヤーAのように一手前の記憶を喪失するプレイヤーは想像しにくいが、例えばプレイヤーAを2名のチームと考え、手番と手番では別のチーム員が指しチーム員同士は情報交換ができないとすれば、現実的な一例となる。

• 
  図3.完全記憶で不完全情報なゲームの木の例。
• 
  図4.不完全記憶ゲームの木の例。同種破線で囲まれた手番は同じ情報集合に属する。

完備情報ゲーム

完備情報ゲーム(Game with complete information)という言葉もあり、これは全プレイヤーがゲームのルールすなわちゲームの木の全体像を知っているゲームである。現実の戦争や経済行為のゲームはほとんどが完備情報ゲームではない、すなわち不完備情報ゲーム(Game with imcomplete information)である。しかし不完備情報ゲームは、情報が不明な部分を偶然手番に置き換えることにより、完備情報ゲームとして表現し解析することができる。

展開型ゲームと標準型ゲーム

標準型ゲームは戦略型ゲームと呼ばれることもあり、各プレイヤーの選択肢の組合わせに対応した利得で表される。例えば「奇数偶数ゲーム」では各プレイヤーの選択肢は偶数か奇数かの2つであり４通りの組み合わせの利得を標準型で表すと図1Bのようになる。ここで一方のプレイヤーが先に選択肢を選び、他方のプレイヤーは何が選択されたかを知らずに自分の選択肢を選ぶと考えると展開型の表現になる。後手の手番での情報集合は2つの分岐点を含んでおり、このゲームは不完全情報ゲームだとわかる。標準型ゲームでの各プレイヤーの選択肢を純戦略と呼ぶ。単に戦略と言うと、各純戦略にそれを選択する確率を与えたものを指す。「奇数偶数ゲーム」の例では例えば、偶数を60%の確率で奇数を40%の確率で出す、というのがひとつの戦略の例である。ゲーム理論の初期の主要な課題は、標準型ゲームでの戦略と平均的利得の関係の解析であり、利得表がわかっていることが前提であった。

関連項目

• ゲーム理論

外部リンク

• Morra モラ（奇数か偶数か）と呼ばれる西洋で広く知られている指を使ったじゃんけんに似た遊び