300字范文 > 博弈基础与例题分析（巴什博弈威佐夫博弈尼姆博奕斐波那契博弈SG博弈）

博弈基础与例题分析（巴什博弈威佐夫博弈尼姆博奕斐波那契博弈SG博弈）

时间：2022-01-27 09:50:11

文章目录

巴什博弈Bash Game威佐夫博弈Wythoff Game尼姆博奕斐波那契博弈:算法如其名SG博弈图mex(minimal excludant)运算获得sg表应用A Brave GameB 取石子游戏C Matches GameD 取石子游戏E Good Luck in CET-4 Everybody!F S-NimG Calendar Game ⚠️H 取(2堆)石子游戏 🌟I Public SaleJ 取(m堆)石子游戏

巴什博弈Bash Game

只有一堆n个物品两个人轮流取，每次只能取1~m个物品，谁先取完，谁胜利；（n,m是输入的随机数）

当目前有1到m个时先手赢m+1个时，后手赢m+2到2m时，先手可以拿走1到m-1个，给后手剩下m+1个，这样后手必输

得到：谁面临m+1个的情况，谁输

总结：谁先面对m+1的倍数，谁就输，k（m+1）+r，先手拿走r，后手面对，后手输

代码实现：

一共n个石子，看是否是m+1的倍数，即有无r存在

if(n%(m+1)==0) cout << "后手赢，先手输";else cout << "先手赢，后手输";

威佐夫博弈Wythoff Game

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

每个人有两种选择：一堆中取出任意个 or 两堆同时x个

每个人都不能把一堆直接取完，否则下一人一定赢，那么肯定就在一堆中取，最后让局势变成（1，2），自己就赢了

所有情况列出来找规律

先手可以赢的情况远远大于输的情况

讨论输的情况

差是递增的

0，1，2，3，4，……

if(x>y) swap(x,y);int t = (y-x)*(sqrt(5)+1)/2;if(x==t) printf("先手输后手赢\n");elseprintf("先手赢后手输\n");

1.618 = (sqrt(5.0) + 1) / 2

尼姆博奕

有多堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者（拿到最后一个石子的人算胜利）得胜。

现在有两堆石子

7，5

二进制表达111 101

4 2 1，4 1

也就是 1，1，2，4，4

11，44，先手必输：

数相同体现在二进制是相同位数：那么就可以用二进制异或比较

石子按二进制展开分为多堆后，可用二进制运算，看第i堆时需要看前面i-1堆的输赢情况，得出结论后把i-1堆视为一堆

当石子数量相同：先手输，把结果0/1与下面的进行异或比较

异或运算：不同是1，相同是0 位运算：跟每一位异或 3^9=10

ans = 0; //0与非0异或非0，不变while(n--){scanf("%d",&t);ans^=t;}if(ans)puts("先手赢");elseputs("先手输");

斐波那契博弈:算法如其名

有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。

sum个

先手x个

后手1～2x个

数量是fib，先手输

结论是：先手胜当且仅当n不是斐波那契数（n为物品总数）：用2验证一下就不会记混了

证明

int fib[maxn]={0,1,1},x;bool vis[maxn];for(int i=2; i<30; i++)fib[i] = fib[i-1] + fib[i-2],vis[fib[i]]=1;cin >> x;if(vis[x])cout << "先手输" << endl;elsecout << "先手赢" << endl;

if(n == 0) break; bool flag = 0; for(int i=0;i<N;i++) {if(f[i] == n) {flag = 1; break; } } if(flag) puts("Second win"); elseputs("First win");

注意斐波那契数大小

SG博弈

学习于1

学习于2

图

SG博弈算法可以看成是一个图的搜索算法，即把每个可能的点抽象成图的点，而这些点有两个状态(0或非0，对应必输或必赢)

前提：双方都最佳策略

那么就能把每一步状态都表示为，在当前情况下，是先手胜还是后手胜这种非0即1的绝对状态

先手胜的状态表示成N状态：下一个人赢，也就是先手下一个拿了会赢

后手胜的状态表示成P状态：上一个人赢，也就是先手下一个拿了会输，所以就是上一个拿的后手会赢

P-和N-状态归纳性地描述如下：

一个点v是P-状态当且仅当它的所有后继都为N-状态也就是后手赢：所有值异或后得到0

一个点v是N-状态当且仅当它的一些后继是P-状态

这个归纳从汇点开始，汇点是P-状态，因为最后一个拿的赢了，下一个人无法拿，输了，所以上一个人赢了，所以是P状态

