博弈论

摘要

博奕论,一门高深的学问。

2019.6.15 编入精选文章。

dls 讲博弈论:“你掉线,我随意”

博弈的分类

博弈大体分为平等博弈和不平等博弈。平等博弈指双方的决策集等价,不平等博弈则指双方决策集不等价。

常见的平等博弈则则是 ICG 公平组合游戏,这之中又有 NIM 博弈。

先别慌,概念性的不必死记硬背。鉴于博弈本身是一个巨大的体系,因此不摆一点干货出来,

ICG 公平组合游戏

两名玩家交替行动;每一个玩家的行动方式相同(决策集等价);不能行动的玩家判负

则该游戏被称作一个公平组合游戏

NIM 博弈

给定 堆物品,第 堆物品有 个。

两名玩家轮流行动,每次可以任选一堆,取走任意多个物品,可把一堆取光,但不能不取

取走最后一件物品的人获胜。若两人都采取最佳策略,问能否获胜

这类游戏被称为 博弈,游戏过程中面临的状态称为局面

博弈(双方均采取最佳策略时)先手必胜,当且仅当 .

证明:

所有物品被取光显然是必败局面,此时 .

对于任意一个 的局面,设 x 的最高位的 1 在第 k 位,显然存在一个 的第 k 位为 1。又因为 ,因此我们把 变成 ,给对手一个 的局面.

而对于 的局面,无论怎么取石子,剩下的异或和都不可能为 0.

用数学归纳法, 为必胜局面,反之必败。

有向图游戏

有向图游戏,鉴于前两者都有一个优美的英文名字,我们给它一个 DAGame 的名字吧。

给一个 DAG,从起点,两个人轮流沿边行动,无法移动者负。

显然出度为 0 的点为必败局面。

任何 ICG 都可以转化为 DAGame:把每一个局面看作点,把合法行动当作有向边

DAGame 的判局

很好这里就是更重点一些的内容了,建议仔细阅读

Mex

对于非负整数集合 ,定义

即 Mex(S) 表示不属于 S 的最小正整数。

SG 函数

在 DAGame 中,对于结点 x :

对于整个有向图游戏 G,若初始局面为 ,有 .

DAGame 的和

给定 个有向图游戏 ,两名玩家轮流行动,每次可以任选一个游戏,行动一步。无法操作者为负。

即多线程版本的 DAGame。这时整个游戏的 SG 值为

即单个游戏的 SG 异或和。

DAGame 的某个局面 必胜,当且仅当 .

DAGame 的某个局面 必败,当且仅当 .

证明略

SG 函数博弈

SG 博弈是 OI 中最常见的博弈类题目。其题目往往千奇百怪,但总的方法大概是:

吃(S)饭(G),睡(da)觉(biao),打(zhao)豆(gui)豆(lv)。

SG 函数是用于 ICG 游戏的判局,因此默认不能行动者判负。所以题面中不再说明胜负条件。除非条件有变

小练习

Exercise 1

有⼀堆⽯⼦,两个⼈轮流取,每次可以取 个。

遇到 SG 函数的题,通常可以打表找规律

⽐如 .

Exercise 2

堆⽯⼦。两个⼈轮流取,每次可以在⼀堆⽯⼦⾥⾯取任意多的⽯头,或者把⼀堆⽯头分裂成两堆。

分裂相当于变成两个独立的游戏,那么这个游戏的 SG 值就是其子游戏的异或值

打表完发现有规律,大概是 .

Exercise 3

博弈,每次能拿掉总数量的⼀个因⼦,不能拿本身。

打表代码

#include<bits/stdc++.h>
#include<bitset>
using namespace std;

int SG[1000];
bool vis[1000];
int SG(int k){
    if(vis[k])return SG[k];
    vis[k]=1;
    if(k==1)return SG[k]=0;
    bool bit[1000]={0};
    for(int i=1;i<k;i++)if(k%i==0)bit[SG(k-i)]=1;
    for(int i=0;i<1000;i++)if(!bit[i])return SG[k]=i;
}
int main(){
    for(int i=1;i<=20;i++)cout<<SG(i)<<' ';
    return 0;
}

