2017-04-23 (Sun.)
ここで単にゲームと言っているのは組み合わせゲームを指している. これは一般にゲーム理論が扱うゲームよりもかなり狭い (扱いやすい) ものを指している.
具体的には次のようなものである.
二人の対局者 (これは左と右と呼ばれる) がただ一つの局面 (状態) を交互に操作をする. 許される操作は左右ともに共通である場合と、左右とで明確に分かれている場合とがある. 共通の場合を 不偏 、共有でない場合を 非不偏 だと表現する. (直感通り、不偏の場合が解析は容易である.)
局面の操作とは形式的かつ一般には、そのときの局面と操作する者が左右どちらであるかに依存して、次の局面に写すような写像である. ただ一つの局面に写すとは限らないので関数ではない. また、写す先がない場合もある. そのような局面を 最終局面 という. というわけで、操作とは局面の集合に写す関数だと記述できる.
\[\rm{Op} : \rm{State} \times \{Left, Right\} \to \mathcal{P}(\rm{State})\]
Left の最終局面とは、 \[\rm{Op}(s, \rm{Left}) = \{\}\] なる \(s \in \rm{State}\) のことである. Right についても同様.
左右が交互に操作をするときに、その操作ができなくなった (つまり、操作を加えようとした局面が最終局面である) とき、その対局者の負けだと定める.
例えば石取りゲーム (ニム) では、「1個以上の石を取る」のが操作である. 最後に一個の石を取ると、次の対局者は石がゼロ個しかないので、一切の操作ができない. 従って、最後の一個の石を取った対局者の勝ちである.
といった風に、組み合わせゲームでは勝敗を定める. 局面に対して許される手を定めた時点で勝敗については定義されていることに註意.
それから、明らかにゲームが引き分けになることはない.
すぐに、そのちょうど逆 「最後の手を打った者が負けで、最終局面を渡された側の勝ち」 という場合を思いつく. これは 逆形 (misère play) と呼ばれる. 対して元の形を正形と呼ぶのだが、逆形は正形に比べて解析が困難なので扱わない.
組み合わせゲームに引き分けは無いわけだが、対局者がともに 正しく 自分の勝ちを目指したとき、 初期局面の時点でどちらが勝てるか？ を予見できる、と言っている.
実際のその証明は局面に関する帰納法によるわけだが、 その中身は min-max 法 である.
簡単に述べると、先攻の Alice が打てる手によって取り得る局面を
\[s_1, s_2, \ldots, s_n\]
とする. 帰納法の仮定で、\(s_1, s_2, \ldots, s_n\) それぞれは 「先攻の Alice が勝つか、後攻の Bob が勝つかのいずれか」 であるとする. 一つでも Alice が勝てる局面があるのなら、Alice は正しくそれを選択することで勝てる. 一つもないのなら、Bob が勝つしか無い. (Bob がミスをしない限りは勝てない. 正しく勝ちを目指すことを仮定するので、これは考えない.)
帰納法の基底として最終局面がある. 最終局面は後攻必勝である (勝敗の定義に註意).
不偏ゲームでは、先の定理で Alice、Bob という名称は無視して、単に先攻、後攻だけを気にすればよい. つまり、不偏ゲームは「先攻必勝か後攻必勝かのいずれかである」ということが言える.
先攻必勝のゲームをクラス \(\mathcal{N}\) という. Next の頭文字である. 後攻必勝のゲームをクラス \(\mathcal{P}\) という. これは Previous の頭文字である. ある不偏ゲーム \(G\) が先攻必勝であることを \(G \in \mathcal{N}\) と書くことがある.
非不偏ゲームにおいては、どちらが先攻でどちらが後攻かが大事である.
Alice や Bob といった固有名詞よりも私は左右という呼び分けが好きなので、 s/Alice/Left/g (左) s/Bob/Right/g (右) とする. 左右の概念はゲーム上に2つの異なる役割を与えるためのもの、 具体的には行える操作に区別をつけるためのものであって、先攻後攻とは独立した概念であることに註意. 基本定理に立ち返ると、次の四通りを考える必要がある.
これらのケースは排他的でなく、2x2 の表にする必要がある.
| - | 1 | 2 |
|---|---|---|
| 3 | \(\mathcal{L}\) | \(\mathcal{P}\) |
| 4 | \(\mathcal{N}\) | \(\mathcal{R}\) |
クラス \(\mathcal{N}\) と \(\mathcal{P}\) は不偏ゲームで紹介したものである. 例えばケース 2 とケース 3 が同時に成り立つときとは、すなわち、常に後攻が勝つ.
新たに導入した クラス \(\mathcal{L}\) と \(\mathcal{R}\) はそれぞれ Left, Right の頭文字であって、 左必勝、右必勝のことである. 例えばケース 1 とケース 3 とが同時に成り立つときは、先攻後攻にかかわらずに左が常に勝っている.
非不偏ゲームは常にこの4クラスのいずれかちょうど1つに属していることが、基本定理から言える.
非不偏ゲームではある局面に対して左右それぞれに一般には異なる許された手が定められる. コンウェイのゲームの形式的表現はゲームそのものを打てる手の集合として表現する. (つまりゲーム木として抽象化するのである.) 非不偏ゲーム \(G\) は 左が打てる手の集合 (左選択肢) \(\mathcal{G}^L\) 及び 右が打てる手の集合 (右選択肢) \(\mathcal{G}^R\) のペア
\[G = \{ \mathcal{G}^L | \mathcal{G}^R \}\]
と記述される.
不偏ゲームは \(\mathcal{G}^L = \mathcal{G}^R\) だと考えれば良いので、 非不偏ゲームの特別な場合だと見なせることが分かる. というわけで非不偏ゲームのことだけを考える.
基本定理では、min-max 法によってどちらが勝つかを示した. 4 クラスへの分類も同様に帰納的に示すことが出来る.
ゲーム \(G\) がクラス \(\mathcal{L}\) に属するのは、先ほどのケース 1, 3 が同時に成立する場合である. ケース 1 とは、先攻が左のときに左が必勝することであった. これは言い換えると、左選択肢の中に左が勝つような選択肢があれば良いということである. 左が勝つのはクラス \(\mathcal{L}\) であればよいが、それだけではない. 左が手を打った後、左は後攻になるので、クラス \(\mathcal{P}\) (後攻必勝) であってもよい. つまり、
ということ. 同様に、ケース 3 についても考える. ケース 3 は、先攻が右のときに左が必勝の場合である. どのような選択をしても右が勝てないとは、どの右選択肢も左が必勝であることを言う. 右が打った直後は左が先攻であるので、
以上から、ある非不偏ゲーム \(G\) がクラス \(\mathcal{L}\) に属する必要十分条件は
\[\exists G^L \in \mathcal{G}^L, G^L \in \mathcal{L} \cup \mathcal{P} ~ \bigwedge ~ \forall G^R \in \mathcal{G}^R, G^R \in \mathcal{L} \cup \mathcal{N}\]
だと分かる.
他についても全く同様に考えると、先ほどの 2x2 の表を次のように形式的に書き換えられる.
| - | \(\exists G^L \in \mathcal{L} \cup \mathcal{P}\) | \(\forall G^L \in \mathcal{R} \cup \mathcal{N}\) |
|---|---|---|
| \(\forall G^R \in \mathcal{L} \cup \mathcal{N}\) | \(\mathcal{L}\) | \(\mathcal{P}\) |
| \(\exists G^R \in \mathcal{R} \cup \mathcal{P}\) | \(\mathcal{N}\) | \(\mathcal{R}\) |
これはクラスを再帰的にゲームに与えている.