博弈论 笔记

· · 算法·理论

天坑+1

巴什游戏

基础版本

一堆共 n 个石子，一轮可以取 [1,k] 个，取走最后的石子的人胜

当 (k+1)\mid n 时后手必胜，反之先手必胜

证明如下：

当石子个数是 k+1 的倍数时，无论先手怎么取，后手都能在先手取完后再取出一些石子使得两人取走的石子数是 k+1

到最后只剩 k+1 个石子时，那显然后手会最后取走石子

变式 1

即P4018 Roy&October之取石子

题意：

共有 n 个石子，每次都只能取 p^k 个（ p 为质数，k 为自然数，且 p^k\le 当前剩余石子数），取走最后一个石子赢

先手必胜的条件是什么?

如果 6\mid n 后手必胜，反之先手必胜

证明如下：

  1. 当 n\in[1,5]，先手显然可以一次取完

  2. 当 n\mid 6 时，因为一定不存在质数的幂次为 6 的倍数，所以先手拿不了 6 的倍数，后手只要不断使得剩余的石子 \mid 6，就可以保证先手拿不到最后的

变式 2

取石子的数量不是 [1,k] 的整数，而是在一个 \{a\} 中选

貌似并没有什么结论，但我们有一种类似于 DP 的方法可求解这种问题

我们定义 P-position ， 和 N-position 分别为刚走一步的玩家的必胜位置和下一个玩家的必胜位置

经过推理，有三条比较显然的性质

我们考虑掏出一张表

假设 a=\{1,3\},n=8

|rest|0|1|2|3|4|5|6|7|8|
------------------------
|N/P |P|N|P|N|P|N|P|N|P|

特殊规定当剩余石子为 0 时是 P-position (可视为因为没有石子所以下一个玩家无子可取)

发现没有？从小到大递推，对每个位置检查他可能的后继节点，当后继节点有 N-position 时，那表明有必胜策略，若没有，那么就是必败（或者说是下一个玩家必胜）

注意到这有循环节，Coding 可以 DP 也可以按周期算

尼姆游戏

基础版本

就是把巴什游戏扩展到多堆石头

有 n 堆石子，数量为 \{a_{1},\cdots ,a_{n}\}，一次可以从一堆中拿任意个，拿走最后一个的胜

若每堆石子的数量异或起来为 0 则后手必胜，反之先手必胜

我们把这个异或和定义为 Nim 和

证明过于鬼畜，抄一下白书（我觉得这个证明有点扯淡但是我也不会证明）

定理：当 Nim 和不为 0 则先手必胜，记此时为 N-position，若不为 0，则先手必败，记为 P-position

  1. 必定能够从 N-position 转换到 P-position。具体方法就是任选一堆石子，把其他的石子异或以来，如果值小于这一堆，就肯定能使得异或和为 0

  2. 进入 P-position 后，轮到后手，后手不管怎么拿绝对会使得异或和不为 0 ,因为异或和可以看成二进制每一位 1 的奇偶性，所以必败

  3. 游戏过程中若按上述步骤，就会在 N/P-position 之间交替转换，直到石子数为 0 ,即终止于 P-position

威佐夫游戏

是一种非常神奇的游戏

规则

有两堆石子，个数分别为 a,b，两种取法，一种是从一堆中任意取，一种是两堆中同时取走同样多个石子

必胜条件

假设 a<b，我们发现，当 a=\left \lfloor (b-a)\times \frac{1+\sqrt 5}{2} \right \rfloor 时先手必败

证明？不会

图游戏与 Sparague-Grundy 函数

又是个大坑

图游戏

给定一个 DAG ，在一个起点上放一个棋子，两个玩家交替移动这个棋子，无法移动的那个输

像巴什游戏和尼姆游戏这样的 ICG 问题都可以抽象成图游戏，把局势看成点，向它的后继局势连有向边即可

SG函数

我们定义一个节点的 SG 函数值为它的后继节点所有 SG 值里没有出现过的最小非负整数

就比如如果他 SG 子节点值有 0,2,3 ,那他的 SG 值就是 1

数学家们发现，当 SG 值为 0 时该点是 P-position，反之即为 N-position

应用

图游戏和 SG 函数结合可以在博弈论方面发挥强大的作用

由多游戏组合而得的‘多堆游戏’

以 1666：取石子游戏 为例

多堆石子，一次取的个数有限定，可以看成是由多个刚开始巴什博弈中的变式组成的游戏

因为石子一堆与另一堆之间并无区别，所以每个子游戏的 SG 函数值可以共用

不妨直接求出只有一堆时，石子数从 0 到 1000 时的所有 SG 值

那么总游戏的 SG 值就是所有子游戏（具体到每一堆）的 SG 值的异或和

若它为 0 ,那么先手必输，反之必胜

再以 1665：【例 3】移棋子游戏 为例

多个棋子看似难搞，但本质还是多游戏组合而来，一样可以用上面的方法

暴力求出每一个节点的 SG 值，然后看所有起点的 SG 值的异或和即可

为 0 则先手必输，反之必胜