打表找规律,发现 的二进制末尾的 的个数

Exercise 4

博弈,每次能拿掉与总数量互质的数。

打表代码

#include<bits/stdc++.h>
#include<bitset>
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int SG[1000];
bool vis[1000];
int SG(int k){
    if(vis[k])return SG[k];
    vis[k]=1;
    bool bit[1000]={0};
    for(int i=1;i<=k;i++)if(gcd(i,k)==1)bit[SG(i)]=1;
    for(int i=0;i<1000;i++)if(!bit[i])return SG[k]=i;
}
int main(){
    for(int i=1;i<=20;i++)cout<<SG(i)<<' ';
    return 0;
}

规律:偶数是 ,其他数的 就是最小质因子在质数表中的编号。

Exercise 5

有⼀个 的纸条,两个⼈轮流在格⼦⾥画 ,谁画了连续的三个 获胜。

放了一个后,左右各延伸的两格都放不了,那么左右两边的纸条就是独立的游戏,于是 SG 异或一下就行了(中间的是一个必胜局面,也要作为一个游戏,也就是说一共有 3 个子游戏)

如果你顺利看完这 5 个 exercise,你就发现博弈通常不是难在推 SG 的过程,而是快速求 SG 的过程(即打表找规律的过程)。接下来的叙述中会更少谈到推 SG,更多地去探求找规律或者找 DAGame 模型的过程。

CF 某题

个数 , 两个轮流选择数字删除,如果 被删除了,那么 也要被⼀起删除。 .

把每个底数的幂拿出来,就会变成若干独立的游戏,每个游戏只和序列长度有关

例如 的分组是这样的

每个组内的数删除后,只会影响组内的数,不会影响别的组的数;而每个组又是等比数列,不用考虑底数,所以每个游戏只和序列长度有关。所以计算每个游戏的 SG,记忆化搜索 or 状压打个表就行(根据 的范围,只需要把 30 的表打出来)

PE306

的⻓条,每个⼈轮流拿连续的两个格子。

打表代码如下

#include<bits/stdc++.h>
#include<bitset>
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int SG[1000];
bool vis[1000];
int SG(int k){
    if(k==1)return 0;
    if(k==2)return 1;
    if(vis[k])return SG[k];
    vis[k]=1;
    bool bit[1000]={0};
    for(int i=1;i+2<=k;i++)bit[SG(i)^SG(k-i-2)]=1;
    for(int i=0;i<1000;i++)if(!bit[i])return SG[k]=i;
}
int main(){
    for(int i=1;i<=1000;i++)cout<<' '<<SG(i);
    return 0;
}

记事本的正确打开方式——拖动找循环节

前几个有 bug,后面的就是循环节(可以在 OEIS 上找到这个序列)

CF 新年睿智题

两个⼩⽼弟玩游戏,有若干⾏,每⾏有三个棋⼦。Alice 可以选择⼀⾏将左边的 1 或 2 个棋⼦往右移 d 步。Bob 可以将右边的 1 或 2 个棋⼦往左移 d 步,移完之后棋⼦的相对顺序不变,要求 d 是素数或者两个素数的乘积。 ⾏,每⾏棋⼦坐标范围在 之内。

不同行的游戏是独立的,考虑一行的游戏。表面上两个人的决策集不等,但由于我们不必关系棋子间的具体坐标,我们只关心三个棋子的间距。我们可以把游戏的过程看做三颗棋子往中间靠,直到靠在一起

因此将右边的 1 枚棋子往左移 d 步等价于右边的间距减少 d;右边 2 枚棋子左移 d 步等价于左边间距减少 d。左边的操作同理。因此这是一个平等博弈。而对两个间距的操作也是独立的,因此我们只需要考虑对一个间距操作的情况:

