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;}