博弈论

· · 个人记录

博弈论

NIM游戏及几个经典模型

经典NIM游戏

给定 n 堆物品，第 i 堆物品有 A_i 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可以一堆取光，但不能不取。取走最后一件物品则获胜。两人都采取最优策略，问先手能否获胜。

结论：对于 Nim 游戏的一个局面 (A_1,A_2,\ldots,A_n) 来说，先手必败当且仅当 A_1 \oplus A_2 \oplus \ldots \oplus A_n=0。

证明：凡是异或和非 0 的都可以通过一次操作变为异或和为 0 的，因此可以归纳证明。

阶梯模型

有 n 层阶梯，编号 1\dots n，每层阶梯上有一些石子。

两个玩家轮流操作，每次操作可以将第 i 层阶梯上若干(至少一个)石头放到 i-1 层阶梯上，第 0 层阶梯即为地板。

将最后一颗石头从阶梯移到地板上的玩家胜利。

不难发现，所有偶数阶梯都等价于垃圾桶。若一方尝试将偶数阶梯中的石子移出(至奇数阶梯)，下一个人只需要紧跟着把这些石子丢到下一个(偶数)阶梯即可，最终会到达地板。这个过程中，先后手是不会转换的。

接下来考虑奇数阶梯，一步就可以把任意多的石子丢进垃圾桶，实际上就等价于 NIM 问题。

例题：SDOI2019移动金币，洛谷P2575高手过招

翻硬币模型

结论：整个游戏的 SG 函数相当于所有反面硬币的 SG 函数的异或和，而位于 x 位置的 SG 函数有规律：SG(x)=lowbit(x)

例题：SDOI2016硬币游戏，CF494E sharti

斐波那契NIM游戏

有 n 枚石子。两位玩家定了如下规则进行游戏：

  • 第一次取石子时可以取走任意多个；
  • 接下来，每次至少要取走一个石子，最多取走上一次取的数量的 2 倍。当然，玩家取走的数量必须不大于目前场上剩余的石子数量。
  • 取走最后一块石子的玩家获胜。

结论：先将 n 写成齐肯多夫表示，即用斐波那契数表示且没有相邻两个都是 1，则先手每次取最低位的 1 即可获胜。

例题：SNOI2020取石子游戏

其他典型博弈

威佐夫博弈

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

结论：当且仅当两堆石子的数量构成黄金比的时候后手获胜。

证明

二分图博弈

在二分图上，两人轮流指定下一步去哪个点，不经过重复的点，无法指定的人输，问谁赢？

结论：当一个点在所有最大匹配的方案中（少了这个点无法最大匹配），那么先手必胜。

证明：后手不可能选到非匹配点，如果后手选到一个非匹配点，设路径为 S_1\rightarrow S_n，那么把现在的匹配换成 S_2\rightarrow S_n，匹配数不变但不包含 S_1，与最大匹配一定包含 S_1 矛盾。

扩展到无向图的情况：不指定起点，则有完美匹配后手必胜；否则结论与上面一样。

树（图）上删边博弈

在一棵树/图上钦定一个根，每次可以删去一条边，若删边后某部分与根不连通则一并删去，不能操作者失败，问谁赢？

结论：叶子的 SG 是 0，其他点的 SG 是所有儿子节点 +1 后异或起来。

证明：考虑往一个子树顶上加一条边是什么意思，就是对于子树内的状态转移 DAG ，加一个点 T, 然后对原来的每个点，加一条到 T 的边，容易归纳说明每个点的 SG 都会增加 1。该思路在其他题目中也可以使用。

图的情况：把所有偶环缩成点，所有奇环缩成一个点和一条边（只连他自己那个点），然后当成树来做。

SG函数

约定终止态的 SG 函数值为 0。

定义 mex(S) 为集合 S 中最小的未出现的自然数。

设 G 能转移到的集合为 T_G，则定义 SG(G)=mex{SG(V):V\in T_G}

性质：SG(G)=0 为必败态，否则为必胜态。

SG和

考虑两个人同时面对多个游戏，但每次只能操作其中一个。则 SG(A+B)=SG(A)\oplus SG(B)，NIM游戏的原理也可以这么解释。

推SG函数的例题：HNOI2007分裂游戏，CF1149E

反SG-游戏

即最后一步不能走的人胜利的游戏。

有以下 SJ 定理：对于任意一个 Anti-SG 游戏，如果规定当局面中所有单一游戏的 SG 值为 0 时，游戏结束。则先手必胜当且仅当：

1.游戏的 SG 函数不为 0 且游戏中某一个单一游戏的 SG 函数大于 1；

2.游戏的 SG 函数为 0 且游戏中没有单一游戏的 SG 函数大于 1。

例题：SHOI2008小约翰的游戏

对抗搜索与其他技巧

对抗搜索&DP

在一个竞争的环境中，双方通过竞争实现相反的利益，一方最大化这个利益，另一方最小化。

定义合适的状态后，先找到必败态，然后通过记忆化搜索的方式实现，如果当前是必胜态就要在所有后继为必败态的结果中取 \max，否则在所有后继状态中取 \min。

例题：CQOI2013棋盘游戏，九省联考2018一双木棋

决策包容性

如果一个状态能直接到达他后继状态的所有后继状态，在该状态是一个必胜态。

例题：ARC137C

建立模型

通过建模把原问题中复杂的操作转化为图形化的，或是易于处理的操作。

例题：AGC002E

通过建模把其他问题转化为博弈论问题。

例题：AGC043C