博弈论
【注明】：引用了两篇博客的内容。
https://blog.csdn.net/qq_36553623/article/details/67061459
https://blog.csdn.net/niushuai666/article/details/6638943
这是我第一次写这样总结性，综合性的讲解文章，大佬们如果发现我的错误，并且指出的话对我的帮助是非常大的。在这里感谢大家啦：）
目录
一．巴什博奕（Bash Game）：
引入
首先我们来玩一个比较古老的报数游戏。A和B一起报数，每个人每次最少报一个,最多报4个。轮流报数,看谁先报到30.
如果不知道巴什博弈的可能会觉得这个是个有运气成分的问题，但是如果知道的人一定知道怎样一定可以赢。
比如A先报数的话,那么B一定可以赢(这里假定B知道怎么正确的报数)
B可以这样报数,每次报5-k(A)个数,其中k(A)是A报数的个数这样的话没一次
两人报完数之后会变成5 10 15 20 25 30这样是不是B一定会赢呢?是不是有一种被欺骗的感觉呢?好吧下面我们来看看这个原理。我们先看下一个一眼就能看出答案的例子 比如说我们报到5(4+1),每次报最多报4个,最少报1个.那么是不是后者一定可以赢呢？答案是肯定的。好了到这巴什博弈的精髓基本就OK了。
那么如果我们要报到n+1,每次最多报n个,最少报1个的话,后者一定能够赢。
现在我们需要报数到n,而每次最多报数m个,最少报数1个.我们可以化成这样
n = k*(1+m)+r(0 <= r <= m）这样的话如果r不等于0那么先手一定会赢，为什么呢？首先先手报r个,那么剩下k倍(1+m)个数,那么我们每次报数1+m-k(B)个数就一定能保证最后剩下1+m个,那么就到了上面我们说的那个了,先手就一定会赢,如果r=0那么后手一定会赢,道理一样的。
到这巴什博弈也就介绍完了,知道这个道理之后我们也可以去骗小朋友了。-_-//
理解
进入游戏的状态就决定了输赢。如果两个人可以说的数是1~K，那么如果进入游戏时，你面对的总数n是（K+1）的倍数，那么对方赢，若不是（K+1）的倍数，则你赢。（因为你一定可以将n变为（K+1）的倍数，而后对方说出一个数x，你说（K+1-x）即可）。
例如可以说的数是1~10，总数是n=30，你先说。（这时我们注意一个隐藏条件，对方说出一个数字，你一定可以说出另外一个数字，并让二者和为11，也就是上一段提到的（K+1））。你说8，n变为22。这时无论对方说什么，你都可以让n变为11，然后再变为0。
习题 hdu 1846 巴什博弈
#include<iostream>
#include<stdio.h>
#include<sstream>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<string.h>
using namespace std;
int main()
{
int c, n, m;
cin>>c;
for(int i=0; i<c; i++) {
cin>>n>>m;
if(n%(m+1) == 0)
cout<<"second"<<endl;
else
cout<<"first"<<endl;
}
return 0;
}
二．威佐夫博奕（Wythoff Game）：
引入
这种博弈比前面一种要稍微复杂一点。我们来看下下面这个游戏。
有两堆火柴棍,每次可以从某一堆取至少1根火柴棍(无上限)，或者从两堆取相同的火柴棍数。最后取完的是胜利者。好了,如果你不知道这个博弈定理,对于小数目的火柴棍数,可能还能推出来,但是如果火柴棍数一多,就不行了。看了下面的这个介绍,你也会有一种被骗的感觉。
首先我们知道两堆火柴是没有差别的,也就是说第一堆有a根,第二堆有b根和第一堆有b根,第二堆有a根是一样的结果。
我们用一个二维的状态（a,b)来记录当前剩下的火柴数，表示第一堆剩下a根火柴,第二堆剩下b根火柴。同样我们假设两个人的编号是A和B，且A先取。
那么如果某个人遇到了这样的状态(0,0)那么也就是说这个人输了。这样的状态我们叫做奇异状态,也可以叫做失败态。
那么接下来的几个失败态为(1,2),(3,5),(4,7),(6,10),(8,13)……
我们用a[i]表示失败态中的第一个,b[i]表示失败态中的第二个.(i从0开始).
那么我们可以看到b[i] = a[i]+i;（i >= 0）,a[i]是前面的失败态中没有出现过的最小的整数
下面我们可以得到三个基本的结论。
1.每个数仅包含在一个失败态中
首先我们知道a[k]是不可能和前面的失败态中的a[i],b[i]重复的(这点由a[i]的得到可以知道)
b[k] = a[k]+k > a[k-1]+k>a[k-1]+k-1+1>a[k-1]+(k-1) = b[k-1]>a[k-1]这样我们知道每个数仅在一个失败态中。
2.每个失败态可以转到非失败态。
加入当前的失败态为(a,b)，那么如果我们只在一堆中取的话,肯定会变成非失败态(这点由第一点可以保证),如果从两堆同时取的话,由于每个失败态的差是不一样的,所以也不可能得到一个失败态。也就是说一个失败态不管你怎么取,都会得到一个非失败态。
3.每个非失败态都可以转到一个失败态
对于这个结论,首先我们要知到每个状态(a,b)要么a = a[i],要么b = b[i].(每个数都出现在一个失败态中),下面我们分两种情况来讨论
I.a = a[i].如果b = a的话那么一次取完就变成了(0,0).如果b > b[i]的话,那么我们从第二堆中取走b-b[i]就变成了一个失败态。如果b < b[i].那么我们从两堆中同时取走a-a[b-a[i]]这样得到失败态(a[b-a[i]],a[b-a[i]]+b-a[i])(a[i] = a)
II.b = b[i].如果a > a[i]那么我们从第一堆中取走a-a[i]根火柴.
如果a < a[i].这里又分两种情况。第一是a = a[k](k < i)
那么我们从第二堆取走b - b[k]就行了。
第二是a = b[k]这样的话由于两堆火柴是没有区别的,所以我们把b变成a[k]就行了,也即是从第二堆火柴中取走b - a[k]就变成了失败态
至于怎么判断一个状态是否是失败态.我们可以用下面的方法来判断(本人暂时还不会证明)
a[i] = [i*(1+√5)/2](这里的中括号表示向下取整) b[i] = a[i]+i;
那么这就是一个失败态
理解
两堆石子，两种取法：①从任意一堆中取任意个；②从两堆中同时取相同多个。
这个Wythoff博弈论和Bash博弈论其实有些像，就是存在两种状态：①必赢，②必输。如果你从必赢状态进入游戏，下一步对手只能进入必输状态，然后轮到你的时候你又可以进入必赢状态。（必赢状态无论怎么走都是进入必输状态，必输状态一定可以一步进入必赢状态）。
而Wythoff的必输状态比较特别，是（0,0），（1,2），（3,5），（4,7），（6,10），（8,13）。。。。
我学习时遇到的疑问就是这些数字怎么来的，设为（a,b）。
([ ]表示向下取整)，
,
具体为什么可以见百度百科有证明过程。
对于我们编代码或者计算呢，背下来就ok了。所以我们只需判断进入游戏时给我们的两个数字是否符合上面的公式，如果符合那么我们输了（后手赢），如果不符合则我们赢（先手赢）。
对于不理解怎么走就不开心的同学呢，我们可以走走试试。①假如初状态是（4，6），我们发现差值为2，则我们可以转化为差值同样为2的失败态（3,5），因为任意差值的失败态我们都可以找到。②假如初状态是（3，6），我们发现差值为3，为啥不行了？？？？别急我们还是可以转化为失败态（3,5），因为我们可以找到和a相比配的失败态。相信我任何组合都逃不出这两种情况。然后对手在（3,5）的情况下任意走，我们还是可以根据上面两种情况找到下一个失败态。如果想口算或者和其他同学玩的话可以用：a=k*1.6试试。数小的时候精度ok的。
习题 poj 1067 威佐夫博弈
#include<iostream>
#include<stdio.h>
#include<sstream>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<string.h>
using namespace std;
int main()
{
int a, b;
while(cin>>a>>b) {
if(a>b)
swap(a,b);
int k = b-a;
int c = k*(1+sqrt(5))/2;
if(c == a)
cout<<"0"<<endl;
else
cout<<"1"<<endl;
}
return 0;
}
三．尼姆博奕（Nimm Game）：
引入
指的是这样的一个博弈游戏，目前有任意堆石子，每堆石子个数也是任意的，双方轮流从中取出石子，规则如下：
1)每一步应取走至少一枚石子；每一步只能从某一堆中取走部分或全部石子；
2)如果谁取到最后一枚石子就胜。
也就是尼姆博弈（Nimm Game）。
必败局面：也叫奇异局势。无论做出何出操作，最终结果都是输的局面。必败局面经过2次操作后，可以达到另一个必败局面。
必胜局面：经过1次操作后可以达到必败局面。
即当前局面不是必败局面就是必胜局面，而必胜局面可以一步转变成必败局面。
最终状态：
（1）最后剩下一堆石子；（必胜局面）
（2）剩下两堆，每堆一个；（必败局面）
（3）当石子剩下两堆，其中一堆只剩下1颗，另一堆剩下多于n颗石子时，当前取的人只需将多于1颗的那一堆取出n-1颗，则局面变为刚才提到的必败局面。（必胜局面）
判断当前局势是否为必胜（必败）局势：
1）把所有堆的石子数目用二进制数表示出来，当全部这些数按位异或结果为0时当前局面为必败局面，否则为必胜局面；
2）在必胜局面下，因为所有数按位异或的结果是大于零的，那么通过一次取，将这个（大于其它所有数按位异或的结果的）数下降到其它所有数按位异或的结果，这时局面就变为必败局面了。
定理：一组自然数中必然存在一个数，它大于等于其它所有数按位异或的结果。
证明：原命题等价于，设a1＾a2＾... ＾an=p，p≠0时，必存在k，使得ak＾p<ak（当p=0时，对于任意的k，有ak＾p=ak）。
设p的最高位是第q位，则至少存在一个k，使得ak的第q位也是1，而ak＾p的第q位为0，所以ak^p<ak
理解
我们可以从n堆石子中的任意一堆石子中取任意个石子，目标是取到最后一堆石子。这其实和前两种博弈也是相同的道理。但是我的思路入口是“平衡”，什么是“平衡”呢？就是在这个状态我们一定可以同过欧数次操作取完石子堆，原因是无论对手如何打破平衡我们都可以再让整个状态回到平衡。
例如两堆石子（10,10）。这就是个平衡态(先手输，后手赢)，对手无论怎么做都会打破这个平衡态。而我们只需模仿对手的行为恢复平衡态，或者直接胜利。因为是n堆，所以我们要找n堆的平衡态就是利用按位异或的方法。
按位异或就是指相同得1，不同得0。把每个石子堆的石子数量按位异或得到的就是整个石子堆的不平衡点，我们只需要从某一堆中那走这么多的石子即可。
例如（1,2,1），按位异或结果为2。我们让每堆石子再去异或[结果2]，若得到的数比原堆数小，则我们让这堆石子变为得到数就可以了（因为这样再去异或结果一定为0），变为（1,0,1）。进入了平衡状态。
又例如（1,2,3），按位异或结果为0，是平衡状态，变为（0,2,3）则可通过变为（0,2,2）回到平衡状态[异或结果为1]，变为（1,2,2）则可通过变为（0,2,2）回到平衡状态。等等。自己可以尝试感受一下按位异或的作用。
所以我们的做题思路就很清晰：按位异或，结果为0后手赢，不为0先手赢。
习题 hdu 1850 尼姆博弈
#include<iostream>
#include<stdio.h>
#include<sstream>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<string.h>
using namespace std;
int main()
{
int m;
while(1) {
cin>>m;
if(!m)
break;
int arr[105];
int temp ;
cin>>temp;
arr[0] = temp;
for(int i=1; i<m; i++) {
cin>>arr[i];
temp ^= arr[i];
}
if(temp == 0)
cout<<0<<endl;
else {
int cnt=0;
for(int i=0; i<m; i++) {
if((temp^arr[i])<arr[i])
cnt++;
}
cout<<cnt<<endl;
}
}
return 0;
}
四、P/N图解博弈论
引入
http://qianmacao.blog.163.com/blog/static/203397180201222945044622/
习题 HDU 2147 kiki's game
#include<iostream>
#include<stdio.h>
#include<sstream>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<string.h>
using namespace std;
int main()
{
int n, m;
while(true) {
cin>>n>>m;
if(n==0 && m==0)
break;
if(n%2!=0 && m%2!=0)
cout<<"What a pity!"<<endl;
else
cout<<"Wonderful!"<<endl;
}
return 0;
} 上一篇： 【数据结构系列】查找算法及其实现