基于Alpha-Beta剪枝的欢乐斗地主残局辅助

2019年4月17日更新：

将搜索主函数优化为局部记忆化搜索，再次提高若干倍搜索速度

更新了main和player，helper无更新

  1 #include "Player-v3.0.cpp"
  2 #include "Helper.cpp"
  3 
  4 #define END {if(fir){newA=a; newB=b;} return 1;}
  5 #define NXT {if(ok&&play(b,a,0)==0) return 1; else return 0;}
  6 #define NO  {printf("Can't Out
"); newA=a; newB=b;}
  7 player newA,newB;
  8 bool play(player,player,bool);
  9 
 10 bool Play_Rocket(player a,player b,bool fir){
 11     if(b.empty()) return 0;
 12     if(a.CanPlayRocket()){
 13         a.PlayRocket();
 14         bool now=play(a,b,0);
 15         if(now){
 16             if(fir) Out_Rocket();
 17             END;
 18         }
 19     }
 20     return 0;
 21 }
 22 
 23 bool Play_Boom(player a,player b,int last,bool fir,bool ok){
 24     if(b.empty()) return 0;
 25     if(Play_Rocket(a,b,fir)) return 1;
 26     player _a=a;
 27     if(a.CanBoom)
 28     for(int i=last+1;i<15;i++)
 29     if(a.CanPlayBoom(i)){
 30         a.PlayBoom(i);
 31         a.ResetCan();
 32         bool now=Play_Boom(b,a,i,0,1);
 33         if(!now){
 34             if(fir) Out_Boom(i);
 35             END;
 36         }
 37         a=_a;
 38     }
 39     NXT;
 40 }
 41 
 42 bool Play_Single(player a,player b,int last,bool fir,bool ok){
 43     if(b.empty()) return 0;
 44     player _a=a;
 45     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
 46     for(int i=last+1;i<15;i++)
 47     if(a.CanPlaySingle(i)){
 48         a.PlaySingle(i);
 49         bool now=Play_Single(b,a,i,0,1);
 50         if(!now){
 51             if(fir) Out_Single(i);
 52             END;
 53         }
 54         a=_a;
 55     }
 56     NXT;
 57 }
 58 
 59 bool Play_Couple(player a,player b,int last,bool fir,bool ok){
 60     if(b.empty()) return 0;
 61     player _a=a;
 62     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
 63     for(int i=last+1;i<13;i++)
 64     if(a.CanPlayCouple(i)){
 65         a.PlayCouple(i);
 66         bool now=Play_Couple(b,a,i,0,1);
 67         if(!now){
 68             if(fir) Out_Couple(i);
 69             END;
 70         }
 71         a=_a;
 72     }
 73     NXT;
 74 }
 75 
 76 bool Play_Three(player a,player b,int last,bool fir,bool ok){
 77     if(b.empty()) return 0;
 78     player _a=a;
 79     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
 80     if(a.CanThree)
 81     for(int i=last+1;i<13;i++)
 82     if(a.CanPlayThree(i)){
 83         a.PlayThree(i);
 84         a.ResetCan();
 85         bool now=Play_Three(b,a,i,0,1);
 86         if(!now){
 87             if(fir) Out_Three(i);
 88             END;
 89         }
 90         a=_a;
 91     }
 92     NXT;
 93 }
 94 
 95 bool Play_3Single(player a,player b,int last,bool fir,bool ok){
 96     if(b.empty()) return 0;
 97     player _a=a;
 98     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
 99     for(int i=last+1;i<13;i++) if(a.CanPlayThree(i))
100     if(a.CanThree)
101     for(int j=0;j<15;j++)
102     if(a.CanPlay3Single(i,j)){
103         a.Play3Single(i,j);
104         a.ResetCan();
105         bool now=Play_3Single(b,a,i,0,1);
106         if(!now){
107             if(fir) Out_3Single(i,j);
108             END;
109         }
110         a=_a;
111     }
112     NXT;
113 }
114 
115 bool Play_3Couple(player a,player b,int last,bool fir,bool ok){
116     if(b.empty()) return 0;
117     player _a=a;
118     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
119     for(int i=last+1;i<13;i++) if(a.CanPlayThree(i))
120     if(a.CanThree)
121     for(int j=0;j<15;j++)
122     if(a.CanPlay3Couple(i,j)){
123         a.Play3Couple(i,j);
124         a.ResetCan();
125         bool now=Play_3Couple(b,a,i,0,1);
126         if(!now){
127             if(fir) Out_3Couple(i,j);
128             END;
129         }
130         a=_a;
131     }
132     NXT;
133 }
134 
135 bool Play_4Single(player a,player b,int last,bool fir,bool ok){
136     if(b.empty()) return 0;
137     player _a=a;
138     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
139     for(int i=last+1;i<13;i++) if(a.CanPlayBoom(i))
140     if(a.CanBoom)
141     for(int j=0;j<15;j++)
142     for(int k=0;k<15;k++)
143     if(a.CanPlay4Single(i,j,k)){
144         a.Play4Single(i,j,k);
145         a.ResetCan();
146         bool now=Play_4Single(b,a,i,0,1);
147         if(!now){
148             if(fir) Out_4Single(i,j,k);
149             END;
150         }
151         a=_a;
152     }
153     NXT;
154 }
155 
156 bool Play_4Couple(player a,player b,int last,bool fir,bool ok){
157     if(b.empty()) return 0;
158     player _a=a;
159     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
160     for(int i=last+1;i<13;i++) if(a.CanPlayBoom(i))
161     if(a.CanBoom)
162     for(int j=0;j<15;j++)
163     for(int k=0;k<15;k++)
164     if(a.CanPlay4Couple(i,j,k)){
165         a.Play4Couple(i,j,k);
166         a.ResetCan();
167         bool now=Play_4Couple(b,a,i,0,1);
168         if(!now){
169             if(fir) Out_4Couple(i,j,k);
170             END;
171         }
172         a=_a;
173     }
174     NXT;
175 }
176 
177 bool Play_MS(player a,player b,int l,int r,bool fir,bool ok){
178     if(b.empty()) return 0;
179     player _a=a; int pls=r-l;
180     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
181     if(a.CanMS)
182     for(int i=l+1;i+pls<=11;i++)
183     if(a.CanPlayMoreSingle(i,i+pls)){
184         a.PlayMoreSingle(i,i+pls);
185         a.ResetCan();
186         bool now=Play_MS(b,a,i,i+pls,0,1);
187         if(!now){
188             if(fir) Out_MS(i,i+pls);
189             END;
190         }
191         a=_a;
192     }
193     NXT;
194 }
195 
196 bool Play_MC(player a,player b,int l,int r,bool fir,bool ok){
197     if(b.empty()) return 0;
198     player _a=a; int pls=r-l;
199     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
200     if(a.CanMC)
201     for(int i=l+1;i+pls<=11;i++)
202     if(a.CanPlayMoreCouple(i,i+pls)){
203         a.PlayMoreCouple(i,i+pls);
204         a.ResetCan();
205         bool now=Play_MC(b,a,i,i+pls,0,1);
206         if(!now){
207             if(fir) Out_MC(i,i+pls);
208             END;
209         }
210         a=_a;
211     }
212     NXT;
213 }
214 
215 map<pair<long long,long long>,int> Visit;
216 bool play(player a,player b,bool fir=0){
217     if(b.empty()) return Visit[make_pair(a.Hash(),b.Hash())]=0;
218     if(a.cnt+b.cnt<16&&fir==0){
219         if(Visit.count(make_pair(a.Hash(),b.Hash())))
220             return Visit[make_pair(a.Hash(),b.Hash())];
221     }
222     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return Visit[make_pair(a.Hash(),b.Hash())]=1;
223     if(a.CanMS)
224     for(int i=11;i>=4;i--){
225         if(Play_MS(a,b,-1,-1+i,fir,0)) return Visit[make_pair(a.Hash(),b.Hash())]=1;
226     }
227     if(a.CanMC)
228     for(int i=8;i>=2;i--){
229         if(Play_MC(a,b,-1,-1+i,fir,0)) return Visit[make_pair(a.Hash(),b.Hash())]=1;
230     }
231     if(a.CanThree) if(Play_Three(a,b,-1,fir,0)) return Visit[make_pair(a.Hash(),b.Hash())]=1;
232     if(a.CanThree) if(Play_3Single(a,b,-1,fir,0)) return Visit[make_pair(a.Hash(),b.Hash())]=1;
233     if(a.CanThree) if(Play_3Couple(a,b,-1,fir,0)) return Visit[make_pair(a.Hash(),b.Hash())]=1;
234     if(Play_Couple(a,b,-1,fir,0)) return Visit[make_pair(a.Hash(),b.Hash())]=1;
235     if(Play_Single(a,b,-1,fir,0)) return Visit[make_pair(a.Hash(),b.Hash())]=1;
236     if(a.CanBoom) if(Play_4Single(a,b,-1,fir,0)) return Visit[make_pair(a.Hash(),b.Hash())]=1;
237     if(a.CanBoom) if(Play_4Couple(a,b,-1,fir,0)) return Visit[make_pair(a.Hash(),b.Hash())]=1;
238     return Visit[make_pair(a.Hash(),b.Hash())]=0;
239 }
240 
241 int Main(){
242     Visit.clear();
243     player a,b;
244     printf("INPUT AI:
");
245     b.read(); 
246     printf("INPUT PLAYER:
");
247     a.read();
248     int staT=clock();
249     if(!play(a,b,1)){
250         printf("DIE
");
251         return 0;
252     }
253     printf("
First Time Use %dms
",clock()-staT);
254     while(1){
255         a=newA; b=newB;
256         printf("
");
257         if(a.empty()){
258             printf("WIN
");
259             return 0;
260         }
261         
262         string now; cin>>now;
263         if(now=="EXIT") return 0;
264         if(Is_Empty(now)){
265             if(!play(a,b,1)){
266                 printf("DIE
");
267             }
268             continue;
269         }
270         for(int i=0;i<now.length();i++) b.PlaySingle(GetVal(now[i]));
271         
272         if(Is_Single(now)&&Play_Single(a,b,GetVal(now[0]),1,0)==0) NO;
273         if(Is_Couple(now)&&Play_Couple(a,b,GetVal(now[0]),1,0)==0) NO;
274         if(Is_Three(now)&&Play_Three(a,b,GetVal(now[0]),1,0)==0) NO;
275         if(Is_Boom(now)&&Play_Boom(a,b,GetVal(now[0]),1,0)==0) NO;
276         if(Is_Rocket(now)&&Play_Rocket(a,b,1)==0) NO;
277         if(Is_3Single(now)&&Play_3Single(a,b,GetVal(now[0]),1,0)==0) NO;
278         if(Is_3Couple(now)&&Play_3Couple(a,b,GetVal(now[0]),1,0)==0) NO;
279         if(Is_4Single(now)&&Play_4Single(a,b,GetVal(now[0]),1,0)==0) NO;
280         if(Is_4Couple(now)&&Play_4Couple(a,b,GetVal(now[0]),1,0)==0) NO;
281         if(Is_MS(now)&&Play_MS(a,b,GetVal(now[0]),GetVal(now[now.length()-1]),1,0)==0) NO;
282         if(Is_MC(now)&&Play_MC(a,b,GetVal(now[0]),GetVal(now[now.length()-1]),1,0)==0) NO;
283     }
284 }
285 
286 int main(){
287     while(1) Main();
288 }

main-v3.0

  1 /*
  2     ???????????????????
  3     ??
  4     ??????
  5 */ 
  6 
  7 #include<bits/stdc++.h>
  8 using namespace std;
  9 
 10 int GetVal(char c){
 11     if(c=='T') return 7;
 12     if(c=='J') return 8;
 13     if(c=='Q') return 9;
 14     if(c=='K') return 10;
 15     if(c=='A') return 11;
 16     if(c=='2') return 12;
 17     if(c=='w') return 13;
 18     if(c=='W') return 14;
 19     if('3'<=c&&c<='9') return c-'3';
 20     assert(0);
 21 }
 22 char SetChar(int x){
 23     if(x<=6) return '3'+x;
 24     if(x==7) return 'T';
 25     if(x==8) return 'J';
 26     if(x==9) return 'Q';
 27     if(x==10) return 'K';
 28     if(x==11) return 'A';
 29     if(x==12) return '2';
 30     if(x==13) return 'w';
 31     if(x==14) return 'W';
 32     assert(0);
 33 }
 34 
 35 struct player{
 36     int a[16],cnt; 
 37     bool CanThree,CanBoom,CanMS,CanMC;
 38     player(){memset(a,0,sizeof(a));cnt=0;}
 39     
 40     void out(){//Output Poker
 41         for(int i=0;i<16;i++) 
 42         for(int j=0;j<a[i];j++)
 43         putchar(SetChar(i));
 44         putchar('
');
 45     }
 46     
 47     inline bool CanPlaySingle(int x){return a[x]>=1;}//? 
 48     
 49     inline bool CanPlayCouple(int x){return a[x]>=2;}//? 
 50     
 51     inline bool CanPlayThree(int x){return a[x]>=3;}//?? 
 52     
 53     inline bool CanPlayBoom(int x){return a[x]>=4;}//?? 
 54     
 55     inline bool CanPlayRocket(){return a[13]&&a[14];}//?? 
 56     
 57     inline bool CanPlayMoreSingle(int l,int r){//?? 
 58         if(r-l+1<5||r>=12) return 0;
 59         for(int i=l;i<=r;i++) if(!CanPlaySingle(i)) return 0;
 60         return 1;
 61     }
 62     
 63     inline bool CanPlayMoreCouple(int l,int r){//?? 
 64         if(r-l+1<3||r>=12) return 0;
 65         for(int i=l;i<=r;i++) if(!CanPlayCouple(i)) return 0;
 66         return 1;
 67     }
 68     
 69     inline bool CanPlayMoreThree(int l,int r){//?? 
 70         if(r-l+1<2||r>=12) return 0;
 71         for(int i=l;i<=r;i++) if(!CanPlayThree(i)) return 0;
 72         return 1;
 73     }
 74     
 75     inline bool CanPlay4Single(int x,int l,int r){//??? 
 76         if(x==l||x==r) return 0;
 77         if(l==r) return CanPlayBoom(x)&&CanPlayCouple(l);
 78         return CanPlayBoom(x)&&CanPlaySingle(l)&&CanPlaySingle(r);
 79     }
 80     
 81     inline bool CanPlay4Couple(int x,int l,int r){//???
 82         if(x==l||x==r) return 0;
 83         if(l==r) return CanPlayBoom(x)&&CanPlayBoom(l);
 84         return CanPlayBoom(x)&&CanPlayCouple(l)&&CanPlayCouple(r);
 85     }
 86     
 87     inline bool CanPlay3Single(int x,int y){
 88         if(x==y) return 0;
 89         return CanPlayThree(x)&&CanPlaySingle(y);
 90     }
 91     
 92     inline bool CanPlay3Couple(int x,int y){
 93         if(x==y) return 0;
 94         return CanPlayThree(x)&&CanPlayCouple(y);
 95     }
 96     
 97     inline void PlaySingle(int x){a[x]--; cnt--;}
 98     
 99     inline void PlayCouple(int x){a[x]-=2; cnt-=2;}
100     
101     inline void PlayThree(int x){a[x]-=3; cnt-=3;}
102     
103     inline void PlayBoom(int x){a[x]-=4; cnt-=4;}
104     
105     inline void PlayRocket(){a[13]--;a[14]--; cnt-=2;}
106     
107     inline void PlayMoreSingle(int l,int r){for(int i=l;i<=r;i++) PlaySingle(i);}
108     
109     inline void PlayMoreCouple(int l,int r){for(int i=l;i<=r;i++) PlayCouple(i);}
110     
111     inline void PlayMoreThree(int l,int r){for(int i=l;i<=r;i++) PlayThree(i);}
112     
113     inline void Play4Single(int x,int l,int r){PlayBoom(x); PlaySingle(l); PlaySingle(r);}
114     
115     inline void Play4Couple(int x,int l,int r){PlayBoom(x); PlayCouple(l); PlayCouple(r);}
116     
117     inline void Play3Single(int x,int y){PlayThree(x); PlaySingle(y);}
118     
119     inline void Play3Couple(int x,int y){PlayThree(x); PlayCouple(y);}
120     
121     inline bool empty(){
122         return cnt==0;
123     }//?????? 
124     
125     inline long long Hash(){long long res=0; for(int i=0;i<16;i++) res=res<<2|a[i]; return res;}//??? 
126     
127     inline int GetMin(){for(int i=0;i<16;i++) if(a[i]) return i; assert(0);}
128     inline int GetMax(){for(int i=13;~i;i--) if(a[i]) return i; return -1;}
129     
130     inline void ResetCan(){
131         CanThree=CanBoom=CanMS=CanMC=0;//!!!
132         for(int i=0;i<16;i++){
133             if(CanPlayThree(i)) CanThree=1;
134             if(CanPlayBoom(i)) CanBoom=1;
135         }
136         if(CanPlayRocket()) CanBoom=1; 
137         for(int i=0;i<=7;i++){
138             if(CanPlayMoreSingle(i,i+4)) {CanMS=1; break;}
139         }
140         for(int i=0;i<=9;i++){
141             if(CanPlayMoreCouple(i,i+2)) {CanMC=1; break;}
142         }
143     }
144     
145     void read(){//Input Poker
146         memset(a,0,sizeof(a)); cnt=0;
147         string s; cin>>s; int len=s.length(); cnt=len;
148         for(int i=0;i<len;i++)
149         a[GetVal(s[i])]++;
150         ResetCan();
151     }
152 };

Player-v3.0

3.0版本在双方牌数不大于15张时，基本可以在1s内出解

（OFast编译，CPU：I5-4210M，辣鸡CPU）

2019年4月16日更新：

优化了分支判断速度，快了若干倍

更新了main和player，helper无更新

  1 #include "Player-v2.0.cpp"
  2 #include "Helper.cpp"
  3 
  4 #define END {if(fir){newA=a; newB=b;} return 1;}
  5 #define NXT {if(ok&&play(b,a,0)==0) return 1; else return 0;}
  6 #define NO  {printf("Can't Out
"); newA=a; newB=b;}
  7 player newA,newB;
  8 bool play(player,player,bool);
  9 
 10 bool Play_Rocket(player a,player b,bool fir){
 11     if(b.empty()) return 0;
 12     if(a.CanPlayRocket()){
 13         a.PlayRocket();
 14         bool now=play(a,b,0);
 15         if(now){
 16             if(fir) Out_Rocket();
 17             END;
 18         }
 19     }
 20     return 0;
 21 }
 22 
 23 bool Play_Boom(player a,player b,int last,bool fir,bool ok){
 24     if(b.empty()) return 0;
 25     if(Play_Rocket(a,b,fir)) return 1;
 26     player _a=a;
 27     if(a.CanBoom)
 28     for(int i=last+1;i<15;i++)
 29     if(a.CanPlayBoom(i)){
 30         a.PlayBoom(i);
 31         a.ResetCan();
 32         bool now=Play_Boom(b,a,i,0,1);
 33         if(!now){
 34             if(fir) Out_Boom(i);
 35             END;
 36         }
 37         a=_a;
 38     }
 39     NXT;
 40 }
 41 
 42 bool Play_Single(player a,player b,int last,bool fir,bool ok){
 43     if(b.empty()) return 0;
 44     player _a=a;
 45     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
 46     for(int i=last+1;i<15;i++)
 47     if(a.CanPlaySingle(i)){
 48         a.PlaySingle(i);
 49         bool now=Play_Single(b,a,i,0,1);
 50         if(!now){
 51             if(fir) Out_Single(i);
 52             END;
 53         }
 54         a=_a;
 55     }
 56     NXT;
 57 }
 58 
 59 bool Play_Couple(player a,player b,int last,bool fir,bool ok){
 60     if(b.empty()) return 0;
 61     player _a=a;
 62     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
 63     for(int i=last+1;i<13;i++)
 64     if(a.CanPlayCouple(i)){
 65         a.PlayCouple(i);
 66         bool now=Play_Couple(b,a,i,0,1);
 67         if(!now){
 68             if(fir) Out_Couple(i);
 69             END;
 70         }
 71         a=_a;
 72     }
 73     NXT;
 74 }
 75 
 76 bool Play_Three(player a,player b,int last,bool fir,bool ok){
 77     if(b.empty()) return 0;
 78     player _a=a;
 79     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
 80     if(a.CanThree)
 81     for(int i=last+1;i<13;i++)
 82     if(a.CanPlayThree(i)){
 83         a.PlayThree(i);
 84         a.ResetCan();
 85         bool now=Play_Three(b,a,i,0,1);
 86         if(!now){
 87             if(fir) Out_Three(i);
 88             END;
 89         }
 90         a=_a;
 91     }
 92     NXT;
 93 }
 94 
 95 bool Play_3Single(player a,player b,int last,bool fir,bool ok){
 96     if(b.empty()) return 0;
 97     player _a=a;
 98     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
 99     for(int i=last+1;i<13;i++) if(a.CanPlayThree(i))
100     if(a.CanThree)
101     for(int j=0;j<15;j++)
102     if(a.CanPlay3Single(i,j)){
103         a.Play3Single(i,j);
104         a.ResetCan();
105         bool now=Play_3Single(b,a,i,0,1);
106         if(!now){
107             if(fir) Out_3Single(i,j);
108             END;
109         }
110         a=_a;
111     }
112     NXT;
113 }
114 
115 bool Play_3Couple(player a,player b,int last,bool fir,bool ok){
116     if(b.empty()) return 0;
117     player _a=a;
118     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
119     for(int i=last+1;i<13;i++) if(a.CanPlayThree(i))
120     if(a.CanThree)
121     for(int j=0;j<15;j++)
122     if(a.CanPlay3Couple(i,j)){
123         a.Play3Couple(i,j);
124         a.ResetCan();
125         bool now=Play_3Couple(b,a,i,0,1);
126         if(!now){
127             if(fir) Out_3Couple(i,j);
128             END;
129         }
130         a=_a;
131     }
132     NXT;
133 }
134 
135 bool Play_4Single(player a,player b,int last,bool fir,bool ok){
136     if(b.empty()) return 0;
137     player _a=a;
138     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
139     for(int i=last+1;i<13;i++) if(a.CanPlayBoom(i))
140     if(a.CanBoom)
141     for(int j=0;j<15;j++)
142     for(int k=0;k<15;k++)
143     if(a.CanPlay4Single(i,j,k)){
144         a.Play4Single(i,j,k);
145     //    a.ResetCan();
146         bool now=Play_4Single(b,a,i,0,1);
147         if(!now){
148             if(fir) Out_4Single(i,j,k);
149             END;
150         }
151         a=_a;
152     }
153     NXT;
154 }
155 
156 bool Play_4Couple(player a,player b,int last,bool fir,bool ok){
157     if(b.empty()) return 0;
158     player _a=a;
159     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
160     for(int i=last+1;i<13;i++) if(a.CanPlayBoom(i))
161     if(a.CanBoom)
162     for(int j=0;j<15;j++)
163     for(int k=0;k<15;k++)
164     if(a.CanPlay4Couple(i,j,k)){
165         a.Play4Couple(i,j,k);
166         a.ResetCan();
167         bool now=Play_4Couple(b,a,i,0,1);
168         if(!now){
169             if(fir) Out_4Couple(i,j,k);
170             END;
171         }
172         a=_a;
173     }
174     NXT;
175 }
176 
177 bool Play_MS(player a,player b,int l,int r,bool fir,bool ok){
178     if(b.empty()) return 0;
179     player _a=a; int pls=r-l;
180     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
181     if(a.CanMS)
182     for(int i=l+1;i+pls<=11;i++)
183     if(a.CanPlayMoreSingle(i,i+pls)){
184         a.PlayMoreSingle(i,i+pls);
185         a.ResetCan();
186         bool now=Play_MS(b,a,i,i+pls,0,1);
187         if(!now){
188             if(fir) Out_MS(i,i+pls);
189             END;
190         }
191         a=_a;
192     }
193     NXT;
194 }
195 
196 bool Play_MC(player a,player b,int l,int r,bool fir,bool ok){
197     if(b.empty()) return 0;
198     player _a=a; int pls=r-l;
199     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
200     if(a.CanMC)
201     for(int i=l+1;i+pls<=11;i++)
202     if(a.CanPlayMoreCouple(i,i+pls)){
203         a.PlayMoreCouple(i,i+pls);
204         a.ResetCan();
205         bool now=Play_MC(b,a,i,i+pls,0,1);
206         if(!now){
207             if(fir) Out_MC(i,i+pls);
208             END;
209         }
210         a=_a;
211     }
212     NXT;
213 }
214 
215 bool play(player a,player b,bool fir=0){
216     if(b.empty()) return 0;
217     if(a.CanBoom) if(Play_Boom(a,b,-1,fir,0)) return 1;
218     if(a.CanMS)
219     for(int i=11;i>=4;i--){
220         if(Play_MS(a,b,-1,-1+i,fir,0)) return 1;
221     }
222     if(a.CanMC)
223     for(int i=8;i>=2;i--){
224         if(Play_MC(a,b,-1,-1+i,fir,0)) return 1;
225     }
226     if(a.CanThree) if(Play_Three(a,b,-1,fir,0)) return 1;
227     if(a.CanThree) if(Play_3Single(a,b,-1,fir,0)) return 1;
228     if(a.CanThree) if(Play_3Couple(a,b,-1,fir,0)) return 1;
229     if(Play_Couple(a,b,-1,fir,0)) return 1;
230     if(Play_Single(a,b,-1,fir,0)) return 1;
231     if(a.CanBoom) if(Play_4Single(a,b,-1,fir,0)) return 1;
232     if(a.CanBoom) if(Play_4Couple(a,b,-1,fir,0)) return 1;
233     return 0;
234 }
235 
236 int Main(){
237     player a,b;
238     printf("INPUT AI:
");
239     b.read(); 
240     printf("INPUT PLAYER:
");
241     a.read();
242     if(!play(a,b,1)){
243         printf("DIE
");
244         return 0;
245     }
246     while(1){
247         a=newA; b=newB;
248         printf("
");
249         if(a.empty()){
250             printf("WIN
");
251             return 0;
252         }
253         
254         string now; cin>>now;
255         if(now=="EXIT") return 0;
256         if(Is_Empty(now)){
257             if(!play(a,b,1)){
258                 printf("DIE
");
259             }
260             continue;
261         }
262         for(int i=0;i<now.length();i++) b.PlaySingle(GetVal(now[i]));
263         
264         if(Is_Single(now)&&Play_Single(a,b,GetVal(now[0]),1,0)==0) NO;
265         if(Is_Couple(now)&&Play_Couple(a,b,GetVal(now[0]),1,0)==0) NO;
266         if(Is_Three(now)&&Play_Three(a,b,GetVal(now[0]),1,0)==0) NO;
267         if(Is_Boom(now)&&Play_Boom(a,b,GetVal(now[0]),1,0)==0) NO;
268         if(Is_Rocket(now)&&Play_Rocket(a,b,1)==0) NO;
269         if(Is_3Single(now)&&Play_3Single(a,b,GetVal(now[0]),1,0)==0) NO;
270         if(Is_3Couple(now)&&Play_3Couple(a,b,GetVal(now[0]),1,0)==0) NO;
271         if(Is_4Single(now)&&Play_4Single(a,b,GetVal(now[0]),1,0)==0) NO;
272         if(Is_4Couple(now)&&Play_4Couple(a,b,GetVal(now[0]),1,0)==0) NO;
273         if(Is_MS(now)&&Play_MS(a,b,GetVal(now[0]),GetVal(now[now.length()-1]),1,0)==0) NO;
274         if(Is_MC(now)&&Play_MC(a,b,GetVal(now[0]),GetVal(now[now.length()-1]),1,0)==0) NO;
275     }
276 }
277 
278 int main(){
279     while(1) Main();
280 }

main-v2.0

  1 /*
  2     ???????????????????
  3     ??
  4     ??????
  5 */ 
  6 
  7 #include<bits/stdc++.h>
  8 using namespace std;
  9 
 10 int GetVal(char c){
 11     if(c=='T') return 7;
 12     if(c=='J') return 8;
 13     if(c=='Q') return 9;
 14     if(c=='K') return 10;
 15     if(c=='A') return 11;
 16     if(c=='2') return 12;
 17     if(c=='w') return 13;
 18     if(c=='W') return 14;
 19     if('3'<=c&&c<='9') return c-'3';
 20     assert(0);
 21 }
 22 char SetChar(int x){
 23     if(x<=6) return '3'+x;
 24     if(x==7) return 'T';
 25     if(x==8) return 'J';
 26     if(x==9) return 'Q';
 27     if(x==10) return 'K';
 28     if(x==11) return 'A';
 29     if(x==12) return '2';
 30     if(x==13) return 'w';
 31     if(x==14) return 'W';
 32     assert(0);
 33 }
 34 
 35 struct player{
 36     int a[16]; 
 37     bool CanThree,CanBoom,CanMS,CanMC;
 38     player(){memset(a,0,sizeof(a));}
 39     
 40     void out(){//Output Poker
 41         for(int i=0;i<16;i++) 
 42         for(int j=0;j<a[i];j++)
 43         putchar(SetChar(i));
 44         putchar('
');
 45     }
 46     
 47     inline bool CanPlaySingle(int x){return a[x]>=1;}//? 
 48     
 49     inline bool CanPlayCouple(int x){return a[x]>=2;}//? 
 50     
 51     inline bool CanPlayThree(int x){return a[x]>=3;}//?? 
 52     
 53     inline bool CanPlayBoom(int x){return a[x]>=4;}//?? 
 54     
 55     inline bool CanPlayRocket(){return a[13]&&a[14];}//?? 
 56     
 57     inline bool CanPlayMoreSingle(int l,int r){//?? 
 58         if(r-l+1<5||r>=12) return 0;
 59         for(int i=l;i<=r;i++) if(!CanPlaySingle(i)) return 0;
 60         return 1;
 61     }
 62     
 63     inline bool CanPlayMoreCouple(int l,int r){//?? 
 64         if(r-l+1<3||r>=12) return 0;
 65         for(int i=l;i<=r;i++) if(!CanPlayCouple(i)) return 0;
 66         return 1;
 67     }
 68     
 69     inline bool CanPlayMoreThree(int l,int r){//?? 
 70         if(r-l+1<2||r>=12) return 0;
 71         for(int i=l;i<=r;i++) if(!CanPlayThree(i)) return 0;
 72         return 1;
 73     }
 74     
 75     inline bool CanPlay4Single(int x,int l,int r){//??? 
 76         if(x==l||x==r) return 0;
 77         if(l==r) return CanPlayBoom(x)&&CanPlayCouple(l);
 78         return CanPlayBoom(x)&&CanPlaySingle(l)&&CanPlaySingle(r);
 79     }
 80     
 81     inline bool CanPlay4Couple(int x,int l,int r){//???
 82         if(x==l||x==r) return 0;
 83         if(l==r) return CanPlayBoom(x)&&CanPlayBoom(l);
 84         return CanPlayBoom(x)&&CanPlayCouple(l)&&CanPlayCouple(r);
 85     }
 86     
 87     inline bool CanPlay3Single(int x,int y){
 88         if(x==y) return 0;
 89         return CanPlayThree(x)&&CanPlaySingle(y);
 90     }
 91     
 92     inline bool CanPlay3Couple(int x,int y){
 93         if(x==y) return 0;
 94         return CanPlayThree(x)&&CanPlayCouple(y);
 95     }
 96     
 97     inline void PlaySingle(int x){a[x]--;}
 98     
 99     inline void PlayCouple(int x){a[x]-=2;}
100     
101     inline void PlayThree(int x){a[x]-=3;}
102     
103     inline void PlayBoom(int x){a[x]-=4;}
104     
105     inline void PlayRocket(){a[13]--;a[14]--;}
106     
107     inline void PlayMoreSingle(int l,int r){for(int i=l;i<=r;i++) PlaySingle(i);}
108     
109     inline void PlayMoreCouple(int l,int r){for(int i=l;i<=r;i++) PlayCouple(i);}
110     
111     inline void PlayMoreThree(int l,int r){for(int i=l;i<=r;i++) PlayThree(i);}
112     
113     inline void Play4Single(int x,int l,int r){PlayBoom(x); PlaySingle(l); PlaySingle(r);}
114     
115     inline void Play4Couple(int x,int l,int r){PlayBoom(x); PlayCouple(l); PlayCouple(r);}
116     
117     inline void Play3Single(int x,int y){PlayThree(x); PlaySingle(y);}
118     
119     inline void Play3Couple(int x,int y){PlayThree(x); PlayCouple(y);}
120     
121     inline bool empty(){
122         for(int i=0;i<16;i++) 
123         if(a[i]) 
124         return 0; 
125     return 1;}//?????? 
126     
127     inline long long Hash(){long long res=0; for(int i=0;i<16;i++) res=res<<2|a[i]; return res;}//??? 
128     
129     inline int GetMin(){for(int i=0;i<16;i++) if(a[i]) return i; assert(0);}
130     inline int GetMax(){for(int i=13;~i;i--) if(a[i]) return i; return -1;}
131     
132     inline void ResetCan(){
133         CanThree=CanBoom=CanMS=CanMC=0;//!!!
134         for(int i=0;i<16;i++){
135             if(CanPlayThree(i)) CanThree=1;
136             if(CanPlayBoom(i)) CanBoom=1;
137         }
138         if(CanPlayRocket()) CanBoom=1; 
139         for(int i=0;i<=7;i++){
140             if(CanPlayMoreSingle(i,i+4)) {CanMS=1; break;}
141         }
142         for(int i=0;i<=9;i++){
143             if(CanPlayMoreCouple(i,i+2)) {CanMC=1; break;}
144         }
145     }
146     
147     void read(){//Input Poker
148         memset(a,0,sizeof(a));
149         string s; cin>>s; int len=s.length();
150         for(int i=0;i<len;i++)
151         a[GetVal(s[i])]++;
152         ResetCan();
153     }
154 };

Player-v2.0

众所周知欢乐斗地主这个游戏有一个叫做残局的模式

模式的特征：你和机器人都互相知道对方的牌，且对面的机器人绝顶聪明。

正常的斗地主规则，问你要如何出牌，才能保证你一定能赢。

我们考虑直接爆搜，发现需要搜一年。

于是我们加一个Alpha-Beta剪枝来加速整个爆搜过程即可。

貌似绝大部分情况下都是秒出结果的

目前最长时间只搜了15s（这是v2.0的时间，旧版貌似接近一分钟了）

正确率100%，快速通关利器233333

输入牌型要求：2~9直接输入，JQKA直接输入，10用T表示，大王小王分别用Ww表示。

输入顺子/连对要从小到大输入（按照斗地主规则的从小到大），输入三带一/对，四带二/对，需要先输入三张/四张，再输入剩下的东西

代码貌似只要10k多一点

注意细节

两个关联文件的代码：

 1 /*
 2     该部分函数用于输出打出的牌
 3     以及
 4     分析当前输入的牌型
 5     
 6 */ 
 7 
 8 inline void Out_Single(int x){printf("%c",SetChar(x));}
 9 
10 inline void Out_Couple(int x){printf("%c%c",SetChar(x),SetChar(x));}
11 
12 inline void Out_Three(int x){printf("%c%c%c",SetChar(x),SetChar(x),SetChar(x));}
13 
14 inline void Out_Boom(int x){printf("%c%c%c%c",SetChar(x),SetChar(x),SetChar(x),SetChar(x));}
15 
16 inline void Out_3Single(int x,int y){Out_Three(x); Out_Single(y);}
17 
18 inline void Out_3Couple(int x,int y){Out_Three(x); Out_Couple(y);}
19 
20 inline void Out_MS(int l,int r){for(int i=l;i<=r;i++) Out_Single(i);}
21 
22 inline void Out_MC(int l,int r){for(int i=l;i<=r;i++) Out_Couple(i);}
23 
24 inline void Out_M3(int l,int r){for(int i=l;i<=r;i++) Out_Three(i);}
25 
26 inline void Out_Rocket(){printf("Ww");}
27 
28 inline void Out_4Single(int x,int l,int r){Out_Boom(x); Out_Single(l); Out_Single(r);}
29 
30 inline void Out_4Couple(int x,int l,int r){Out_Boom(x); Out_Couple(l); Out_Couple(r);}
31 
32 inline bool Is_Empty(string s){return s.length()==1&&s[0]=='*';}
33 
34 inline bool Is_Single(string s){return s.length()==1;}
35 
36 inline bool Is_Rocket(string s){return s=="Ww"||s=="wW";}
37 
38 inline bool Is_Couple(string s){return s.length()==2&&s[0]==s[1];}
39 
40 inline bool Is_Three(string s){return s.length()==3&&s[0]==s[1]&&s[1]==s[2];}
41 
42 inline bool Is_Boom(string s){return s.length()==4&&s[0]==s[1]&&s[1]==s[2]&&s[2]==s[3];}
43 
44 inline bool Is_3Single(string s){return s.length()==4&&s[0]==s[1]&&s[1]==s[2]&&s[2]!=s[3];}
45 
46 inline bool Is_3Couple(string s){return s.length()==5&&s[0]==s[1]&&s[1]==s[2]&&s[2]!=s[3]&&s[3]==s[4];}
47 
48 inline bool Is_MS(string s){
49     int len=s.length(); if(len<5) return 0; 
50     for(int i=1;i<len;i++) if(GetVal(s[i-1])+1!=GetVal(s[i])) return 0; 
51     return 1;
52 }
53 
54 inline bool Is_MC(string s){
55     int len=s.length(); if((len&1)||len<6) return 0;
56     for(int i=1;i<len;i+=2){
57         if(s[i]!=s[i-1]) return 0;
58     }
59     for(int i=2;i<len;i+=2){
60         if(GetVal(s[i-2])+1!=GetVal(s[i])) return 0;
61     }
62     return 1;
63 }
64 
65 inline bool Is_4Single(string s){return s.length()==6&&s[0]==s[1]&&s[1]==s[2]&&s[2]==s[3]&&s[3]!=s[4];}
66 
67 inline bool Is_4Couple(string s){return s.length()==8&&s[0]==s[1]&&s[1]==s[2]&&s[2]==s[3]&&s[3]!=s[4]&&s[4]==s[5]&&s[6]==s[7];}

Helper.cpp

  1 /*
  2     该部分函数用于判定是否可以出该类型的牌
  3     以及
  4     模拟出牌过程
  5 */ 
  6 
  7 #include<bits/stdc++.h>
  8 using namespace std;
  9 
 10 int GetVal(char c){
 11     if(c=='T') return 7;
 12     if(c=='J') return 8;
 13     if(c=='Q') return 9;
 14     if(c=='K') return 10;
 15     if(c=='A') return 11;
 16     if(c=='2') return 12;
 17     if(c=='w') return 13;
 18     if(c=='W') return 14;
 19     if('3'<=c&&c<='9') return c-'3';
 20     assert(0);
 21 }
 22 char SetChar(int x){
 23     if(x<=6) return '3'+x;
 24     if(x==7) return 'T';
 25     if(x==8) return 'J';
 26     if(x==9) return 'Q';
 27     if(x==10) return 'K';
 28     if(x==11) return 'A';
 29     if(x==12) return '2';
 30     if(x==13) return 'w';
 31     if(x==14) return 'W';
 32     assert(0);
 33 }
 34 
 35 struct player{
 36     int a[16]; 
 37     player(){memset(a,0,sizeof(a));}
 38     void read(){//Input Poker
 39         memset(a,0,sizeof(a));
 40         string s; cin>>s; int len=s.length();
 41         for(int i=0;i<len;i++)
 42         a[GetVal(s[i])]++;
 43     }
 44     
 45     void out(){//Output Poker
 46         for(int i=0;i<16;i++) 
 47         for(int j=0;j<a[i];j++)
 48         putchar(SetChar(i));
 49         putchar('
');
 50     }
 51     
 52     inline bool CanPlaySingle(int x){return a[x]>=1;}//单 
 53     
 54     inline bool CanPlayCouple(int x){return a[x]>=2;}//对 
 55     
 56     inline bool CanPlayThree(int x){return a[x]>=3;}//三张 
 57     
 58     inline bool CanPlayBoom(int x){return a[x]>=4;}//炸弹 
 59     
 60     inline bool CanPlayRocket(){return a[13]&&a[14];}//火箭 
 61     
 62     inline bool CanPlayMoreSingle(int l,int r){//顺子 
 63         if(r-l+1<5||r>=12) return 0;
 64         for(int i=l;i<=r;i++) if(!CanPlaySingle(i)) return 0;
 65         return 1;
 66     }
 67     
 68     inline bool CanPlayMoreCouple(int l,int r){//连对 
 69         if(r-l+1<3||r>=12) return 0;
 70         for(int i=l;i<=r;i++) if(!CanPlayCouple(i)) return 0;
 71         return 1;
 72     }
 73     
 74     inline bool CanPlayMoreThree(int l,int r){//飞机 
 75         if(r-l+1<2||r>=12) return 0;
 76         for(int i=l;i<=r;i++) if(!CanPlayThree(i)) return 0;
 77         return 1;
 78     }
 79     
 80     inline bool CanPlay4Single(int x,int l,int r){//四带二 
 81         if(x==l||x==r) return 0;
 82         if(l==r) return CanPlayBoom(x)&&CanPlayCouple(l);
 83         return CanPlayBoom(x)&&CanPlaySingle(l)&&CanPlaySingle(r);
 84     }
 85     
 86     inline bool CanPlay4Couple(int x,int l,int r){//四带对
 87         if(x==l||x==r) return 0;
 88         if(l==r) return CanPlayBoom(x)&&CanPlayBoom(l);
 89         return CanPlayBoom(x)&&CanPlayCouple(l)&&CanPlayCouple(r);
 90     }
 91     
 92     inline bool CanPlay3Single(int x,int y){
 93         if(x==y) return 0;
 94         return CanPlayThree(x)&&CanPlaySingle(y);
 95     }
 96     
 97     inline bool CanPlay3Couple(int x,int y){
 98         if(x==y) return 0;
 99         return CanPlayThree(x)&&CanPlayCouple(y);
100     }
101     
102     inline void PlaySingle(int x){a[x]--;}
103     
104     inline void PlayCouple(int x){a[x]-=2;}
105     
106     inline void PlayThree(int x){a[x]-=3;}
107     
108     inline void PlayBoom(int x){a[x]-=4;}
109     
110     inline void PlayRocket(){a[13]--;a[14]--;}
111     
112     inline void PlayMoreSingle(int l,int r){for(int i=l;i<=r;i++) PlaySingle(i);}
113     
114     inline void PlayMoreCouple(int l,int r){for(int i=l;i<=r;i++) PlayCouple(i);}
115     
116     inline void PlayMoreThree(int l,int r){for(int i=l;i<=r;i++) PlayThree(i);}
117     
118     inline void Play4Single(int x,int l,int r){PlayBoom(x); PlaySingle(l); PlaySingle(r);}
119     
120     inline void Play4Couple(int x,int l,int r){PlayBoom(x); PlayCouple(l); PlayCouple(r);}
121     
122     inline void Play3Single(int x,int y){PlayThree(x); PlaySingle(y);}
123     
124     inline void Play3Couple(int x,int y){PlayThree(x); PlayCouple(y);}
125     
126     inline bool empty(){
127         for(int i=0;i<16;i++) 
128         if(a[i]) 
129         return 0; 
130     return 1;}//判断是否出完 
131     
132     inline long long Hash(){long long res=0; for(int i=0;i<16;i++) res=res<<2|a[i]; return res;}//哈希值 
133     
134     inline int GetMin(){for(int i=0;i<16;i++) if(a[i]) return i; assert(0);}
135     inline int GetMax(){for(int i=13;~i;i--) if(a[i]) return i; return -1;}
136 };

Player.cpp

主代码：

  1 #include "Player.cpp"
  2 #include "Helper.cpp"
  3 
  4 #define END {if(fir){newA=a; newB=b;} return 1;}
  5 #define NXT {if(ok&&play(b,a,0)==0) return 1; else return 0;}
  6 #define NO  {printf("Can't Out
"); newA=a; newB=b;}
  7 player newA,newB;
  8 bool play(player,player,bool);
  9 
 10 bool Play_Rocket(player a,player b,bool fir){
 11     if(b.empty()) return 0;
 12     if(a.CanPlayRocket()){
 13         a.PlayRocket();
 14         bool now=play(a,b,0);
 15         if(now){
 16             if(fir) Out_Rocket();
 17             END;
 18         }
 19     }
 20     return 0;
 21 }
 22 
 23 bool Play_Boom(player a,player b,int last,bool fir,bool ok){
 24     if(b.empty()) return 0;
 25     if(Play_Rocket(a,b,fir)) return 1;
 26     player _a=a;
 27     for(int i=last+1;i<15;i++)
 28     if(a.CanPlayBoom(i)){
 29         a.PlayBoom(i);
 30         bool now=Play_Boom(b,a,i,0,1);
 31         if(!now){
 32             if(fir) Out_Boom(i);
 33             END;
 34         }
 35         a=_a;
 36     }
 37     NXT;
 38 }
 39 
 40 bool Play_Single(player a,player b,int last,bool fir,bool ok){
 41     if(b.empty()) return 0;
 42     player _a=a;
 43     if(Play_Boom(a,b,-1,fir,0)) return 1;
 44     for(int i=last+1;i<15;i++)
 45     if(a.CanPlaySingle(i)){
 46         a.PlaySingle(i);
 47         bool now=Play_Single(b,a,i,0,1);
 48         if(!now){
 49             if(fir) Out_Single(i);
 50             END;
 51         }
 52         a=_a;
 53     }
 54     NXT;
 55 }
 56 
 57 bool Play_Couple(player a,player b,int last,bool fir,bool ok){
 58     if(b.empty()) return 0;
 59     player _a=a;
 60     if(Play_Boom(a,b,-1,fir,0)) return 1;
 61     for(int i=last+1;i<13;i++)
 62     if(a.CanPlayCouple(i)){
 63         a.PlayCouple(i);
 64         bool now=Play_Couple(b,a,i,0,1);
 65         if(!now){
 66             if(fir) Out_Couple(i);
 67             END;
 68         }
 69         a=_a;
 70     }
 71     NXT;
 72 }
 73 
 74 bool Play_Three(player a,player b,int last,bool fir,bool ok){
 75     if(b.empty()) return 0;
 76     player _a=a;
 77     if(Play_Boom(a,b,-1,fir,0)) return 1;
 78     for(int i=last+1;i<13;i++)
 79     if(a.CanPlayThree(i)){
 80         a.PlayThree(i);
 81         bool now=Play_Three(b,a,i,0,1);
 82         if(!now){
 83             if(fir) Out_Three(i);
 84             END;
 85         }
 86         a=_a;
 87     }
 88     NXT;
 89 }
 90 
 91 bool Play_3Single(player a,player b,int last,bool fir,bool ok){
 92     if(b.empty()) return 0;
 93     player _a=a;
 94     if(Play_Boom(a,b,-1,fir,0)) return 1;
 95     for(int i=last+1;i<13;i++) if(a.CanPlayThree(i))
 96     for(int j=0;j<15;j++)
 97     if(a.CanPlay3Single(i,j)){
 98         a.Play3Single(i,j);
 99         bool now=Play_3Single(b,a,i,0,1);
100         if(!now){
101             if(fir) Out_3Single(i,j);
102             END;
103         }
104         a=_a;
105     }
106     NXT;
107 }
108 
109 bool Play_3Couple(player a,player b,int last,bool fir,bool ok){
110     if(b.empty()) return 0;
111     player _a=a;
112     if(Play_Boom(a,b,-1,fir,0)) return 1;
113     for(int i=last+1;i<13;i++) if(a.CanPlayThree(i))
114     for(int j=0;j<15;j++)
115     if(a.CanPlay3Couple(i,j)){
116         a.Play3Couple(i,j);
117         bool now=Play_3Couple(b,a,i,0,1);
118         if(!now){
119             if(fir) Out_3Couple(i,j);
120             END;
121         }
122         a=_a;
123     }
124     NXT;
125 }
126 
127 bool Play_4Single(player a,player b,int last,bool fir,bool ok){
128     if(b.empty()) return 0;
129     player _a=a;
130     if(Play_Boom(a,b,-1,fir,0)) return 1;
131     for(int i=last+1;i<13;i++) if(a.CanPlayBoom(i))
132     for(int j=0;j<15;j++)
133     for(int k=0;k<15;k++)
134     if(a.CanPlay4Single(i,j,k)){
135         a.Play4Single(i,j,k);
136         bool now=Play_4Single(b,a,i,0,1);
137         if(!now){
138             if(fir) Out_4Single(i,j,k);
139             END;
140         }
141         a=_a;
142     }
143     NXT;
144 }
145 
146 bool Play_4Couple(player a,player b,int last,bool fir,bool ok){
147     if(b.empty()) return 0;
148     player _a=a;
149     if(Play_Boom(a,b,-1,fir,0)) return 1;
150     for(int i=last+1;i<13;i++) if(a.CanPlayBoom(i))
151     for(int j=0;j<15;j++)
152     for(int k=0;k<15;k++)
153     if(a.CanPlay4Couple(i,j,k)){
154         a.Play4Couple(i,j,k);
155         bool now=Play_4Couple(b,a,i,0,1);
156         if(!now){
157             if(fir) Out_4Couple(i,j,k);
158             END;
159         }
160         a=_a;
161     }
162     NXT;
163 }
164 
165 bool Play_MS(player a,player b,int l,int r,bool fir,bool ok){
166     if(b.empty()) return 0;
167     player _a=a; int pls=r-l;
168     if(Play_Boom(a,b,-1,fir,0)) return 1;
169     for(int i=l+1;i+pls<=11;i++)
170     if(a.CanPlayMoreSingle(i,i+pls)){
171         a.PlayMoreSingle(i,i+pls);
172         bool now=Play_MS(b,a,i,i+pls,0,1);
173         if(!now){
174             if(fir) Out_MS(i,i+pls);
175             END;
176         }
177         a=_a;
178     }
179     NXT;
180 }
181 
182 bool Play_MC(player a,player b,int l,int r,bool fir,bool ok){
183     if(b.empty()) return 0;
184     player _a=a; int pls=r-l;
185     if(Play_Boom(a,b,-1,fir,0)) return 1;
186     for(int i=l+1;i+pls<=11;i++)
187     if(a.CanPlayMoreCouple(i,i+pls)){
188         a.PlayMoreCouple(i,i+pls);
189         bool now=Play_MC(b,a,i,i+pls,0,1);
190         if(!now){
191             if(fir) Out_MC(i,i+pls);
192             END;
193         }
194         a=_a;
195     }
196     NXT;
197 }
198 
199 bool play(player a,player b,bool fir=0){
200     if(b.empty()) return 0;
201     if(Play_Boom(a,b,-1,fir,0)) return 1;
202     for(int i=11;i>=4;i--){
203         if(Play_MS(a,b,-1,-1+i,fir,0)) return 1;
204     }
205     for(int i=8;i>=2;i--){
206         if(Play_MC(a,b,-1,-1+i,fir,0)) return 1;
207     }
208     if(Play_Three(a,b,-1,fir,0)) return 1;
209     if(Play_3Single(a,b,-1,fir,0)) return 1;
210     if(Play_3Couple(a,b,-1,fir,0)) return 1;
211     if(Play_Couple(a,b,-1,fir,0)) return 1;
212     if(Play_Single(a,b,-1,fir,0)) return 1;
213     if(Play_4Single(a,b,-1,fir,0)) return 1;
214     if(Play_4Couple(a,b,-1,fir,0)) return 1;
215     return 0;
216 }
217 
218 int Main(){
219     player a,b;
220     printf("INPUT AI:
");
221     b.read(); 
222     printf("INPUT PLAYER:
");
223     a.read();
224     if(!play(a,b,1)){
225         printf("DIE
");
226         return 0;
227     }
228     while(1){
229         a=newA; b=newB;
230         printf("
");
231         if(a.empty()){
232             printf("WIN
");
233             return 0;
234         }
235         
236         string now; cin>>now;
237         if(now=="EXIT") return 0;
238         if(Is_Empty(now)){
239             if(!play(a,b,1)){
240                 printf("DIE
");
241             }
242             continue;
243         }
244         for(int i=0;i<now.length();i++) b.PlaySingle(GetVal(now[i]));
245         
246         if(Is_Single(now)&&Play_Single(a,b,GetVal(now[0]),1,0)==0) NO;
247         if(Is_Couple(now)&&Play_Couple(a,b,GetVal(now[0]),1,0)==0) NO;
248         if(Is_Three(now)&&Play_Three(a,b,GetVal(now[0]),1,0)==0) NO;
249         if(Is_Boom(now)&&Play_Boom(a,b,GetVal(now[0]),1,0)==0) NO;
250         if(Is_Rocket(now)&&Play_Rocket(a,b,1)==0) NO;
251         if(Is_3Single(now)&&Play_3Single(a,b,GetVal(now[0]),1,0)==0) NO;
252         if(Is_3Couple(now)&&Play_3Couple(a,b,GetVal(now[0]),1,0)==0) NO;
253         if(Is_4Single(now)&&Play_4Single(a,b,GetVal(now[0]),1,0)==0) NO;
254         if(Is_4Couple(now)&&Play_4Couple(a,b,GetVal(now[0]),1,0)==0) NO;
255         if(Is_MS(now)&&Play_MS(a,b,GetVal(now[0]),GetVal(now[now.length()-1]),1,0)==0) NO;
256         if(Is_MC(now)&&Play_MC(a,b,GetVal(now[0]),GetVal(now[now.length()-1]),1,0)==0) NO;
257     }
258 }
259 
260 int main(){
261     while(1) Main();
262 }