公平组合游戏学习笔记

公平组合游戏：双方操作形式相同，先手操作一次后相当于交换先后手。

Part 1 Nim 游戏

有 $n$ 个非负整数 $\{a_i\}$，双方轮流选择一个 $1\le id\le n$ 并将 $a_{id}$ 减少任意正整数，不能操作者输。

先抛结论，先手必胜当且仅当 $\oplus a_i\not=0$。

证明考虑归纳，显然 $\forall a_i=0$ 的状态满足该结论。假设对于某个状态 $\{a_i\}$，已经证明其能到达的所有状态（满足 $b_i\le a_i$ 且和 $\{a_i\}$ 不相同的状态 $\{b_i\}$）满足该结论，那么设当前异或和为 $x$：

• 若 $x=0$ 那么无论怎么操作都会到达异或和不为 $0$ 的状态，即当前状态先手必败；
• 否则设 $2^y$ 为 $x$ 的二进制最高位，那么一定存在某个 $j$ 满足 $a_j$ 该位也为 $1$，那么有 $a_j\oplus x<a_j$，所以先手可以通过将 $a_j$ 修改为 $a_j\oplus x$ 来到达异或和为 $0$ 的状态，即当前状态先手必胜；

即 $\{a_i\}$ 也满足该结论，证毕。

Part 2 DAG 走路游戏和 SG 定理

有一个有向无环图，初始某个点上有一个棋子，双方轮流沿着有向边推动棋子，无法操作者输。

几乎所有公平组合游戏都能转换为该游戏。

对于节点 $x$，设 $SG(x)=\text{mex}\{SG_v\}$，其中 $v$ 是 $x$ 的所有后继节点，$\text{mex}(S)$ 表示最小的不在集合 $S$ 中的非负整数。

特别的，若 $x$ 没有后继节点，则 $SG(x)=0$。

SG 引理断言：

多个棋子情况下，棋子集合为 $\{s_i\}$ 的 DAG 走路游戏先手必胜当且仅当 $\oplus SG(s_i)\not=0$。

证明考虑归纳，边界情况显然满足。

对于 $x$ 的所有后继 $v$，显然 $SG(v)\not=SG(x)$，且走到 $SG(v)>SG(x)$ 的 $v$ 是没有意义的，因为可以走回某一个 $SG(y)=SG(x)$ 的 $y$。

由于 $\forall s<SG(x)$ 都存在一个 $v$ 满足 $SG(v)=s$，所以这就是一个 Nim 游戏，根据 Nim 游戏的结论即可证明 SG 引理。

同理，有推论：

SG 定理：多个棋子情况下，棋子集合为 $\{s_i\}$ 的 DAG 走路游戏满足 $SG(\{s_i\})=\oplus SG(s_i)$。

证明依旧是归纳，边界情况显然成立。

对于一个状态 $\{s_i\}$，显然 $\oplus SG(s_i)$ 是无法达到的，而对于 $x<\oplus SG(s_i)$ 的 $x$，证明类比 Nim 游戏结论的证明，这些 $x$ 一定都能达到，故 $SG(\{s_i\})=\oplus SG(s_i)$。

Part 3 一些特殊的游戏

3.1 二分图游戏

有一个二分图，初始有一个棋子在 $s$，每次可以将棋子移到相邻的点，不能移动到重复的点，无法操作的人输。

3.2 翻转黑白棋游戏

局面上有一些黑白棋，棋子总数不变，每次操作形如：

• 若 $x$ 为白色则可以翻转满足 $s\in S_x$ 的集合 $s$ 中棋子的颜色（$S_x$ 为集合组成的集合）；

操作保证不能无限进行，终止局面为全黑。