[博弈论]博弈论基本题型及5大常见博弈论原理

发表于 | 分类于 ， | 热度 ℃
字数统计: 4,138 | 阅读时长 ≈ 17

取石子游戏

根据题目的意思，看它属于哪种博弈，属于哪种博弈的变形。 然后根据对应的博弈模型的解题策略来求解， 有时候并不一定能够直接看出它属于哪种模型，那这个时候就可以通过判断自己每步可选的策略，对于自己每步走的，对当前局势的影响。然后推断出与之相对应的博弈模型。

巴什博奕（Bash Game）

有n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m个。最后取光者得胜。

假设n = m + 1，那么无论如何取，先取者必输。因为先取者无论取多少，后者一次性便可将剩余取完。

胜利法则：如果 n=（m+1）r+s，（r 为任意自然数，s≤m),那么先取者要拿走 s 个物品，如果后取者拿走 k（≤m)个，那么先取者再拿走 m+1-k 个，结果剩下 （m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream> 
using namespace std;
int main() {
	int iCase;
	cin >> iCase;
	while (iCase--) {
		int n, m;
		cin >> n >> m;
		if (n % (m + 1) == 0) cout << "lost" << endl;
		else cout << "win" << endl;
	}
	return 0;
}

威佐夫博奕（Wythoff Game）

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

这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，…,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们 称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。

可以看出,a0=b0=0,ak 是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有如下三条性质：

1。任何自然数都包含在一个且仅有一个奇异局势中。

2。任意操作都可将奇异局势变为非奇异局势。

3。采用适当的方法，可以将非奇异局势变为奇异局势。

两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。

如何判定是否是奇异局势呢？

有如下公式： ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括号表示取整函数)

其中（1+√5）/2 = 1.618…,即为黄金分割数。因此,由 ak，bk 组成的矩形近似为黄金矩形，由于 2/（1+√5）=（√5-1）/2，可以先求出 j=[a（√5-1）/2]，若a=[ j（1+√5）/2]，那么 a = aj，bj = aj + j，若不等于，那么 a = aj+1，bj+1 = aj+1 + j + 1，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h> 
#include <math.h> 
const double ep1 = (sqrt(5.0) - 1.0) / 2.0;
const double ep2 = (sqrt(5.0) + 1.0) / 2.0;
int main() {
	int m, n;
	while (scanf("%d %d", &m, &n) != EOF) {
		if (m > n) {
			int tmp;
			tmp = m, m = n, n = tmp;
		}
		int id = m * ep1;
		int tmp1 = ep2 * id, tmp2 = id + tmp1;
		int tmp3 = ep2 * (id + 1), tmp4 = id + 1 + tmp3;
		if (tmp1 == m && tmp2 == n) printf("0\n");
		else if (tmp3 == m && tmp4 == n) printf("0\n");
		else printf("1\n");
	}
	return 0;
}

斐波那契博弈（Fibonacci Nim）

有一堆个数为 n 的石子，游戏双方轮流取石子，满足

1)先手不能在第一次把所有的石子取完；

2)之后每次可以取的石子数介于 1 到对手刚取的石子数的 2 倍之间（包含 1 和对手刚取的石子数的 2 倍）。

约定取走最后一个石子的人为赢家，求必败态。

这个和之前的 Wythoff’s Game 和取石子游戏 有一个很大的不同点，就是游戏规则的动态化。之前的规则中，每次可以取的石子的策略集合是基本固定的，但是这次有规则 2：一方每次可以取的石子数依赖于对手刚才取的石子数。

胜利法则：先手胜当且 仅当 n 不是 Fibonacci 数。换句话说，必败态构成 Fibonacci 数列。

证明：

这里需要借助“Zeckendorf定理”（齐肯多夫定理）：任何正整数可以表示为若干个不连续的 Fibonacci 数之和。

FIB 数列的必败证明：

1、当 i=2 时，先手只能取 1 颗，显然必败，结论成立。

