题解：UVA10111 Find the Winning Move

Lacuna · 2025-05-11 19:35:06 · 题解

思路：

爆搜肯定不行，考虑 Minimax 加 Alpha-Beta 剪枝。不会的可以看这里。

我们通过 Minimax 算法模拟两名玩家交替下棋的过程，枚举可供落子的点，落子后继续搜索之后的状态，直到出现以下情况：

某一方获胜，此时返回一个状态，例如我方获胜返回 1，敌方获胜返回 -1。我方获胜的返回值需大于敌方获胜的返回值，因为后面的 Alpha-Beta 剪枝要用。
棋盘填满，此时返回 0。返回的值介于两者中间。

再设一个可能达到的最大下界，用 alpha 表示，同理设一个可能达到的最小上界，用 beta 表示，当 alpha \ge beta 时，就可以将剩下的状态减掉。因为我们不可能在搜到比这更优的方案。仔细观察发现这里的 alpha 和 beta 其实就是我们设的那三种状态，按对我方的有利程度从大到小排序。

最开始时我们枚举一个我方落子的点，若能获胜直接返回坐标，否则跑 Minimax 搜索去评估在这个点落子的优劣性，若返回值等于 1，说明我方有必胜策略，返回该点坐标。

否则输出无解。

实现细节：

棋盘落子需改变棋盘的状态，为了方便，我们用临时数组存储落子后棋盘的状态，搜索时当做参数传进去即可。

代码，可以看看注释：

#include<bits/stdc++.h>
using namespace std;
#define gc getchar
template<typename T>inline void read(T&x){x=0;char ch=gc();while(ch<'0'||ch>'9')ch=gc();while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}}
template<typename T,typename ...T1>inline void read(T&x,T1&...x1){read(x);read(x1...);}
const int ri=105;
struct node{int x,y; node(int l=-1,int r=-1):x(l),y(r){}};//结构体存坐标 
char T[ri][ri]; string s,a[ri]; int tot;
bool check(char E[ri][ri],char player){//判断player这方是否获胜 
  for(int i=0;i<4;i++){
    if(E[i][0]==player&&E[i][1]==E[i][2]&&E[i][2]==E[i][3]&&E[i][0]==E[i][1])
      return true;
  }
  for(int i=0;i<4;i++){
    if(E[0][i]==player&&E[1][i]==E[2][i]&&E[2][i]==E[3][i]&&E[0][i]==E[1][i])
      return true;
  }
  if(E[1][1]==player&&E[2][2]==player&&E[3][3]==player&&E[0][0]==player)
    return true;
  if(E[0][3]==player&&E[1][2]==player&&E[2][1]==player&&E[3][0]==player)
    return true;
  return false;
}bool full(char E[ri][ri]){//判断棋盘是否被填满，即平局 
  for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(E[i][j]=='.') return false;
  return true;
}int alpha_beta(char Y[ri][ri],int alpha,int beta,bool ismax){//Minimax搜索+Alpha-Beta剪枝 
  if(check(Y,'x')) return 1;//我方获胜 
  if(check(Y,'o')) return -1;//敌方获胜 
  if(full(Y)) return 0;//平局 
  if(ismax){//取最优值，即我方落子 
    int mx=-0x3f3f3f3f;
    for(int i=0;i<4;i++){//枚举可以落子的点 
      for(int j=0;j<4;j++){
        if(Y[i][j]=='.'){
          char T[ri][ri];
          for(int x=0;x<4;x++) for(int y=0;y<4;y++) T[x][y]=Y[x][y];
          T[i][j]='x'; int tmp=alpha_beta(T,alpha,beta,false);
          mx=max(mx,tmp); alpha=max(alpha,tmp);//更新，取最优值 
          if(beta<=alpha) break;//Alpha-Beta剪枝 
        }
      }
      if(beta<=alpha) break;
    }
    return mx;
  }else{////取最劣值，即敌方落子 
    int mi=0x3f3f3f3f;
    for(int i=0;i<4;i++){//同理，枚举可以落子的点 
      for(int j=0;j<4;j++){
        if(Y[i][j]=='.'){
          char T[ri][ri];
          for(int x=0;x<4;x++) for(int y=0;y<4;y++) T[x][y]=Y[x][y];
          T[i][j]='o'; int tmp=alpha_beta(T,alpha,beta,true); 
          mi=min(mi,tmp); beta=min(beta,tmp);//更新，取最劣值 
          if(beta<=alpha) break;
        }
      }
      if(beta<=alpha) break;
    }
    return mi;
  }
}node move(char E[ri][ri]){
  for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
      if(E[i][j]=='.'){//枚举可以落子的点 
        char T[ri][ri];
        for(int x=0;x<4;x++) for(int y=0;y<4;y++) T[x][y]=E[x][y];
        T[i][j]='x'; if(check(T,'x')) return node(i,j);//直接获胜 
        if(alpha_beta(T,-0x3f3f3f3f,0x3f3f3f3f,false)==1)  return node(i,j);//有必胜策略 
      }
    }
  }
  return node();//没有必胜策略 
}
int main(){
  while(getline(cin,s)&&s!="$") a[++tot]=s;
  for(int i=1;i<=tot; ){
    if(a[i]=="?"){
      i++; char T[ri][ri];//临时存棋盘 
      for(int x=0;x<4;x++,i++) for(int y=0;y<4;y++) T[x][y]=a[i][y];
      node mov=move(T);
      if(mov.y==-1) puts("#####");
      else printf("(%d,%d)\n",mov.x,mov.y);
    }else i++;
  }
  return 0;
}