0x3A 博弈论之 SG 函数

在许多地方曾经流行过这样一个小游戏：摆出三堆硬币，分别包含3枚、5枚、7枚。两人轮流行动，每次可以任选一堆，从中取走任意多枚硬币，可把一堆取光，但不能不取。取走最后一枚硬币者获得胜利。

这类游戏可以推广为更加一般的形式：

给定 $n$ 堆物品，第 $i$ 堆物品有 $A_{i}$ 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手能否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对手面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

定理

NIM 博弈先手必胜，当且仅当 $A_{1}$ xor $A_{2}$ xor … xor $A_{n} \neq 0$ 。

证明：

所有物品都被取光是一个必败局面（对手取走最后一件物品，已经获得胜利），此时显然有 $A_{1}$ xor $A_{2}$ xor ... xor $A_{n} = 0$ 。

对于任意一个局面，如果 $A_{1}$ xor $A_{2}$ xor ... xor $A_{n} = x \neq 0$ ，设 $x$ 的二进制表示下最高位的1在第 $k$ 位，那么至少存在一堆石子 $A_{i}$ ，它的第 $k$ 位是1。显然 $A_{i}$ xor $x < A_{i}$ ，我们就从 $A_{i}$ 堆中取走若干石子，使其变为 $A_{i}$ xor $x$ ，就得到了一个各堆石子数异或起来等于0的局面。

对于任意一个局面，如果 $A_{1}$ xor $A_{2}$ xor ... xor $A_{n} = 0$ ，那么无论如何取石子，得到的局面下各堆石子异或起来都不等于0。可用反证法证明，假设 $A_{i}$ 被取成了 $A_{i}^{\prime}$ 并且 $A_{1}$ xor $A_{2}$ xor ... xor $A_{i}^{\prime}$ xor ... xor $A_{n} = 0$ 。由异或运算的消去律得 $A_{i}^{\prime} = A_{i}$ 与“不能不取石子”的规则矛盾。

综上所述，再由数学归纳法可知， $A_{1}$ xor $A_{2}$ xor…xor $A_{n}\neq 0$ 为必胜局面，一

定存在一种行动让对手面临“各堆石子异或起来等于0”。 $A_{1}$ xor $A_{2}$ xor … xor $A_{n} = 0$ 为必败局面，无论如何行动，都会让对手面临一个“各堆石子异或起来不等于0”的必胜局面。

证毕。

公平组合游戏ICG

若一个游戏满足：

由两名玩家交替行动。
在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关。
不能行动的玩家判负。

则称该游戏为一个公平组合游戏。

NIM 博弈属于公平组合游戏，但常见的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件 2 和条件 3。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设 $S$ 表示一个非负整数集合。定义 $\operatorname{mex}(S)$ 为求出不属于集合 $S$ 的最小非负整数的运算，即：

\operatorname {m e x} (S) = \min _ {x \in \mathbb {N}, x \notin S} \{x \}

SG函数

在有向图游戏中，对于每个节点 $x$ ，设从 $\pmb{x}$ 出发共有 $k$ 条有向边，分别到达节点 $y_{1}, y_{2}, \dots, y_{k}$ ，定义 $\mathrm{SG}(x)$ 为 $x$ 的后继节点 $y_{1}, y_{2}, \dots, y_{k}$ 的 SG 函数值构成的集合再执行 mex 运算的结果，即：

\operatorname {S G} (x) = \max (\{\operatorname {S G} (y _ {1}), \operatorname {S G} (y _ {2}), \dots , \operatorname {S G} (y _ {k}) \})

特别地，整个有向图游戏 $G$ 的SG函数值被定义为有向图游戏起点 $s$ 的SG函数值，即 $\mathrm{SG}(G) = \mathrm{SG}(s)$ 。

有向图游戏的和

设 $G_{1}, G_{2}, \dots, G_{m}$ 是 $m$ 个有向图游戏。定义有向图游戏 $G$ ，它的行动规则是任选某个有向图游戏 $G_{i}$ ，并在 $G_{i}$ 上行动一步。 $G$ 被称为有向图游戏 $G_{1}, G_{2}, \dots, G_{m}$ 的和。