游戏的P-和N-状态的信息提供了它的必胜策略。如果轮到我们且游戏处在一个N-状态，我们应该转移到一个P-状态。接着我们的对手就会被迫进入N-状态，依此类推。我们最终会移入一个汇点并获得胜利。

mex(minimal excludant)运算

表示，最小的不属于这个集合的非负整数

mex{0,1,2,4} = 3; mex{2,3,5} = 0

也就是从0，1，2，3，4，5，6，7……一直往后数，第一个不存在于原集合的数

给定一个有向无环图，定义每个顶点，sg[x] = mex{sg（y) | y是x后继节点}

取石子问题，1堆n个，每次拿1/3/4个，先拿完的胜利，那么各个数的sg值是多少？

|x|取走f{}|剩余| mex| sg|

|–|–|–|–|–|–|

|0|{0}|{0}||sg[0] = 0

|1|{1}|{0}|mex{sg[0]} = mex{0} |sg[1] = 1

2|{1}|{1}|mex{sg[1]} = mex{1} |sg[2] = 0

3|{1,3}|{0,2}|mex{sg[0], sg[2] } = mex{0,0} |sg[3] = 1

4|{1,3,4}|{0,1,3}| mex{sg[0], sg[1], sg[3]} = mex{0,1,1}|sg[4] = 2

5|{1,3,4}|{1,2,4}| mex{sg[1],sg[2],sg[4]} = mex{1,0,2}|sg[5] = 3

f[0] = {1,3,4}表示有3种走法

f[]需要升序排序

获得sg表

可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+1);

可选步数为任意步，SG(x) = x;

可选步数为一系列不连续的数，用GetSG()计算