表示可选的 d 的集合。直接计算这个式子,复杂度是 .

用 bitset 存 表示 j 这个位置是否有 SG 值为 的后继,or 一下就行

算完异或起来就行

[POJ2311]Cutting Game

初始时,给出一个 的网格,每次可以选择一个网格,沿网格线水平或者垂直切割,将其分为两个更小的网格。谁切出了 的网格谁获胜。 .

由于 ICG 游戏是以必败局面收尾的,因此思考哪些局面是必败局面。

对于任何一个人,都不会先剪出 或者 ,这样必败;同时 的局面也是必败的。SG 函数如下

#include<cstdio>
#include<cstring>
#include<bitset>
using namespace std;
const int N=505;
int n,m,c[N][N];
int SG(int a,int b){
    if(~c[a][b])return c[a][b];
    bool bit[N]={0};
    for(int i=2;i<=a-i;i++)bit[SG(i,b)^SG(a-i,b)]=1;
    for(int i=2;i<=b-i;i++)bit[SG(a,i)^SG(a,b-i)]=1;
    for(int i=0;i<N;i++)if(!bit[i])return c[a][b]=i;
}
int main(){
    memset(c,-1,sizeof(c));
    while(~scanf("%d%d",&n,&m))puts(SG(n,m)?"WIN":"LOSE");
    return 0;
}

[LG1290] 欧几里德的游戏

给定两个正整数 M 和 N,每次选择其中较大的数,减去较小数的正整数倍,要求得到的数不能小于 0。得到了 0 的人取得胜利。

暴力 SG:

想办法简化计算过程。我们发现

因此, 可以由 推导。

对于

,则

往上依次递增,直到 . 此时为必胜局

,则

往上依次递增,直到 . 此时视 的情况而定。

因此,只需计算 再加以讨论即可

复杂度 .

#include<cstdio>
using namespace std;
typedef long long ll;
ll t,m,n;
bool SG(ll m,ll n){//m<n
    if(!m)return 0;// 面对 m=0 的局面为负
    if(n-m<m)return !SG(n%m,m);// 如果 SG!=0,则 SG(n,n%m +m)=0
    else return 1;// 不管 SG(n,n%m) 的值,之后都不为 0
}
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&m,&n);
        if(m>n)m^=n^=m^=n;
        puts(SG(m,n)?"Stan wins":"Ollie wins");
    }
    return 0;
}

[SDOI2009] E&D

堆石子,编号为 。我们将第 堆与第 堆 ( )视为同一组。第 堆的石子个数用一个正整数 表示。 一次分割操作指的是,从桌子上任取一堆石子,将其移走。然后分割它同一组的另一堆石子,从中取出若干个石子放在被移走的位置,组成新的一堆。操作完成后,所有堆的石子数必须保证大于 0。

这是多个 ICG 游戏,对于单个游戏 ,相当于有 .

设计 SG 函数如下

const int N=100;
int SG[N][N];
bool vis[N][N];
int mex(bitset<N> bit){
    int res=0;
    while(bit[res])res++;
    return res;
}
int SG(int a,int b){
    if(a==1&&b==1)return 0;
    if(vis[a][b])return SG[a][b];
    bitset<N> bit;
    for(int i=1;i<a;i++)bit[SG(i,a-i)]=1;
    for(int i=1;i<b;i++)bit[SG(i,b-i)]=1;
    return mex(bit);
}

复杂度

利用上述函数打表。因为我们只关心每一个 ICG 中, ,因此对于 的所有 ,考虑其对应的 的 SG 值的取值集合(用二进制数表示,右边第一位为 0,往左依次为 0,1,2…)

a=1    :00000000000
a=2    :00000000001
a=3    :00000000010
a=4    :00000000011
a=5    :00000000100
a=6    :00000000101
a=7    :00000000110
a=8    :00000000111
a=9    :00000001000
a=10    :00000001001

发现,关于 a 的 集合即为 的二进制表示中,值为 1 的位,如

