博弈论入门（Game Theory）

一、巴什博弈（Bash Game）

一堆n个物品，两人从中轮流取出（1~m）个；最后取光者胜。

操作：

n=k * (m+1)+r
先手拿走r个，那么后手无论拿走几个（1~m），先手只要使得拿走的和为m+1，先手就赢。
反之，n=k * (m+1)
先手无论怎么操作都会输

代码：

int main(){LL t;sf(t);while(t--){LL n,m;sf(n),sf(m);if(n%(m+1))printf("first\n");//可以把k*(m+1)这个状态给对面else printf("second\n");//到自己手上的状态是k*(m+1)}
}

例题：

1.Brave Game

HDU - 1846
十年前读大学的时候，中国每年都要从国外引进一些电影大片，其中有一部电影就叫《勇敢者的游戏》（英文名称：Zathura），一直到现在，我依然对于电影中的部分电脑特技印象深刻。
今天，大家选择上机考试，就是一种勇敢（brave）的选择；这个短学期，我们讲的是博弈（game）专题；所以，大家现在玩的也是“勇敢者的游戏”，这也是我命名这个题目的原因。
当然，除了“勇敢”，我还希望看到“诚信”，无论考试成绩如何，希望看到的都是一个真实的结果，我也相信大家一定能做到的~

各位勇敢者要玩的第一个游戏是什么呢？很简单，它是这样定义的：
1、 本游戏是一个二人游戏;
2、 有一堆石子一共有n个；
3、 两人轮流进行;
4、 每走一步可以取走1…m个石子；
5、 最先取光石子的一方为胜；

如果游戏的双方使用的都是最优策略，请输出哪个人能赢。
Input
输入数据首先包含一个正整数C(C<=100)，表示有C组测试数据。
每组测试数据占一行，包含两个整数n和m（1<=n,m<=1000），n和m的含义见题目描述。
Output
如果先走的人能赢，请输出“first”，否则请输出“second”，每个实例的输出占一行。
Sample Input
2
23 2
4 3
Sample Output
first
second

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
using namespace std;int main()
{int T,n,m;cin>>T;while(T--){cin>>n>>m;int l=n%(m+1);if(l) cout<<"first"<<endl;else cout<<"second"<<endl;}
}

2. kiki’s game

HDU - 2147
Recently kiki has nothing to do. While she is bored, an idea appears in his mind, she just playes the checkerboard game.The size of the chesserboard is n*m.First of all, a coin is placed in the top right corner(1,m). Each time one people can move the coin into the left, the underneath or the left-underneath blank space.The person who can’t make a move will lose the game. kiki plays it with ZZ.The game always starts with kiki. If both play perfectly, who will win the game?
Input
Input contains multiple test cases. Each line contains two integer n, m (0<n,m<=2000). The input is terminated when n=0 and m=0.
Output
If kiki wins the game printf “Wonderful!”, else “What a pity!”.

Sample Input
5 3
5 4
6 6
0 0
Sample Output
What a pity!
Wonderful!
Wonderful!

Tips： 只要m或者n有一个是偶数先手就能必胜。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
using namespace std;int main( )
{int n,m;while(~scanf("%d%d",&n,&m)){if(m==0||n==0) break;if(n%2==0||m%2==0)printf("Wonderful!\n");elseprintf("What a pity!\n");}
}

二、威佐夫博弈（Wythoff Game）

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

操作：

求出差值，如果 差值*黄金分割==最小值 后手赢，否则先手赢。

代码：

int main(){int a,b;while(scanf("%d%d",&a,&b)!=EOF){if(a>b)swap(a,b);int k=b-a;int ans=(a!=floor(k*(1.0+sqrt(5.0))/2));printf("%d\n",ans);//0必败态 1必胜态}return 0;
}

例题：

1.取石子游戏

HDU - 1527
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

Input
输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。
Output
输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。

Sample Input
2 1
8 4
4 7
Sample Output
0
1
0

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
using namespace std;int main()
{int n,m;while(~scanf("%d%d",&n,&m)){if(n>m) swap(n,m);int l=(m-n)*(1.0*(sqrt(5)+1)/2);if(n==l) printf("0\n");else printf("1\n");}
}

三、尼姆博弈论（Nim Game）

巴什博弈论扩展到多堆石头就是尼姆博弈论。
有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负。

操作：

a₁⊕a₂⊕a₃⊕…⊕a_k ==0，先手胜。
a₁⊕a₂⊕a₃⊕…⊕a_k !=0，先手败。

异或运算的结果不等于0，先手必胜。

在数学中,二进制的异或运算也可以看成是统计每一位上1的总个数的奇偶性:这一位上有偶数个1,那么这一位的计算结果为0;如果有奇数个，计算结果为1.所以，尼姆游戏中的异或运算也被称为Nim-sum运算。

下面对操作做简单的证明:
.
(1)必定能够从N- position转化到P-position.也就是说，先手处于必胜点N-position时可以拿走一一些石子，让后手必败。
读者可以先自己思考如何转化。下面是具体方法:任选一堆，例如第i堆，石头数量是k;对剩下的n-1堆做异或运算，设结果为H；如果H比k小，就把第i堆石头减少到H；这样操作之后，因为H^H=Q，所以n堆石头的异或等于0。可以证明，总会存在这样的第i堆石头，而且可能有多种转化方案。
下面例题hdu1850的程序中的“if((sum^a[i])<=a[i])”统计了所有方案。
.
(2)进人P-position后，轮到的下一个玩家，不管拿多少石子都会转移到N-position,因为任何一堆的数量变化,都会使得这堆的进制数至少有一位发生变化，导致异或运算的结果不等于0。也就是说,这一个玩家不管怎么拿石子都必败。

.
(3)在游戏过程中，按上述(1)和(2)的步骤在Nposition和P-position之间交替转化，直到所有堆的石头都是0,即终止于P-position。

上述证明过程也说明了玩家该如何进行游戏。
——《算法竞赛入门到进阶》

代码：

int main(){int m,ans,n;while(~scanf("%d",&m)){n=ans=0;while(m--)scanf("%d",&n),ans^=n,printf("ans=%d\n",ans);if(ans)printf("Yes\n");else printf("No\n");}
}

例题：

1. Being a Good Boy in Spring Festival

HDU - 1850
一年在外 父母时刻牵挂
春节回家 你能做几天好孩子吗
寒假里尝试做做下面的事情吧

陪妈妈逛一次菜场
悄悄给爸爸买个小礼物
主动地 强烈地 要求洗一次碗
某一天早起 给爸妈用心地做回早餐

如果愿意 你还可以和爸妈说
咱们玩个小游戏吧 ACM课上学的呢～

下面是一个二人小游戏：桌子上有M堆扑克牌；每堆牌的数量分别为Ni(i=1…M)；两人轮流进行；每走一步可以任意选择一堆并取走其中的任意张牌；桌子上的扑克全部取光，则游戏结束；最后一次取牌的人为胜者。
现在我们不想研究到底先手为胜还是为负，我只想问大家：
——“先手的人如果想赢，第一步有几种选择呢？”
Input
输入数据包含多个测试用例，每个测试用例占2行，首先一行包含一个整数M(1<M<=100)，表示扑克牌的堆数，紧接着一行包含M个整数Ni(1<=Ni<=1000000，i=1…M)，分别表示M堆扑克的数量。M为0则表示输入数据的结束。
Output
如果先手的人能赢，请输出他第一步可行的方案数，否则请输出0，每个实例的输出占一行。
Sample Input
3
5 7 9
0
Sample Output
1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
using namespace std;const int N = 100;
int a[N];int main()
{int n;while(~scanf("%d", &n) && n){int ans = 0;for(int i=0;i<n;i++){scanf("%d",&a[i]);ans^=a[i];}if(ans==0)printf("0\n");else {int cnt=0;for(int i=0;i<n;i++)if((ans^a[i])<a[i]) cnt++;printf("%d\n",cnt);}}
}

四、斐波那契博弈论

有一堆个数为n的石子，游戏双方轮流取石子，满足：
1)先手不能在第一次把所有的石子取完；
2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。
约定取走最后一个石子的人为赢家，求必败态。

操作：

当n为Fibonacci数时，先手必败。
否则先手必胜。

代码：

int f[1000];
int F(int n)
{f[1]=1;f[2]=1;for(int i=3;i<=100;i++){f[i] = f[i-1]+f[i-2];if(f[i]==n)return 1;if(f[i]>n)break;}return 0;
}

例题：

1. 取石子游戏

HDU - 2516
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".
Input
输入有多组.每组第1行是2<=n<2^31. n=0退出.
Output
先取者负输出"Second win". 先取者胜输出"First win".
参看Sample Output.
Sample Input
2
13
10000
0
Sample Output
Second win
Second win
First win

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
using namespace std;int f[1000];
int F(int n)
{f[1]=1;f[2]=1;for(int i=3;i<=100;i++){f[i] = f[i-1]+f[i-2];if(f[i]==n)return 1;if(f[i]>n)break;}return 0;
}
int main()
{int n;while(cin>>n){if(n==0)break;if(F(n)==0)printf("First win\n");elseprintf("Second win\n");}
}

五、SG函数

先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。
例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

操作：

求出sg(x),为等于没有指定给它的任意后继结点的sg值得最小非负整数。

代码：

void getSG(int n){memset(sg,0,sizeof sg);for(int i=1;i<=n;i++){               //n个物品memset(vis,0,sizeof vis);for(int j=0;j<=m&&i-j>0;j++)vis[sg[i-j]]=1;              //j表示可以取的数for(int j=0;j<=n;j++)if(!vis[j]){sg[i]=j;break;}}
}

例题：

1. Good Luck in CET-4 Everybody!

HDU - 1847
大学英语四级考试就要来临了，你是不是在紧张的复习？也许紧张得连短学期的ACM都没工夫练习了，反正我知道的Kiki和Cici都是如此。当然，作为在考场浸润了十几载的当代大学生，Kiki和Cici更懂得考前的放松，所谓“张弛有道”就是这个意思。这不，Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
“升级”？“双扣”？“红五”？还是“斗地主”？
当然都不是！那多俗啊~
作为计算机学院的学生，Kiki和Cici打牌的时候可没忘记专业，她们打牌的规则是这样的：
1、 总共n张牌;
2、 双方轮流抓牌；
3、 每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…）
4、 抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；
假设Kiki和Cici都是足够聪明（其实不用假设，哪有不聪明的学生~），并且每次都是Kiki先抓牌，请问谁能赢呢？
当然，打牌无论谁赢都问题不大，重要的是马上到来的CET-4能有好的状态。

Good luck in CET-4 everybody!
Input
输入数据包含多个测试用例，每个测试用例占一行，包含一个整数n（1<=n<=1000）。
Output
如果Kiki能赢的话，请输出“Kiki”，否则请输出“Cici”，每个实例的输出占一行。
Sample Input
1
3
Sample Output
Kiki
Cici

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
using namespace std;const int N=1010;
int sg[N],f[11];
bool vis[N];void getSG(int n)
{memset(sg,0,sizeof sg);for(int i=1;i<=n;i++){memset(vis,0,sizeof vis);for(int j=0;f[j]<=i;j++)vis[sg[i-f[j]]]=1;for(int j=0;j<=n;j++)if(!vis[j]){sg[i]=j;break;}}
}
int main()
{int n;for(int i=0;i<=10;i++) f[i]=(1<<i);getSG(1000);while(~scanf("%d",&n)&&n){if(sg[n]) printf("Kiki\n");else printf("Cici\n");}
}

2. S-Nim

POJ - 2960
Arthur and his sister Caroll have been playing a game called Nim for some time now. Nim is played as follows:
The starting position has a number of heaps, all containing some, not necessarily equal, number of beads.
The players take turns chosing a heap and removing a positive number of beads from it.
The first player not able to make a move, loses.
Arthur and Caroll really enjoyed playing this simple game until they
recently learned an easy way to always be able to find the best move:
Xor the number of beads in the heaps in the current position (i.e. if we have 2, 4 and 7 the xor-sum will be 1 as 2 xor 4 xor 7 = 1).
If the xor-sum is 0, too bad, you will lose.
Otherwise, move such that the xor-sum becomes 0. This is always possible.
It is quite easy to convince oneself that this works. Consider these facts:
The player that takes the last bead wins.
After the winning player’s last move the xor-sum will be 0.
The xor-sum will change after every move.
Which means that if you make sure that the xor-sum always is 0 when you have made your move, your opponent will never be able to win, and, thus, you will win.

Understandibly it is no fun to play a game when both players know how to play perfectly (ignorance is bliss). Fourtunately, Arthur and Caroll soon came up with a similar game, S-Nim, that seemed to solve this problem. Each player is now only allowed to remove a number of beads in some predefined set S, e.g. if we have S = {2, 5} each player is only allowed to remove 2 or 5 beads. Now it is not always possible to make the xor-sum 0 and, thus, the strategy above is useless. Or is it?

your job is to write a program that determines if a position of S-Nim is a losing or a winning position. A position is a winning position if there is at least one move to a losing position. A position is a losing position if there are no moves to a losing position. This means, as expected, that a position with no legal moves is a losing position.
Input
Input consists of a number of test cases.
For each test case: The first line contains a number k (0 < k ≤ 100) describing the size of S, followed by k numbers si (0 < si ≤ 10000) describing S. The second line contains a number m (0 < m ≤ 100) describing the number of positions to evaluate. The next m lines each contain a number l (0 < l ≤ 100) describing the number of heaps and l numbers hi (0 ≤ hi ≤ 10000) describing the number of beads in the heaps.
The last test case is followed by a 0 on a line of its own.
Output
For each position: If the described position is a winning position print a ‘W’.If the described position is a losing position print an ‘L’.
Print a newline after each test case.
Sample Input
2 2 5
3
2 5 12
3 2 4 7
4 2 3 7 12
5 1 2 3 4 5
3
2 5 12
3 2 4 7
4 2 3 7 12
0
Sample Output
LWW
WWL

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
using namespace std;
int s[105],sg[10001];
bool vis[10001];
void getSG(int t)
{int i,j;memset(sg,0,sizeof sg );for(i=1;i<=10001;i++){memset(vis,0,sizeof vis );for(j=1;j<=t&&s[j]<=i;j++)vis[sg[i-s[j]]]=1;for(j=0;j<=10001;j++)if(!vis[j])break;sg[i]=j;}
}
int main()
{int k;while(cin>>k,k){for(int i=1;i<=k;i++)cin>>s[i];sort(s+1,s+k+1);getSG(k);int m,n,ans,t;cin>>m;while(m--){cin>>n;ans=0;for(int i=0;i<n;i++){cin>>t;ans^=sg[t];}if(ans)cout<<'W';elsecout<<'L';}cout<<endl;}
}

参考资料：
https://blog.csdn.net/haha294182852/article/details/77572639
https://blog.csdn.net/jk_chen_acmer/article/details/82082653
https://blog.csdn.net/bestsort/article/details/88197959
https://www.bilibili.com/video/BV1Ut4y1X7ry?from=search&seid=2134696235016320646
https://www.bilibili.com/video/BV15b411W73J?from=search&seid=11761397602115561012
↓ 觉得还ok，留下一个赞吧~ 蟹蟹~