博弈论详解

2021-01-31


写在前面

因为图论专题考试考到了博弈论,然后就跑过来通了一遍
至于图论考试为什么会扯到博弈论?我不知道,就很奇怪

正文

何为博弈论?

博弈论 ,是经济学的一个分支,主要研究具有竞争或对抗性质的对象,在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为,并研究它们的优化策略。

详细解释可以请自行百度百科

先看一个简单的例题

先来看一道小学就接触过的思维题

你和好基友在玩一个取石子游戏。面前有30颗石子,每次只能取一颗或两颗,你先取,取完的人为胜,问你是否有必胜策略

Q:什么?有必胜策略?能否胜利不应该随着我们选择而改变吗?
A:确实。但如果我们足够聪明呢?每次都做最优的选择,把取胜之路留给自己
Q:我一点也不聪明,那该如何做呢?

先从简单入手,
假如只有一个或两个石子,无疑先手必胜
只有三个石子,无疑先手必输

(我们约定先手必败状态必败状态先手必胜状态必胜状态)
这就是我们的终止状态,即无论怎么拿,都会回到这几个状态
因为我们想赢,所以我们要让自己处于必胜状态,即剩下一个或两个石子的时候,我们是先手。不难发现,我们也许不能使自己处于必胜态,但我们可以让对方处于必败态。即剩下三个石子的时候,我们是后手。

不难发现,只要是三的倍数就一定是必败状态,否则就是必胜状态。
证明:
假设不是三的倍数,我们使它成为三的倍数,此时我们是后手。对方如果拿一个,我们就拿两个;如果拿两个,我们就拿一个。所以我们那完后剩下的一定永远是三的倍数,所以只剩下三个石子的时候我们一定是后手,此时对手必输,也就是我们必胜。
假设是三的倍数,因为两个人都足够聪明,所以对方一定会使我们永远处于三的倍数中。所以我们必败。
所以只要判断是不是三的倍数,就可以确定我们是否必胜了

至此,小学时代遗留的问题已经解决了可以拿去欺负同学,(这也是博弈论最基础的问题,Nim游戏)
可以说,你已经学会博弈论了

现在,让我们对自己的思考做一下规范

博弈图和状态

把每个可到达的状态都看做结点,每次做出决策都是从旧的状态转移到新的状态,也就是在两个状态结点间连一条有向边。如果把所有状态转移都画出来,我们就得到了一张博弈图

就像这样
就像这样

大多数博弈图会是一个DAG,否则游戏不可能结束

三个基本定理

通过推理不难得到这几个定理

  • 定理一:没有后继状态的状态是必败状态
  • 定理二:一个状态是必胜状态 当且仅当 存在至少一个必败状态为它的后继状态。
  • 定理三:一个状态是必败状态 当且仅当 它的所有后继状态均为必胜状态。

对于定理一,游戏进行不下去了,即这个玩家没有可操作的了,那么这个玩家就输掉了游戏

对于定理二,如果该状态至少有一个后继状态为必败状态,那么玩家可以通过操作到该必败状态;此时对手的状态为必败状态,即对手必定是失败的,而相反地,自己就获得了胜利。

对于定理三,如果不存在一个后继状态为必败状态,那么无论如何,玩家只能操作到必胜状态;此时对手的状态为必胜状态——对手必定是胜利的,自己就输掉了游戏。

