【学习笔记】博弈论

· · 算法·理论

简单的说就是一个问题，然后在该问题下双方都按照最优策略来行动，然后对先手的必胜策略（有些时候还有方案）进行讨论的问题。

博弈论的一些性质

双方行动的限制都是相同的，并且双方所知道的信息都是相同的。

游戏所行动的步数应该是有限的，这个条件也可以等价于，如果我们达到了一个状态，那么我们应该就不会再次达到这个状态。

博弈一定会有胜负，没有平局。

博弈图

如果将每个状态视为一个节点，再从每个状态向它的后继状态连边，我们就可以得到一个博弈状态图。

在博弈图上，我们可以给出如下定义：

可以发现，根据上面的胜负性，可以发现，博弈图一定可以被二染色（好像在 DAG 的背景下这是废话）。并且由于自己必胜就是对方必败，我们可以得到如下的求解方法：

那么根据上面的有限性，我们可以发现，博弈图是个 DAG，这就告诉我们：需要时，我们可以 O(n+m) 拓扑排序/记搜进行处理。

经典的博弈论

Bash Game

一共 n 个石子，双方轮流取石子，每次最多取 m 个，哪一方无法取石子哪一方为败，问先手是否有必胜策略。

我们可以考虑以剩余的石子数为状态，建立博弈图（下图中蓝点为必胜点，红点为必败点），比如 m=2 的情况：

\cdots\rightarrow{\color{red}\texttt{3}}\rightarrow{\color{blue}\texttt{2}}\rightarrow{\color{blue}\texttt{1}}\rightarrow{\color{red}\texttt{0}}

那么我们可以猜得：当 (m+1)\mid n 时，n 为必败点，否则为必胜点。

我们仍然是通过博弈图的求解方法来证明。

证明如下：

变形

如果是取完最后一个棋子必败，那么我们可以想到：谁都不想取最后一颗棋子，所以其实问题就转化成了 n-1,m 的 Bash Game。

Wythoff Game

有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

我们可以证明必败点的一些性质：

引理 1： (x,y)\Leftrightarrow(y,x)

证明：

显然。

那么所有状态的表达形式，都可以变为 (a_k,b_k)(a_k<b_k)，并且由于 (0,0) 的特殊性，我们把它记作 a_0,b_0。我们记 A=\{a_k,k\in\mathbb N_+\},B=\{b_k,k\in\mathbb N_+\}。

引理 2：不存在 k 使得存在 a,b(a<b)，(k,a),(k,b) 均为必败点。

证明：

显然 (k,b) 中 b\gets b-(b-a) 后会得到 (k,a)，若 (k,a) 为必败点，那么 (k,b) 为必胜点，与原命题矛盾。

同理，还可以证明不存在 a,b(a<b) 使得 (a,k),(b,k) 均为必败点，以及不存在 a,b(a<b) 使得 (a,a+\Delta),(b,b+\Delta) 均为必败点。

引理 3：A\cap B=\varnothing

证明：

反证法。

若存在 k\in(A\cap B)，那么就存在 (k,a),(b,k) 均为必败点，由引理 1，显然可以知道 (b,k)\Leftrightarrow(k,b)。由引理 2，不存在 (k,a),(k,b)(a<b)，故矛盾。

引理 4：a_k=MEX(a_0,\cdots,a_{k-1},b_0,\cdots,b_{k-1})

证明：

数形结合。

可以考虑这样一件事情：

首先把 (a_k,a_k) 加入必败点中，然后把过它的与一三象限角平分线（y=x）的平行线和它与 x,y 轴（x=0,y=0）的平行线加入这个平面，再这些直线上的点都应该是必胜点，其它点都是必败点。

那么现在我们每次可取的必败点的集合一定是两个三角形，然后每次由于 a 递增，又要保证此时以 a 为第一关键字，b 为第二关键字最小，那么一定是左上角那个三角形的最下角。

