POJ 1085 Triangle War（博弈，大小搜索+alpha_beta剪枝）

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

目：出10，共有18，每次人流加入一，如果形成一三角形，三角形他所有，而且可以外再走一步。最後三角形多的人

http://poj.org/problem?id=1085

博弈

所的大小搜索，其就是搞估函。然後主角肯定估函最大的，即自己最有利的局面走。

而到方的候，方肯定估函最小的，局面是主角最不利的。

道理很的，但是每走一步，要判所有情的估函，然後找一最大或者最小的，其就是枚了。

度是很高的~~~~

alpha_beta剪枝正是用於大小搜索的一有效剪枝。

是第一次接搜索，理解不

我的理解是alpha的是博弈搜索到前深度的最大的估值，也就是最好的情

而beta的是博弈搜索到前深度的最小的估值，最的情

需要再研究研究

本考http://blog.csdn.net/dooder_daodao/article/details/6682971

#include<iostream>  #include<cstdio>  #include<map>  #include<cstring>  #include<cmath>  #include<vector>  #include<queue>  #include<algorithm>  #include<set>  #define inf (1ull<<63)-1  #define N 50005  #define maxn 100005  #define Min(a,b) ((a)<(b)?(a):(b))  #define Max(a,b) ((a)>(b)?(a):(b))  #define pb(a) push_back(a)  #define mem(a,b) memset(a,b,sizeof(a))  #define eps 1e-9  #define zero(a) fabs(a)<eps  #define LL long long  #define ULL unsigned long long  #define lson (step<<1)  #define rson (step<<1|1)  #define MOD 1000000007  #define mp(a,b) make_pair(a,b)  using namespace std;  //10个顶点之间的连线编号int mat[11][11]={{0,0,0,0,0,0,0,0,0,0,0},  {0,0,0,1,0,0,0,0,0,0,0},  {0,0,0,2,3,4,0,0,0,0,0},  {0,1,2,0,0,5,6,0,0,0,0},  {0,0,3,0,0,7,0,9,10,0,0},  {0,0,4,5,7,0,8,0,11,12,0},  {0,0,0,6,0,8,0,0,0,13,14},  {0,0,0,0,9,0,0,0,15,0,0},  {0,0,0,0,10,11,0,15,0,16,0},  {0,0,0,0,0,12,13,0,16,0,17},  {0,0,0,0,0,0,0,14,0,17,0}  };  //9个三角形组成的边状态压缩一下int tri[9]={7,152,52,352,34304,3200,71680,12544,155648};  int STATUS=(1<<18)-1;int Get_Status(int old,int seg,int &cnt){int now=old|seg;for(int i=0;i<9;i++){//之前不包含这个三角形，现在包含了if((old&tri[i])!=tri[i]&&(now&tri[i])==tri[i])cnt++;}return now;}int MaxSearch(int state,int alpha,int ca,int cb);int MinSearch(int state,int beta,int ca,int cb){//出现5个三角形，胜负已分if(ca>=5) return 1;if(cb>=5) return -1;//所有的边都取了,游戏也结束if(state==STATUS) return ca>cb?1:-1;int ans=1;int remain=(~state)&STATUS;  //剩下还有哪些边可以取while(remain){int seg=remain&(-remain); //枚举int ta=ca,tb=cb;int now=Get_Status(state,seg,tb),tmp;//是否有新的三角形生成if(tb>cb) tmp=MinSearch(now,beta,ca,tb);else tmp=MaxSearch(now,ans,ca,tb);if(tmp<ans) ans=tmp;//beta剪枝if(tmp<=beta) return ans;remain-=seg;}return ans;}int MaxSearch(int state,int alpha,int ca,int cb){//出现5个三角形，胜负已分if(ca>=5) return 1;if(cb>=5) return -1;//所有的边都取了,游戏也结束if(state==STATUS) return ca>cb?1:-1;int ans=-1;int remain=(~state)&STATUS;  //剩下还有哪些边可以取while(remain){int seg=remain&(-remain); //枚举int ta=ca,tb=cb;int now=Get_Status(state,seg,ta),tmp;//是否有新的三角形生成if(ta>ca) tmp=MaxSearch(now,alpha,ta,cb);else tmp=MinSearch(now,ans,ta,cb);if(tmp>ans) ans=tmp;//alpha剪枝if(tmp>=alpha) return ans;remain-=seg;}return ans;}int main(){int t,cas=0;scanf("%d",&t);while(t--){int n,u,v;scanf("%d",&n);//已经走了多少步，当前边的状态int cnt=0,state=0;//两个人分别有几个三角形int ca=0,cb=0;while(n--){scanf("%d%d",&u,&v);int ta=ca,tb=cb;state=Get_Status(state,1<<mat[u][v],(cnt&1)?cb:ca);//没有新的三角形，if(ta==ca&&tb==cb)cnt++;}int ans;if(cnt&1) ans=MinSearch(state,-1,ca,cb);else ans=MaxSearch(state,1,ca,cb);printf("Game %d: %c wins.\n",++cas,ans==1?'A':'B');}return 0;}