博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
博弈问题之SG函数博弈小结
阅读量:4839 次
发布时间:2019-06-11

本文共 5438 字,大约阅读时间需要 18 分钟。

SG函数:

给定一个有向无环图和一个起始顶点上的一枚棋子,两名选手交替的将这枚棋子沿有向边进行移动,无法移 动者判负。事实上,这个游戏可以认为是所有Impartial Combinatorial Games的抽象模型。也就是说,任何一个ICG都可以通过把每个局面看成一个顶点,对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下 面我们就在有向无环图的顶点上定义Sprague-Garundy函数。首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

在我的理解中,sg函数就是一个对有向无环图dfs的过程,在处理nim博弈时,多个石堆可以看成多个sg函数值的异或。

例题:

POJ2311 Cutting Game

典型的sg博弈,找后继状态。题意是给出一个n*m的纸片,每次剪成两部分,谁先剪到1*1就胜利。这就是一个找后继的题目,每次剪成的两部分就是前一状态的后继,只要将两个部分的sg值异或起来就是前一状态的sg值。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))#define FOR(a,b,i) for(i=a;i<=b;++i)#define For(a,b,i) for(i=a;i
'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); }}inline void OT(int a){ if(a>=10) { OT(a/10); } putchar(a%10+'0');}int sg[201][201];int dfs(int a,int b)//sg函数的一般写法{ if(sg[a][b]>=0) { return sg[a][b]; } int i,map[201],r;//map标记数组一定要在dfs内部定义,不然会出现错误 mem(map,0); FOR(2,(a/2),i) { r=dfs(i,b)^dfs(a-i,b);//后继的异或得到前一状态的sg值 map[r]=1; } FOR(2,(b/2),i) { r=dfs(a,i)^dfs(a,b-i); map[r]=1; } FOR(0,200,i) { if(map[i]==0) { return sg[a][b]=i;//mex公式的应用 } }}int main(){ int n,m,sum; mem(sg,-1); while(scanf("%d%d",&n,&m)!=EOF) { sum=dfs(n,m); if(sum>0) { printf("WIN\n"); } else { printf("LOSE\n"); } } return 0;}

 

 

POJ2425 A Chess Game

题意是给你一个拓扑图,一个起点上的n个棋子,两个玩家交替移动棋子,谁无法移动谁输,典型的sg函数运用。套用模板就行了。此题数据量较大,加入了输入优化后刷到了第一版第四名,nice!

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))#define FOR(a,b,i) for(i=a;i<=b;++i)#define For(a,b,i) for(i=a;i
'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); }}inline void OT(int a){ if(a>=10) { OT(a/10); } putchar(a%10+'0');}int vis[1001][1001],sg[1001];int n;int dfs(int x)//典型的sg过程{ int i; if(sg[x]!=-1) { return sg[x]; } int f[1001]; mem(f,0); For(0,n,i) { if(vis[x][i]!=-1) { f[dfs(i)]=1; } } i=0; while(f[i]) { i++; } return sg[x]=i;}int main(){ int i,j,k,t,x,p,sum; while(scanf("%d",&n)!=EOF) { mem(vis,-1); mem(sg,-1); For(0,n,i) { RD(k); if(k==0) { sg[i]=0; } For(0,k,j) { RD(t); vis[i][t]=1;//建图 } } while(1) { RD(x); if(x==0) { break; } sum=0; For(0,x,i) { RD(p); sum^=dfs(p); } if(sum!=0) { printf("WIN\n"); } else { printf("LOSE\n"); } } } return 0;}

POJ2068 Nim

 

题意是圆桌上有2n个人,奇数一队,偶数一队,每个人都有一个拿走棋子的最高限额,问你最后1对能否获胜。

