【POJ1568】【极大极小搜索+alpha-beta剪枝】Find the Winning Move

Description

4x4 tic-tac-toe is played on a board with four rows (numbered 0 to 3 from top to bottom) and four columns (numbered 0 to 3 from left to right). There are two players, x and o, who move alternately with x always going first. The game is won by the first player to get four of his or her pieces on the same row, column, or diagonal. If the board is full and neither player has won then the game is a draw.
Assuming that it is x's turn to move, x is said to have a forced win if x can make a move such that no matter what moves o makes for the rest of the game, x can win. This does not necessarily mean that x will win on the very next move, although that is a possibility. It means that x has a winning strategy that will guarantee an eventual victory regardless of what o does.

Your job is to write a program that, given a partially-completed game with x to move next, will determine whether x has a forced win. You can assume that each player has made at least two moves, that the game has not already been won by either player, and that the board is not full.

Input

The input contains one or more test cases, followed by a line beginning with a dollar sign that signals the end of the file. Each test case begins with a line containing a question mark and is followed by four lines representing the board; formatting is exactly as shown in the example. The characters used in a board description are the period (representing an empty space), lowercase x, and lowercase o. For each test case, output a line containing the (row, column) position of the first forced win for x, or '#####' if there is no forced win. Format the output exactly as shown in the example.

Output

For this problem, the first forced win is determined by board position, not the number of moves required for victory. Search for a forced win by examining positions (0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), ..., (3, 2), (3, 3), in that order, and output the first forced win you find. In the second test case below, note that x could win immediately by playing at (0, 3) or (2, 0), but playing at (0, 1) will still ensure victory (although it unnecessarily delays it), and position (0, 1) comes first.

Sample Input

?
....
.xo.
.ox.
....
?
o...
.ox.
.xxx
xooo
$

Sample Output

#####
(0,1)

Source

Mid-Central USA 1999

【分析】

经典的题目，第一次写。。参考了别人的代码

  1 /*
  2 宋代仲殊
  3 《南柯子·十里青山远》
  4 十里青山远，潮平路带沙。数声啼鸟怨年华。又是凄凉时候，在天涯。
  5 白露收残月，清风散晓霞。绿杨堤畔问荷花：记得年时沽酒，那人家？ 
  6 */
  7 #include <set>
  8 #include <map>
  9 #include <cmath>
 10 #include <cstdio>
 11 #include <vector>
 12 #include <cstring>
 13 #include <cstdlib>
 14 #include <iostream>
 15 #include <algorithm>
 16 #define LOCAL
 17 const int MAXL = 20;
 18 const long long MOD = 1000000007;
 19 const int MAXK = 10000 + 10;
 20 const int MAXN = 35000 + 10;
 21 const int MAXM = 35;
 22 const int INF = 0x7fffffff;
 23 using namespace std;
 24 char str[10][10];
 25 int tot, X, Y;//代表棋子的数量 
 26 
 27 void init(){
 28      tot = 0;
 29      for (int i = 1; i <= 4; i++){
 30          scanf("%s", str[i] + 1);
 31          for (int j = 1; j <= 4; j++) if (str[i][j] != '.') tot++;
 32      }
 33      /*for (int i = 1; i <= 4; i++){
 34          for (int j = 1; j <= 4; j++)
 35          printf("%c", str[i][j]);
 36          printf("
");
 37      }*/
 38 }
 39 //判断是否达成胜利条件 
 40 bool check(int x, int y){
 41      int num = 0;//判断棋子的个数 
 42      for (int i = 1;i <= 4; i++){
 43          //注意不要全部判断了 
 44          if (str[x][i] == 'o') num++;
 45          else if (str[x][i] == 'x') num--;
 46      }
 47      if (num == 4 || num == -4) return 1;
 48      num = 0;
 49      for (int i = 1; i <= 4; i++){
 50          if (str[i][y] == 'o') num++;
 51          else if (str[i][y] == 'x') num--;
 52      }
 53      if (num == 4 || num == -4) return 1;
 54      num = 0;
 55      //判断主对角线
 56      for (int i = 1; i <= 4; i++){
 57          if (str[i][i] == 'o') num++;
 58          else if (str[i][i] == 'x') num--;
 59      }
 60      if (num == 4 || num == -4) return 1;
 61      num = 0;
 62      for (int i = 1; i <= 4; i++){
 63          if (str[i][4 - i + 1] == 'o') num++;
 64          else if (str[i][4 - i + 1] == 'x') num--;
 65      }
 66      if (num == 4 || num == -4) return 1;
 67      return 0;
 68 }
 69 int MaxSearch(int x, int y, int alpha);
 70 int MinSearch(int x, int y, int beta);
 71 
 72 int MaxSearch(int x, int y, int alpha){
 73     int Ans = -INF;
 74     //最大获益 
 75     if (check(x, y)) return Ans;
 76     if (tot == 16) return 0;
 77     
 78     for (int i = 1; i <= 4; i++)
 79     for (int j = 1; j <= 4; j++){
 80         if (str[i][j] != '.') continue;
 81         str[i][j] = 'x';tot++;
 82         int tmp = MinSearch(i, j, Ans);
 83         str[i][j] = '.';tot--;
 84         Ans = max(Ans, tmp);
 85         if (Ans >= alpha) return Ans;
 86     }
 87     return Ans;
 88 }
 89 int MinSearch(int x, int y, int beta){
 90     int Ans = INF;
 91     //最小损失 
 92     if (check(x, y)) return Ans;
 93     if (tot == 16) return 0;//平局 
 94     
 95     for (int i = 1; i <= 4; i++)
 96     for (int j = 1; j <= 4; j++){
 97         if (str[i][j] != '.') continue;
 98         str[i][j] = 'o'; tot++;
 99         int tmp = MaxSearch(i, j, Ans);
100         str[i][j] = '.'; tot--;
101         Ans = min(Ans , tmp);
102         if (Ans <= beta) return Ans;
103     }
104     return Ans;
105 }
106 bool dfs(){
107      int beta = -INF;
108      for (int i = 1; i <= 4; i++)
109      for (int j = 1; j <= 4; j++){
110          if (str[i][j] != '.') continue;
111          str[i][j] = 'x'; tot++;
112          int tmp = MinSearch(i, j, beta);
113          str[i][j] = '.'; tot--;
114          beta = max(beta, tmp);
115          if (beta == INF){
116             X = i;Y = j;
117             return 1;
118          }
119      }
120      return 0;
121 }
122 
123 int main () {
124     
125     char ch[2];
126     while (scanf("%s", ch)!= EOF && ch[0] != '$'){
127           init(); 
128           if (dfs()) printf("(%d,%d)
", X - 1, Y - 1);//代表终点坐标
129           else printf("#####
"); 
130     }
131     return 0;
132 }

View Code