展開型ゲーム
ゲームの木は点で示されるノードと2点を結ぶ有向線分である枝とから成る。ノードは状態とも呼ばれ、ゲームのひとつの局面を表す。枝は一人のプレイヤーの意志または偶然による選択により、あるノードから別のノードへ遷移できることを示すもので選択肢(alternative)とも呼ばれる。ノードは分岐点と頂点に分けられる。頂点はそこから枝が出ていないノード、すなわちゲームが終了した局面を示す点であり、各プレイヤーの利得(pay off)が与えられている。利得は利得関数とも呼ばれ、プレイヤーの数だけの成分数を持つベクトル量として表せる。分岐点は頂点以外のノードであり、手番(move)とも呼ばれる。各手番では一人のプレイヤーの意志または偶然により、その手番から出ている選択肢のひとつが選択されてその先の手番に遷移する。偶然により選択がなされる手番を偶然手番と呼ぶ。
完備情報ゲーム(Game with complete information)という言葉もあり、これは全プレイヤーがゲームのルールすなわちゲームの木の全体像を知っているゲームである。現実の戦争や経済行為のゲームはほとんどが完備情報ゲームではない、すなわち不完備情報ゲーム(Game with imcomplete information)である。しかし不完備情報ゲームは、情報が不明な部分を偶然手番に置き換えることにより、完備情報ゲームとして表現し解析することができる。
情報分割(information partition)とは手番の集合を情報集合(information set)に分割したものである。プレイヤー甲の情報集合とは甲の手番から成る集合であり、ひとつの情報集合の中のある手番に居るとき、甲はその情報集合の中のどの手番に居るのかを知ることができない。
例えば多くのカードゲームでは各プレイヤーは自分の手札と場札しか知ることができず、他のプレイヤーの手札と山札は知ることができない。つまり自分がプレイしようとする時に、現在の局面はある複数の局面の中のどれかひとつであることしかわからない。このとき、自分の手札と場札はわかるが他の札の状態はわからないので、現在の局面には知らない札の組み合わせの数だけの可能性がある。これらの可能な局面つまり手番の全ての集合が情報集合になる。チェスなど多くのボードゲームのように自分の手番の状態を全て知ることができるゲームは、全ての情報集合がただひとつの手番を持つゲームと定義でき、このようなゲームを完全情報ゲーム(Game with perfect information)と呼ぶ。完全情報ゲームではないゲームを不完全情報ゲーム(Game with imperfect information)という。麻雀、七並べ、大富豪、UNOなどは相手の手札が見えないので不完全情報ゲームである。