那么要证明 a_k 的这个 MEX 我们可以分为如下两步：

由此，我们也可以得到 A\cup B=\mathbb R。

引理 5：b_k-a_k=k

证明：

数学归纳法。

由于 (a_0,b_0),(a_1,b_1) 均满足如上性质，所以我们现在可以假设 [0,m-1] 均满足引理 5。

那么我们现在要证的事情就是 (a_m,b_m) 满足引理 5。

首先我们可以知道，因为与一三象限角平分线平行的直线只覆盖到了 y=x+(m-1)，那么 y=x+m 是没有覆盖的，所以一定存在一个点在 y=x+m 上，使得它为必败点。

然后根据上面的两个三角形的性质，我们可以发现，由于该三角形每次斜边的总结距同一三象限角平分线一同增加 1，该三角形的斜边正好过 y=x+m。

故此时 (a_m,a_m+m) 显然为合法解。

接下来还要证明 \nexists\Delta<m，(a_m,a_m+\Delta) 为必败点。

考虑反证：可以发现，若 (a_m,a_m+\Delta) 为必败点，那么我们可以发现，由于 [0,m-1] 的差值已经被覆盖，那么一定存在 a' 使得 (a',a'+\Delta)，与引理二矛盾。

那么此时我们一定把必败点的性质推导完了，此时我们还需要引出一个新的东西：

Betty 定理：若 \dfrac{1}{a}+\dfrac{1}{b}=1，且此时 a,b 为正无理数，那么令 A=\{[an]|n\in\mathbb N_+\},B=\{[bn]|n\in\mathbb N_+\}。此时有 A\cap B=\varnothing,A\cap B=\mathbb N_+。

反证法。

对于 A\cap B=\varnothing：

那么我们可以假设 k\in A,k\in B，那么有 \exists m,n\in\mathbb N_+,[am]=[bn]=k，那么根据高斯函数的性质，有 k<am,bn<k+1，那么有 \dfrac{m}{k+1}<\dfrac{1}{a}<\dfrac{m}{k},\dfrac{n}{k+1}<\dfrac{1}{b}<\dfrac{n}{k}。

根据不等式的同向可加性，有 \dfrac{m+n}{k+1}<1<\dfrac{m+n}{k}，那么就有 k<m+n<k+1，与皮亚诺公理矛盾。

对于 A\cup B=\mathbb N_+：

假设 k\notin A,k\notin B，那么有 \nexists m,n\in\mathbb N_+,[am]\ne k,[bn]\ne k\Leftrightarrow\exists m,n\in\mathbb N_+,am<k<a(m+1)-1,bn<k<b(m+1)-1。

那么就有 \dfrac{m}{k}<\dfrac{1}{a}<\dfrac{m+1-\frac{1}{a}}{k},\dfrac{n}{k}<\dfrac{1}{b}<\dfrac{n+1-\frac{1}{b}}{k}，仍然是同向可加性，\dfrac{m+n}{k}<1<\dfrac{m+n+1}{k} 那么有 m+n<k<m+n+1，与皮亚诺公理矛盾。

我们可以发现，此时，必败点的性质和 Betty 定理中的 a,b 性质非常相似：无交集，并集为全集。

那么我们我们可以令 a_k=[\Delta k],b_k=[\Delta k]+k=[(\Delta+1)k]。

带入 Betty 定理，有 \dfrac{1}{\Delta}+\dfrac{1}{\Delta+1}=1，解得 \Delta=\dfrac{1\pm\sqrt{5}}{2}，由于 Betty 定理要求为正无理数，所以 \Delta=\dfrac{1+\sqrt{5}}{2}。

那么我们就得到了必败点的通项公式：a_k=[\dfrac{1+\sqrt{5}}{2}\times k],b_k=a_k+k(k\in\mathbb N_+)，然后我们会惊奇地发现 (0,0) 也满足该通项！

有了通项公式后，我们可以发现，k 与 a_k,b_k 一一对应。