如果博弈图是一个有向无环图,则通过这三个定理,我们可以在绘出博弈图的情况下用 \(O(n + m)\) 的时间(其中 \(n\) 为状态种数, \(m\) 为边数)得出每个状态是必胜状态还是必败状态。(利用拓扑排序

Nim 和

让我们回顾Nim游戏,显然我们可以通过构建博弈图获得是否必胜
但这样的复杂度是 \(O(\begin{matrix} \prod_{i=1}^n a_i \end{matrix})\),显然不能接受。

有没有什么快速简单的方法呢?
定义 Nim 和 = \(a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n\)
当且仅当 Nim 和 为 \(0\) 时,该状态为必败状态;否则该状态为必胜状态。

证明过程详见Oi-wiki
其实是我没看懂
后面内容也一定程度上会证明这个定理

有向图游戏和SG函数

有向图游戏是一个经典的博弈游戏——实际上,大部分的公平组合游戏都可以转换为有向图游戏。

在一个有向无环图中,只有一个起点,上面有一个棋子,两个玩家轮流沿着有向边推动棋子,不能走的玩家判负。

定义 \(mex\) 函数的值为不属于集合 \(S\) 中的最小非负整数,即:

\[mex(S) = min\{x\} \ \ (x \notin S,x\in \mathbb{N}) \]

例如 \(mex(\{ 0, 1, 3, 4\}) = 1\)\(mex(\{1,2 \}) = 0,mex(\{\}) = 0\)

对于状态 \(x\) 和它的所有 \(k\) 个后继状态 \(y_1,y_2,...,y_k\),定义 \(SG\) 函数:

\[SG(x) = mex\{SG(y_1),SG(y_2),...,SG(y_k)\} \]

SG定理:

而对于由 \(n\) 个有向图游戏组成的组合游戏,设它们的起点分别为 \(s_1,s_2,...,s_n\) ,则有定理: 当且仅当 \(SG(s_1) \oplus SG(s_2) \oplus ... \oplus SG(s_n) \ne 0\) 时,这个游戏是先手必胜的。

还是拿原来那个图开刀

就像这样

\(SG[]\) 数组来存所有结点的 \(SG\) 函数值
因为 \(9,3,8,10,4\) 这几个点都没有后继状态,所以它们 \(SG\) 值均为 \(0\),同理推出 2,7,5这个点的 \(SG\) 值为 \(1\),而

\[SG[6] = mex(SG[7],SG[8]) = 2 \]

\[SG[1] = mex(SG[2],SG[5],SG[6]) = 0 \]

把 Nim游戏 转化为有向图游戏

我们可以将一个有 \(x\) 个物品的堆视为节点 \(x\) ,拿掉若干个石子后剩下 \(y\)个,则当且仅当 \(0 < y < x\) 时,节点 \(x\) 可以到达 \(y\)

那么,由 \(n\) 个堆组成的 Nim 游戏,就可以视为 \(n\) 个有向图游戏了。

根据上面的推论,可以得出 \(SG(x) = x\) 。再根据 SG 定理,就可以得出 Nim 和的结论了。

博弈论DP

不得不说,博弈论DP就是个神仙做法,能有博弈论DP做的都是神仙题!

并没有什么固定的做法,但基本原理还是照着那三个定理来。能用DP的一般是因为想不出来如何用 \(SG\) 定理。状态的设计都比较神仙,主要是根据题目要求来设计。

可以参考一下下面两个博弈论DP习题找找感觉,我也不是很会,主要是学会如何去设计状态。

博弈论习题

1、取石子游戏 1
2、取石子游戏 2
3、移棋子游戏

其实这三道题大体思路上面都讲过了,比较基础

4、取石子游戏

Describe

同样是n堆石子,只不过可取的石子数只有m个数,求先手必胜还是先手必败,并输出第一次取的方案

Solution

现根据 \(m\) 个数预处理出 \(1000\) 以内的数的 \(SG\) 值,再将 \(n\) 堆石子的数量异或,如果是 \(0\) 先手必败,反之先手必胜。
寻找一个方案:在从第一堆石子开始,一次拿取所有能拿取的情况,并判断能否达成必胜条件。必胜条件是拿去枚举的拿取石子数量后,剩下的石子数异或起来为 \(0\) ,因为你拿了一次石子后你就变成后手了

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

int n, m;
int a[15], SG[MAXN], val[15];
int pos[15];
bool vis[MAXN];

int read(){
	int s = 0, f = 0;
	char ch = getchar();
	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
	return f ? -s : s;
}

void init_SG(){
	SG[0] = 0;
	for(int i = 1; i <= 1000; ++i){
//		int maxm = -1;
		memset(vis, false, sizeof vis);
		for(int j = 1; j <= m && (i - val[j]) >= 0; ++j){
			vis[SG[i - val[j]]] = true;
//			maxm = max(maxm, SG[i - val[j]]);
		}
		int j = 0;
		while(vis[j]) j++;
		SG[i] = j;
	}
}

bool check(int x, int y){
	for(int i = 1; i <= n; ++i){
		pos[i] = a[i];
	}
	pos[x] -= y;
	int ans = 0;
	for(int i = 1; i <= n; ++i)	ans ^= SG[pos[i]];
	if(ans) return false;
	return true;
}

int main()
{
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	m = read();
	for(int i = 1; i <= m; ++i) val[i] = read();
	init_SG();
	int ans = 0;
	for(int i = 1; i <= n; ++i) ans ^= SG[a[i]];
	if(ans) {
		printf("YES\n");
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j <= m && (a[i] - val[j]) >= 0; ++j){
				if(check(i, val[j])) {
					printf("%d %d", i, val[j]);
					return 0;
				}
			}
		}
	}
	else printf("NO");
	return 0;
}

