组合游戏基础之 SG 函数和 SG 定理

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 \dots \oplus x_{n} = 0$ 时，先手获胜；否则后手胜。证明很简单，当 $X = x_{1} \oplus x_{2} \oplus \dots \oplus x_{n} \neq 0$ 时，设 $X$ 的二进制最高位为 $k$ ，那么一定存在一个 $x_{i}$ 其第 $k$ 位为 $1$ 。我们只需要从第 $i$ 堆石子中取走 $X \oplus x_{i}$ 个 ^[1]，那么新的游戏状态为：

X^{'} = x_{1} \oplus x_{2} \oplus \dots (x_{i} \oplus X) \oplus x_{n} = X \oplus X = 0

事实上，这也是构造 Nim 游戏方案的方法。接下来，介绍 $S G$ 函数和 $S G$ 定理， $S G$ 函数和 $S G$ 定理是解决一类组合游戏的有力工具。

SG 函数
¶

对于任意状态 $x$ ，定义 $S G (x) = m e x (S)$ ；其中， $S$ 是 $x$ 的所有后继状态的 $S G$ 函数值集合， $m e x (S)$ 表示不在 $S$ 中的最小非负整数。特别地，当 $S$ 为空集，即 $x$ 没有后继节点时， $S G (x) = 0$ 。不难验证：

x is {\begin{aligned} P-position, & S G (x) = 0 \\ N-position, & S G (x) \neq 0 \end{aligned}

SG 定理
¶

游戏和的 $S G$ 函数等于各子游戏的 $S G$ 函数的 $N i m$ 和。 具体来说，若游戏 $A$ 可以看做由 $n$ 个互不干扰的子游戏 $(A_{1}, A_{2}, \dots, A_{n})$ 构成；也就是对于游戏任一状态 $(x_{1}, x_{2}, \dots, x_{n})$ ，只能选择一个子游戏 $A_{i} (1 ⩽ i ⩽ n)$ 进行操作，得到状态 $(x_{1}, x_{2}, \dots, x_{i}^{'}, \dots, x_{n})$ ；那么有：

S G_{A} (x_{1}, x_{2}, \dots, x_{n}) = S G_{A_{1}} (x_{1}) \oplus S G_{A_{2}} (x_{2}) \oplus \dots \oplus S G_{A_{n}} (x_{n})

不妨假设当前游戏状态为 $X = (x_{1}, x_{2}, \dots, x_{n})$ ；记 $X$ 的所有后继状态集合为 $S$ ；并记 $b = S G_{A_{1}} (x_{1}) \oplus S G_{A_{2}} (x_{2}) \oplus \dots \oplus S G_{A_{n}} (x_{n})$ 。我们的证明分两步：

$\forall_{0 ⩽ a < b}, \exists_{X^{'} \in S} S G_{A} (X^{'}) = a$ .
$\forall_{X^{'} \in S} S G_{A} (X^{'}) \neq b$ .

step 1
¶

记 $c = b \oplus a$ ；因为 $a < b$ ，所以必有：若 $c$ 的二进制最高位为 $k$ ，则 $b$ 的二进制第 $k$ 位也为 $1$ ；否则必有 $a > b$ 。于是必有 $x_{i} \in X$ 满足 $S G_{A_{i}} (x_{i})$ 的二进制第 $k$ 位为 $1$ 。令 $d = c \oplus S G_{A_{i}} (x_{i})$ ，不难验证： $d < S G_{A_{i}} (x_{i})$ 。所以，根据 $S G$ 函数的定义可知，子游戏 $A_{i}$ 必有一个 $S G$ 值为 $d$ 的后继节点 $x_{i}^{'}$ 。此时，

\begin{aligned} (1) & S G_{A_{1}} (x_{1}) \oplus S G_{A_{2}} (x_{2}) \oplus \dots \oplus S G_{A_{i}} (x_{i}^{'}) \dots \oplus S G_{A_{n}} (x_{n}) \\ (2) & = & S G_{A_{1}} (x_{1}) \oplus S G_{A_{2}} (x_{2}) \oplus \dots \oplus (S G_{A_{i}} (x_{i}^{'}) = d = c \oplus S G_{A_{i}} (x_{i}) = b \oplus a \oplus S G_{A_{i}} (x_{i})) \dots \oplus S G_{A_{n}} (x_{n}) \\ (3) & = & (S G_{A_{1}} (x_{1}) \oplus S G_{A_{2}} (x_{2}) \oplus \dots \oplus S G_{A_{i}} (x_{i}) \dots \oplus S G_{A_{n}} (x_{n})) \oplus b \oplus a \\ (4) & = & b \oplus b \oplus a \\ (5) & = & a \end{aligned}

step 2
¶

不妨操作子游戏 $A_{i}$ 到状态 $x_{i}^{'}$ 得到游戏状态 $X^{'} = (x_{1}, x_{2}, \dots, x_{i}^{'}, \dots, x_{n})$ 。由 $S G$ 函数的定义可知， $S G_{A_{i}} (x_{i}^{'}) \neq S G_{A_{i}} (x_{i})$ ，即 $S G_{A_{i}} (x_{i}^{'}) \oplus S G_{A_{i}} (x_{i}) \neq 0$ 。那么：

\begin{aligned} (6) & S G_{A_{1}} (x_{1}) \oplus S G_{A_{2}} (x_{2}) \oplus \dots \oplus S G_{A_{i}} (x_{i}^{'}) \dots \oplus S G_{A_{n}} (x_{n}) \\ (7) & = & S G_{A_{1}} (x_{1}) \oplus S G_{A_{2}} (x_{2}) \oplus \dots \oplus ((S G_{A_{i}} (x_{i}^{'}) \oplus S G_{A_{i}} (x_{i})) \oplus S G_{A_{i}} (x_{i})) \dots \oplus S G_{A_{n}} (x_{n}) \\ (8) & = & b \oplus S G_{A_{i}} (x_{i}^{'}) \oplus S G_{A_{i}} (x_{i}) \\ (9) & \neq & b \end{aligned}

小结
¶

由 $S G$ 函数的定义，不难联系到 Nim 游戏。实际上，我们可以用解决 Nim 游戏的方法来构造一般组合游戏的方案。只需要顺着将 $S G (X)$ 变成 0 的方向做出决策就好了。在实际问题上，通常 $x$ 是一个很大的数，但是一般 $S G$ 函数是有规律的（总要给点活路= =），然后只要本地打表找规律。。。

练习
¶

#	problems	categories	solution/code
1	51node / 1661	$S G$ 函数（本地打表找规律）	solution.cpp

SG定理

NP 状态描述¶

Nim 游戏¶

SG 函数¶

SG 定理¶

step 1¶

step 2¶

小结¶

练习¶

Related¶