ニムゲームの基本構造
ニムゲームは組合せゲーム（Combinatorial Game）の代表例であり、両者交互に行動し、最終的に移動できない者が敗れるというルールを持つ。各ターンで、プレイヤーは任意の山から1個以上の石を取り除くことができる。
重要な性質として、ある状態 (a₁, a₂, ..., aₙ) がP-ポジション（後手必勝）であるための条件は、すべての山の石の数のビット単位排他的論理和（XOR）が0になることである。すなわち：
a₁ ⊕ a₂ ⊕ ... ⊕ aₙ = 0
この定理はボトンの定理（Bouton's Theorem）として知られている。実装では、この判定は線形時間で可能である。
コード例：ニムゲームの判定
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int T, n, xorSum;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
xorSum = 0;
for (int i = 0; i < n; ++i) {
int pile;
scanf("%d", &pile);
xorSum ^= pile;
}
if (xorSum == 0)
printf("No\n"); // 先手必敗
else
printf("Yes\n"); // 先手必勝
}
return 0;
}
スプラグ-グリニー関数（SG関数）の導入
複数の独立したゲームを組み合わせた場合、それぞれのゲームに対してSG関数を定義し、全体の状態の性質をその異或によって決定できる。これは、任意の公平な組合せゲーム（Impartial Combinatorial Game）に一般化可能な理論である。
SG関数の定義：
- 終端状態（移動不能）のSG値は0。
- 頂点 x に対するSG値 g(x) は、x の後続状態のSG値集合の最小非負整数でない値（mex: minimal excludant）。
例：1つの山に n 個の石があるとき、1～3個取り出すゲームでは、g(n) = n % 4 となる。
複数ゲームの合成（ゲームの和）
複数の独立ゲーム G₁, G₂, ..., Gₙ を組み合わせる場合、全体のゲーム G = G₁ + G₂ + ... + Gₙ のSG値は、各ゲームのSG値の異或で表される：
g(G) = g(G₁) ⊕ g(G₂) ⊕ ... ⊕ g(Gₙ)
この性質により、複雑なゲームも「分けて計算→異或する」という戦略で解析可能になる。
応用例：異なる制約を持つ山の混合
例えば、以下のようなゲームを考える：
- 第1山：1～3個まで取り出せる。
- 第2山：奇数個しか取り出せない。
- 第3以降の山：任意個取り出せる（通常のニム）。
各山のSG値を計算してから全体の異或を求めれば、先手必勝か否かがわかる。
多枚のコマを持つグラフゲーム
有向無閉路グラフ上に複数のコマがある場合、各コマの位置に対応する頂点のSG値を計算し、それらの異或が0なら後手必勝、そうでなければ先手必勝となる。
翻訳ゲームとパスターゲーム
特定のゲーム（例：パスターゲーム）では、盤面の長さ p に対して、各色のコマ（サイズ c, z, n）の配置可能性を考慮し、全体の状態のSG値を動的計画法で求める。
var
c: array[1..3] of longint;
g, q: array[0..1000] of longint;
b: array[0..1000] of boolean;
m, maxq, i, j, k: longint;
begin
readln(c[1], c[2], c[3]);
readln(m);
maxq := 0;
for i := 1 to m do begin
read(q[i]);
if q[i] > maxq then maxq := q[i];
end;
g[0] := 0;
for i := 1 to maxq do begin
fillchar(b, sizeof(b), false);
for j := 1 to 3 do
for k := 0 to i - c[j] do
b[g[k] xor g[i - c[j] - k]] := true;
j := 0;
while b[j] do inc(j);
g[i] := j;
end;
for i := 1 to m do
if g[q[i]] = 0 then writeln(2) else writeln(1);
end.
必敗状態の発見戦略
多くのゲームにおいて、必敗状態（すべての選択肢が相手に有利になる状態）のパターンを見つけることで、解法が劇的に簡略化される。典型的なアプローチは：
- 小規模なケースを手で調べる。
- パターンを仮定（予想）。
- その予想が「必敗状態の三条件」を満たすことを確認する。
これにより、複雑なゲームでも効率的に解が得られる。