SG 函数

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

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

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

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

NIM 博弈定理

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

证明：

必败局面的性质：所有物品都被取光是一个必败局面（对手取走最后一件物品，已经获得胜利），此时显然有
$A_{1} xor, A_{2} xor, \dots xor, A_{n} = 0$
非零异或和的策略构造：对于任意一个局面，如果 $A_{1} xor, A_{2} xor, \dots 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, \dots xor, A_{n} = 0$ ，那么无论如何取石子，得到的局面下各堆石子异或起来都不等于 $0$ 。

综上所述，再由数学归纳法可知， $A_{1} xor, A_{2} xor, \dots xor, A_{n} \neq 0$ 为必胜局面，一定存在必胜策略。

公平组合游戏

一个游戏若满足以下三个条件，则称为公平组合游戏（ICG）：

交替行动：游戏由两名玩家轮流进行操作。
行动对等性：在游戏的任意时刻，当前玩家可执行的所有合法行动，与轮到哪一方行动无关（即双方可选择的操作集合完全相同）。
失败判定：当某玩家无法执行任何合法行动时，该玩家判负，游戏结束。

典型例子分析

NIM 博弈属于 ICG：符合 ICG 的所有条件：两名玩家轮流从若干堆石子中取走任意数量，行动选择仅依赖于当前石子堆状态，与玩家身份无关；无法取石子者判负。
围棋不属于 ICG

不满足条件 2：双方只能分别落黑子或白子，行动选择受限于玩家身份（黑方/白方）。
不满足条件 3：胜负判定依赖复杂的规则（如气、围地、劫争等），而非简单的“无法行动则判负”。

策梅洛定理（Zermelo's Theorem）

在 ICG 中，一个局面是必胜的，当且仅当：

可以一步之内赢得游戏；

或其后继局面中至少有一个是必败的；

一个局面是必败的，当且仅当：

无论如何决策，都将马上输掉游戏；

或其后继局面中都是必胜的。

有向图游戏

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

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

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

mex (S) = min_{x \in N, x \notin S} {x}

例如：

mex ({0, 1, 2, 4}) = 3

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

SG (x) = mex ({SG (y_{1}), SG (y_{2}), \dots, SG (y_{k})})

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

NIM 游戏可以看成 SG 函数的直接应用，单堆石子的 SG 函数为 $SG (n) = n$ 。

有向图游戏的和

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

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

SG (G) = SG (G_{1}) xor SG (G_{2}) xor \dots xor SG (G_{m})

定理：

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

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

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

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

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

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