ゲームの直和

$G_1, G_2$ を不偏ゲームとする。

$G_i$ の状態集合を $X_i$、遷移関数を $F_i \colon X_i \to 2^{X_i}$ とする ($i=1,2$)

2つの不偏ゲーム $G_1, G_2$ の和 $G_1 + G_2$ は次の状態集合と遷移関数を持つ不偏ゲームであると定義される。

Sprague Grundy の定理

$G_1, G_2$ を不偏ゲームとする。

$G_i$ の状態集合を $X_i$, 、$G_i$ の Sprague Grundy 関数を $g_i\colon X_i\to \mathbb{N}$ とする。($i=1,2$)

$G_1 + G_2$ の Sprague Grundy 関数 $g$ は以下のように表せる。

$$ \begin{array}{lll} X_1\times X_2 &\to &\mathbb{N}\\ (x_1, x_2) &\mapsto &g_1(x_1) \oplus g_2(x_2)\end{array} $$

$n$ 個の不偏ゲームにも簡単に拡張できる。

Sprague Grundy はスプレイグ・グランディと読む。

Nim 和

$a \oplus b = \operatorname{mex}(\{ a' \oplus b \mid 0 \leq a' < a\} \cup \{ a \oplus b' \mid 0 \leq b' < b\} )$ が成り立つ