2、假设当 i<=k 时，结论成立。则当 i=k+1 时，f[i] = f[k]+f[k-1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream> 
using namespace std;
long long int f[50];
int main() {
	int n, i;
	f[0] = f[1] = 1;
	for (i = 2; i < 50; i++) {
		f[i] = f[i - 1] + f[i - 2];
	}
	while (cin >> n) {
		if (n == 0) break;
		for (i = 0; i < 50; i++) {
			if (f[i] == n) break;
		}
		if (i < 50) cout << "Second win" << endl;
		else cout << "First win" << endl;
	}
	return 0;
}

K倍博弈

共 n 个石子，两个人按顺序依次取石子。先手不能全部取完，之后每人取的个数不能超过另一个人上轮取的 K倍。 对于给定的 n, k， 先手是否有必胜的策略。

当 k=1 的时候 可知必败局面都是 2^i 将 n 分解成二进制，然后先手取掉最后一个 1，然后对方必然无法去掉更高的 1，而对方取完我方至少还能拿掉最后一 个 1 导致对方永远取不完。

当 k=2 的时候，必败局面都是斐波那契数列。利用“先手去掉最后一个 1，则后手必不能去掉更高阶的 1 导致取不完”的思想，斐波那契数列有一个非常好 的性质就是：任意一个整数可以写成斐波那契数列中的不相邻的项的和，于是将 n 写成这种形式，先取走最后一个 1，对方能取的数是这个数*2，小于高 2 位的 1，所以取不完。

当 K 的时候， 想办法构造数列，将 n 写成数列中一些项的和，使得这些被取到的项的相邻两个倍数差距>k 那么每次去掉最后一个 1 还是符合上面的条件。

设这个数列已经被构造了 i 项，第 i 项为 a[ i ]，前 i 项可以完美对 1..b[ i ] 编码使得每个编码的任意两项倍数>K 那么有 a[ i+1 ] = b[ i ] + 1;这是显然的 因为 b[ i ] + 1 没法构造出来，只能新建一项表示。然后计算 b[ i+1] 既然要使用 a[ i+1 ] 那么下一项最多只能是某个 a[ t ] 使得 a[ t ] * K < a[ i+1 ] 于是b[ i ] = b[ t ] + a[ i+1 ] 然后判断 n 是否在这个数列里面如果在，那么先手必败。否则不停的减掉数列 a 中的项构造出 n 的分解，最后一位就是了。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h> 
#include <string.h> 
#include <iostream> 
using namespace std;
const int maxn = 2000000;
int a[maxn], b[maxn];
int main()
{
	int n, k;
	int cas = 0, cass;
	for (scanf("%d", &cass); cass--;)
	{
		scanf("%d%d", &n, &k);
		++cas;
		printf("Case %d: ", cas);
		int i = 0, j = 0;
		a[0] = b[0] = 1;
		while (a[i]<n)
		{
			i++;
			a[i] = b[i - 1] + 1;
			while (a[j + 1] * k<a[i])
				j++;
			if (a[j] * k<a[i])
				b[i] = a[i] + b[j];
			else
				b[i] = a[i];
		}
		if (a[i] == n)
			puts("lose");
		else puts("win");
	}
	return 0;
}

ＳＧ函数的求解(SG博弈）

给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。

这个游戏可以认为是所有 Impartial Combinatorial Games 的抽象模型。也就是说，任何一个 ICG 都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。

下 面我们就在有向无环图的顶点上定义 Sprague-Garundy 函数。首先定义 mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如 mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

对于一个给定的有向无环图，定义关于图的每个顶点的 Sprague-Grundy 函数 g如下：g(x)=mex{ g(y) | y 是 x 的后继 }。

SG 函数的性质：

1.首先，所有的 terminal position 所对应的顶点，也就是没有出边的顶点，其 SG 值为 0，因为它的后继集合是空集。

2.然后对于一个 g(x)=0 的顶点 x，它的所有后继 y 都满足 g(y)!=0。

3.对于一个 g(x)!=0 的顶点，必定存在一个后继 y 满足 g(y)=0。

以上这三句话表明，顶点 x 所代表的 postion 是 P-position 当且仅当 g(x)=0。我们通过计算有向无环图的每个顶点的 SG 值，就可以对每种局面找到必胜策略了。

Nim 游戏的规则：

每次选择 一堆数量为 k 的石子，可以把它变成 0、变成 1、……、变成 k-1，但绝对不能保持 k不变。

变形

假设不是一枚棋子，而是n枚棋子，如何获胜？

让我们再来考虑一下顶点的 SG 值的意义。当 g(x)=k 时，表明对于任意一个0<=i<k，都存在 x 的一个后继 y 满足 g(y)=i。也 就是说，当某枚棋子的 SG 值是 k 时，我们可以把它变成 0、变成 1、……、变成 k-1，但绝对不能保持 k 不变。

这表明，如果将 n 枚棋子所在的顶 点的 SG 值看作 n 堆相应数量的石子，那么这个 Nim 游戏的每个必胜策略都对应于原来这 n 枚棋子的必胜策略！

对于 n 个棋子，设它们对应的顶点的 SG 值分别为(a1,a2,…,an)，再设局面(a1,a2,…,an)时的 Nim 游戏的一种必胜策略是把 ai 变成 k，那么原游戏的一种必胜策略就是把第 i 枚棋子移动到一个 SG 值为 k 的顶点。

其实我们还是只要证明这种多棋子的有向图游戏的局面是 P-position 当且仅当所有棋子所在的位置的 SG 函数的异或为 0。这个证明与上节的 Bouton’s Theorem 几乎是完全相同的，只需要适当的改几个名词就行了。

刚才，我为了使问题看上去更容易一些，认为 n 枚棋子是在一个有向图上移动，但如果不是在一个有向图上，而是每个棋子在一个有向图上，每次可 以任选一个棋子（也就是任选一个有向图）进行移动，这样也不会给结论带来任何变化。 所以我们可以定义有向图游戏的和(Sum of Graph Games)：设 G1、G2、……、Gn是 n 个有向图游戏，定义游戏 G 是 G1、G2、……、Gn 的和(Sum)，游戏 G的移动规则是：任选一个子游戏 Gi 并移动上面的棋子。Sprague-Grundy Theorem 就是：g(G)=g(G1)^g(G2)^…^g(Gn)。也就是说，游戏的和的 SG 函数值是它的所有子游戏的 SG 函数值的异或。

再考虑在本文一开头的一句话：任何一个 ICG 都可以抽象成一个有向图游戏。所以“SG 函数”和“游戏的和”的概念就不是局限于有向图游戏。我们给每 个 ICG 的每个 position 定义 SG 值，也可以定义 n 个 ICG 的和。所以说当我们面对由 n 个游戏组合成的一个游戏时，只需对于每个游戏找出求它的每个 局面的 SG 值的方法，就可以把这些 SG 值全部看成 Nim 的石子堆，然后依照找 Nim 的必胜策略的方法来找这个游戏的必胜策略了！

NIM游戏

有 n 堆石子，每次可以从第 1 堆石子里取 1 颗、2 颗或 3颗，可以从第 2 堆石子里取奇数颗，可以从第 3 堆及以后石子里取任意颗… … 我们可以把它看作 3 个子游戏，第 1 个子游戏只有一堆石子，每次可以取 1、2、3颗，很容易看出 x 颗石子的局面的 SG 值是 x%4。第 2 个子游戏也是只有一 堆 石子，每次可以取奇数颗，经过简单的画图可以知道这个游戏有 x 颗石子时的 SG值是 x%2。第 3 个游戏有 n-2 堆石子，就是一个 Nim 游戏。对于原游戏的每 个局面，把三个子游戏的 SG 值异或一下就得到了整个游戏的 SG 值，然后就可以根据这个 SG 值判断是否有必胜策略以及做出决策了。其实看作 3 个子游戏还是保守了些，干脆看作 n 个子游戏，其中第 1、2 个子游戏如上所述，第 3 个及以后的子游戏都是“1 堆石子，每次取几颗都可以”，称为“任取石子游戏”，这个超简 单的游戏有 x 颗石子的 SG 值显然就是 x。其实，n 堆石子的 Nim 游戏本身不就是 n 个“任取石子游戏”的和吗？

总结

SG 函数与“游戏的和”的概念不是让我们去组合、制造稀奇古怪的游戏，而是把遇到的看上去有些复杂的游戏试图分成若干个子游戏，对于每个比原游戏简化很多的子游戏找出它的 SG 函数，然后全部异或起来就得到了原游戏的 SG 函数，就可以解决原游戏了。

HDU 3032 Nim or not Nim

Lasker’s Nim 游戏：每一轮允许两会中操作之一：①、从一堆石子中取走任意多个，②、将一堆数量不少于 2 的石子分成都不为空的两堆。

很明显：sg(0) = 0，sg(1) = 1。 状态 2 的后继有：0，1 和（1，1），他们的 SG 值分别为 0，1，0，所以 sg(2)=2。 状态 3 的后继有：0、1、2、（1，2），他们的 SG 值分别为 0、1、2、3，所以sg(3) = 4。 状态 4 的后继有：0、1、2、3、（1，3）和（2，2），他们的 SG 值分别为 0，1，2，4，5，0，所以 sg(4) = 3. 由数学归纳法可以得出 sg(4k)=4k-1;sg(4k+1)=4k+1;sg(4k+2)=4k+2;sg(4k+3)=4k+4;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream> 
using namespace std;
int main() {
	int iCase;
	cin >> iCase;
	while (iCase--) {
		int n, cnt = 0, num;
		cin >> n;
		while (n--) {
			cin >> num;
			if (num % 4 == 0) num--;
			else if (num % 4 == 3) num++;
			cnt ^= num;
		}
		if (cnt == 0) cout << "Bob" << endl;
		else cout << "Alice" << endl;
	}
	return 0;
}

寻找必败态

必败态就是“在对方使用最优策略时，无论做出什么决策都会导致失败的局面”。其他的局面称为胜态，值得注意的是在 胜态下做出错误的决策也有可能导致失败。此类博弈问题的精髓就是让对手永远面对必败态。

必败态和胜态有着如下性质：

1、若面临末状态者为获胜则末状态为胜态否则末状态为必败态。

2、一个局面是胜态的充要条件是该局面进行某种决策后会成为必败态。

3、一个局面是必败态的充要条件是该局面无论进行何种决策均会成为胜态。

这三条性质正是博弈树的原理，但博弈树是通过计算每一个局面是胜态还是必败态来解题，这样在局面数很多的情况下是很难做到的，此时，我们可以利用人脑的推演归纳能力找 到必败态的共性，就可以比较好的解决此类问题了。

解题思路

分析初始局势是属于哪种形态，然后根据博弈中的些结论去推导当前状态是否是必败态。

文章结束了，但我们的故事还在继续
坚持原创技术分享，您的支持将鼓励我继续创作！