博弈论总结四大博弈模型 SG函数

小鱼儿 2022-12-02 00:56 299阅读 0赞

### 一、博弈论 ###

#### 1、博弈论是什么 ####

**博弈论**是二人在平等的对局中各自利用对方的策略变换自己的对抗策略，达到取胜的目的。

#### 2、平等博弈 ####

在我们平时做题碰见的博弈都是平等博弈，平等博弈满足下面这几个要求：  
1.两人游戏，每人轮流做出决策，且每人的决策都是对自己有利的。（让自己赢）  
2.有一个终止状态，到终止状态后游戏结束，不会有平局状态。（获胜的条件）  
3.游戏可以在有限步数内结束。（不会无限重复，得不到答案）  
4.所有规定对两人都是一样的。（平等游戏）

### 二、四大博弈模型 ###

#### 1、巴什博弈： ####

**1.定义：** 只有**一堆**物品，共n个，两人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取完这堆物品的人获胜。

**2.结论：** n%(m+1) != 0，先手肯定获胜

**3.证明：** 关于严格证明这里不多提，自己可以分析一下，每次给对手留剩m+1的倍数，最后一轮自己一定获胜，所以就看第一次取，自己能否构建这个局势（剩下m+1的倍数个物品），使得对手必输。

--------------------

#### 2、尼姆博弈 ####

**1.定义：** 有**任意堆**物品，每堆物品的个数也任意，双方轮流取物品，每次只能从一堆中取至少一个物品，取到最后一件物品的人获胜。

**2.结论：** 把每堆物品数全部异或起来，若值为0，则先手必败，否则先手必胜。

**3.证明：** 我们也是不严格证明，我们将每堆物品数异或起来为0这个状态称为**必败态**，顾名思义，这个状态下，谁取谁必败。因为当这个状态时，经过两人轮流取物，后者始终可以维持这个必败态，即A取完后，B一定可以取一个数，使得取完后每堆物品数异或起来仍为0。这样一**直到最后一轮**，B取完一定会使每堆数都为0，此时同样也是必败态（异或起来为0），这时B获胜，A面对所有堆都为0这个状态取，直接失败。  
所以当每堆物品数全部异或起来，若值为0，此时已是必败态，先手必败；若值不为0，则先手一定会取一个数使得每堆数异或起来为0，达到必败态，从而后手必败。  
**注：** 博弈时，每个人都会走当前最优策略，所以每个人都会尽量给对方创造必败态，给自己创造必胜态。

--------------------

#### 3、斐波那契博弈（k倍动态减法） ####

**1.定义：** 有一堆物品，共n个，两人轮流取物，先手可取任意件，但不能不取，也不能把物品取完，之后每次取的物品数不能超过上一次的两倍，且至少为1件，取走最后一件物品的人获胜。

**2.结论：** 当且仅当n不是斐波那契数时，先手胜。

**3.证明：** 此博弈的证明需要各种不等式关系证明，一般记住结论即可，具体证明可以看[这篇文章][Link 1]

##### 扩展：k倍动态减法 #####

**1.定义：** 有一堆物品，共n个，两人轮流取物，先手可取任意件，但不能不取，也不能把物品取完，之后每次取的物品数不能超过上一次的k倍，且至少为1件，取走最后一件物品的人获胜。  
和斐波那契博弈一样，只不过拿的不是2倍了，而是一个任意的k倍，当k为2时就是完全的斐波那契博弈了。

**2.结论：** 我们手动构建一个a数列，若n是该数列中的数时，先手必败，否则后手必败。即该数列是必败态。

**3.证明：** 代码如下，具体证明可以看[这篇文章][Link 2]

**4.构建队列模板**

#include<iostream>
    using namespace std;
    const int N = 10010;
    
    int main()
    { 
    	int n,k,a[N],b[N];
    	cin >> n >> k;
    	a[0] = b[0] = 1;
    	int i = 0,j = 0;
    	while(n > a[i])
    	{ 
    		i++;
    		a[i] = b[i-1] + 1;
    		while(a[j+1] * k < a[i])
    			j++;
    		if(a[j] * k < a[i])
    			b[i] = b[j] + a[i];
    		else
    			b[i] = a[i];
    	}
    	if(n == a[i])
    		cout << "lose" << endl;
    	else
    		cout << "win" << endl;
    
    	return 0;
    }

--------------------

#### 4、威佐夫博弈 ####

**1.定义：** 有两堆物品，数量分别为a个和b个，两人轮流取物，每次可以从一堆中取出任意个，也可以从两堆中取出相同数量的物品，每次至少要取一个，最后取完所有物品的人获胜。

**2.结论：** 我们规定两堆数量为a和b且a < b，若a和b的差值乘上1.618恰好是a的值，则次为必败态，先手必败。有时追求精度可记w = (int)\[( (sqrt(5)+1) / 2) \* (b-a)\]，若w == a，则先手必败，否则先手必胜。

**3.证明：** 这个证明比较神奇，也出现了神奇的黄金分割率618，具体证明可以看[这篇文章][Link 3]

**4.代码模板：**

#include<iostream>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    
    int main()
    { 
    	int a,b;
    	cin >> a >> b;
    	if(b < a)
    		swap(a,b);
    	double c = (double)(b-a);
    	int w = (int)(((sqrt(5)+1) / 2) * (b-a));
    	if(w == a)
    		cout << "lose" << endl;
    	else
    		cout << "win" << endl;
    
    	return 0;
    }

### 三、SG函数 ###

**1.mex函数：** mex函数就是求集合中未出现的最小自然数。如mex\{1，4，5，8\} = 0，mex\{0，1，5，9，13\} = 2 。

**2.SG函数：** SG函数是将一个ICG（公平组合游戏）看作一个有向无环图，每一个局面看作一个结点，给所有当前局面和能走到的下一个局面建一条有向边。

> 对于一个给定的有向无环图，定义关于图的每个顶点的SG函数SG如下，SG(x)= mex(\{ SG(y1),SG(y2),…,SG(yk)\}) (y是x的后继) 。

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

整个有向图游戏G的SG函数值被定义为有向图游戏起点的SG函数值。

**3.结论：**  
先定义 有向图游戏的和的**SG函数值**等于它包含的**各个子游戏SG函数值的异或值**。而终点也就是游戏结束局面的SG(x) = 0。  
则有：

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

具体证明可以参考[这篇文章][Link 4]

--------------------

这些就是基础博弈的一些总结，后期可能会修改增加。  
小白自用笔记，简单整理。

[Link 1]: https://blog.csdn.net/acm_cxlove/article/details/7835016
[Link 2]: https://blog.csdn.net/bless924295/article/details/51365505
[Link 3]: https://blog.csdn.net/qq_41311604/article/details/79980882
[Link 4]: https://blog.csdn.net/qq_39239844/article/details/81100916