博弈论相关知识及其应用
组合游戏
Nim游戏
有两位优秀的OIer玩取石子游戏，有n堆石子，每次都要选出一堆石子从里面取出任意正整数枚石子扔掉，直至某一人操作时无石子可取，该选手就输了。
简单的分析
假如只有3堆石子，数量分别是1、2、3，我们用(1, 2, 3)来表示这一初始状态。我们来试着枚举一下先手的操作：
- 先手拿完第一堆的1个石子，即转移至(0, 2, 3)。则对手会拿去第三堆的一个石子，变为(0, 2, 2)，这时，无论你对一堆做什么样的操作，对手都可以在另一堆做同样的操作，使得两堆石子总相等，最后输的一定是先手。因此这种情况，先手必输。
- 完全拿走第二堆或第三堆，即转移至(1, 0, 3)或(1, 2, 0)。我们发现对手仍然可以用类似1的策略使得其中两堆石子数量总保持相等，先手必输。
- 其他走法。(1, 1, 3)，对手会把第三堆拿空，又回到了上面的必输局面。(1, 2, 2)，对手把第一堆拿空，依然必输。(1, 2, 1)，对手把第二堆拿空，同上。
通过上面的讨论，我们已经枚举了先手下一步的所有可能操作，但是每种操作都必输，因此我们称(1, 2, 3)为一个先手必败态（简称必败态）。
对模型的抽象
我们给出一个对上面这种游戏模型的抽象，即我们讨论的满足下列条件的一类组合游戏：
- 有两个玩家，轮流操作。
- 游戏状态集合有限，且无论如何操作，都不会转移到一个之前出现过的状态。这一条保证了游戏不会无限继续下去。
- 无法进行合法操作者输。这一条保证了不会出现平局。
必胜态与必败态的性质
- 一个状态是必败态当且仅当它的所有后继是必胜态或它没有后继状态
- 一个状态是必胜态当且仅当它至少有一个后继是必败态
我们考虑利用这两条性质，对游戏局面之间的转移建立有向边，不难发现该图是一个DAG，可以通过反向拓扑排序递推出每个状态的胜败性质。
Nim和
解决一个Nim游戏的场面是必胜还是必败，可以通过对状态图的拓扑排序来完成，但是它的时间复杂度很高。有没有更加优秀的做法呢？
L. Bouton发现了一个非常美妙的定理：
定理 一个Nim游戏的场面 (x_1, x_2, \dots, x_n) 为必败态当且仅当 x_1 \operatorname{xor} x_2 \operatorname{xor} \cdots \operatorname{xor} x_n = 0 。这个异或起来的类似加和形式的东西，又被称为Nim和。
要想证明这个定理，也就是证明是否满足必胜态和必败态的性质。我们分别来入手：
- 没有后继状态的局面是必败态。没有后继状态的局面Nim和显然是0，满足这一条。
- 对于必败态，所有后继状态都必胜。换句话说，就是对于一个Nim和为0的状态，所有后继Nim和都非0。由于一次操作必须对局面做出改变，无论如何改变都会使改变后的Nim和非0，这一条也得到满足。
- 对于必胜态，一定存在一个后继状态必败。换句话说，就是对于一个Nim和非0的状态，存在后继Nim和为0。考虑对于当前状态Nim和K二进制中最高位的1，一定存在一堆石子X的二进制该位也是1，只需要把它拿成K xor X，Nim和便可以变为0，这一条也得到满足。
综上，这个定理是成立的。
SG函数与SG定理
组合游戏之和
假设有n个组合游戏G_1, G_2, \dots, G_n，可以定义一个新游戏G，在每个回合中，当前玩家可以任选一个子游戏G_i进行一次合法操作，而使其他子游戏的局面保持不变，不能进行操作的玩家输。这个新游戏G称为G_1, G_2, \dots, G_n的和。
如何判断一个组合游戏的和的局势是一个很复杂的问题，需要用到SG函数和SG定理。
SG函数
对于任意状态x，定义SG(x) = \operatorname{mex}\{ SG(x') \}。mex运算求出一个集合中最小未出现的自然数。x’是x的后继状态，所有后继状态的SG值构成了一个集合，而x的SG值就是这个集合的mex值。
显然，SG(x) = 0当且仅当x是一个必败态。
SG定理
定理 组合游戏和的SG函数等于各子游戏SG函数的Nim和。
我们来尝试用它解释一下Nim游戏。对于一堆个数为x的石子，可以视作单独的一个组合游戏，初始状态的SG值就是石子数x，这个可以脑补证明一下。因此对每一堆石子求异或和，就是整个Nim游戏的SG值，通过SG值我们就知道了胜败性质。
应用：阶梯博弈
题目描述
你有一个高度单调的阶梯，每一级上都放有若干石子，两个玩家，每一次操作可以把一个台阶的正整数个石子移到低一级的台阶上，无法操作（所有石子都在最低台阶上）的人输。求是否存在先手必胜策略。
题解思路
结论：这个游戏等价于奇数阶梯上的Nim游戏。
偶数阶梯对博弈不产生影响，最低级（0号）阶梯显然不影响，而如果对手将一个偶数阶梯上的石子移动到一个奇数阶梯上，我们可以原样再移到下一级偶数阶梯上，这对奇数阶梯上的博弈并无法造成影响。
我们考虑将奇数移动到偶数的操作视为丢弃，则Nim游戏的所有规律在此依然适用。
参考资料
- 《算法竞赛入门经典 训练指南》，刘汝佳，陈锋著，清华大学出版社，9787302291077
- [学习笔记] （博弈论）Nim游戏和SG函数 – CSDN博客
- 博弈论 SG函数 – CSDN博客
- 【P2197】nim游戏 – 洛谷
- 阶梯博弈算法详解（尼姆博弈进阶） – CSDN博客