因此，在一个已知局面 (a,b) 下，我们显然可以得到 k=b-a，那么我们只需要算出 a_k 和 a 进行比较，显然 a_k=a 时 b_k=b。

Fibonacci Game

一堆石子有 n(n>1)个，两人轮流取，先取者第一次必须取，但是不能取完，也不能不取；以后每次取的石子数不能超过上次取子数的 2 倍，先取完者胜。

首先我们需要一个东西：

Zeckendorf 定理：任何正整数可以表示为若干个不连续的 Fibonacci 数之和。

证明：

数学归纳法。

对于 1=1,2=2,3=3,4=1+3，我们可以假设对 [1,m-1]，上述定理成立。

现在我们需要证明上述定理对 m 也成立：

那么存在 k 使得 Fib_k<m<Fib_{k+1}，那么我们可以分解一个 Fib_k。此时，令 m'=m-Fib_k<Fib_{k+1}-Fib_k=Fib{k-1}，那么此时 m' 可以被分解为 [1,k-2] 项的不连续的 Fibonacci 数之和，显然 k 和 k-2 不连续。

Zeckendorf 定理告诉我们一件事：对于任意正整数 k，存在数列 \{a_m\}，满足 \forall i\in[2,m],a_i>2a_{i-1},k=\sum\limits_{i=1}^ma_i。

对于这个问题，有这样一个结论：当且仅当 n 为 Fibonacci 数时，先手必败。

数学归纳法。

注意到 2,3 时先手必败， 4 先手必胜，所以我们可以假设 n\in[2,m-1] 时，上述命题成立，下证 n=m 时上述命题成立。

根据结论，容易想到对 m 进行分类讨论。

若 m 不为 Fibonacci 数，由 Zeckendorf 定理，我们可以把 m 分解成 \sum a 的形式，其中 a 为 Fibonacci 数，并且 \forall 2a_i<a_{i+1}。

那么先手只需要取 a_2 即可，这样由于 a_2>2a_1，那么后手显然不能一次取完 a_2，那么此时先手就存在方案让自己取完 a_2 的最后一个，并且此时 a_3 不会被取完，以此类推，可以发现此时先手必胜。

若 m 为 Fibonacci 数，令 m 为 Fib_k，先手取 x 个。

若 x\ge Fib_{k-2}，有 m-x=Fib_{k}-x\le Fib_k-Fib_{k-2}=Fib_{ k-1}\le2Fib_k，那么先手能一次取完。

若 x<Fib_{k-2}，有 m-x=Fib_k-x>Fib_{k}-Fib_{k-2}=Fib_{k-1}，且 x>0，所以 m-x<m，那么 Fib_{k-1}<m-x<Fib_k，所以 m-x 不为 Fibonacci 数，那么此时后手必胜。

在实际操作的时候，a,b 显然不会很大，所以直接暴力就可以了。

Nim 博弈

有 n 堆物品，每堆有 a_i 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取，取走最后一个物品的人获胜。

结论：当且仅当 a_1\oplus\cdots\oplus a_n=0 时，先手必败。

那么我们回到博弈图上来证明：

博弈图上这个归纳的思想挺有意思的。

限定取物上界

这就是一个 Bash 博弈和 Nim 博弈的结合，于是把 a 分成 m+1 的倍数的部分和余数的部分。

容易想到若先手在 Nim 部分若有必胜策略那么他可以让自己在 Bash 和 Nim 都必胜；同样地，若先手没有必胜策略，那么他在 Nim 和 Bash 部分都必败。

综上，这个问题就是讨论的 Nim 部分，和 Bash 部分无关。

首先异或起来不为 0 的时候答案是 \infty。

否则找到最大的出现次数为奇数的数 mx，答案就是 mx-1。

从两个方面证明它是正确的：

Nimk 博弈

即每次可以取 k 堆。

