POJ 1568 Find the Winning Move

Find the Winning Move

题意：

4*4的棋盘，给出一个初始局面，问先手有没有必胜策略？

　　有的话输出第一步下在哪里，如果有多个，按(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1) ... 的顺序输出第一个。没有输出“#####”。

分析：

　　极大极小搜索或者对抗搜索，α+β剪枝。

　　极大极小搜索：每个人都会进行最聪明的决策，假设有1号玩家为我们希望的玩家（即判断他能否有必胜的走法），那么对于一号玩家进行决策时，让他去所有后继状态中最大的，即Max节点。而二号玩家也会进行最聪明的决策，他会去所有后继状态中最小的，即Min节点。于是我们搜索出所有的后继状态的估价值，判断。

　　α+β剪枝：思想：搜索到一个节点时，如果他进行最优决策，已经比父节点档当前的答案不优了，这个节点父节点是不会选的，这个节点的其他子节点的也不用搜了。

代码：

α+β剪枝：16ms

 1 #include<cstdio>
 2 
 3 char g[5][5];
 4 int ansx,ansy;
 5 
 6 int judge() {
 7     int za = 0,zb = 0; // 主对角线
 8     int fa = 0,fb = 0; // 副对角线 
 9     for (int i=1; i<=4; ++i) {
10         if (g[i][i] == 'x') za++; 
11         else if (g[i][i]=='o') zb++;
12         if (g[i][5-i] == 'x') fa++; 
13         else if (g[i][5-i]=='o') fb++;
14     }
15     if (za==4 || fa==4) return 1;
16     if (zb==4 || fb==4) return -1;
17     
18     for (int i=1; i<=4; ++i) {
19         int ra = 0,rb = 0; // 行 
20         int ca = 0,cb = 0; // 列 
21         for (int j=1; j<=4; ++j) {
22             if (g[i][j] == 'x') ra++; 
23             else if (g[i][j] == 'o') rb++;
24             if (g[j][i] == 'x') ca++; 
25             else if (g[j][i] == 'o') cb++;
26         }
27         if (ra == 4 || ca == 4) return 1;
28         if (rb == 4 || cb == 4) return -1;
29     }
30     
31     return 0;    
32 }
33 int Minimax(int player,int alpha,int beta) {
34     int res= judge();
35     if (res) return res;
36     if (player) {
37         for (int i=1; i<=4; ++i) 
38             for (int j=1; j<=4; ++j) 
39                 if (g[i][j] == '.') {
40                     g[i][j] = 'x';
41                     res = Minimax(player^1,alpha,beta);
42                     g[i][j] = '.';
43                     if (res > alpha) alpha = res,ansx = i,ansy = j;
44                     if (alpha >= beta) return alpha;
45                 }
46         return alpha; //-
47     }
48     else {
49         for (int i=1; i<=4; ++i) 
50             for (int j=1; j<=4; ++j) 
51                 if (g[i][j] == '.') {
52                     g[i][j] = 'o';
53                     res = Minimax(player^1,alpha,beta);
54                     g[i][j] = '.';
55                     if (res < beta) beta = res;
56                     if (alpha >= beta) return beta;
57                 }
58         return beta; //-
59     }
60 }
61 
62 int main() {
63     char op[5];
64     while (scanf("%s",op) && op[0]!='$') {
65         int cnt = 0;
66         for (int i=1; i<=4; ++i) {
67             scanf("%s",g[i]+1);
68             for (int j=1; j<=4; ++j) 
69                 if (g[i][j] != '.') cnt++;
70         }
71         if (cnt <= 4) {
72             puts("#####");continue;
73         }
74         int ans = Minimax(1,-1,1); 
75         if (ans > 0) printf("(%d,%d)
",ansx-1,ansy-1);
76         else puts("#####");
77     }
78     return 0;
79 }

View Code

没有α+β剪枝：63ms

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4  
 5 char g[5][5];
 6 int ansx,ansy,f;
 7 
 8 int judge() {
 9     int za = 0,zb = 0; // 主对角线
10     int fa = 0,fb = 0; // 副对角线 
11     for (int i=1; i<=4; ++i) {
12         if (g[i][i] == 'x') za++; 
13         else if (g[i][i]=='o') zb++;
14         if (g[i][5-i] == 'x') fa++; 
15         else if (g[i][5-i]=='o') fb++;
16     }
17     if (za==4 || fa==4) return 1;
18     if (zb==4 || fb==4) return -1;
19     
20     for (int i=1; i<=4; ++i) {
21         int ra = 0,rb = 0; // 行 
22         int ca = 0,cb = 0; // 列 
23         for (int j=1; j<=4; ++j) {
24             if (g[i][j] == 'x') ra++; 
25             else if (g[i][j] == 'o') rb++;
26             if (g[j][i] == 'x') ca++; 
27             else if (g[j][i] == 'o') cb++;
28         }
29         if (ra == 4 || ca == 4) return 1;
30         if (rb == 4 || cb == 4) return -1;
31     }
32     
33     return 0;    
34 }
35 int Minimax(int player,bool flag) {
36     int res= judge(),t;
37     if (res) return res;
38     if (player) {
39         for (int i=1; i<=4; ++i) 
40             for (int j=1; j<=4; ++j) 
41                 if (g[i][j] == '.') {
42                     g[i][j] = 'x';
43                     t = Minimax(player^1,0); 
44                     if (t > res) {
45                         res = t;
46                         if (flag) {
47                             printf("(%d,%d)
",i-1,j-1);
48                             f = 1;
49                             return 2;
50                         }
51                     }
52                     g[i][j] = '.';
53                 }
54         return res;
55     }
56     else {
57         res = 1000;
58         for (int i=1; i<=4; ++i) 
59             for (int j=1; j<=4; ++j) 
60                 if (g[i][j] == '.') {
61                     g[i][j] = 'o';
62                     res = std::min(res,Minimax(player^1,0));
63                     g[i][j] = '.';
64                 }
65         return res; //-
66     }
67 }
68 
69 int main() {
70     char op[5];
71     while (scanf("%s",op) && op[0]!='$') {
72         int cnt = 0;
73         f = 0;
74         for (int i=1; i<=4; ++i) {
75             scanf("%s",g[i]+1);
76             for (int j=1; j<=4; ++j) 
77                 if (g[i][j] != '.') cnt++;
78         }
79         if (cnt <= 4) {
80             puts("#####");continue;
81         }
82         Minimax(1,1); 
83         if (!f) puts("#####");
84     }
85     return 0;
86 }

View Code