2017-03-25 (Sat.)
二人が交互に手を打つ (一つの局番に関する操作) 完全情報ゲームであって, 二人ともが打てる手が同じものを不偏ゲームという. ただし, 千日手が無く, どのような手を打っていても有限回でゲームが終了することが保証されているものだけを扱う.
典型的な, 不偏ゲームの例に Nim (石取りゲーム) である. 端的に言ってしまうなら, あらゆる不偏ゲームは Nim（石取りゲーム）をちょっと拡張した程度のものに帰着することができる.
一方で, 例えばオセロやチェスは動かせるコマが色によって区別されており, 二人のプレイヤーで打てる手が違うので, 不偏ゲームの定義からは外れる.
以降では不偏ゲームを指して「ゲーム」という.
まず直感的にゲームを形式化する. ゲームとは, 局面の初期状態 \(I_0\) と, 局面に対して打つ手を定めるルール \(R\) の2つ組 \((I_0, R)\) のことである. 局面の状態空間を \(\I\) とすると,
だと言える. ここで \(\P(\I)\) は \(\I\) の冪集合のこと. ある局面 \(\I\) に対してルール \(R\) はいくつか（０個以上）の手を用意していて, それらによって \(\{I_1, \ldots, I_N\} \subset \I\) に写ることを \[R(I) = \{I_1, \ldots, I_N\}\] と定めることができる.
さて「ゲーム」の定義に初期状態 \(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' \in g\] という手を選んで打つことが出来る. つまり \(|g| = n\) なら, \(n\) 個の選択肢があることになる. そして \(g'\) を選んでこれを後手の人に渡す.
ところで, ここでは「ゲーム」という言葉と普段我々が使う「局面」という言葉を区別しない. 日常的な感覚ではゲームは最初の定義のような形であって局面はその中の一つの状態のことだろう. だが, 局面が変化したある状態を切り取ってきて, これを初期状態とするゲームを考えることが出来る. 最初の定義で言えばゲームとは \((I_0, R)\) のことだったが, これは局面 \(I_0\) のことを指してると思ってもいいし, 局面 \(I_1\) のことをゲーム \((I_1, R)\) のことと思っても良い.
簡単のために, つまらない石取りゲームを考える. 局面の状態として石が \(N\) 個山積みにしてある. 二人のプレイヤーはここからちょうど \(1\) 個ずつ取り除いていく. 石が取れなくなった人の負け.
石が \(N\) 個ある状態というのを, 今の集合の形式で書き直したものを \(\bar{N}\) と書くことにしよう. するとゲーム集合というのは \[\G = \{ \bar{0}, \bar{1}, \ldots, \bar{N} \}\] である. \(N\) より大きな局面はここでは考える必要がない.
さてまず自明なのは \(\bar{0}\) で, これは石がゼロ個の状態であって何もできない. これを空集合で表す. \[\bar 0 = \{\}\] 次に \(\bar 1\) を考える. このゲームでは選択肢は特に無く, 一個取り除いて \(\bar{0}\) にすることしかできない. \[\bar 1 = \{ \bar 0 \} = \{\{\}\}\] 他も同様で, \[\bar 2 = \{ \bar 1 \} = \{\{\{\}\}\}\] といった具合.
不偏ゲームの定義から次が言える.
これは不偏ゲームが有限ステップで終了することを言っている. 特に \(\{\}\) はこれ以上打てる手が無いような局面のことを言っているので 最終局面 と呼ぶことにする. これを初期状態にするゲームは当然初めから何もできないので, 先手は何も出来ずに負け, 後手必勝のゲームだと言える.
不偏ゲームは先手/後手のどちらが必勝かが予め決まっている. これを調べるにあたって グランディ数 という道具が大変便利である. これはニム数, 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\]
を得る.
不偏ゲーム \(G\) のグランディ数 \(g\) が \(g(G)=0\) のとき, またそのときに限り, ゲーム \(G\) は後手必勝である.
ゲームのグランディ数が \(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)\]
である.