VG 的博弈系列学习笔记（3）：谈谈 SG 函数与 SG 定理及其若干拓展

· · 个人记录

这篇文章有一些不足之处，但是由于 VG 现在比较没有时间也比较咕，所以有可能会比较少改动，但是最终会修改好的（）

有关下文中内容

后继状态：操作一次能达到的状态。

终态：没有合法操作的状态，亦即没有后继状态的状态。

多堆游戏的子游戏表示一个单堆游戏。

符号 \oplus 表示按位异或。

本文中对 SG 函数值的讨论限制在非负整数范围内。

下文主要参考了贾志豪大神的集训队论文。

正文

SG 函数（Sprague-Grundy函数）是解决很多博弈论问题的关键。一个游戏状态是必败状态当且仅当该状态 SG 函数值为 0。

现在有一个前提条件：游戏的每次操作只能改变单个子游戏的状态，不能操作者败。

单个游戏状态（即 Nim 游戏中的一堆石子一类）的 SG 函数的定义为 \operatorname{SG}(i)=\operatorname{mex}{S_i}，其中 S_i 是这个游戏状态的后继状态 SG 函数值的集合。

说完单个游戏状态的 SG 函数，那么由多个不相交的子游戏组合成的大游戏的 SG 函数又怎么计算呢？那么就讲到了重头戏—— SG 定理。

SG 定理的内容如下：

一个游戏的 SG 函数值等于其子游戏的 SG 值的异或和（即全部 SG 值按位异或后得到的值）。

下面来证明一下这个定理。

首先，有两个博弈论中很重要的概念：必胜状态至少有一个后继状态是必败的与必败状态的所有后继状态都是必胜的。

我们先证明 SG 值为 0 的状态的后继状态 SG 值都不为 0。

对于一个 SG 值为 0 的状态，假设我们改变其中的第 i 堆而获得一个后继状态，设第 i 堆的 SG 值为 s。则由 SG 函数的定义，有 s 不曾出现在其后继状态的 SG 值集合里，亦即该堆的任意一个后继状态 SG 值均不为 s。所以经过操作它的 SG 值必然改变，设改变后的 SG 值为 t。则整个游戏的 SG 值将变为 0 \oplus s \oplus t=s \oplus t \neq 0，得证。

我们再证明 SG 值不为 0 的状态至少有一个后继状态 SG 值为 0。

由 SG 函数的定义可知比一个游戏状态的SG值小的所有值都在该状态后继状态的 SG 函数值中出现过。换句话说，每个游戏状态都可以通过一次操作变成 SG 函数取任一小于原状态 SG 值的状态。

现在假设整个游戏的 SG 值为 x，设 x 用二进制表示后为 1 的最高位为第 t 位。由于异或和第 t 位上为 1，所以必定有一个子游戏的 SG 值第 t 位为 1，设为第 i 项。用这一项的 SG 值异或 x，得到的值在比第 t 位高的位上不变，在第 t 位上变成 0，所以必然小于原来的 SG 值。根据刚刚证明的结论，这肯定是第 i 项的一个后继状态，必然可以达到。此时整个游戏的 SG 值为 x \oplus x=0，得证。

由于每个子游戏都是没有后继状态即 SG 值是 0 的游戏是终态，为必败状态，所以可以推出 SG 值为 0 的是必败状态，其余是必胜状态。

这样我们就证明了 SG 定理。

接下来我们来看一些 SG 函数和 SG 定理的具体应用。

最著名也是最简单的就是 Nim 游戏了。递推可以得到，单堆 Nim 游戏的 SG 函数值就是该堆石子个数。所以 Nim 和就是各堆石子个数的异或和。

作业练习题：

P2197 Nim游戏

ACM/ICPC Live Archive 5059/UVA 1482 Play with Stones

有关考场上应用方式

面向数据编程可以知道，通常打个暴力推一下SG函数再找规律或优化思路减少时间复杂度再预处理+输入后直接异或就行了。

