aiura/

不偏ゲームのグランディ数 (ニム数)

2017-03-25 (Sat.)

数学 ゲーム理論

index

不偏ゲームとは何か

二人が交互に手を打つ (一つの局番に関する操作) 完全情報ゲームであって、 二人ともが打てる手が同じものを不偏ゲームという. ただし、千日手が無く、どのような手を打ってもいつかは最終局面に移ることが保証されているものとする.

例えばオセロやチェスは置ける/動かせるコマが色によって区別されて打てる手が違う (黒のコマを置く操作は一方しか行えない) ため、不偏ゲームではない.

不偏ゲームとして有名なゲームの例は Nim (石取りゲーム) である.

コンウェイによるゲームの抽象化

直感的にはゲームとは、局面の初期状態 \(I_0\) と、局面に対して打つ手を定めるルール \(R\) の2つ組 \((I_0, R)\) のことである.

手を打つとは、局面に操作を加える操作である. 局面が初期状態 \(I_0\) から \(I\) に変更したとき、 これを、ゲーム \((I_0, R)\) からゲーム \((I, R)\) への変更だと見做す. 即ち、手を打つという操作は、ゲームを別なゲームに変更する操作である.

ルールとは局面それぞれに対して (もし非不偏ゲームであればプレイヤーにも依存して) 打てる手を定めるものである. 打てる手全てを集めた集合が局面に対して与えられていればルールが与えられたと見なせる.

以上の考察から、次のような形式化が思いつく.

ゲームとは、一回の打てる手によって写せる先のゲーム全てからなる集合のこと.

例えば「最終局面」とはそれ以上打てる手がないゲームのことであるが、 最終局面は全て空集合 \(\{\}\) によって表現される. 或いは、打てる手が 1 つ以上あるが、どれを打っても全て最終局面になるのならば、 そのような局面は空集合からなる \(\{\{\}\}\) として表現される.

このように「ゲーム」とは局面及びその局面に対して打てる手を情報として持たせたものとして定められるが、 単に「局面」と呼んで同一視することがある. これは「ゲームをゲームに写す」よりは「局面を局面に写す」と言った方が一般的だから. あるいは局面と言った時に、暗黙的に、ルールを既に一つ定めて仮定しているから.

グランディ数 (ニム数, Grundy value, Nim value, Nimber, Energy などとも)

グランディ数とは不偏ゲーム \(G\) を (\(0\) を含む) 自然数に写す写像であって、

\[g: \mathcal{G} \to \mathbb{N}\] \[g(G) = \text{mex } \{ g(G') : G' \in G \}\]

ここで mex とは、最小除外数 (minimum exclusion) などと呼ばれるもので、 \(\text{mex }T\) (\(T\) は自然数の部分集合) とは、\(T\) に含まれない自然数の中で最小の数のことである. すなわち \(\text{mex } T = \text{min }(\mathbb{N} \setminus T)\) である.

例えば

定義から、\(G\) が最終局面ならば、\(g(G) = \text{mex }\{\} = 0\) である.

例. 制限付き Nim (石取りゲーム)

ルール

取れる石の数に制限を設けた Nim を考える.

山に \(N\) 個の石がある. プレイヤーが行える操作は 1 個以上 3 個以下の石を取ることである. これを交互に行い、先に手が打てなくなった方の負け (つまり最後の一個を取れば勝ち).

グランディ数

このゲームのグランディ数を考える.

局面を考えるには、単に石がいくつ残っているかを考えれば良い. 先述したゲームの形式的表現を用いる.

石が \(n\) 個あるゲームを \(\overline{n}\) とすると、

これらに対して、グランディ数 \(g\) を計算すると次のようになる.

簡単に次のような事実に気附く:

\[g(\overline{n}) = n \bmod 4\]

更に石の数の制限を 1 個以上 \(k\) 個以下とするとき、

\[g(\overline{n}) = n \bmod (k+1)\]

と出来そう. 制限なし (いくつでも取っていい) なら、\(k=\infty\) とすることで、

\[g(\overline{n}) = n\]

を得る.

定理

不偏ゲーム \(G\) のグランディ数 \(g\)\(g(G)=0\) のとき、またそのときに限り、 ゲーム \(G\) は後手必勝である.

ゲームのグランディ数が \(0\) である状態を考える.

  1. \(G=\{\}\) のとき、これは最終局面であるので後手必勝であるし \(g(G)=0\) である.
  2. \(G \ne \{\}\) のとき、先手には打てる手があるので、先手は \(G' \in G\) に写したとする. \(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つ山の制限付き Nim (石取りゲーム)

2つの山があって、それぞれ \(n\) 個、\(m\) 個の石からなる. プレイヤーは交互に、1つの山を選んで石を取る. 先ほどと同様に、取る石の数は1個以上3個以下と制限する. 手が打てなくなったら負け (最後の最後の一個を取ったら勝ち).

局面の状態は \((n,m)\) で表せるので先ほどと同様に \(\overline{(n,m)}\) と書くことにする. 終盤局面は \(\overline{(0,0)}\) である.

愚直にグランディ数を計算するには先ほどと同様に、 \(\overline{(0,0)}\) から \(\overline{(4,4)}\) くらいまでのグランディ数を愚直に計算すれば良い.

二次元のテーブルの上でグランディ数を具体的に書きだしてみると、 周期性が見えて、やはりなんとなく分かるが、 先ほどのニム和の性質が満たされていることも確認できる. すなわち、

\[g \overline{(n,m)} = g(\overline{n}) \oplus g(\overline{m}) = (n \bmod 4) \oplus (m \bmod 4)\]

である.