【数学】博弈论

更新于 2023-04-07 分类于 ACM ，数学阅读次数：本文字数： 3.4k 阅读时长 ≈ 3 分钟

几个典型的博弈论问题

博弈：每个人都会走当前最优策略，所以每个人都会尽量给对方创造必败态，给自己创造必胜态。

巴什博弈

定义

只有一堆物品，共 $n$ 个，两人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取完这堆物品的人获胜。

结论

$n\neq 0(\mod m+1)$ ，先手肯定获胜

证明

关于严格证明这里不多提，自己可以分析一下，每次给对手留剩 $m+1$ 的倍数，最后一轮自己一定获胜，所以就看第一次取，自己能否构建这个局势（剩下 $m+1$ 的倍数个物品），使得对手必输。每次后手走的时候都是 $x$ 个 $m+1$ 的局面，那么无论他怎么走，先手都可以使这个局面一直保持，最后一轮，后手一定拿不完，剩下的一定能一次拿完。

尼姆博弈

~~讲到这个不得不想起大一微积分课老师搞的课前小游戏。。。现在想想好尴尬。。。（如果同学看到要掉码了救命）~~

定义

有任意堆物品，每堆物品的个数也任意，双方轮流取物品，每次只能从一堆中取至少一个物品，取到最后一件物品的人获胜。

结论

把每堆物品数全部异或起来，若值为0，则先手必败，否则先手必胜。

证明

也是不严格证明，我们将每堆物品数异或起来为0这个状态称为必败态，顾名思义，这个状态下，谁取谁必败。因为当这个状态时，经过两人轮流取物，后者始终可以维持这个必败态，即A取完后，B一定可以取一个数，使得取完后每堆物品数异或起来仍为0。这样一直到最后一轮，B取完一定会使每堆数都为0，此时同样也是必败态（异或起来为0），这时B获胜，A面对所有堆都为0这个状态取，直接失败。所以当每堆物品数全部异或起来，若值为0，此时已是必败态，先手必败；若值不为0，则先手一定会取一个数使得每堆数异或起来为0，达到必败态，从而后手必败。

斐波那契博弈（k倍动态减法）

定义

有一堆物品，共n个，两人轮流取物，先手可取任意件，但不能不取，也不能把物品取完，之后每次取的物品数不能超过上一次的两倍，且至少为1件，取走最后一件物品的人获胜。

结论

当且仅当n不是斐波那契数时，先手胜。

证明

Zeckendorf 定理（齐肯多夫定理）：任何正整数可以表示为若干个不连续的Fibonacci数之和。
非斐波那契数：分解，每次都取最小堆，保证了下一个堆的最后一个一定是我取。
斐波那契数：先手取不完，后手开始取一定能保证自己拿到最后一个（若剩非斐波那契，同上；若是斐波那契，一定能一下取完）
这里面利用数学关系能严格证明。

扩展：k倍动态减法

定义

有一堆物品，共n个，两人轮流取物，先手可取任意件，但不能不取，也不能把物品取完，之后每次取的物品数不能超过上一次的k倍，且至少为1件，取走最后一件物品的人获胜。

和斐波那契博弈一样，只不过拿的不是2倍了，而是一个任意的k倍，当k为2时就是完全的斐波那契博弈了。

结论

我们手动构建一个a数列，若n是该数列中的数时，先手必败，否则后手必败。即该数列是必败态。