Part 3 谈谈阶梯 SG， k-SG， anti-SG 与翻棋子游戏

阶梯SG

有若干级阶梯，每级阶梯上有一个单个游戏，每次可以对一个阶梯操作并将操作中失去的东西丢到下一级阶梯上。

应用范围

对于单个游戏状态，若操作集合可逆（即上一级丢给这级的东西在这级可以再丢掉），则可以应用。

解法

令最低级阶梯为第 0 级，对奇数级阶梯上的游戏 SG 值取异或和，为 0 先手必败，否则先手必胜。

解法证明

显然终态只有第 0 级的 SG 值不为 0，满足上述必败条件。

如果满足必败条件，则若我们对某个奇数级阶梯操作，则该阶梯的 SG 值会改变，其他奇数级阶梯的 SG 值都不会改变，此时奇数级阶梯的 SG 值异或和会改变，即不为 0。若我们对某个偶数级阶梯操作，那么因为操作可逆，故任意阶梯操作一次后它的下一级阶梯操作前的状态是操作后状态的后继状态，所以该阶梯下一级阶梯，即一个奇数级阶梯，的 SG 值会改变，同上可证操作后奇数级阶梯的 SG 值不为 0。

如果满足必胜条件，则我们就把奇数级当作 SG 定理中的游戏，直接扔给偶数级就好了。

k-SG

有N堆石子，每次可以从不超过k堆中按规定规则各取一些石子，不能操作者败。

解法

解法适用范围为所有 SG 值为 0 的状态都无后继状态的游戏。

首先将每堆石子的 SG 值设为 s_i。

将所有 s_i 二进制第 j 位上的数相加得到 r_1,r_2,\dots,r_J（J 为所有 s_i 二进制最高位的位数），如果 \forall i \in [1,J] 有 r_i \equiv 0\pmod{k+1}，那么先手必败；否则先手必胜。

如： k=3，每堆石子 SG 值为 1,2,3,4,5,6,7，即 (001)_2,(010)_2,(011)_2,(100)_2,(101)_2,(110)_2 与 (111)_2，则有 r_1=4,r_2=4,r_3=4，故此时先手必败。

特殊情况 1-SG 的解法与普通 SG 定理没有区别。

解法证明

如果所有的 r_i 都为 0，则一次操作肯定会使得某些数位上的值改变。又因为一堆石子每位上都是 0 或 1，所以变动的绝对值不会超过 k。因此操作结束后该位置上的 r_i 必不能为 0。

如果有一些 r_i 不为 0。则肯定有 r_i 堆石子的数量二进制表示该位上为 1。此时我们只要从高到低扫每一个二进制位，选择 r_i 堆该位上为 1 的石子，再使每堆石子的个数 \operatorname{xor} 2^i，此时这些堆的石子个数会变少，而 r_i 会变为 0。

但是有一个问题：如果这样选出来的石子堆数超过了 k 怎么办？

此时我们知道：如果一个数的高位从 1 变成 0，则其低位无论怎么变化，这个数还是变小。

于是我们每次只要尽量优先选择有高位由 1 变为 0 的数，再选择该位上为 1 的数，这样由于每个位置要选的数不到 k+1（r_i < k+1）个，所以总共要选的堆数不会超过 k 堆。

又因为终态各个 r_i 均为 0。所以我们得到了解法。

anti-SG

按照游戏规则，当某个人面临的所有子游戏的 SG 值都为 0 时获胜。

解法（SJ 定理）

解法适用范围为所有 SG 值为 0 的状态都无后继状态或有一个后继状态 SG 值为 1 的游戏。

即 Sprague-Grundy-Jia Zhihao 定理（在缩写时 Grundy 被吃了，不像 KMP 一样都列上了， Grundy 真可怜

