博弈论/组合游戏学习笔记

目录

1.公平组合游戏定义

2.必胜态与必败态定义

3.sg函数及Mex运算

4.各类经典博弈及例题整理

（1）Nim博弈（经典Nim+阶梯Nim）

（2）巴什博弈

（3）威佐夫博弈

（4）斐波那契博弈

（5）集合、拆分Nim游戏（sg函数求值）

注：以下部分文案摘自《算法进阶指南》

一、公平组合游戏定义

1.公平组合游戏ICG

若一个游戏满足：

1. 由两名玩家交替行动；
2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
3. 不能行动的玩家判负；

则称该游戏为一个公平组合游戏。

NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

2.有向图游戏：

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

二、必胜态与必败态

1.必胜态：任一后继局面为必败态，当前局面为必胜态

2.必败态：所有后继局面均为必胜态，当前局面为必败态

ps：其实这个必败态和必胜态很抽象，反正我是当初没有理解，后来才明白的。其实以石子游戏为例，说通俗点就是，我只要有一种拿石子的方式，拿完以后，轮到你，你不管怎么拿我都能赢，那么我就是必胜态，你就是必败态。

三、sg函数及Mex运算

1.Mex运算

设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：

mex(S) = min{x}, x属于自然数，且x不属于S

2.sg函数

在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk，定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果，即：

SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})

特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。

3.有向图游戏的和

设G1, G2, …, Gm 是m个有向图游戏。定义有向图游戏G，它的行动规则是任选某个有向图游戏Gi，并在Gi上行动一步。G被称为有向图游戏G1, G2, …, Gm的和。

有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：

SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)

4.定理

有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。

有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。

一般解题模型：把原组合游戏转化成一个个独立的子游戏，分别求出sg值，最后将他们异或起来，为0先手必败，否则的话先手必胜

四、几种经典博弈

1.Nim游戏

概述：给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。

所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。

NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

定理： NIM博弈先手必胜，当且仅当 A1 ^ A2 ^ … ^ An != 0

证明：设a1 ^ a2 ^ a3 … ^ an = x（x不为0） ， 若x的二进制最高位为第k位，那么a1 - an中一定有一个数ai二进制的第k位为1，（若所有数第k位都不为1，他们的异或不可能产生一个二进制第k位为1的数）。那么ai和x异或起来一定会把第k位变为0，那么一定有ai ^ x<ai，那么我们拿走（ai - ai ^ x）个石子，即让ai这一堆剩下ai ^ x个石子，那么这时的异或值就变成 a1 ^ a2 ^ a3 … ^ ai ^ x ^… ^an = x ^ x = 0 。无论后手下一步的操作是什么，我们都可以采用相同的方式，让后手的sg异或值变为0，直至游戏结束。那么先手一定是最后一个拿完石子的，即先手必胜。证明完毕。

洛谷P2197–Nim博弈模板题

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,ans=0;
		cin>>n;
		for(int i=0;i<n;i++)
		{
			int x;
			scanf("%d",&x);
			ans^=x;
		}
		if(!ans)
			printf("No\n");
		else 	printf("Yes\n");
	}
	return 0;
}
           

阶梯Nim游戏

概述：现在，有一个n级台阶的楼梯，每级台阶上都有若干个石子，其中第i级台阶上有ai个石子(i≥1)。

两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。

已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

结论：先手必胜当且仅当奇数级台阶的异或!=0

证明：若奇数级台阶的异或值为k，那么我进行类似上面nim游戏的操作，将某个奇数级台阶上的石子拿到偶数级台阶上，那么轮到后手时，如果他拿偶数级台阶上的石子，先手将这些石子继续向下移动一个，让奇数级台阶的异或值不变，继续为0。如果他拿奇数级台阶上的石子，那么现在奇数级台阶的异或值一定不为0，我们可以进行类似nim游戏的操作，拿走某一个奇数级台阶上的部分石子，使得异或值变为0。直到变为全0的局面。那么面对全0局面的一定是后手，即先手必胜。证明完毕。

Acwing 892. 台阶nim游戏

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    int ans=0,n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        if(i&1)
            ans^=x;
    }
    
    if(!ans)
       printf("No\n");
      else
        printf("Yes\n");
    return 0;
}
           

2.巴什博弈

概述：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。问先手是否必胜。

结论：先手必胜当且仅当n%(m+1) != 0

证明：如果n%(m+1)=k(k不为0)，那么先手可以取走k个石子，让后手的石子数变为m+1的倍数，无论后手取多少，采取相同操作。直至后手剩下m+1个石子，由于一次最多只能取m个，所以，无论后手取多少个，先手都能一次取完所有石子，那么先手必胜。证明完毕。

Hdu 1846 Brave Game – 巴什博弈模板题

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		if(n%(m+1)==0)
			printf("second\n");
		else 
			printf("first\n");
	}
}
           

