Click here to Skip to main content
15,886,518 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
C++
#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;
}






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.
Posted
Updated 3-Jul-14 21:33pm
v2
Comments
OriginalGriff 4-Jul-14 2:51am    
This is not a good question - we cannot work out from that little what you are trying to do.
Remember that we can't see your screen, access your HDD, or read your mind.

"is not working correctly" is not a problem report. It doesn't tell us anything, particularly.
When isn't it working? How isn't it working? What is it doing that you don't expect or not doing that you do? What is the game state when it fails?
What have you tried? What do you know about the problem? Have you tried the debugger?
And at the moment, this is a code dump - and a bad code dump, given the poor commenting - so cut it down to just the important stuff so we don't have to wade through loads of irrelevant cr@p to find the problem.
Help us to help you!

Use the "Improve question" widget to edit your question and provide better information.
KarstenK 4-Jul-14 5:07am    
Some tips:

make some output in your code so you can figure it out. The return statements are a good place.
you are calling play() recursivly. It is bad style. use while( !won ) {}
int* x=new int[2]; //memory leak

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900