还是用强大的sg函数过的,记录下每个状态的sg。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))#define FOR(a,b,i) for(i=a;i<=b;++i)#define For(a,b,i) for(i=a;i
'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); }}inline void OT(int a){ if(a>=10) { OT(a/10); } putchar(a%10+'0');}int n,s,m[22],sg[22][8200],sum;int dfs(int x,int y){ if(sg[x][y]!=-1) { return sg[x][y]; } int i,j; FOR(1,m[x],i) { if(y-i<0) { break; } if(x+1>=2*n) { j=0; } else { j=x+1; } if(dfs(j,y-i)==0) { return sg[x][y]=1; } } return sg[x][y]=0;}int main(){ int i; while(1) { RD(n); if(n==0) { break; } RD(s); For(0,2*n,i) { RD(m[i]); } mem(sg,-1); FOR(0,2*n,i) { sg[i][0]=1; } sum=dfs(0,s); if(sum==0) { printf("0\n"); } else { printf("1\n"); } } return 0;}

POJ3537 Crosses and Crosses

 

题意:给出一个1*n的矩形,上面有n个方格,现有两人分别在上面画×,谁先能画出三个×相连就赢了。这就是一个sg函数的母问题转化为子问题的题目,由于在第x位置画了×后,则就转变成(x-3)个格子画×和(n-x-2)个格子画×。。。这就能不断的分解下去,最后将所有sg值异或起来就是正解了。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))#define FOR(a,b,i) for(i=a;i<=b;++i)#define For(a,b,i) for(i=a;i
'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); }}inline void OT(int a){ if(a>=10) { OT(a/10); } putchar(a%10+'0');}int sg[2001];int dfs(int x){ if(x<0) { return 0; } if(sg[x]>=0) { return sg[x]; } int i,y; bool v[2001]={false}; FOR(1,x,i) { y=dfs(i-3)^dfs(x-i-2);//找后继(经典) v[y]=true; } for(i=0;;i++) { if(v[i]==false) { return sg[x]=i; } }}int main(){ int n,sum; mem(sg,-1); while(scanf("%d",&n)!=EOF) { sum=dfs(n); if(sum) { printf("1\n"); } else { printf("2\n"); } } return 0;}

POJ2599 A funny game

 

记忆化搜索,这题的博弈味道不浓,更多的是搜索。题意是给一个图,两人轮流移动,走过的节点不能再走。水题,dfs+标记就行。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))#define FOR(a,b,i) for(i=a;i<=b;++i)#define For(a,b,i) for(i=a;i
'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); }}inline void OT(int a){ if(a>=10) { OT(a/10); } putchar(a%10+'0');}int n,v[1001][1001],vis[1001];int dfs(int x){ int i; FOR(1,n,i) { vis[x]=1; if(v[i][x]&&!vis[i]) { if(!dfs(i)) { vis[x]=0; return i; } } vis[x]=0; } return 0;}int main(){ int m,i,a,b; while(scanf("%d%d",&n,&m)!=EOF) { mem(v,0); mem(vis,0); FOR(1,n-1,i) { RD(a); RD(b); v[a][b]=v[b][a]=1; } i=dfs(m); if(i!=0) { printf("First player wins flying to airport %d\n",i); } else { printf("First player loses\n"); } } return 0;}

 

 

转载于:https://www.cnblogs.com/james1207/p/3301610.html

你可能感兴趣的文章
大数加减1——将两个数均前后倒置,以对齐最低位
查看>>
Array
查看>>
百度联想
查看>>
java项目——淘宝商城
查看>>
uestc 1904
查看>>
静态构造函数
查看>>
js创建10万行表格 页面显示10万行数据
查看>>
in_array()和explode()的使用笔记
查看>>
centos7重新调整分区大小
查看>>
javascript 时间格式化
查看>>
Tensorflow学习之一 (运算)
查看>>
Web开发者不可不知的15条编码原则
查看>>
小用ACE_Acceptor
查看>>
156. Merge Intervals【LintCode by java】
查看>>
linux 程序管理与SElinux
查看>>
foreach循环
查看>>
Mysql笔记之 -- 小试MYSQL主从配置
查看>>
webpack核心概念使用的综合小案例
查看>>
常用汇编
查看>>
CSS的引入方式
查看>>