博弈论入坑导论

如果你对博弈论感兴趣，并且对自己的英文水平有很自信，并且有大把大把时间，可以读一读”GAME THEORY”–Tomas S.Ferguson
经过我 40 分钟的阅读，我认为该教材写的十分详细，但是由于内容较多并不适合作为竞赛学习的资料，不过大家按自己的实际情况随便读一读未尝不好。
教材下载：GAME THEORY–Thomas S.Ferguson

1. 定义

这篇文章所讨论的游戏有如下几个性质。

• 1. 游戏有两个玩家
• 2. 游戏总状态数一般有限，且有唯一的初始状态
• 3. 对每个状态，两种玩家可行的决策完全相同
• 4. 两个玩家交替执行决策
• 5. 无论游戏怎样进行，总步数有限
• 6. 游戏最终达到一种状态 (终态)，两玩家均不能继续操作，这时分出胜负 (一般为不能操作者输)

这也是我们所说的 “组合游戏”。

所谓状态，就是一个游戏局面。比如跳棋中每个棋子的位置决定了一个游戏局面，如果两个局面不同，那这两个局面就对应这不同的状态。

根据性质 4，我们可以知道组合游戏的状态一定不存在环，所以我们可以认为所有可达到的游戏状态构成一个 DAG。

我们对这个 DAG 上的每一个状态给出如下定义：

• 如果这个状态下的先手可以保证自己绝对不会输，这个状态叫必胜态，简称 P (previous)
• 如果这个状态下的后手可以保证自己绝对不会输，这个状态叫必败态，简称 N (next)

接着，我们根据这两个定义继续给出必胜态和必败态的判定方法：

• 终态为给定的必胜/必败态
• 可以转移到必败态的状态是必胜态
• 只能转移到必胜态的状态是必败态

2. 游戏之母：Nim Game

为什么

为什么叫 Nim 游戏为游戏之母呢？因为所有组合游戏都可以相互规约，而我们不妨将所有组合游戏都规约为最简单的 Nim 游戏。

只要知道了 Nim 游戏必胜的判定方法，我们就能通过这种规约得到所有组合游戏的必胜判定方法。当然，为了简单，我们这里谈到的组合游戏都是 “第一个不能操作的人输” 的游戏。要注意：如果这个定义改成 “第一个不能操作的人赢”，先手和后手的获胜并不是简单的交换一下，因为必胜态的定义不是对称的。

规则

• 初始有 n 堆石头，每堆 $x_i$个石头
• 两人轮流取石子，第一个不能取的人输
• 每个人只能在一堆中取至少一个石子，可以将整堆取完

判定

令 $S=X_1\oplus X_2 \oplus X_3\cdots\oplus X_n$

其中 $X_i$为第 i 堆的石头数的二进制表示。

若 S 为 0, 则先手必败，反之先手必胜。对于任何一个状态该定理都成立。

证明

下面给出一种比较容易理解的证明。

当前 S 为零，如果后手可以采取一种策略，无论先手如何操作，S 始终为 0，则后手一定可以达到所有石子为 0 的状态，这时后手胜利了。因为无论先手怎么操作，先手只能把 S=0 变成非零的数，而非零的数意味着场上还有石子，因此先手不可能胜利。

下面我们就证明，当 S 一开始为 0 的时候，后手的确存在一种策略，将 S 保持为 0。证明了这个，我们还可以知道，当 S 一开始不为 0 的时候，先手可以把非零变成 0，这样先手就占据了主动，最终赢得游戏。

如果先手将 S 变成了非 0 的数，假设此时 $S=\overline{1X}$，那么至少有一堆石子个数的最高位和这个数一样，为 1。假设这堆石子有 Y 个。那么我们就在这一堆中取石子，使得这一堆的最高位变成 0，同时剩余位与其他堆的异或为 0。这是一定可以做到的。因为最高位变成 0 后

即一定存在 $Z\leq Y$使得 $S\oplus Y\oplus Z=0$，即把 Y 用 Z 替换之后，S 转而变成了 0。

证明完毕。

3.SG 函数

移石子游戏 1.0

现在考虑一个看似比较好玩的游戏：移石子游戏。

• 给出一个 DAG，DAG 中某个点上有一个石子
• 两玩家交替沿 DAG 的有向边移动石子
• 最先不能移动石子的玩家失败

这个游戏有着十分强的代表性。

首先，这个 DAG 上的节点可以看成任何一种组合游戏的所有状态，而所有状态之间又存在单向转移。而石子可以看成当前状态。这样，所有组合游戏都可以抽象为移石子游戏。下面，我们将把移石子游戏抽象为 Nim 游戏。