有向图游戏的和的 SG 函数值等于它包含的各个子游戏 SG 函数值的异或和，即：

\operatorname {S G} (G) = \operatorname {S G} \left(G _ {1}\right) \text {x o r} \operatorname {S G} \left(G _ {2}\right) \text {x o r} \dots \text {x o r} \operatorname {S G} \left(G _ {m}\right)

定理

有向图游戏的某个局面必胜，当且仅当该局面对应节点的 SG 函数值大于 0。

有向图游戏的某个局面必败，当且仅当该局面对应节点的 SG 函数值等于 0。

我们不再详细证明该定理。读者可以这样理解：

在一个没有出边的节点上，棋子不能移动，它的 SG 值为 0，对应必败局面。

若一个节点的某个后继节点 SG 值为 0，在 mex 运算后，该节点的 SG 值大于 0。这等价于，若一个局面的后继局面中存在必败局面，则当前局面为必胜局面。

若一个节点的后继节点 SG 值均不为 0，在 mex 运算后，该节点的 SG 值为 0。这等价于，若一个局面的后继局面全部为必胜局面，则当前局面为必败局面。

对于若干个有向图游戏的和，其证明方法与NIM博弈类似。

【例题】Cutting Game FOJ2311

给定一张 $N * M$ 的矩形网格纸，两名玩家轮流行动。在每一次行动中，可以任选一张矩形网格纸，沿着某一行或者某一列的格线，把它剪成两部分。首先剪出 $1 * 1$ 的玩家获胜。两名玩家都采取最优策略行动，求先手是否必胜。 $1 \leq N, M \leq 200$ 。

在游戏开始时，只有一张 $N * M$ 的矩形网格纸。但在游戏过程中，可能会有若干张大小不同的矩形网格纸。我们可以把每张矩形网格纸作为一个“游戏”，所有矩形网格纸构成一个“游戏的和”。

这个剪纸游戏与有向图游戏稍有不同。在剪纸游戏中，不能行动的局面，即1*1的纸张，是一个必胜局面。而有向图要求在不能行动时判负。因此，我们需要作出一些转化。

首先，若两人都采取最优策略行动，则他们一定不会剪出 $1*X$ 或 $X*1$ 的纸张。否则对手就可以剪出 $1*1$ 从而立即获胜。除了 $1*X$ 和 $X*1$ 的纸张以外，能够剪出 $1*1$ 的方法必定要经过 $2*2, 2*3$ 和 $3*2$ 三种局面之一。而在 $2*2, 2*3$ 和 $3*2$ 局面下，先手无论如何行动，都会剪出 $1*X$ 或 $X*1$ 的形状。故 $2*2, 2*3$ 和 $3*2$ 是必败局面。我们把这三者作为终止局面判负，剪纸游戏就符合有向图游戏的特点了。

对于一张 $N * M$ 的矩形网格纸，我们可以枚举如何行动，把这张纸剪成两部分。这两部分是两个“子剪纸游戏”，二者的 SG 值执行 xor 运算，可得到这个行动之后局

面的 SG 值。对所有合法行动产生的子局面构成的集合做 mex 运算，即可得到这张 $N * M$ 网格纸的 SG 函数值，从而判断它是否先手必胜。即：

\operatorname {S G} (N, M) = \max \left(\left\{\operatorname {S G} (i, M) \text {x o r} \operatorname {S G} (N - i, M), \text {其 中} 1 \leq i < N \right\} \right.

\cup \left\{\operatorname {S G} (N, i) \text {x o r} \operatorname {S G} (N, M - i), \text {其 中} 1 \leq i < M \right\}

$\mathrm{SG}(i,M)$ xor $\mathrm{SG}(N - i,M)$ 为沿着第 $i$ 行下边的格线剪开，两个子游戏 SG 值 xor 的结果。 $\mathrm{SG}(N,i)$ xor $\mathrm{SG}(N,M - i)$ 为沿着第 $i$ 列右边的格线剪开，两个子游戏 SG 值 xor 的结果。 $\cup$ 表示集合的并集运算。最后执行 mex 运算，就得到了 $\mathrm{SG}(N,M)$ 。

0x3A_博弈论之SG函数