博弈论：公平组合游戏（Nim 游戏 & SG 定理）学习笔记

公平组合游戏

定义：

1. 两人轮流以最优方式操作，两人的操作方式相同。
2. 每次操作游戏状态必须改变，不能操作者输，另一人赢。
3. 每个游戏状态不能重复到达。

我们把每个状态看作一个点，每个状态的点向它后继状态的点连有向边，可以生成一张 DAG（有向无环图）。

所以公平组合游戏也叫做有向图游戏。

必胜状态 & 必负状态

定义：

1. 没有后继状态的状态为必负状态。
2. 至少有一个后继状态为必负状态的状态为必胜状态。
3. 所有后继状态都为必胜状态的状态为必负状态。
4. 所有状态为必胜状态或必负状态。

记 \(n,m\) 为游戏生成的有向图的点数和边数。
则我们可以根据必胜状态和必负状态在 \(O(n+m)\) 的时间用记忆化搜索解决游戏的胜负。

Nim 游戏

有 \(n\) 堆石子，每堆石子有 \(a_i\) 个，两个人轮流取正整数个石子，不能取者输。

Nim 和

设一个状态 Nim 和为 \(S=a_1\oplus a_2\oplus\cdots\oplus a_n\)。

性质：Nim 和为 0 的状态为必负状态，Nim 和不为 0 的状态为必胜状态。

证明

根据必胜状态和必负状态的定义，我们只需证明：

1. 没有后继状态的状态，满足 \(S=0\)。
2. 对于 \(S\ne0\) 的状态，至少有一种操作使得后继状态 \(S=0\)。
3. 对于 \(S=0\) 的状态，没有一种操作使得后继状态 \(S\ne 0\)。

证明如下：

1. 没有后继状态的状态，\(a_1=a_2=\cdots=a_n=0\)，则 \(S=0\)。
2. 对于 \(S\ne 0\) 的状态，考虑操作 \(a_i\) 变为 \(a_i'\) 可以满足条件。则 \(S\oplus a_i\oplus a_i'=0\)，即 \(a_i'=a_i\oplus S\)。
   由于 \(S\ne 0\)，因此考虑 \(S\) 的最高位的一位 1，根据异或的定义，有奇数个 \(a\) 这一位为 1，对于这一位为 1 的 \(a_j\)，一定有 \(a_j\oplus S<a_j\)，则操作 \(j\) 可以使 \(S'\) 为 0。
3. 对于 \(S=0\) 的状态，根据异或的定义，其中一个 \(a\) 改变则 \(S\) 也会改变。

SG 函数

定义：

1. 对于没有后继状态的状态 \(x\)，\(SG(x)=0\)。
2. 对于状态 \(x\) 和它的所有后继状态 \(y\)，\(SG(x)=mex(\{SG(y)\})\)。

其中 \(mex(S)\) 表示集合 \(S\) 中最小没出现过的非负整数。

性质：\(SG(x)=0\) 时，\(x\) 为必败状态；\(SG(x)\ne 0\) 时 \(x\) 为必胜状态。

证明

根据必胜状态和必败状态的定义，我们只需证明：

1. 没有后继状态的状态满足 \(SG=0\)。
2. 对于后继状态存在 \(SG=0\) 的状态，它的 \(SG\ne 0\)。
3. 对于后继状态没有 \(SG=0\) 的状态，它的 \(SG=0\)。

根据 \(SG\) 的定义，这三点都是显然的。

SG 定理

对于由 \(n\) 个有向图游戏组成的游戏，这个游戏每次操作可以选择一张图操作一次。

若当前每张图的状态为 \(s_i\)，当且仅当 \(SG(s_1)\oplus SG(s_2)\oplus\cdots SG(s_n)\ne 0\) 时，先手必胜。

证明

我们可以把第 \(i\) 堆石子有 \(SG(s_i)\) 个，由于 \(SG(x)=mex(\{SG(y)\})\)，则 \(SG(s_i)=x\) 可以转移到所有的 \(SG(s_i')=y,0\le y<x\)，这符合 Nim 游戏的要求，于是可以用 Nim 和来解释。