小谈博弈论（公平组合游戏篇）

0x40119 · 2023-07-12 20:42:52 · 个人记录

（观前提示：本人的语言风格偏啰嗦，图也比较少，请多见谅）

本篇为公平组合游戏篇。

总集篇在这里：小谈博弈论（总集篇）。

在最开始，我们要做的第一件事，是对公平组合游戏这个概念先下个定义：当一局游戏满足以下条件时，我们就称其为公平组合游戏：

（1）、游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；

（2）、任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；

（事实上，这也是大部分棋类游戏都不是公平组合游戏的原因之一：双方所能做出的决策是与他们自己有关的，如围棋中黑方不可能走白子）

（3）、游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

接下来，是一些经典的例子：

【1】、Nim游戏：最经典的博弈论游戏之一。

有n堆物品，每堆有a_i个，两位玩家轮流选择一堆，取走这堆中的任意个物品，但是不能不取（否则这游戏就会变得有亿点点长）。取走最后一个物品的人获胜。

虽说是玩游戏，可是没人愿意输。这时就需要能快速判断当前状态是否对你有利。此时，我们把先手（就是当前状态下的决策方。注意，先手是会改变的，当轮到你做决策时，你是先手，当轮到对方决策时，对方就是先手）一定能赢的状态称为先手必胜状态，先手一定会输的状态称为先手必败状态。

接下来，让我们画一张图（叫做博弈图）来表示可能发生的状态：

以三堆物品，每堆分别有两个，一个，一个为例，用（i,j,k）表示三堆分别为i个，j个，k个的状态。

（图源自oi-wiki，图中状态不完整）

通过这张图，相信各位一定看出了些端倪。事实上，前人已经为我们总结出了三条定理：

定理1：没有后继状态的状态为必败状态；（显而易见，此时先手已经没得取了）

定理2：当且仅当一个状态的后继状态中至少有一个是必败状态时，该状态是必胜状态；（你只需要让当前状态变成让你的对手必败的状态就行了）

定理3：当且仅当一个状态的后继状态全都是必胜状态时，该状态是必败状态。（显然，这意味着无论你怎么决策，对你的对手而言都是必胜的）

但还是好复杂呀！难道每次玩Nim游戏都必须换一张图吗？要是有很多堆，每堆的物品数量又很大，这岂不是要画到猴年马月了？

没关系，前人还有一招：Nim和。

我们定义，一个状态的Nim和等于当前状态下，每堆物品数量的异或和。

当且仅当一个状态的Nim和为零时，该状态为必败状态。

（还是好麻烦。。。毕竟我们大家没有那么强大的计算能力，但这已经比画图好多了）

看到这里，就有人要发问了：为什么游戏的胜负会和异或有关嘞？

事实上，证明这个它是正确的并不难。主要是证明用异或计算时，结果与前文提及的三个定理是一致的。

定理1：没有后继状态的状态在Nim游戏中只有一个：全都为0。0与0异或，结果当然是0。

定理2：假设有一个状态，其Nim和为0，那么在改变这个状态时，就要改变一堆物品的数量，使得其Nim和不为0，此时根据异或的运算法则，可以得到这堆物品改变后的数量就是改变前的数量与改变前的Nim和的异或值。此时我们就可以通过操作保持自己必胜，而对手必败。