ps:其实也可以枚举找规律，求sg值，上面的规律很容易发现。

3.威佐夫博弈

概述：有两堆各若干个物品，两个人轮流从某一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。问先手是否必胜

结论：先手必胜当且仅当两堆石子的差值乘以黄金分割数 !=较小堆的石子数

ps:黄金分割数为（1+sqrt(5.0) / 2

上图是两堆石子数目在30以内的所有必败态，找找规律其实能发现

1.每次较小的一堆石子数都是前面未出现过的最小的正整数。

2.两堆石子的差值是在递增的，每次递增1。

3.所有必败态里面，没有相同的两堆石子，即，所有的必败态，构成了整数集合。

那么怎么用公式将这个规律表示出来呢。本人表示，我只能看懂别人的证明，但是让我自己推推不出来。。上面的结论用到了beatty定理和beatty序列的相关概念。我看到网上有一篇证的比较详细的证明。感兴趣的戳这里

威佐夫博弈证明

（我第一次妄图自己打表找出规律，推了一个小时，也没推出来，，还是把它记住算了）。

Hdu 1527 取石子游戏–威佐夫博弈模板题

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;

int main()
{
	int n,m;
	double gold=(1+sqrt(5.0))/2;
	while(~scanf("%d%d",&n,&m))
	{
		if(n>m)
			swap(n,m);
		int x=(m-n)*gold;
		if(x==n)
			printf("0\n");
		else 	
			printf("1\n");
	}
	return 0;
}
           

4.斐波那契博弈

概述：1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜。问先手是否必胜。

结论：先手必胜当且仅当石子数n不是斐波那契数

证明： 斐波那契博弈较详细证明

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll f[55];
int main()
{
	f[1]=1;f[2]=2;
	for(int i=3;i<=50;i++)
		f[i]=f[i-1]+f[i-2];
	ll n;
	while(cin>>n && n)
	{
		int flag=1;
		for(int i=1;i<=50&&flag;i++)
			if(f[i]==n)
				flag=0;
		if(!flag)
			printf("Second win\n");
		else
			printf("First win\n");
	}
	return 0;
}
           

5.sg函数求解问题

（1）集合-Nim游戏

概述：给定n堆石子以及一个由k个不同正整数构成的数字集合S。

现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合S，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

输入格式

第一行包含整数k，表示数字集合S中数字的个数。

第二行包含k个整数，其中第i个整数表示数字集合S中的第i个数si。

第三行包含整数n。

第四行包含n个整数，其中第i个整数表示第i堆石子的数量hi。

输出格式

如果先手方必胜，则输出“Yes”。

否则，输出“No”。

数据范围

1≤n,k≤100,

1≤si,hi≤10000

输入样例：

2

2 5

3

2 4 7

输出样例：

Yes

思路：sg函数模板，求出每一堆的sg值，最后看异或值是否为0

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N =1e4+10;
int s[105],sg[N];
int k,n;
int get_sg(int x)
{
    if(sg[x]!=-1)
        return sg[x];
    int vis[N];
    memset(vis,0,sizeof vis);
    for(int i=0;i<k;i++)
    {
        if(x>=s[i])
            vis[get_sg(x-s[i])]=1;
    }
    for(int i=0;;i++)
        if(!vis[i])
            return sg[x]=i;
}
int main()
{
    cin>>k;
    for(int i=0;i<k;i++)
        cin>>s[i];
    cin>>n;
    int ans=0;
    memset(sg,-1,sizeof sg);
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        ans^=get_sg(x);
    }
    if(!ans)
        printf("No\n");
    else
        printf("Yes\n");
    return 0;
}
           

（2）拆分Nim游戏

给定n堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

输入格式

第一行包含整数n。

第二行包含n个整数，其中第i个整数表示第i堆石子的数量ai。

输出格式

如果先手方必胜，则输出“Yes”。

否则，输出“No”。

数据范围

1≤n,ai≤100

输入样例：

2

2 3

输出样例：

Yes

思路：还是求每堆石子的sg值，只不过每次取完以后的局面比较多，每次变成两堆石子，那么当前这个局面的sg值就是这两个后继的异或，最后进行Mex运算即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int sg[1005];
int get_sg(int x)
{
    if(sg[x]!=-1)
        return sg[x];
    int vis[1005];
    memset(vis,0,sizeof vis);
    for(int i=0;i<x;i++)
    {
        for(int j=0;j<x;j++)
            vis[get_sg(i)^get_sg(j)]=1;
    }
    for(int i=0;;i++)
        if(!vis[i])
            return sg[x]=i;
}
int main()
{
    int n,ans=0;
    cin>>n;
    memset(sg,-1,sizeof sg);
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        ans^=get_sg(x);
    }
    if(!ans)
        printf("No\n");
    else 
        printf("Yes\n");
    return 0;
}