NP 状态描述
- 无法进行任何移动的局面为 P-position
- 可以移动到 P-position 的局面为 N-position
- 任意移动都到达 N-position 的局面为 P-position
Nim 游戏
Nim 游戏是组合游戏中的经典游戏，描述如下：
有 $n$ 堆石子，第 $i$ 堆有 $x_i$ 颗石子。$A$、$B$ 两人轮流取石子，每次仅能选择一堆不为空的石子进行操作：取走至少一颗石子。不能操作的人输。
关于 Nim 游戏有一个著名的结论：当且仅当 $x_1\oplus x_2\oplus\cdots\oplus x_n=0$ 时，先手获胜；否则后手胜。
证明很简单，当 $X=x_1\oplus x_2\oplus\cdots\oplus x_n\neq 0$ 时，设 $X$ 的二进制最高位为 $k$，那么一定存在一个 $x_i$ 其第 $k$ 位为 1。我们只需要从第 $i$ 堆石子中取走 $X\oplus x_i$ 个（显然，$X\oplus x_i < x_i$，所以此操作是有效的），那么新的游戏状态下：$x_1\oplus x_2\oplus\cdots(x_i\oplus X)\oplus x_n=X\oplus X=0$。
事实上，这也是构造 Nim 游戏方案的方法。
接下来，介绍 $SG$ 函数和 $SG$ 定理，$SG$ 函数和 $SG$ 定理是解决一类组合游戏的有力工具。
SG 函数
对于任意状态 $x$，定义 $SG(x)=mex(S)$；其中，$S$ 是 $x$ 的所有后继状态的 $SG$ 函数值集合，$mex(S)$ 表示不在 $S$ 中的最小非负整数。 特别地，当 $S$ 为空集，即 $x$ 没有后继节点时，$SG(x)=0$。
不难验证：
\begin{align}
x~\text{is}\left\lbrace
\begin{aligned}
&\text{P-position}, &SG(x)=0 \
&\text{N-position}, &SG(x)\neq0 \
\end{aligned}
\right.
\end{align}
SG 定理
游戏和的 $SG$ 函数等于各子游戏的 $SG$ 函数的 $Nim$ 和。
具体来说，若游戏 $A$ 可以看做由 $n$ 个互不干扰的子游戏 $(A_1,A_2,\cdots,A_n)$ 构成；也就是对于游戏任一状态 $(x_1,x_2,\cdots,x_n)$，只能选择一个子游戏 $A_i(1\leqslant i\leqslant n)$ 进行操作，得到状态 $(x_1,x_2,\cdots,x’_i,\cdots,x_n)$；那么，$SG_A\big((x_1,x_2,\cdots,x_n)\big)=SG_{A_1}(x_1)\oplus SG_{A_2}(x_2)\oplus \cdots\oplus SG_{A_n}(x_n)$。
证明
不妨假设当前游戏状态为 $X=(x_1,x_2,\cdots,x_n)$；记 $X$ 的所有后继状态集合为 $S$；
并记 $b=SG_{A_1}(x_1)\oplus SG_{A_2}(x_2)\oplus \cdots\oplus SG_{A_n}(x_n)$。
我们的证明分两步：
- $\forall_{0\leqslant a < b},\exists_{X’\in S} SG_{A}(X’) = a.$
- $\forall_{X’\in S} SG_{A}(X’) \neq b.$
step 1
记 $c=b\oplus a$；因为 $a < b$，所以必有：若 $c$ 的二进制最高位为 $k$，则 $b$ 的二进制第 $k$ 位也为 1；否则必有 $a > b$。于是必有 $x_i \in X$ 满足 $SG_{A_i}(x_i)$ 的二进制第 $k$ 位为 1。
令 $d=c\oplus SG_{A_i}(x_i)$，不难验证：$d < SG_{A_i}(x_i)$。
所以，根据 $SG$ 函数的定义可知，子游戏 $A_i$ 必有一个 $SG$ 值为 $d$ 的后继节点 $x_i’$。此时，
\begin{align}
&SG_{A_1}(x_1)\oplus SG_{A_2}(x_2)\oplus \cdots\oplus SG_{A_i}(x_i’)\cdots\oplus SG_{A_n}(x_n)\
=&SG_{A_1}(x_1)\oplus SG_{A_2}(x_2)\oplus \cdots\oplus \big(SG_{A_i}(x_i’)=d=c\oplus SG_{A_i}(x_i)=b\oplus a\oplus SG_{A_i}(x_i)\big)\cdots\oplus SG_{A_n}(x_n)\
=&\big(SG_{A_1}(x_1)\oplus SG_{A_2}(x_2)\oplus \cdots\oplus SG_{A_i}(x_i)\cdots\oplus SG_{A_n}(x_n)\big)\oplus b\oplus a\
=&b\oplus b\oplus a=a.
\end{align}
step 2
不妨操作子游戏 $A_i$ 到状态 $x_i’$ 得到游戏状态 $X’=(x_1,x_2,\cdots,x_i’,\cdots,x_n)$。
由 $SG$ 函数的定义可知，$SG_{A_i}(x_i’) \neq SG_{A_i}(x_i)$，即 $SG_{A_i}(x_i’)\oplus SG_{A_i}(x_i)\neq 0$。那么：
\begin{align}
&SG_{A_1}(x_1)\oplus SG_{A_2}(x_2)\oplus \cdots\oplus SG_{A_i}(x_i’)\cdots\oplus SG_{A_n}(x_n)\
=&SG_{A_1}(x_1)\oplus SG_{A_2}(x_2)\oplus \cdots\oplus \Big(\big(SG_{A_i}(x_i’)\oplus SG_{A_i}(x_i)\big)\oplus SG_{A_i}(x_i)\Big)\cdots\oplus SG_{A_n}(x_n)\
=&b\oplus SG_{A_i}(x_i’)\oplus SG_{A_i}(x_i) \neq b.
\end{align}
Hint
由 $SG$ 函数的定义，不难联系到 Nim 游戏。实际上，我们可以用解决 Nim 游戏的方法来构造一般组合游戏的方案。只需要顺着将 $SG(X)$ 变成 0 的方向做出决策就好了。
在实际问题上，通常 $x$ 是一个很大的数，但是一般 $SG$ 函数是有规律的（总要给点活路= =），然后只要本地打表找规律。。。
练习
| problems | categories | solution/code |
|---|---|---|
| 51Nod/1661 | $SG$ 函数（本地打表找规律） | Code |