(严谨点的证明：假定我们把第i堆的物品数量从a_i个变为a_i'个。

改变前a_1⊕a_2⊕a_3⊕……⊕a_n=0，

得a_i= a_1⊕a_2⊕a_3⊕……⊕a_{i-1}⊕a_{i+1}⊕a_{i+2}⊕……⊕a_n⊕0= a_1⊕a_2⊕a_3⊕……⊕a_{i-1}⊕a_{i+1}⊕a_{i+2}⊕……⊕a_n；

改变后，a_1⊕a_2⊕a_3⊕……⊕a_n=k，

得a_i'= a_1⊕a_2⊕a_3⊕……⊕a_{i-1}⊕a_{i+1}⊕a_{i+2}⊕……⊕a_n⊕k；

得a_i' =a_i⊕k。)

假定k在二进制下的最高位1是第d位，由异或的定义可以知道，此时一定有奇数个ai在二进制下第d位为1。这些a_i也一定满足a_i>a_i⊕k，也就是说，我们是在减少而非增加那一堆的数量。因此，这一操作是合法的。

定理3：证明方法和定理2相似，假设有一个状态，其Nim和为0，那么在改变这个状态时，就要改变一堆物品的数量，使得其Nim和仍为0，此时根据异或的运算法则，可以得到这堆物品改变后的数量与改变前的数量相等，而这违反了游戏规则。因此不存在合法的操作，使得当前游戏连续两轮为必胜状态。下一轮是必胜状态，前一轮就只能必败了。

(严谨点的证明：还是假定我们把第i堆的物品数量从a_i个变为a_i'个。

改变前，a_1⊕a_2⊕a_3⊕……⊕a_n=0，

得a_i= a_1⊕a_2⊕a_3⊕……⊕a_{i-1}⊕a_{i+1}⊕a_{i+2}⊕……⊕a_n⊕0= a_1⊕a_2⊕a_3⊕……⊕a_{i-1}⊕a_{i+1}⊕a_{i+2}⊕……⊕a_n；

改变后a_1⊕a_2⊕a_3⊕……⊕a_n=0，

得a_i'= a_1⊕a_2⊕a_3⊕……⊕a_{i-1}⊕a_{i+1}⊕a_{i+2}⊕……⊕a_n⊕0= a_1⊕a_2⊕a_3⊕……⊕a_{i-1}⊕a_{i+1}⊕a_{i+2}⊕……⊕a_n；

得a_i'=a_i。故该操作不合法。)

到这里，三个定理就证完了，可见，用异或的结果来判定胜负是有道理的。

【2】、有向图游戏：SG函数简介。

有向图游戏可以作为大部分公平组合游戏的抽象模型。

有向图游戏，正如其名，是在一个有向无环图中进行的。在这张图中，只有一个起点，一个棋子，两位玩家轮流沿着图上的有向边移动棋子，没法移动的一方输。 还是那句话，没人愿意输，那么有向图游戏有什么必胜策略吗？

答案当然是肯定的。不过在介绍必胜策略之前，要先了解一些有关概念。

首先，定义一个集合A的mex函数是指不属于A的最小自然数，用数学语言表述就是：

例如，mex（{0,3,6,7,9}）=1，mex（{1,2,3}）=0

对于游戏中的某个状态x以及它的所有k个后继状态y_1,y_2,y_3,......,y_n定义SG函数：

对于没有后继节点的节点，我们定义其SG函数的值为0。

然后，就是大家期盼已久的必胜策略啦：

_对于由n个有向图游戏组成的组合游戏，设当前的总状态为s，其中每个有向图游戏的状态分别为s_1,s_2,s_3.......s_n,则当且仅当SG(s_1)⊕SG(s_2)⊕SG(s_3)⊕......⊕SG(s_n)的值不为0时，该状态是先手必胜状态，同时，这个值也是这个组合游戏的状态s的SG值。_

这个定理叫做Sprague-Grundy定理（注1），简称SG定理。

为什么是这样呢？

先假设对于总体的某个状态x，其每个游戏当前的状态为s_1,s_2,s_3,......,s_n。

那么很显然，当SG(s_1),SG(s_2),SG(s_3),......,SG(s_n)都为零时，是符合SG定理的。因为此时先手没法操作了。

接下来只要证明对于其它游戏状态，其每个游戏当前的状态s_1,s_2,s_3,......,s_n符合SG定理即可。

前文提过，“有向图游戏可以作为大部分公平组合游戏的抽象模型。”，那么，我们也可以用其它的公平组合游戏来模拟有向图游戏。在这里，我们把每一个总状态看作每堆物品数量分别为s_1,s_2,s_3,......,s_n的Nim游戏。

对于某个状态xi，就像是在Nim游戏中取走物品一样，在进行移动时，一定是向着SG值减小的方向移动的。

不过，我们也不能排除在某个时刻，一个状态会移到一个SG值比它大的状态。

有人马上就要问了：那不就相当于在放物品进去吗？这种不合法的情况也能像其它情况一样计算吗？

答案是可以的。我们需要注意这么一个事实，就是这样的情况并不会无限制地进行下去，毕竟SG值最终一定会变为零的。偶尔出现了这样的情况，是不会影响我们用异或来计算的。别忘了，我们的根本目的是通过取物品让异或和从非零变成零的，即使有物品放进去，我们也是可以取走那部分物品恢复原来的状态的。因此移到SG值较大的状态对整个游戏不能说是影响巨大吧，至少也可以说是聊胜于无了。

综上，我们是可以像Nim游戏一样，通过异或的方式来判断胜负的，而对于胜负的判断，则很显然应该与Nim游戏一致了。至此，我们可以下结论了：SG定理是正确的。

最后，简单介绍一些例题。 关于Nim游戏，在洛谷上，主要有以下几个题目：P2599 [ZJOI2009] 取石子游戏 P3235 [HNOI2014] 江南乐 P7490 「Stoi2031」蒲公英的约定（vol.1） P7491 「Stoi2031」蒲公英的约定（vol.2）等等。各位可以自行挑战。这些题码量并不多（跟树状数据结构之类的相比真的很少），只要掌握了以上内容，想要AC还是比较容易的。（其实也是我懒得上代码了）

在洛谷以外，还有蓝桥杯的小明的游戏1,AcWing 891、892、893和894，LeetCode 292等等。（其中AcWing891,和LeetCode 292是没有背景的纯粹的Nim游戏模板题）

关于有向图游戏，则有 P2575 高手过招，HDU-1524 A Chess Game（HDU的题目洛谷上都没有），Codeforces Round#406(Div. 2)C.Berzerk（洛谷上依旧没有）等等。

【3】.稍微介绍一下其他公平组合游戏

①．巴什游戏：有些像Nim游戏，不过只有一堆物品，共n个，规定每次最少取一个，最多取m个，取走最后一个物品者胜。它有一个我们比较熟悉的变相玩法：报数。例如两人轮流报数，每次至少报1个，最多报3个，报到30的胜。

②．威佐夫游戏：还是取物品，现在有两堆物品，数量任意，可以不同。两个人轮流取石子。有两种不同的取法，每次选择一种：一种是在其中任意一堆中取走任意多的石子；另一种是在两堆中同时取走相同数量的石子，取走最后一个物品者胜。

③．Chomp游戏：也可以用取东西来理解。有一个n×m的棋盘，每个格子上有一件物品。两人先后进行操作，每次选择一个点，取走以该店作为左上角的极大子矩形中的所有物品。取走（1,1）中物品者输。

............

好了，公平组合游戏到这里也就告一段落了。如果还想了解反常游戏及一些其它的经典博弈论问题，请移步其它游戏篇：小谈博弈论（其它游戏篇）

关于本文中没有提及的公平组合游戏，还请各位读者自行了解。

注释：

注1.关于SG定理，也有的地方认为SG(s)=SG(s1)⊕SG(s2)⊕SG(s3)⊕......⊕SG(sn)是SG定理，此处采用的是oi-wiki的说法