即二进制下最低位的 0

那么回到一个 ICG 游戏 的初始局面,则利用上述结论,我们取 在二进制表示下最低位的 0 即为 .

最后异或和一下即可

复杂度 .

#include<cstdio>
#include<bitset>
using namespace std;
int t,n;
int mex(int x){
    int res=0;
    while(x&1)x>>=1,res++;
    return res;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int ans=0;
        for(int i=1,a,b;i<=n;i+=2){
            scanf("%d%d",&a,&b);
            ans^=mex((a-1)|(b-1));
        }
        puts(ans?"YES":"NO");
    }
    return 0;
}

[SPOJ] COT3

⼀个有根树一开始每个点有黑白两种颜色。每次可以选择⼀个白点,然后把它到根的路径全部变黑。 .

考虑 DFS 算子树 SG。对每个子树 u 枚举子树内的点 v 被选择时,剩下的点的 SG(即 v 到 u 路径上非 v 祖先的那些儿子结点的 SG 异或和)这样暴力的复杂度是 的。

p1

我们选择子树 u 中的 v1,选择 v,两者的公共贡献就是 u 到 v1 路径左右部分的 SG 值。因此在算 SG[u] 的时侯,在计算了其子树的 SG 值后,可以做一个 的 DFS。累加一个路径的贡献即可。这样的总复杂度是 的。

我们把这个问题做得更加形式化一点。 表示子树 u 的 SG 值。为了写出 SG[u] 的式子,我们再记 表示在子树 u 中选择 v 标记后,剩下的连通块的 SG 值,而 则表示所有 f[u,v] 的数集

因此问题转化为求 f[u]。设

我 TM 第一次打出了大异或的符号(大雾)

分情况讨论:

  1. 如果 u 是黑点,那么假设选择 u 的子树 v 中的某个结点 w,则后继状态 SG 值为 .
  2. 如果 u 是白点,则多了一个选 u 的决策。选了 u,则后继状态 SG 值就是 ;不选 u 的话,u 仍然会变黑,因此与 1 的状态集等价。也就是说只是多了一个 sum[u] 的状态。

综上,得出

于是,我们要想办法维护这个 f[u],它要支持整体异或、合并、查询 Mex。01Trie 可以胜任。01Trie 的本质就是权值线段树。则复杂度 .

博弈 DP

练习 1

给你 的⽹格, 的位置标着移到这个位置的胜负情况,初始时有⼀个在 位置的棋⼦,Alice 和 Bob 轮流移动,每次可以往左或者往上。Alice 先手. .

考虑 DP, 表示走到 的胜负情况

方程的含义是,如果 都是必胜态的话,那么当前的 对于当前的执行者就是必败态;反之当任意一个不是必胜态时亦然。最后状态取反。

打表找规律,发现除了前三行前三列的 DP 值,其他的主对角线上的胜负状态是一样的

AGC 002E

堆糖,Alice 和 Bob 轮流操作。可以吃完最⼤的⼀堆,也可以每堆吃⼀个。 .>

放在二维方格上表示,相当于每次可以横着切一片或者竖着切一片,可以看做往右走和往上走

p1

那么同样可以用二维 dp 来做

把每一列的顶上两三个的 DP 值求出来,发现剩下的主对角线上的状态相等

K 倍动态减法游戏

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

考虑暴力 .

表示当前数字是 ,能减的数字是

我 TM 又第一次打出了大 And 的符号

暴力是

这东西在第二维上是单调递增(非严格)的( 能赢, 也能赢),那么令 表示在 的情况下什么时候开始赢(最后一个输位置)

由于

即这些状态必胜,它才会输。那么可以暴力枚举判断

而决策点集 其实是在斜率 的直线上的决策点(注意纵轴是第一关键字,所以斜率为倒数),相当于从下往上发射激光一样,碰到 0 就结束。那么单调栈扫一遍即可?

p1

阶梯 NIM

