NIM
- 初始状态：三列铜板（或石子），数量分别为 3、4、5，共 12 枚。
- 两人轮流操作，每次只能从某一列中取走至少 1 枚，不能跨列取。
- 拿光最后一枚铜板的人获胜
后来，大家发现，先取的人只要在3那列里取走2枚，变成了1、4、5，就能稳操胜券了，游戏也就变得无趣了。
NIM 博弈先手必胜，当且仅当 \( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n \neq 0 \)。
证明： 所有物品都被取光是一个必败局面（对手取走最后一件物品，已经获得胜利），此时显然有 \( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n = 0 \)。
对于任意一个局面，如 \( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n = x \neq 0 \)，设 \( x \) 的二进制表示下最高位的 1 在第 \( k \) 位，那么至少存在一堆石子 \( A_i \)，它的第 \( k \) 位是 1。显然 \( A_i \text{ xor } x < A_i \)，我们就从 \( A_i \) 堆中取走若干石子，使其变为 \( A_i \text{ xor } x \)，就得到了一个各堆石子数异或起来等于 0 的局面。对于任意一个局面，如果 \( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n = 0 \)，那么无论如何取石子，得到的局面下各堆石子异或起来都不等于 0。可用反证法证明，假设 \( A_i \) 被取成了 \( A_i' \)，并且 \( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_i' \text{ xor } \dots \text{ xor } A_n = 0 \)。由异或运算的消去律得 \( A_i' = A_i \)，与“不能不取石子”的规则矛盾。
综上所述，再由数学归纳法可知，\( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n = 0 \) 为必败局面，一定存在一种行动让对方面临“各堆石子异或起来等于 0”。\( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n \neq 0 \) 为必胜局面，无论如何行动，都会让对方面临一个“各堆石子异或起来不等于 0”的必胜局面。
证毕。公平组合游戏 ICG
若一个游戏满足：
- 由两名玩家交替行动。
- 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关。
- 不能行动的玩家判负。
则称该游戏为一个公平组合游戏。
NIM 博弈属于公平组合游戏，但常见的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件 2 和条件 3。
有向图游戏
给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。
Mex运算
设 \( S \) 表示一个非负整数集合。定义 \( \text{mex}(S) \) 为求出不属于集合 \( S \) 的最小非负整数的运算，即： \[ \text{mex}(S) = \min_{x \in \mathbb{N}, x \notin S} \{x\} \]
SG函数
在有向图游戏中，对于每个节点 \( x \)，设从 \( x \) 出发共有 \( k \) 条有向边，分别到达节点 \( y_1, y_2, \dots, y_k \)，定义 \( \text{SG}(x) \) 为 \( x \) 的后继节点 \( y_1, y_2, \dots, y_k \) 的 SG 函数值构成的集合再执行 mex 运算的结果，即： \[ \text{SG}(x) = \text{mex}(\{\text{SG}(y_1), \text{SG}(y_2), \dots, \text{SG}(y_k)\}) \]
特别地，整个有向图游戏 \( G \) 的 SG 函数值被定义为有向图游戏起点 \( s \) 的 SG 函数值，即： \( \text{SG}(G) = \text{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 函数值的异或和，即： \[ \text{SG}(G) = \text{SG}(G_1) \oplus \text{SG}(G_2) \oplus \dots \oplus \text{SG}(G_m) \]
定理
有向图游戏的某个局面必胜，当且仅当该局面对应节点的 SG 函数值大于 0。
有向图游戏的某个局面必败，当且仅当该局面对应节点的 SG 函数值等于 0。
我们不再详细证明该定理。读者可以这样理解：
- 在一个没有出边的节点上，棋子不能移动，它的 SG 值为 0，对应必败局面。
- 若一个节点的某个后继节点 SG 值为 0，在 mex 运算后，该节点的 SG 值大于 0。这等价于，若一个局面的后继局面中存在必败局面，则当前局面为必胜局面。
- 若一个节点的后继节点 SG 值均不为 0，在 mex 运算后，该节点的 SG 值为 0。这等价于，若一个局面的后继局面全部为必胜局面，则当前局面为必败局面。