5、S-Nim

Describe

和第二题一样,就是多了 \(T\) 组数据,每组数据又有多轮游戏,每轮游戏如果存在先手必胜输出 \(W\) 否则输出 \(L\)

Solution

直接根据Nim和来做就好了,需要注意的是每次都要预处理一遍 \(SG\) 函数,每次预处理之前都要拍一遍序

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

int k, m, n;
int SG[10010], val[110];
int vis[10010];

int read(){
	int s = 0, f = 0;
	char ch = getchar();
	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
	return f ? -s : s;
}

void init_SG(){
	SG[0] = 0;
	for(int i = 1; i <= 10000; ++i){
		memset(vis, false, sizeof vis);
		for(int j = 1; j <= k && (i - val[j]) >= 0; ++j){
			vis[SG[i - val[j]]] = true;
		}
		int j = 0;
		while(vis[j]) ++j;
		SG[i] = j;
	}
}

int main()
{
//	freopen("test1.in","r",stdin);
//	freopen("test.out","w",stdout);
	while(true){
		memset(SG, 0, sizeof SG);
		k = read();
		if(!k) break;
		for(int i = 1; i <= k; ++i) val[i] = read();
		sort(val + 1, val + k + 1);
		init_SG();
		m = read();
		for(int j = 1; j <= m; ++j){
			n = read();
			int ans = 0;
			for(int i = 1; i <= n; ++i) ans ^= SG[read()];
			if(ans) printf("W");
			else printf("L");
		}
		printf("\n");
	}
	return 0;
}

6、巧克力棒

Describe

一共10轮,每次一人可以从盒子里取出若干条巧克力棒,或是将一根取出的巧克力棒吃掉正整数长度。TBL 先手两人轮流,无法操作的人输。如果胜输出 \(NO\) ,负输出 \(YES\)

Solution

需要对Nim博弈有深入的了解,这题如果不用取巧克力,就是典型的Nim博弈。
我们知道,Nim博弈,如果异或和为0则是必败状态,所以,如果先手拿出几根巧克力异或和不为0,后手就可以使异或和变为0,此时先手再拿,后手又可以通过操作使异或和变为0。
所以,先手要想取胜,必须先拿出最大的异或和为0的集合,此时后手无论怎么操作,都会使异或和变为不等于0。所以,如果有异或和为0的集合,先手必胜。如果没有,先手必输。因为n很小,所以直接暴搜判断即可。

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

int n; 
int a[22];

int read(){
	int s = 0, f = 0;
	char ch = getchar();
	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
	return f ? -s : s;
}

bool dfs(int pos, int val, int cnt){
	if(cnt && !val) return true;
	if(pos > n) return false;
	if(dfs(pos + 1, val, cnt)) return true;
	if(dfs(pos + 1, val ^ a[pos], cnt + 1)) return true;
	return false;
}

int main()
{
	for(int i = 1; i <= 10; ++i){
		n = read();
		for(int j = 1; j <= n; ++j) a[j] = read();
		dfs(1, 0, 0) ? printf("NO\n") : printf("YES\n");
	}
	return 0;
}

博弈论DP习题

7、取石子

Describe

同样n堆石子,两种操作,拿一个或者合并其中两堆,不能操作的人输

Solution

参考的这篇博客https://www.cnblogs.com/JCNL666/p/10904187.html

把一个石子的堆的数量作为一个状态,将多个石子的堆的数量作为一个状态跑搜索,同时用f数组来记录答案减少搜索量

把自己的理解放到了注释里,看代码吧

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1010;
const int INF = 1e9+7;
const int mod = 1e9+7;

int T, n;
int f[55][55 * MAXN];

int read(){
	int s = 0, f = 0;
	char ch = getchar();
	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
	return f ? -s : s;
}

