如何使用Alpha Beta修剪来纠正这个井字游戏程序 [英] How Can I Correct This Tic-Tac-Toe Program Using Alpha Beta Pruning

问题描述

#include<iostream>
using namespace std;
enum player{
    comp,user
};

void print();
char grid[3][3]={{' ',' ',' '},{' ',' ',' '},{' ',' ',' '}};
int evaluateLine(int,int,int,int,int,int,int);
int evaluate(int);
void move(int*);
void minimax(int,int,int,int,int*);
bool has_won();
void play(int);
bool IsFull(){//tests if there is no empty cell in the grid
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(grid[i][j]==' ')
                return false;
        }
    }
    return true;
}
int main(){
    play(user);
}
void print(){//prints the current state of the grid on console
        for(int i=0;i<3;i++){
        for(int j=0;j<3;j++)
            cout<<grid[i][j]<< "  |  ";
        cout<<"\n --   --   --  \n";
    }
}
void play(int player)
{
    int x,y;
    if(player==user){
        cout<<"Enter your move\n";
        cin>>x>>y;
        if(grid[x-1][y-1]!=' '){
            cout<<"enter a valid move\n";
            play(player);
        }
        grid[x-1][y-1]='X';
        print();
        if(has_won())
            exit(0);
        else
            play(comp);
    }
    else{//comp uses move method to determine next best move
        int* x=new int[2];
        x[0]=0;
        x[1]=0;
        move(x);
        cout<<x[0]<<x[1]<<endl;
        grid[x[0]][x[1]]='0';
        print();
        if(has_won())
            exit(0);
        else
            play(user);
    }
}
bool has_won()//checks if any one of the players-comp,user has won
{
    char win=' ';
      for (int i = 0; i <3; i++) {
         if(grid[i][0]==grid[i][1] && grid[i][1]==grid[i][2])
           {
                win=grid[i][1];
                break;
           }
         else if(grid[0][i]==grid[1][i] && grid[1][i]==grid[2][i]){
            win=grid[0][i];
            break;
         }
      }
      if(grid[1][1]==grid[0][0] && grid[1][1]==grid[2][2])
        win=grid[0][0];
      else if(grid[0][2]==grid[1][1] && grid[1][1]==grid[2][0])
        win=grid[1][1];
      if(win==' ')
       return false;
      if(win=='0'){
          cout<<"You lost\n";
          return true;
      }
      if(win=='X'){
          cout<<"You win\n";
          return true;
      }

}
void move(int* x){//minimax function returns row and col for next move of comp
    int z[]={0,0,0};
    int alpha=-1000,beta=1000;
    minimax(3,comp,alpha,beta,z);//3 is the depth upto which comp checks possible grid
    x[0]=z[1];                   //states to make best move
    x[1]=z[2];
}
void minimax(int level,int player,int alpha,int beta,int* x)
{
    int score=0;
    int row=-1,col=-1;
    if(level==0){
        score=evaluate(comp)-evaluate(user);
    }else{
        int count=0;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(grid[i][j]==' '){//check all empty cells for player's next move
                    count++;
                    if(player==0){//maximising player(comp)
                        grid[i][j]='0';
                        score=alpha;
                        minimax(level-1,1-player,score,beta,x);
                        int v=x[0];
                        if(level==1)
                            cout<<v<<endl<<i<<j<<endl;
                        if(v>=score){
                            score=v;
                            row=i;
                            col=j;
                        }
                        if(score>=beta){
                            i=3;
                            j=3;
                        }

                    }
                    else if(player==1){//minimising player-user
                        grid[i][j]='X';
                        score=beta;
                        minimax(level-1,1-player,alpha,score,x);
                        int v=x[0];
                        if(v<=score){
                            score=v;
                            row=i;
                            col=j;
                        }
                        if(score<=alpha){
                            i=3;
                            j=3;
                        }

                    }
                    grid[i][j]=' ';
                }
            }
        }
       if(count==0){
           score=evaluate(comp)-evaluate(user);
        }
    }
   // cout<<score<<row<<col<<endl;
    x[0]=score;
    x[1]=row;
    x[2]=col;
}
int evaluate(int player)
{
     int score = 0;
      // Evaluate score for each of the 8 lines (3 rows, 3 columns, 2 diagonals)
      //score is 1 if player has a possible path to win in a row(in future)
      //score is 0 if both player and opponent can't win in a row
      //score is 1000 if player wins in a row
      //score is -1000 if opponent wins in a row
      score += evaluateLine(0, 0, 0, 1, 0, 2,player);  // row 0
      score += evaluateLine(1, 0, 1, 1, 1, 2,player);  // row 1
      score += evaluateLine(2, 0, 2, 1, 2, 2,player);  // row 2
      score += evaluateLine(0, 0, 1, 0, 2, 0,player);  // col 0
      score += evaluateLine(0, 1, 1, 1, 2, 1,player);  // col 1
      score += evaluateLine(0, 2, 1, 2, 2, 2,player);  // col 2
      score += evaluateLine(0, 0, 1, 1, 2, 2,player);  // diagonal
      score += evaluateLine(0, 2, 1, 1, 2, 0,player);  // alternate diagonal
      return score;
}
int evaluateLine(int row1,int col1,int row2,int col2,int row3,int col3,int player)
{
    char o;//opponent
    char p;//player
     if(player==0){
        p='0';
        o='X';
        }
     else{
        o='0';
        p='X';
        }
     int score=0;
     if (grid[row1][col1] == p) {
         score = 1;
      } else if (grid[row1][col1] == o) {
         score = -1;
      }

      // Second cell
      if (grid[row2][col2]  == p) {
         if (score == 1) {   // cell1 is p
            score = 10;
         } else if (score == -1) {  // cell1 is o
            return 0;
         } else {  // cell1 is empty
            score = 1;
         }
      } else if (grid[row2][col2]  == o) {
         if (score == -1) { // cell1 is o
            score = -10;
         } else if (score == 1) { // cell1 is p
            return 0;
         } else {  // cell1 is empty
            score = -1;
         }
      }

      // Third cell
      if (grid[row3][col3]  == p) {
         if (score > 0) {  // cell1 and/or cell2 is p
            score *= 10;
         } else if (score < 0) {  // cell1 and/or cell2 is o
            return 0;
         } else {  // cell1 and cell2 are empty
            score = 1;
         }
      } else if (grid[row3][col3]  == o) {
         if (score < 0) {  // cell1 and/or cell2 is o
            score *= 10;
         } else if (score > 1) {  // cell1 and/or cell2 is p
            return 0;
         } else {  // cell1 and cell2 are empty
            score = -1;
         }
      }
      if(score==-1000)
        return score;
      else if(score==1000)
        return score;
      else if(score>=0)
        return 1;
      else
        return 0;
}

这是我为使用alpha beta修剪的3x3 Tic Tac Toe游戏编写的一个程序。每次它的动作都会移动它从网格中选择最后一个空单元格。我甚至尝试过将alpha beta修剪更改为简单的minimax，但它也有同样的问题。请帮我找到我的解决方案的问题。

谢谢。

This is a program i wrote for a 3x3 Tic Tac Toe game using alpha beta pruning.Every time its comp's turn to make a move it selects last empty cell from the grid.I have tried even changing alpha beta pruning to simple minimax,but it also has the same problem.Please help me to find the problem with my solution.
Thanks.

推荐答案

这篇关于如何使用Alpha Beta修剪来纠正这个井字游戏程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！