在2002年张一飞写过一篇论文 《由感性认识到理性认识－透析一类博弈游戏的解答过程》 从此开启了这类博弈问题的大门，留下学习笔记。
取石子游戏
$A,B$ 两人面对若干堆石子，按照如下规则取石子
- 每步至少取一枚石子
- 每步只能在某一堆取走部分或者全部石子
- 谁无法按照规则取石子，谁就是输家
首先抛开问题，我们先从一般的入手。
我们可以用一个 $n$ 元组 $(a_1,a_2,\cdots,a_n)$ 表示一个局面 $S$。显然改变 $n$ 元组的顺序仍然是一个局面。
一个局面 $n$ 元局面$(a_1,a_2,\cdots,a_n)$和一个 $m$ 元局面 $(b_1,b_2,\cdots,b_m)$ 之和显然就是一个 $m + n$ 元局面 $(a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_m)$。类似的一个局面也可以有多种分解。
对于局面 $S$，若先行者有必胜策略，则称 “$S$ 胜”；
对于局面 $S$，若后行者有必胜策略，则称 “$S$ 负”。
如果局面 $S$ 胜，则必然存在取子方式 $S \to T$，且 $T$ 负；
如果局面 $S$ 负，则对任意取子方式 $S \to T$，有 $T$ 胜。
局面分解理论，若 $S = A + B$ 则下面结论显然
- 若 $A,B$ 一胜一负，则 $S$ 胜
- 若 $A,B$ 全为负，则 $S$ 负
- 若 $A,B$ 全为胜，则 $S$ 无法判断
- 若 $A=B$，则 $S$ 负
- 空局面是负局面
因此根据上面的分解理论，可以将一个局面进行化简。例如 $(2,2,2,7,9,9)$ 可以化简成 $(2,7)$
而局面分解的关系，很容易让人联想到整数的位运算－异或。
对于上面取石子问题，每一个局面都可以分解成只有一堆石子的局面。
对一个局面，定义一个函数 $f$，然后把它们异或是不是，然后判断是非为0，作为是否胜的充要条件.这样做是否可行呢？先对原始例子进行实验。
函数 $f$：若局面 $S$ 只有一个石子，设 $S={a}$，则定义 $f(a) = a$。
设局面 $S = (a_1,a_2,\cdots,a_n)=(a_1)+(a_2)+\cdots (a_n)$，则 $f(S) = f(a_1) \oplus f(a_2) \oplus \cdots \oplus f(a_n)$
对于一个局面 $S$，若 $f(S) = 0$，则 $S$ 负，否则，$S$ 胜。
下面证明上面的结论。
引理：$a_1 \oplus a_2 \oplus a_n = p \neq 0$，则必存在 $1 \leq k \leq n$，使得 $a_k \oplus p < a_k$。这是因为我们看 $p$ 的最高位即知存在 $a_k$ 其最高位也为 $1$, 那么与 $p$ 异或后，这一位就从 $1$ 变为 $0$，证毕。
若 $f(S) = 0$，则无论先行者如何取子 $S \to T$，都有 $f(T) \neq 0$。
若 $f(S) \neq 0$，则先行者存在一种取法 $S \to T$, 使得 $f(T) = 0$。这是因为由引理 $a_1 \oplus a_2 \oplus a_n = p \neq 0$，存在 $1 \leq k \leq n$，使得 $x = a_k \oplus p < a_k$。那么我们在第 $k$ 堆取走 $a_k - x$ 个石子，那么 $a_1 \oplus a_2 \oplus a_n \oplus p = 0$，证毕。
这说明了上述想法的可行性。下面把这种思想推广成一般的 SG 函数的情形
SG 函数
当对石子的取法进行限制时，例如每次最多能去 $m$ 个，或每次最少取 $l$ 个等，此时再令 $f(x) = x$ 就不合适了。那么应该选择怎样的 $f$ 呢。显然 $f$ 必须满足：
- 若 $f(S) = 0$, 则无论先行者如何取子 $S \to T$，都有 $f(T) \neq 0$
- 若 $f(S) \neq 0$, 则先行者存在一种取子 $S \to T$，使得 $f(T) = 0$。
我们用 $(S) = \lbrace S_1,S_2, \cdots S_k \rbrace$ 表示 $S$ 的下一个可能的局面，定义 $g(S) = \lbrace f(S_1),f(S_2), \cdots f(S_k) \rbrace $。
由 $f$ 满足条件1知
$$ \lbrace f(S) \rbrace \cap g(S) = \emptyset $$
由条件2知
$$ \max g(S) < f(S)$$
因此我们定义函数 $f(S)$ 为 $f(S) \equiv \min g(S)$
写的这么乱，估计只有自己看的懂 0.0