mex 函数 & SG 函数

为了解决上面这个问题，我们首先定义这样一个函数，这个函数相当于是移石子游戏 (也就是所有组合游戏) 和 Nim 游戏之间最直接的桥梁。

• 定义 $mex(S)$为集合 S 中第一个没有出现的自然数 (包含 0)
• 定义 $SG(X)=\mathop{mex}\limits_{X->Y}(SG(Y))$，其中所有终态由于没有后续状态，所以 SG 值为 0

于是，有定理称：一个组合游戏后手必胜当且仅当 SG(X)=0.

具体原因可以大致这样理解：mex 函数的功能类似于 Nim 游戏对某一堆去石子的逆操作。即：一堆石子可以变少为任意一个小于它本身的数，不能变多或不变。而类似的,SG 函数也表明一个状态可以转移到任意一个 SG 值小于它的状态。因此 SG 函数的值就是抽象的石子数。

所以，我们只要按移石子游戏中的拓扑序求每个状态的 SG 函数值即可明确每个状态的胜负情况。

移石子游戏 2.0

若有多个 DAG，每个 DAG 上有一个石子，游戏状态数的规模将会变得非常大，是每个 DAG 点数的乘积。但是类似于 Nim 游戏，我们只需要将每个石子在所在 DAG 上的 SG 函数值异或起来，将是整个” 移石子游戏 2.0“的 SG 值。

4. 整理

现在我们知道了如何快速 (当然也不是很快) 求一个组合游戏的任意一个状态的胜负情况。

• 对于一个大型组合游戏，由多个独立的子游戏组成，那么其 SG 值为子游戏 SG 值的异或
• 对于一个独立的游戏的一个状态 X,$SG(X)=\mathop{mex}\limits_{X->Y}(SG(Y))$
• 若一个状态 $SG(X)=0$则后手必胜
• 若一个状态 $SG(X)\neq 0$则先手必胜

5. 实践导论

世界上有许许多多的组合游戏。组合游戏，如果是非常有吸引力的游戏，一般状态数都很多，比如大到 $10^9$这个级别以上的比比皆是。如果每个组合游戏我们都只采用上文提到的做法，未免解决起来有点吃力了。

所以，现在的主要矛盾是：如何寻找到一个高效的直接判断胜负或通过求 SG 函数判断胜负的方法？

答案是：暂时不存在一个普适的方法。

但是并不意味着每个游戏我们都需要列出所有状态进行 Dp, 而是可以采用一些非常高级的方法去求解，那就是打表。除了这个，还有一些针对特殊游戏的特殊方法 (主要学习自”https://blog.csdn.net/kyleyoung_ymj/article/details/51494139″)：

• Bash Game
  • 每人最多一次取 m 个石子，其他规则同 Nim
  • SG(X)=X mod (m+1)
• Nim~K~ Game
  • 每个人最多从最多 K 堆石子中取出任意多个，其他规则同 Nim
  • 在二进制下将石子数每一位的 1 的个数累加，当每一位的 1 的个数均为 (K+1) 的倍数时后手必胜，反之
• X~K~ Game
  • 每个人最多在最多 K 个子游戏中操作
  • 同 Nim~K~游戏，在二进制下累加每个游戏 SG 函数值中每位 1 的个数，当每一位的 1 的个数均为 (K+1) 的倍数时后手必胜，反之。可以看成是在 $K+1$这个周期下的异或
• Misère Nim
  • 不能取的一方获胜，其他规则同 Nim
  • 当 SG 不为 0 且至少有一堆石子数大于 1，先手必胜
  • SG 为 0 且不存在石子数大于 1 的堆，先手必胜
  • 反之后手必胜
  • 以上三点又称 SJ 定理
• Staircase Nim
  • 每个人可以从某一堆取走若干个石子，放到前一堆中，第一堆取出的石子消失，其他规则同 Nim
  • 当且仅当奇数编号的石子异或为 0 时后手必胜
• Wythoff Game
  • 两堆石子，双方轮流从某一堆取走若干石子或从两堆取走相同数目的石子，不能取者输
  • 另一个题面是：双方在棋盘上轮流向左或下或左下移动一个皇后，不能移动者输
  • 利用棋盘我们可以发现，只有少数点后手必胜，这些点满足坐标：$(\lfloor n\cdot \frac{\sqrt{5}+1}{2}\rfloor,\lfloor n\cdot \frac{\sqrt{5}+3}{2}\rfloor)$
  • 每个点的横坐标对应第一堆石子，纵坐标对应第二堆石子，就是 Wythoff Game