[組み合わせゲーム理論] 帰結類について

組み合わせゲームの基本定理

組み合わせゲームにおいて、双方の対局者が完璧な手を打ち続けた場合、必ずいずれか一方の対局者が勝つことが知られています。

定理 2.1 (組み合わせゲームの基本定理)

アルバートとバーサの対局するゲームGが与えられて、アルバートを先手番とするとき、このゲームは、先手番のアルバートが必ず勝つか、後手番のバーサが必ず勝つかのどちらかで、その両方ということはない。

(組み合わせゲーム理論入門 P.45より)

この定理を理解するために、まず「完璧な手」について考えます。

ある局面において、対局者は複数の選択肢をもち、その中から一手を選択することになります。「完璧な手」を打つということは、選択肢のなかから勝てない手を選ばない、少なくとも「勝つことができる」選択肢を選び続けるということになります。

ゲーム木において「勝つことができる」選択肢とは、即ち終端の局面を相手番で迎える形に繋げることが出来るような手を指します。つまり対局者がある局面からのゲーム木を完全に把握し、それに従って終局を望ましい形で迎えることが出来る選択肢を打ち続けた場合、これが「完璧な手」を打ち続けるということになります。

では、双方が「完璧な手」を打ち続けた場合、どうなるのでしょうか？

例えば、ある局面においてアルバートが勝つことができる選択肢を持つ場合、アルバートは必ずその手を打ちます。ここでいう「勝つことができる」とは、バーサがいかなる選択肢を選んだとしても勝利するようなことができる手のことです。何故なら、バーサもまたゲーム木を把握しており、相手の勝利を防ぐ(自分が勝利する)選択肢があるなら必ずこれを選ぶためです。

一方で、アルバートが勝つことができる選択肢を持たない場合、どのような手を打ったとしてもバーサが必ず対応し、結果としてバーサが必ず勝つことになります。

このように、組み合わせゲームにおいて、双方が完璧な手を打ち続けた場合、必ずいずれか一方の対局者が勝つこととなります。組み合わせゲームにおいては偶然性はないため、何度対局してもこの結果は変わりません。

帰結類

組み合わせゲームの基本定理により、ある局面においてお互いが完璧な手を打ち続けた場合、いずれか一方の対局者が必ず勝利することがわかっています。この時、その局面はいずれの対局者が勝利するかによって分類されます。この分類のことを帰結類と呼びます。

不偏ゲームの場合、お互いの対局者は同一の選択肢を持つため、帰結類は「先手番が必ず勝つ」「後手番が必ず勝つ」の2種類となります。

非不偏ゲームの場合は、左右の対局者がそれぞれ異なる選択肢を持ち、さらに局面に対してどちらが先手番の時に勝利するかによって帰結類が決まります。帰結類は以下の4パターンに分けられます。

先手番、勝者と帰結類の対応は以下の通りとなります。

[latex][/latex]