当 k = 1 时，必败态为 n = 2 ^ i, 因为我们把数按二进制分解后，拿掉二进制的最后一个1，那么对方必然不能拿走倒数第二位的1，因为他不能拿的比你多。你只要按照这个策略对方一直都不可能拿完。所以你就会赢。而当分解的二进制中只有一个1时，因为第一次先手不能全部取完，所以后手一定有办法取到最后一个1，所以必败！
举个例子，当 n = 6 = （110）时:
第一轮：先手第一次取最右边的1，即2个，此时还剩4（100）个，后手能取1或2个；
第二轮：假如上轮后手取的两个，先手再取两个直接赢了
假如后手取了一个，那么还剩三个，自己只能去1个，以后也只能取一个，所以必胜！
当 k = 2 时，赤裸裸的Fibonacci博弈了，具体这儿不多说，自己再上述博客已写的很明白了。其实n经拆解后也可以表示成二进制的形式，用 k = 1时的方法来理解，比如 n = 11 = 7 + 3 + 1，可表示成 10101；
当 k 取任意非零正值时，重点来了：
犹如Fibonacci博弈，我们首先要求一个数列，将n分解成数列中一些项的和，然后就可以按Fibonacci博弈的解决方法来完成，也可以按二进制的方法来理解，每次取掉最后一个1 还是符合上面的条件。我们用a数组表示要被求的数列，b数组中的b[i]保存 a[0…i] 组合能够构造的最大数字。这儿有点难理解，所谓构造就是指n分解为Fib数相加的逆过程。举例说明，当k = 2 时，a[N]={1, 2, 3, 5, 8, 13, 21, 33…} （Fibonacci数组）；那么b[3] 即 1、2、 3 能够构造的最大数字，答案是4，有点匪夷所思？或许你会问为什么不是5、6或者其它的什么，其实是这样的，4 能分解成 1+3 是没有争议的，但5能分解成2+3吗? 不能，因为5本身也是Fibonacci数；6虽然能分解，但不是分解成1+2+3，而是分解成1+5。
经过上述，我们知道b[i] 是 a[0…i] 能够构造出的最大数字，那么a[i +1] = b[i]+1；因为a数组（Fib数组）所存的数字都是不可构造的（取到它本身就是必败态），显然a[0…i]构造的最大数字 + 1 即为下一个不可构造的数字了(a[i + 1])。
然后关于b[i]的计算，既然是a[0…i]构造最大数字，那么 a[i]是一定要选用的（这儿需要一定的推理，a[i]构造数字时，相邻的j个是不能同时用的，就像上述的2、3不能构造出5一样，推理请自己完成），那么要选用的下一项只能递减寻找，直到找到 a[t] 满足 a[t] * K < a[i] ，而b[t]就是a[0…t]所能构造的最大数字，再加上a[i], 即为a[0…i]能构造的最大数字，于是b[i] = b[t] + a[i]。
求得数列后，之后的工作就简单了，跟Fibonacci博弈一样一样的，如果n=数列中的数，则必败，否则必胜；必胜时还要求输出第一步取法，其实就是分解的数列中最小的一个，将见代码。

威佐夫博弈

定义

有两堆物品，数量分别为a个和b个，两人轮流取物，每次可以从一堆中取出任意个，也可以从两堆中取出相同数量的物品，每次至少要取一个，最后取完所有物品的人获胜。

结论

我们规定两堆数量为a和b且a < b，若a和b的差值乘上1.618恰好是a的值，则次为必败态，先手必败。有时追求精度可记 $w = (int)[( (sqrt(5)+1) / 2) * (b-a)]$ ，若w == a，则先手必败，否则先手必胜。

SG函数

解决公平组合游戏（Impartial Combinatorial Games，ICG）问题的一种方法

条件

两名玩家，轮流操作，无法操作者输
每次操作在一个有限集合中选
合法操作只取决于游戏局面且一定，与玩家无关

定义

设$sg(x)=\text{mex} ({sg(y)|x\rightarrow y}) $ ， $\text{mex}$ 函数不用多说（一个集合中未出现的最小自然数）， $y$ 是 $x$ 状态可以一步操作到的状态，则 $x$ 状态可以转移到 $[0,sg(x)-1]$ 状态。

$sg(x)=0$ 为必败态； $sg(x)\neq 0$ 为必胜态，因为可以执行操作 $x\rightarrow 0$ ，使得对手必败。

// mex函数打表
int mex(auto v)
{
    unordered_set<int> S;
    for (auto e : v)
        S.insert(e);
    for (int i = 0;; ++i)
        if (S.find(i) == S.end())
            return i;
}

Sprague-Grundy定理

ICG中每一局都是一些子游戏的组合。

$sg(x)=sg(x_1+x_2+\cdots +x_n)=sg(x_1)\oplus sg(x_2)\oplus\cdots sg(x_n)$

状态 $sg$ 值异或和不为 $0$ ，则一定可以转移到 $sg$ 值异或和为 $0$ 的状态，即使对手必败。

反过来，状态 $sg$ 值异或为 $0$ ，则只能转移到 $sg$ 值异或和不为 $0$ 的状态，即对手必胜。