堆⽯⼦。两个⼈轮流取,每次可以在第 堆⽯⼦⾥⾯选取若⼲⽯头放到 堆⾥⾯。

移动奇数编号第 堆的石子到 堆,下一个人可以模仿他的行为,把他动的那些石子从 继续移到 上(因为是奇数,保证存在 ),且先后手关系不变

因此只用考虑偶数堆的异或和是否为 .(为 0 则必败)

博弈杂题

经典题

你有⼀个⽆向图,Alice 和 Bob 轮流移棋⼦,不能移到走过的点上。

在点 u 上,先手必败当且仅当存在最大匹配的方案,不包含结点 u。

略证如下:如果存在最大匹配的方案且该方案不包含结点 u,那么先手从 u 出发,一定会走到一个匹配点 v(如果 v 不是匹配点的话,那么 可以形成一个匹配,则与最大匹配矛盾),于是后手沿着匹配边走,先手只能沿非匹配边走。最后一定会以匹配边结束,使得先手没有非匹配边可走(如果仍存在可走的非匹配点的话,那么 和这条边都是非匹配边,可以构成增广路,与最大匹配的条件矛盾),于是先手必败。

反之亦然,必胜的条件即该图的任意最大匹配都包含 u,那么先手可以走匹配边,后手走非匹配边,最后一定以匹配边结束(如果以非匹配边结束,那么我们可以把走的路径上的匹配边移到与它紧邻的下一个非匹配边,于是可以构造一个最大匹配,不包含结点 u。与条件矛盾),于是后手必败。

那么跑图的最大匹配即可(不一定是二分图,这里只是一个算法思路,重点在于博弈胜负的判定证明)

[NOIP2010] 三国游戏

人选的一定 max(每一行的次大的默契值).

证明

我们先选 max(每一行的次大的默契值)对应的那一行的武将

这时,计算机会把这一行最大的默契值(记为 max)对应的另一个武将选走,双方都不能拿到最大的默契值

然后人把max(每一行的次大的默契值)对应的另一个武将选择,配出max(每一行的次大的默契值),记为 x

注意,人已经配出了max(每一行的次大的默契值),这是事实。显然

那么接下来,计算机选择的武将将会配出一对默契值(记为 y)。而 。使用反证法:

  • 如果 ,那么有 ,而 都与计算机选的第一个武将有关,两者在同一列(行),因此max(每一行的次大的默契值)就应该为 而不是 ,矛盾
  • 如果 ,则max(每一行的次大的默契值) ,矛盾

同样的,既然计算机的先手拆散没有意义 ,则人转变为先手,继续按上述策略配出每行次大的默契值,同时把每行最大的默契值拆掉即可

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=502;
int n,a[N][N],ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++)scanf("%d",&a[i][j]),a[j][i]=a[i][j];
    }
    for(int i=1;i<=n;i++){
        sort(a[i]+1,a[i]+n+1);
        ans=max(ans,a[i][n-1]);
    }
    printf("1\n%d",ans);
    return 0;
}

总结

你发现,博奕论是个 DP(感觉这句话曾经在什么地方说过)

学习博奕论教会我,用好 才是王道。(大雾)


  转载请注明: Sshwy's Blog 博弈论

 上一篇
[SDOI2010] 地精部落 [SDOI2010] 地精部落
题意问 1-n 的排列中,峰谷交替的排列有多少个,答案对 P 取模。 峰谷交替:即对于一个排列中的任意一个数 ,满足以下条件之一: a_{i-1}>a_i using namespace std; const int N=420
2018.12.15
下一篇 
[SCOI2005] 最大子矩阵 [SCOI2005] 最大子矩阵
题意矩形的每一个格子有权值 一个宽 1 或 2 的矩形选出 k 个子矩形,问最大权值和 分析既然宽度只有 2, 状压一下每行状态 DP 即可 定义 表示前 行选 个子矩形的最大权值. 其中 k: k=
2018.12.13
  目录