Alioth_ 的博客

Alioth_ 的博客

博弈论一些结论

posted on 2020-05-11 11:06:29 | under 知识点 |

k倍减法游戏

有⼀个整数$S\ge 2$,先⾏者在S上减掉⼀个数x,⾄少是1,但⼩于S。之后双⽅轮流把S减掉⼀个正整数,但都不能超过先前⼀回合对⽅减掉的数的k倍,减到0的⼀⽅获胜。

考虑构造一个数列 满足数列上的数都必败 记为$a$ 另一个序列为$b$ 表示$a_1$到$a_i$可以表示出的最大数(比$a_{i+1}$小的) 那么有转移$$ a_{i+1}=b_{i}+1 $$

$$ b_{i+1}=a_{i+1}+b_{j} $$

其中$j$为满足$a_j\times k <a_{i+1}$的最大数

SG函数

没啥可说的 就是后继状态的$mex$ 注意多个独立游戏的和为$sg$的异或

N阶Nim游戏

就是每次可以选择$N$堆石子 每堆减少任意多个 其它不变

有结论 后手必胜当且仅当在每一个二进制位上 所有数这一位为1的个数是$N+1$的倍数 否则先手必胜

阶梯Nim

就是奇数段的异或和是否为0

翻硬币游戏

特征是翻的最右边的硬币一定是从正面翻到反面

有结论每个硬币独立 那么就是每个硬币的$sg$的异或和

例如每次只能翻连续不超过三个硬币 那么$$ sg_i=mex(0,sg_{i-1},sg_{i-1}xor\ sg_{i-2}) $$ 可以找规律

砍树游戏

一棵树 每次删掉一条边以及它的子树 不能操作的人输

有结论$x$节点的$sg$值等于所有儿子的$sg$值$+1$的异或和

Anti-SG游戏

即不能操作的人赢

则先⼿必胜当且仅当:

• (1)游戏的SG函数不为0且游戏中某个单⼀游戏的SG函数 ⼤于1。

• (2)游戏的SG函数为0且游戏中没有单⼀游戏的SG函数⼤ 于1。

Nim积

我们对于一些二维$Nim$ 游戏 可以拆分成两维单独的 $Nim$然后求 $Nim$ 积。

定义为$$ x⊗y=mex{(a⊗b)⊕(a⊗y)⊕(x⊗b),0≤a<x,0≤b<y} $$ 其中 $⊗$ 定义为 $Nim$ 积,⊕ 定义为异或。

由于$nim$积有分配律 我们可以把两个数的积拆成一些$2$的整数次幂之和的积

考虑求$2$的整数次幂的$nim$积 $2$的整数次幂又可以拆成一些$2^{2^k}$ 之积 那么对于两个相同的$2^{2^k}$ 它们的积等于$\frac{3}{2}\times 2^{2^k}$ 还有结论$2^{2^k}$和任意一个比它小的数的$nim$积等于它们之积

那么可以记忆化$O(log^2n)$解决 具体实现时两个函数互相调用 第一个求$2$的整数次幂中合并两个$2^{2^k}$的答案时要用到第二个也就是算任意整数的$nim$积的函数

这东西的应用 比如说二维的翻硬币游戏 两个边长只能分别从两个集合中选取 那么分别先求出一个点行的$sg$值和列的$sg$值 最后的值就是它们的$nim$积