当且仅当所有子游戏的 SG 函数均 \le 1 且游戏的 SG 值为 0 或者有一个子游戏局面的 SG 值 >1 且游戏的 SG 值不为 0，先手必胜。

解法证明

所以我们可以直接把 SG 值为 0 的子游戏看作没有。接下来，我们还是用老套路——分必胜必败情况讨论。

如果当前状态必胜，那么若全部子游戏的 SG 值均 \le 1，显然直接把一个 SG 值为 1 的子游戏 SG 值变为 0 就可以了。

如果有 SG 值 >1 的子游戏，如果只有一个子游戏的 SG 值 >1，我们只要分 SG 值为 1 的子游戏个数的奇偶性操作把这个子游戏的 SG 值变为 0 或 1，必定可以通过一次操作使游戏局面变为奇数个 SG 值为 1 的子游戏和一堆相当于没有的 SG 值为 0 的子游戏。

否则我们只要像 SG 定理证明中让整个游戏的 SG 值变为 0 即可。

再看看必败状态。若全部子游戏的 SG 值均为 1。则无论如何操作，必定变为偶数个 1 或偶数个 1 和一个 >1，显然均满足必胜条件。

否则进行一次操作后整个游戏 SG 值必定不为 0，又因为游戏 SG 值为 0 时不可能只有一个子游戏 SG 值 >1，所以操作后必定有子游戏的 SG 值 >1，为必胜状态。

终态显然满足必胜条件。证毕。

问题转化

贾志豪大神在论文里提到了一个这样出题的想法：如果有一个开关，某位游戏者可以在某个时刻按下这个开关，接下来的游戏从其对手开始操作，但是按下开关者只能在其对手上次操作的堆里面进行操作，不能操作者败（按下开关也算一次合法操作，但是开关只能按一次）。下面证明这个问题和 Anti-SG 胜负情况相同。

显然若 Anti-SG 中的必胜方在游戏 SG 值全为 0 时按下开关则无论对手如何操作他都能够将每堆游戏的 SG 值均保持为 0。若必败方为了不让这种情况发生，则他必然在一个 SG 值不全为 0 时按下开关，那么每次对方可以选择一个 SG 值不为 0 的子游戏操作使其 SG 值变为 0，此时只有无法继续操作和后继状态 SG 不为 0 两种情况，归纳即证他仍然必败。

翻棋子游戏

在一些棋子中，有的正面朝上，有的反面朝上，每次操作可以翻其中一颗正面朝上的棋子，会带动一些其他棋子的组合翻面。

解法

将每颗棋子翻面后可能影响的其他棋子组成的游戏作为一个后继状态，对每颗棋子求 SG 值，然后求所有正面朝上的棋子 SG 值的异或和，为 0 先手必败，否则先手必胜。（如果感觉不够清晰可以结合 P3179 及其题解理解）

解法证明

很显然，一颗棋子翻面相当于整个游戏的 SG 值异或了它的 SG 值。那么，根据后继状态的定义，我们可以发现我们将一颗棋子翻面后，相当于整个游戏的 SG 值异或了它的 SG 值又异或了它的某个后继状态的 SG 值，和 SG 定理中游戏的一次操作本质相同，故解法也本质相同。

一些有趣的练习题

阶梯 SG：P2575,P3480

k-SG：P2490

Anti-SG：P4279

翻棋子游戏：P3179

附上P2575题解，P2490题解和P3179题解

写这篇文章的想法和动力都来自我在看刘汝佳、陈锋《算法竞赛入门经典训练指南》，即大家所熟知的刘汝佳蓝书时对博弈论的入门的兴趣的兴起，也有一些部分参考了此书。后来也逐渐接触了其他资料，主要是贾志豪的论文，对我有很大帮助。

如果有好的练习题希望和大家共享学习资源欢迎私信我，我可以在题单里与大家共同分享。

如果您认为有参考您的博客且没有注明，可以私信找我，如果重复度较高，我也可以补充上您的博客以保护您的版权（广告位招租。