int dfs(int cnt, int stp){
	if(cnt <= 0 && stp <= 0) return 0;//如果没有石子了,游戏结束
	if(f[cnt][stp] != -1) return f[cnt][stp];//如果以前搜到过,直接返回存储的值,减少搜索复杂度
	if(cnt <= 0) return f[cnt][stp] = (stp & 1);//只剩下热闹堆值,只需要判断热闹堆里石子的奇偶性就好了
	if(stp == 1) return f[cnt][stp] = dfs(cnt + 1, 0);//如果热闹堆还剩下一个石子,就变成了一个寂寞堆
	
	f[cnt][stp] = 0;//先赋为0,后面再看看是否有使这个状态必胜的后续状态
	
	if(cnt && !dfs(cnt - 1, stp)) return f[cnt][stp] = 1;//从寂寞堆里拿一颗石子
	if(stp && !dfs(cnt, stp - 1)) return f[cnt][stp] = 1;//从热闹堆里拿一颗石子
	if(cnt && stp && !dfs(cnt - 1, stp + 1)) return f[cnt][stp] = 1;//将寂寞堆合并到热闹堆里
	if(cnt > 1 && !dfs(cnt - 2, stp + 2 + (stp ? 1 : 0))) return f[cnt][stp] = 1;//将两个寂寞堆合并,至于后面为啥多加个1?还不是很懂
	return f[cnt][stp]; 
}

int main()
{
	T = read();
	memset(f, -1, sizeof f);
	while(T--){
		int cnt = 0, stp = 0;
		n = read();
		for(int i = 1, x; i <= n; ++i) x = read(), (x == 1) ? ++cnt : stp = (stp + x + 1);
		//通过题解的论证,发现热闹堆的合并并不影响结果,所以直接合并起来
		if(stp) stp--;//少合并一次要减一(感觉这里有问题?)
		dfs(cnt, stp) ? puts("YES") : puts("NO");
	}
	return 0;
}

8、取石子游戏

Describe

n堆石子,一次取任意个,但是只能从第一堆或者最后一堆取,求是否先手必胜

Solution

yyb神仙%%%!

洛谷题解

设的神仙状态,建议亲自观摩;还有一个很神奇的做法也能过,可惜正确性不能保证

Code

DP:

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e3+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

int T, n;
int a[MAXN], L[MAXN][MAXN], R[MAXN][MAXN];

int read(){
	int s = 0, f = 0;
	char ch = getchar();
	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
	return f ? -s : s;
}

int main()
{
	T = read();
	while(T--){
		n = read();
		for(int i = 1; i <= n; ++i) L[i][i] = R[i][i] = a[i] = read();
		for(int len = 2; len <= n; ++len){
			for(int i = 1, j = i + len - 1; j <= n; ++i, ++j){
				int x = a[j], l = L[i][j - 1], r = R[i][j - 1];
				if(x == r) L[i][j] = 0;
				else if((x < l && x < r) || (x > l && x > r)) L[i][j] = x;
				else if(r < x && x < l) L[i][j] = x - 1;
				else L[i][j] = x + 1;
				
				x = a[i], l = L[i + 1][j], r = R[i + 1][j];
				if(x == l)  R[i][j] = 0;
				else if((x < l && x < r) || (x > l && x > r)) R[i][j] = x;
				else if(r < x && x < l) R[i][j] = x + 1;
				else R[i][j] = x - 1; 
 			}
		}
		printf("%d\n", (L[2][n] == a[1]) ? 0 : 1);
	}
	return 0;
}

奇技淫巧:(虽然过了但已被Hack)
主要是判断最外边两个堆的关系,看能不能让对手先拿里面的堆

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

int T, n;
int a[MAXN];

int read(){
	int s = 0, f = 0;
	char ch = getchar();
	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
	return f ? -s : s;
}

int main()
{
	T = read();
	while(T--){
		n = read();
		int ans = 0;
		for(int i = 1; i <= n; ++i)	a[i] = read();
		if(abs(a[1] - a[n]) <= 1){
			if(a[1] != 1 && a[n] != 1) printf("0\n");
			else printf("1\n");
		}
		else printf("1\n"); 
	}
	return 0;
}

如果本文有什么错误,或者您有什么问题,请在评论区提出。