博弈论导读¶

约 1226 个字 18 行代码预计阅读时间 4 分钟

最简单的博弈论是奇偶性，比如cf round 885A。还有一个比较常见的技巧是下模仿棋，就是对方怎么做，你做一模一样的或者对称地做。

公平组合游戏(Impartial Combinatorial Games,ICG)¶

两名选手，交替进行预先规定好的操作
任何时刻，合法操作只取决于局面本身，与选手无关
不能合法操作的选手判负

和图论的联系¶

把一种局面看成一个点，一次操作会改变局面，每个局面向其后继局面连边，那么可以得到一个博弈状态图

定义必胜态是先手必胜的状态，必败态是先手必败的状态。之后也沿用这个概念

根据ICG定义，没有后继状态的状态是必败态

根据贪心策略，若后继状态有必败态，则当前状态是必胜态；否则当前状态是必败态

如果博弈图是有向无环图，那么每个点的状态都是确定的

常见结论¶

这部分感觉就了解一下，碰到了相关题翻一下板子

Chomp游戏¶

问题：Chomp是一个双人游戏，有 $n*m$ 块曲奇饼排成一个矩形格状，称作棋盘。两个玩家轮流自选吃掉一块还剩下的曲奇饼，而且要把它右边和下面所有的曲奇饼都被取走（如果存在）。如果不吃左上角的那一块曲奇饼（位置记为(1, 1)）就没有其他选择的玩家为失败。

答案：除了 $1*1$ 的情况，必胜

解释：如果先手吃了 (1,1)，而后手有必败策略，那么先手直接走后手策略，使得必胜

对于棋盘特殊形状可以找到具体执行策略，但是一般情形尚未有具体执行策略

Bash博弈¶

问题：一堆 n 个石子，可取出 1~m 个。 $m<n$ ，拿走最后一个石子者获胜

答案：当 n 不是 m+1 的倍数，必胜，否则必败

解释：

$n\%(m+1)\ne 0$ 可以变成 $n\%(m+1)\ne 0$ 或 $n\%(m+1)= 0$

而 $n\%(m+1)= 0$ 只能变成 $n\%(m+1)\ne 0$

必胜证明：先手把 $n\%(m+1)\ne 0$ 变成 $n\%(m+1)= 0$ ，后手只能变成 $n\%(m+1)\ne 0$ ，不断重复此过程，最终 $n=0,n\%(m+1)=0$ ，所以最后一个石子是先手拿的。

必败证明：后手模仿棋使得必败

Fibonacci博弈¶

问题：一堆n个石子，先手者第一次可以取任意多个，但是不能取完，以后每次取的石子数不能超过上次取子数的2倍。取完者胜

答案：n是斐波那契数，必败，否则必胜

解释：

当 $n\le 3$ ，显然必败，即 $f_3,f_4$ 必败

当 $i>=5,n=f_i=f_{i-1}+f_{i-2}$ ， $2f_{i-2}>f_{i-1}$

必败证明：如果先手取大于等于 $f_{i-2}$ 个石子，那么后手可以拿完剩下石子。如果先手拿小于 $f_{i-2}$ 石子，那么局面转换到谁拿完 $f_{i-2}$ 胜，因为拿完后局面变成 $f_{i-1}$ ，碰到此局面者输。而拿完 $f_{i-2}$ 的局面先手也是输，因此先手必败

齐肯多夫定理：任何正整数n可以被表示成若干个不连续的斐波那契数之和

$n=f_{a_1}+f_{a_2}+f_{a_3}+...$ ， $a_1+1<a_2,a_2+1<a_3,...$

$2f_{a_{i-1}}<f_{a_i}$

必胜证明：如果先手拿完 $f_{a_1}$ ，那么后手不可能拿完 $f_{a_2}$ ，因为局面和必败局面类似，类似地，后手也不可能拿完 $f_{a_3},f_{a_4},...$ ，所以最后一个是先手拿

Wythoff博弈¶

问题：两堆各若干石子，从任意一堆中至少取出一个或者从两堆中取出同样多的石子，规定每次至少取一个，至多不限，最后取光者胜。

这里的必输局势：(0，0)、(1，2)、(3，5)、(4，7)、(6，10)、(8，13)、(9，15)、(11，18)、(12，20)...

通过Beatty序列计算（这里省去），可以得出必输局势：

$(a_i,b_i)=(i∗\frac{1+\sqrt 5}2,i∗\frac{1+\sqrt 5}2+i),i=0,1,2,3...$

double r = (sqrt(5) + 1) / 2;
int d = abs(a - b) * r;
return (d != min(a, b));

如果a,b的值非常大的话，需要高精度来计算这个double类型的r。

Nim博弈¶

问题：有n堆石子，两人轮流取，每次取某堆中不少于1个，最后无合法操作者输

答案：所有堆石子数量，异或和不为0，必胜，否则必败

Nim-k¶

可以同时取最多k堆石头

若满足：将 $a_i$ 写成二进制，若对于每一个二进制位，所有的 $a_i$ 那一位的1的数量 %k=0，则先手必败，否则必胜

阶梯Nim¶

每次将所取第i堆的石头转移到第i-1堆，到0停止

若所有奇数位的数异或起来，若不为0则必胜

证明：移入偶数堆的石头可以看做是被清除了

如果有人拿出来就再将其丢去下一个偶数堆，对局面不影响

之所以是偶数是因为0是偶数，移入0的石头无法再移出，不再有影响。

二分图博弈¶

给出一张二分图和起始点 H ，A和B轮流操作，每次只能选与上个被选择的点（第一回合则是点 H ）相邻的点，且不能选择已选择过的点，无法选点的人输掉。一个经典的二分图博弈模型是在国际象棋棋盘上，双方轮流移动一个士兵，不能走已经走过的格子，问谁先无路可走。

如果最大匹配一定包含 H ，那么先手必胜，否则先手必败。

如果采用Dinic，在建图时把涉及 H 点的边存下来，跑完第一次Dinic后再建这些边，第二次Dinic看有没有增加流量。

K倍动态减法游戏¶

有n个石子，两个游戏者轮流操作，第一个操作的人最多能拿走n-1个石子，以后，每个游戏者最多能拿走前一个游戏者拿走数目的k倍

k=1,必败态是 $2^i$

k=2,Fibonacci博弈

k>2，类似Fibonacci博弈，把n分解成数列中不连续项的和，如果n就是数列中的数，必败

ll f[N],g[N];//f代表类Fibonacci数列，g[i]表示f[0-i]能组成的最大数
void init(int k)
{
    f[0]=g[0]=1;
    for(int i=1,j=0;i<N;++i)
    {
        f[i]=g[i-1]+1;
        while(f[j+1]*k<f[i])
            ++j;
        if(f[j]*k<f[i])
            g[i]=g[j]+f[i];
        else
            g[i]=f[i];
    }
}

如果采用Dinic，在建图时把涉及 H 点的边存下来，跑完第一次Dinic后再建这些边，第二次Dinic看有没有增加流量。