根据异或，考虑位拆，对于每一位，我们把 \bmod(k+1)\ne0 的部分取出来，如果有可以取出来的，那么先手就可以把这些取出来，然后根据 Bash 博弈，后手无论怎么取，先手都可以让每一位 \bmod(k+1)=0；否则无论先手怎么取，后手都可以让每一位 \bmod(k+1)=0。

那么，当且仅当每一位的 1 的数量 \bmod(k+1)=0 时，先手必败，否则先手必胜。

阶梯博弈

每名玩家只能将石子转移到左边那一堆，或者从 1 号堆转移到 0 号堆。

若先手在奇数堆存在必胜状态，那么显然无论后手怎么取，原来奇数堆的石头仍然在奇数堆，偶数堆的石头仍然偶数堆，先手必胜；否则原来奇数堆的石头仍然在奇数堆，偶数堆的石头仍然偶数堆，最后后手取完最后一棵石头，后手必胜。

综上，我们只需要堆奇数堆做一个 Nim 博弈即可。

反 Nim 博弈

取完最后一个败。

约定 a_{0/1/2} 表示 a_1\oplus\cdots\oplus a_n\ne0 时存在 0/1/\ge2 个 a>1，b_{0/2} 表示 a_1\oplus\cdots\oplus a_n=0 时存在 0/\ge2 个 a>1，显然 b_1 不存在。

考虑博弈图的思想，递归处理：

故 b_0,a_1,a_2 为必胜点。

ICG 博弈

问题模型是这样的：在 DAG 上有若干颗棋子，每名玩家每次可以选择一颗棋子移动，哪名玩家无法移动棋子则失败。

可以发现，我们上面讲的博弈的非扩展原始版本都是 ICG 博弈的一部分。

首先，如果只有一颗棋子，我们显然可以在博弈图上算，那如果有多颗棋子呢？

我们可以用如下方法解决：

SG 函数

计算公式如下：

SG(i)=mex\{SG(j)\}(j\in next_i)

可以发现，在只有一颗棋子的时候，对于这颗棋子的起始状态 u，根据博弈图，当且仅当 SG(u)>0 时，先手必胜。

SG 定理

我们令 m 个棋子的状态分别为 u_1,\cdots,u_m。

那么当且仅当 SG(u_1)\oplus\cdots SG(u_m)=0 时，先手必败。

证明：

发现这个式子很像 Nim 博弈，所以用和 Nim 博弈类似的方法证明。

那么这样我们就可以快读地求解了，可以发现 SG 定理的难点在于 SG 里面这玩意的定义和 SG 到后继点的转移。

二分图博弈

给你一个二分图，两人轮流移动棋子，不能移动到已经到过的节点，无法移动则输。

结论：如果起点一定在二分图的最大匹配上，那么先手必胜；反之先手必败。

证明：

从二分图性质入手。

注意到增广路一共有奇数条边，那么路径上就有偶数个点，能走的点是奇数，最后走到的就是先手，后手无路可走，必败。

所以匹配点，走增广路，先手必胜。

那么先手肯定是沿着匹配边走，后手到达匹配点。

注意到这时如果后手走到匹配点的话，就走进了增广路，后手必败。

那么后手能不能走到非匹配点呢？我们令起点为 s，先手走到了 u，后手走到了 t，如果 t 为非匹配点，那么 s\to u 可以替换为 u\to t，此时 s 不一定在最大匹配中。

故后手只能走到匹配点。

由此，从一定在最大匹配中的点走，先手必胜。

否则，在某一个最大匹配中，先手处于非匹配点，只能走向匹配点，因为如果存在非匹配点到非匹配点的边，那么这条边可以加入最大匹配。

在这种情况下，这个点一定在最大匹配上，所以后手必胜，先手必败。

Hackenbush/树上公平删边游戏

结论是：一个节点的 SG 值等于其所有儿子的 SG 值 +1 的异或和。

对于叶子节点 u，显然有 SG(u)=0。