2017-03-25 (Sat.)
\[ \def\I{\mathcal I} \def\P{\mathcal P} \def\G{\mathcal G} \def\mex{\mathrm{mex}} \def\bar#1{\overline{#1}} \]二人が交互に手を打つ (一つの局番に関する操作) 完全情報ゲームであって, 二人ともが打てる手が同じものを不偏ゲームという. ただし, 千日手が無く, どのような手を打っていても有限回でゲームが終了することが保証されているものだけを扱う.
典型的な不偏ゲームの例に Nim (石取りゲーム) である. 端的に言ってしまうなら, あらゆる不偏ゲームは Nim（石取りゲーム）をちょっと拡張した程度のものに帰着することができる.
以降では不偏ゲームを指して「ゲーム」という.
ある \(N\) 個の石が山積みにされている. 二人のプレイヤーが交互にこの石を取り合う. 一度に取れる石の数は \(1\) 個以上好きな個数だけ取って良い. 石が取れなくなった人の負け.
バリエーションとして, 取れる石の数に制限を設けたり, 複数山の石取りゲームにしたりすることで普通は遊ぶ.
麻雀は不偏ゲームではない. 相手の手が見えない不完全情報ゲームなので.
オセロやチェスは完全情報ゲームではあるが, 不偏ゲームではない. 先手と後手とで動かせるコマが色によって区別されているから不偏ゲームの定義からは外れる.
まず直感的にゲームを形式化する. ゲームとは, 局面の初期状態 \(I_0\) が与えられ, 各局面に対して打つことのできる手を定めるルール \(R\) の2つ組 \((I_0, R)\) のことである. 局面の状態空間を \(\I\) とすると,
だと言える. ここで \(\P(\I)\) は \(\I\) の冪集合のこと.
例えばある局面 \(\I\) に対して \(N\) 個の手が打てるとすると, 打った先の局面 \(I_1, I_2, \ldots, I_N\) に \(R\) はこれを写す:
\[R(I) = \{I_1, \ldots, I_N\} (\subset \I).\]そして特に \(R(I) = \{\}\) であるような局面 \(I\) があったとき, これを 最終局面 と呼ぶ. 最終局面を与えられたプレイヤーはもう手を打てないので負けだと定義する.
ここからもう一歩, 抽象化を進める.
さて「ゲーム」の定義に初期状態 \(I_0\) を入れておいたがこれは必要だろうか. 特に次のような状況を考える. もし \(R(I_0) = R(I_1)\) のとき, この２つの局面 \(I_0, I_1\) を区別する必要があるだろうか. もし単に勝ち負けの決定に興味があるのなら, この区別は必要なく, 必要なのは今の状態 \(I_0\) ではなくて \(R(I_0)\) だけである.
というわけで, 次の形式化を思いつく:
この \(G\) は先程まで局面と呼んでいた \(I \in \I\) に対応しているが, 同時に集合 \(R(I)\) の値を持っている. \(R(I)\) がまた \(\I\) の部分集合だったのと同様に \(G\) は \(\G\) の部分集合なのである.
今ゲーム (局面) \(G\) があるときに先手は 集合 \(G\) の中から 要素
\[G' \in G\]という手を選んで打つことが出来る. つまり \(|G| = n\) なら, \(n\) 個の選択肢があることになる. そして \(G'\) を選んでこれを後手の人に渡す.
特に \(G = \{\}\) のとき, これはもう手が打てない最終局面である.
ところで, ここでは「ゲーム」という言葉と普段我々が使う「局面」という言葉を区別しない. 日常的な感覚ではゲームは最初の定義のような形であって局面はその中の一つの状態のことだろう. だが, 局面が変化したある状態を切り取ってきて, これを初期状態とするゲームを考えることが出来る. 最初の定義で言えばゲームとは \((I_0, R)\) のことだったが, これは局面 \(I_0\) のことを指してると思ってもいいし, 局面 \(I_1\) のことをゲーム \((I_1, R)\) のことと思っても良い.
つまらない石取りゲームを考える. 局面として \(N\) 個の石が山積みにされている. 二人のプレイヤーは交互にここからちょうど \(1\) 個ずつ取り除いていく. 石が取れなくなった人の負け. （つまり \(N\) の偶数奇数で勝敗が決まるだけのゲームだ.）
石が \(N\) 個ある状態のことを, コンウェイによる集合形式で書いたものを \(\bar{N}\) としよう. するとゲーム集合は
\[\G = \{ \bar{0}, \bar{1}, \ldots, \bar{N} \}\]である. \(N\) より大きな局面は登場しないので考えない.
実際に各 \(\bar n\) の値を書いてみよう. まず自明なのは \(\bar{0}\) で, これは石がゼロ個の状態であって何もできない. 従って空集合になる.
\[\bar 0 = \{\}\]次に \(\bar 1\) を考える. このゲームでは選択肢は常に一つしかなく, 一個取り除いて \(\bar{0}\) にすることしかできない.
\[\bar 1 = \{ \bar 0 \} = \{\{\}\}\]他も同様で,
\[\bar 2 = \{ \bar 1 \} = \{\{\{\}\}\}\] \[\bar{(n+1)} = \{ \bar n \} = \{\{\{ \ldots \{\}\ldots \}\}\}\]といった具合.
不偏ゲームの定義から次が言える.
これは不偏ゲームが有限ステップで終了することを言っている. 特に \(\{\}\) はこれ以上打てる手が無いような局面のことを言っているので 最終局面 と呼ぶことにする. これを初期状態にするゲームは当然初めから何もできないので, 先手は何も出来ずに負け, 後手必勝のゲームだと言える.
不偏ゲームは先手または後手のどちらが必勝かが予め決まっている. これを調べるにあたって グランディ数 という道具が大変便利である. これはニム数, Grundy value, Nim value, Nimber, Energy など様々な呼ばれ方を持つ.
グランディ数とは不偏ゲーム \(G\) を自然数（ \(0\) 以上の整数）に写す写像, またはその写した先の値のことを言う.
\[g: \mathcal{G} \to \mathbb{N}\] \[g(G) = \mex \{ g(G') : G' \in G \}\]ここで \(\mex\) とは, 最小除外数 (minimum exclusion) などと呼ばれるもので, \(\mex T\) ( \(T\) は自然数の部分集合) とは, \(T\) に含まれない自然数の中で最小の数のことである. \(\mex T = \min(\mathbb{N} \setminus T)\) と言ってもいい.
例えば
定義から, \(G\) が最終局面ならば, \(g(G) = \text{mex }\{\} = 0\) である.
先程のちょうど一個の石を取り除くだけのゲームでは次のようになる.
取れる石の数に制限を設けた Nim を考える.
山に \(N\) 個の石がある. プレイヤーが行える操作は \(1\) 個以上 \(3\) 個以下の石を取ることである. これを交互に行い, 先に手が打てなくなった方の負け (つまり最後の一個を取れば勝ち).
石が \(N\) 個あるゲームを \(\bar{N}\) とすると,
これらに対して, グランディ数 \(g\) を計算すると次のようになる.
簡単に次のような事実に気附く:
\[g(\bar{n}) = n \bmod 4\]更に石の数の制限を 1 個以上 \(k\) 個以下とするとき,
\[g(\bar{n}) = n \bmod (k+1)\]と出来そう. 制限なし (いくつでも取っていい) なら, \(k=\infty\) とすることで,
\[g(\bar{n}) = n\]を得る.
ゲームのグランディ数が \(0\) である状態を考える.
\(g(G)=0\) より \(g(G')>0\) . \(g(G')>0\) より \(G' \ne \{\}\) であることと, \(\exists G'' \in G', g(G'')=0\) が分かる. 即ち, 先手がどのような手を打っても, 後手はゲームのグランディ数を再び \(0\) にできる.
後手はゲームのグランディ数を常に \(0\) になるような手を打ち続けることで, いつかは \(G=\{\}\) にでき勝てる (千日手は無いと仮定している).
しばしばゲームはより簡単なゲームに分解でき, それらの和とすることで簡単に考えることが出来る. 典型的な例は複数山の Nim である. 一山からなる Nim の直和だと見做すことが出来る.
ゲーム \(G\) と \(H\) の和 \(G + H\) とは, その2つを並べて, プレイヤーは \(G, H\) の内一つを自由に選んで手を打つようなゲームのことである. どちらともに最終局面の場合に限って, 和も最終局面だとする.
形式的には次のように再帰的に定義する.
特にこの三式目が再帰的定義となっているので註意.
この二項演算子を用いることで \(G_1 + G_2 + \cdots + G_n\) が定義出来る.
グランディ数 \(g(G), g(H)\) が明らかな時 \(g(G+H)\) を容易に計算することが出来,
\[g(G+H) = g(G) \oplus g(H)\]と書ける. この \(\oplus\) をニム和という.
ニム和の具体的な計算であるが, これは実はグランディ数 (自然数) を bit 表現したときの 排他的論理和 となっている.
\(n\) 個のゲーム和のグランディ数も, 同じ \(\oplus\) を用いて
\[g(G_1,G_2,..,G_n) = g(G_1) \oplus g(G_2) \oplus \ldots \oplus g(G_n)\]で与えられる.
2つの山があって, それぞれ \(n\) 個, \(m\) 個の石からなる. プレイヤーは交互に, 1つの山を選んで石を取る. 先ほどと同様に, 取る石の数は1個以上3個以下と制限する. 手が打てなくなったら負け (最後の最後の一個を取ったら勝ち).
局面の状態は \((n,m)\) で表せるので先ほどと同様に \(\bar{(n,m)}\) と書くことにする. 終盤局面は \(\bar{(0,0)}\) である.
愚直にグランディ数を計算するには先ほどと同様に, \(\bar{(0,0)}\) から \(\bar{(4,4)}\) くらいまでのグランディ数を愚直に計算すれば良い.
二次元のテーブルの上でグランディ数を具体的に書きだしてみると, 周期性が見えて, やはりなんとなく分かるが, 先ほどのニム和の性質が満たされていることも確認できる. すなわち,
\[g \bar{(n,m)} = g(\bar{n}) \oplus g(\bar{m}) = (n \bmod 4) \oplus (m \bmod 4)\]である.