int sg[maxn];bool vis[maxn];int f[maxn];void get_sg(int n){memset(sg, 0, sizeof(sg));//根据题意不同的ffor(int i=1; i<=石子数量的max; i++){//i是所有可能情况！！注意memset(vis, 0, sizeof(vis));for(int j=1; f[j]<=i && j<=n ; j++)//j是能拿走不同个数的种类最多就是f数组大小 n个vis[sg[i-f[j]]] = 1;for(int j=0;j<=n; j++) //mes运算，从0开始找if(vis[j]==0){sg[i] = j;break;}}}

应用

取石子问题，1堆n个，每次拿1/3/4个，先拿完的胜利判断先后手？

f初始化为134 求出sg

一个点v是P-状态当且仅当它的所有后继都为N-状态

也就是后手赢：所有值异或后得到0

sg=0 说明后手赢

多组的话：多组的值异或

A Brave Game

巴什博弈模板题

直接套板子

B 取石子游戏

威佐夫博弈模板

C Matches Game

尼姆博奕模板

D 取石子游戏

注意斐波那契数列开多大

E Good Luck in CET-4 Everybody!

sg模板题

#include<cstdio>#include<iostream>#include<cstdlib>#include<algorithm>#include<cmath>#include<vector>#include<string>#include<queue>#include<stack>#include<map>#define M 200000010#define INF 0x3f3f3f3ftypedef long long ll;using namespace std;const int maxn = 1005;int sg[maxn];bool vis[maxn];int f[maxn];void get_sg(int n){f[1] = 1;for(int i=2; i<=n; i++)f[i] = f[i-1]*2;memset(sg, 0, sizeof(sg));for(int i=1; i<=n; i++){memset(vis, 0, sizeof(vis));for(int j=1; f[j]<=i; j++)vis[sg[i-f[j]]] = 1;for(int j=0; j<=n; j++) //mes运算，从0开始找if(vis[j]==0){sg[i] = j;break;}}}int main(){int n;while(cin >> n){get_sg(n);if(sg[n])puts("Kiki");elseputs("Cici");}}

F S-Nim

注意超时！

memset函数对bool运算要快于int

注意理解sg怎么来的，对应的i值和j值

#include<cstdio>#include<iostream>#include<cstdlib>#include<algorithm>#include<cmath>#include<vector>#include<string>#include<queue>#include<stack>#include<map>#define M 200000010#define INF 0x3f3f3f3ftypedef long long ll;using namespace std;const int maxn = 10005;int k,s[maxn];int m,l,h;int sg[maxn];bool vis[maxn];void get_sg(int n){memset(sg, 0,sizeof(sg));for(int i=1; i<maxn; i++){//石子数最多maxnmemset(vis, 0, sizeof(vis));for(int j=1; s[j]<=i && j<=n; j++)vis[sg[i-s[j]]] = 1;for(int j=0; j<=n; j++) //j种取法if(vis[j]==0){sg[i] = j;break;}}}int main(){while(scanf("%d",&k) && k){for(int i=1; i<=k; i++)scanf("%d",&s[i]);sort(s+1,s+1+k);get_sg(k);scanf("%d",&m);while(m--){scanf("%d",&l);int flag = 0;while(l--){scanf("%d",&h);flag ^= sg[h];}if(flag) printf("W");else printf("L");}printf("\n");}}

G Calendar Game ⚠️

准确到达2001年11月4日时获胜————玩家可以day+1 或者month+1

由sg思想

一天是必败的————这一天的后一天胜 + 后一个月的这一天胜，后手必胜，先手必败

一天是胜的————这一天的后一天必败或者后一月的这一天必败，那么先手可以每次都跳到让后手面临必败的情况，

从后往前倒推

看似找到了规律

验证关键位置，把边界的几天都验证一下，因为中间的那些天都是规律的

#include<cstdio>#include<iostream>#include<cstdlib>#include<algorithm>#include<cmath>#include<vector>#include<string>#include<queue>#include<stack>#include<map>#define M 200000010#define INF 0x3f3f3f3ftypedef long long ll;using namespace std;const int maxn = 10005;int T,y,m,d;bool flag[13][32];int main(){cin >> T;while(T--){cin >> y >> m >> d;if((m==9 && d==30) || (m==11 && d==30))printf("YES\n");else if((m+d)% 2)printf("NO\n");elseprintf("YES\n");}}

H 取(2堆)石子游戏 🌟

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你胜，你第1次怎样取子?
Input
输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000，且a<=b。a=b=0退出。
Output
输出也有若干行，如果最后你是败者，则为0，反之，输出1，并输出使你胜的你第1次取石子后剩下的两堆石子的数量x,y,x<=y。如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜，先输出取走相同数量的石子的情况.

思路：暴力

#include<cstdio>#include<iostream>#include<cstdlib>#include<algorithm>#include<cmath>#include<vector>#include<string>#include<queue>#include<stack>#include<map>#define M 200000010#define INF 0x3f3f3f3ftypedef long long ll;using namespace std;const int maxn = 4e5+10;int main(){int a,b;while(cin >> a >> b && a&&b){if(a==0){printf("1\n0 0\n");continue;}int t = (b-a)*(sqrt(5.0)+1)/2;if(t==a)puts("0");else{puts("1");bool vis[maxn];memset(vis, 0, sizeof(vis));//一样的情况for(int i=1; i<a; i++){if((a-i)==int ((b-a)*(sqrt(5.0)+1)/2) && !vis[a-i]){printf("%d %d\n",a-i,b-i);vis[a-i]=1;}}//不一样for(int i=1; i<a; i++){if((a-i)==int ((b-a+i)*(sqrt(5.0)+1)/2)&& !vis[a-i]){printf("%d %d\n",a-i,b);vis[a-i]=1;}}for(int i=1; i<b; i++){if(a==int ((b-i-a)*(sqrt(5.0)+1)/2)&& !vis[a-i]){printf("%d %d\n",a,b-i);vis[a]=1;}if((b-i)==int ((a-b+i)*(sqrt(5.0)+1)/2)&& !vis[a-i]){printf("%d %d\n",b-i,a);vis[b-i]=1;}}}}}

I Public Sale

通过打听，Lele知道这场拍卖的规则是这样的：刚开始底价为0，两个人轮流开始加价，不过每次加价的幅度要在1～N之间，当价格大于或等于田地的成本价 M 时，主办方就把这块田地卖给这次叫价的人。

等价于总共mmin，每次减掉1～，最后一个减掉的人 win

lele先开始

只有一堆n个物品两个人轮流取，每次只能取1~m个物品，谁先取完，谁胜利；（n,m是输入的随机数）

#include<cstdio>#include<iostream>#include<cstdlib>#include<algorithm>#include<cmath>#include<vector>#include<string>#include<queue>#include<stack>#include<map>#define M 200000010#define INF 0x3f3f3f3ftypedef long long ll;using namespace std;const int maxn = 4e5+10;int range,mmin;int main(){while(~scanf("%d %d",&mmin,&range)){if(mmin%(range+1)==0)puts("none");else{//lele可以拍下if(mmin<=range){printf("%d",mmin);for(int i=mmin+1; i<=range; i++) printf(" %d",i);puts("");}else{bool flag = 0;for(int k=mmin/(range+1); k>=1; k--){int t = k*(range+1);//k倍，t是留下给下一个人面对的数 //那么这次取走的应该是mmin-t个数if(mmin-t>0 && mmin-t<=range){if(flag)puts(" ");printf("%d",mmin-t);flag = 1;}}puts("");}}}}