TicTacToe error in alpha beta pruning.

Started by mandar9589 March 30, 2010 09:45 AM

8 comments, last by mandar9589 14 years, 7 months ago

Author

100

March 30, 2010 09:45 AM

This thread is not created to spam or something. How ever I am unable to find solution to this logical mistake. I have programed alpha-beta pruning however, it doesn't make the best possible move. Here is the code: //negamax

 int negamax(boolean xTurn,int depth,int alpha,int beta,char[]legal_moves,char[]board1)
    {
        int eval;
         eval=check_Win();
        if(eval==-1 || depth==0)
            return eval;
        if(legal_moves.length==0)
            return check_Win();
         for (int sq = 0; sq < legal_moves.length; sq++) {
           board1[legal_moves[sq]]=( xTurn ? 'X' : 'O');
            eval = -negamax(!xTurn, depth - 1, -beta, -alpha,legal_moves,board1);
           board1[legal_moves[sq]]=' ';
            if (eval >= beta) {
                return beta;
            }
            if (eval > alpha) {
                alpha = eval;
            }
        }
        return alpha;
    }

//get_Move()

 public int get_Move(boolean turn)
      {
        int alpha = -2;
        int index=0;
        int beta = 2;
        int player;
        if (turn == true)
          {
            player = 1;
          } else
          {
            player = 2;
          }

        int sq;
        int eval = 0;
        int count = 0;
        char board1[] = new char[size * size];

        for (sq = 0; sq < 9; sq++)
          {
            board1[sq] = board[sq / 3][sq % 3];
          }

        for (sq = 0; sq < 9; sq++)
          {
            if (board1[sq] == ' ')
              {
                count++;
              }
          }
        char legal_moves[] = new char[count];

        for (sq = 0; sq < legal_moves.length - 1; sq++)
          {
            board1[legal_moves[sq]] = (turn ? 'X' : 'O');
            eval = -negamax(!turn, maxDepth - 1, -beta, -alpha,legal_moves,board1);

            if (eval > alpha)
              {
                alpha = eval;
              }
             index = sq;
          }

        return index;


      }

Beyond_Repair

116

March 30, 2010 01:21 PM

The code you currently have always returns the last move checked in get_Move. Your indentation is a bit weird, but I think you should put index = sq into between the braces of the if-statement. Alpha represents the best score at that level, so the move which increases alpha must be recorded.

mandar9589

Author

100

March 30, 2010 01:50 PM

Thanks for replying,I rectified it but still didnt work.

[source language="Java"]    public int get_Move(boolean turn)      {        int alpha = -2;        int beta = 2;        int index = 0;        int sq;        int eval = 0;        char board1[] = new char[size * size];        for (sq = 0; sq < 9; sq++)          {            board1[sq] = board[sq / 3][sq % 3];          }               for (sq = 0; sq < 9; sq++)          {            if (board1[sq] == ' ')              {                board1[sq] = (turn ? 'X' : 'O');                eval = -negamax(!turn, maxdepth - 1, -beta, -alpha, board1);                if (eval >alpha)                  {                    alpha = eval;                    index = sq;                  }              }          }        return index;      }    int negamax(boolean xTurn, int depth, int alpha, int beta,            char[] board1)      {        int eval;        eval = check_Win();        System.out.println("eval " + eval);        if ((eval == -1) || (depth == 0))          {            return eval;          }        if (board1[0] != ' ' && board1[1] != ' ' && board1[2] != ' ' && board1[3] != ' ' && board1[4] != ' ' && board1[5] != ' ' && board1[6] != ' ' && board1[7] != ' ' && board1[8] != ' ')          {            return check_Win();          }        for (int sq = 0; sq < 9; sq++)          {            if (board1[sq] == ' ')              {                board1[sq] = (xTurn ? 'X' : 'O');                //          System.out.println(xTurn);                eval = -negamax(!xTurn, depth - 1, -beta, -alpha, board1);                board1[sq] = ' ';                if (eval >= beta)                  {                    return beta;                  }                if (eval > alpha)                  {                    alpha = eval;                  }                              }          }        return alpha;      }

Beyond_Repair

116

March 30, 2010 03:50 PM

if ((eval == -1) || (depth == 0)): It's probably a good idea to add a check for eval == 1 as well... Otherwise you'll be continuing calculations without registering the win (assuming 1 is what represents a win).

If it still doesn't work after this, can you show code of check_Win()? In fact, I just realized it's a bit weird check_Win does not receive board1 as a parameter.....

Some cleaning tips:

For clarity you should replace 1 with WIN_SCORE, -1 with LOSE_SCORE, and initialize starting window accordingly with a MIN_SCORE = LOSE_SCORE - 1 and MAX_SCORE = WIN_SCORE + 1.

Also factor out that huge if in negamax()... Ie.

if (board1[0] != ' ' && board1[1] != ' ' && board1[2] != ' ' && board1[3] != ' ' && board1[4] != ' ' && board1[5] != ' ' && board1[6] != ' ' && board1[7] != ' ' && board1[8] != ' ')          {            return check_Win();          }

into

if (boardFull(board1)) {    return eval;}

And implement boardFull() it with a for loop from 0 to 8.

mandar9589

Author

100

March 31, 2010 04:09 AM

kk, I will do that.
I will post entire code here in this forum.

This class implements interface, how ever, all the things mentioned here is are enough to understand what it is all about.

package consoletictactoe;import java.util.*;public class Game        implements gameProperties    {    int maxdepth = 4;    int i;    int j;    int status = 0;    Scanner read = new Scanner(System.in);    public Game()      {        for (i = 0; i < size; i++)          {            for (j = 0; j < size; j++)              {                board[j] = ' ';              }          }        status = 0;      }    public int check_Win()//Winning Conditions      {        int stat = 0;        //Testing for Horizontal Win        for (int row = 0; row < size; ++row)          {            for (int col = 0; col < size - 2; ++col)              {                if (board[row][col] == board[row][col + 1] && board[row][col] == board[row][col + 2] && board[row][col] != ' ')                  {                    // System.out.println("Horizontal Win");                    stat = -1;                  }              }          }        //Testing for Vertical Win        for (int row = 0; row < size - 2; ++row)          {            for (int col = 0; col < size; ++col)              {                if (board[row][col] == board[row + 1][col] && board[row][col] == board[row + 2][col] && board[row][col] != ' ')                  {                    //System.out.println("Vertical Win");                    stat = -1;                  }              }          }//Testing for positive diagonal win (0,4,8)        for (int row = 0; row < size - 2; ++row)          {            for (int col = 0; col < size - 2; ++col)              {                if (board[row][col] == board[row + 1][col + 1] && board[row][col] == board[row + 2][col + 2] && board[row][col] != ' ')                  {                    //   System.out.println("+ve Diagonal Win");                    stat = -1;                  }              }          }//Testing for negative diagonal win (2,4,6)        for (int row = 2; row < size; ++row)          {            for (int col = 0; col < size - 2; ++col)              {                if (board[row][col] == board[row - 1][col + 1] && board[row - 2][col + 2] == board[row][col] && board[row][col] != ' ')                  {                    //    System.out.println("-ve Diagonal Win");                    stat = -1;                  }              }          }        return stat;      }    public void play()//Main method for handlng of the game.      {        int player = 1;        int no = 1;        int moves = 1;        while (status != -1 && moves < 10)          {            no = player % 2;            switch (no)              {                case 1:                  {                    Computer();                  }                break;                case 0:                    Player2();                    break;              }            status = check_Win();            if (status == -1)              {                System.out.println("Game Over - Player " + player + " Wins ");              }            moves++;            if (moves > 9 && status != -1)              {                System.out.println("Draw");              }            player = 3 - player;            // System.out.println("moves= " + moves);          }      }    public void Display()//Displays the board.      {        System.out.print(board[0][0] + "  | " + board[0][1] + "  | " + board[0][2] + "\n");        System.out.print("---+----+---\n");        System.out.print(board[1][0] + "  | " + board[1][1] + "  | " + board[1][2] + "\n");        System.out.print("---+----+---\n");        System.out.print(board[2][0] + "  | " + board[2][1] + "  | " + board[2][2] + "\n");      }    public void Player1()// Moves of Player 1.      {        int row, column, square;        System.out.println("Make your move PLAYER1, enter the square number,the starting square number is 0");//This is done purposely to show how to conver a 1d array in 2-d array.        square = read.nextInt();        row = square / 3;        column = square % 3;        boolean valid = Condition(row, column);        if (valid == true)          {            if (board[row][column] == ' ')              {                board[row][column] = 'X';              }            System.out.println();            System.out.println();            System.out.println();            System.out.println();            Display();          } else          {            Player1();          }      }    public void Player2()//Moves of Player 2      {        int row, column, square;        System.out.println("Make your move PLAYER2, enter the square number,the starting square number is 0");//This is done purposely to show how to conver a 1d array in 2-d array.        square = read.nextInt();        row = square / 3;        column = square % 3;        boolean valid = Condition(row, column);        if (valid == true)          {            if (board[row][column] == ' ')              {                board[row][column] = '0';              }            System.out.println();            System.out.println();            System.out.println();            System.out.println();            Display();          } else          {            Player2();          }      }    public void Computer()      {        int index;        index = get_Move(true);        board[index / 3][index % 3] = 'X';        Display();      }    public int get_Move(boolean turn)      {        int alpha = -2;        int beta = 2;        int index = 0;        int sq;        int eval = 0;        char board1[] = new char[size * size];        for (sq = 0; sq < 9; sq++)          {            board1[sq] = board[sq / 3][sq % 3];          }               for (sq = 0; sq < 9; sq++)          {            if (board1[sq] == ' ')              {                board1[sq] = (turn ? 'X' : 'O');                eval = -negamax(!turn, maxdepth - 1, -beta, -alpha, board1);                if (eval >alpha)                  {                    alpha = eval;                    index = sq;                  }              }          }        return index;      }    int negamax(boolean xTurn, int depth, int alpha, int beta,            char[] board1)      {        int eval;        eval = check_Win();        System.out.println("eval " + eval);        if ((eval == -1) || (depth == 0))          {            return eval;          }        if (board1[0] != ' ' && board1[1] != ' ' && board1[2] != ' ' && board1[3] != ' ' && board1[4] != ' ' && board1[5] != ' ' && board1[6] != ' ' && board1[7] != ' ' && board1[8] != ' ')          {            return check_Win();          }        for (int sq = 0; sq < 9; sq++)          {            if (board1[sq] == ' ')              {                board1[sq] = (xTurn ? 'X' : 'O');                //          System.out.println(xTurn);                eval = -negamax(!xTurn, depth - 1, -beta, -alpha, board1);                board1[sq] = ' ';                if (eval >= beta)                  {                    return beta;                  }                if (eval > alpha)                  {                    alpha = eval;                  }                              }          }        return alpha;      }    boolean Condition(int row, int column)      {        try          {            if (row > 2 || column > 2)              {                System.out.println("Out of Bounds");              }            if (board[row][column] != ' ')              {                System.out.println("Already Occupied");              } else              {                return true;              }          } catch (Exception e)          {          }        return false;      }    }

Beyond_Repair

116

March 31, 2010 10:27 AM

Ok, ignore what I said about eval == 1, you're right you don't need to check that.

Overall, this is what is weird:

You use this board variable in check_Win(). However, you're sending around and updating board1 in your search! Am I missing something here or are you only checking the original board for wins in your search rather than the actual search node (board1)? This looks extremely suspicious.

That's why I said check_Win() should take board1 as a parameter.

(I can't see declaration of board, I presume it is a static variable in gameInterface.)

mandar9589

Author

100

March 31, 2010 12:19 PM

Thanks. I am posting entire code here. check out.

/*//Interface for all constants. * To change this template, choose Tools | Templates * and open the template in the editor. */package consoletictactoe;/** * * @author Administrator */public interface gameProperties {    int size = 3;    int maxDepth=3;    char board[][] = new char[size][size];    int check_Win();    void play();    void Display();    void Player1();    void Player2();}

//Main body

package consoletictactoe;import java.util.*;public class Game        implements gameProperties    {    int maxdepth = 4;    int i;    int j;    int status = 0;    Scanner read = new Scanner(System.in);    public Game()      {        for (i = 0; i < size; i++)          {            for (j = 0; j < size; j++)              {                board[j] = ' ';              }          }        status = 0;      }    public int check_Win()//Winning Conditions      {        int stat = 0;        //Testing for Horizontal Win        for (int row = 0; row < size; ++row)          {            for (int col = 0; col < size - 2; ++col)              {                if (board[row][col] == board[row][col + 1] && board[row][col] == board[row][col + 2] && board[row][col] != ' ')                  {                    // System.out.println("Horizontal Win");                    stat = -1;                  }              }          }        //Testing for Vertical Win        for (int row = 0; row < size - 2; ++row)          {            for (int col = 0; col < size; ++col)              {                if (board[row][col] == board[row + 1][col] && board[row][col] == board[row + 2][col] && board[row][col] != ' ')                  {                    //System.out.println("Vertical Win");                    stat = -1;                  }              }          }//Testing for positive diagonal win (0,4,8)        for (int row = 0; row < size - 2; ++row)          {            for (int col = 0; col < size - 2; ++col)              {                if (board[row][col] == board[row + 1][col + 1] && board[row][col] == board[row + 2][col + 2] && board[row][col] != ' ')                  {                    //   System.out.println("+ve Diagonal Win");                    stat = -1;                  }              }          }//Testing for negative diagonal win (2,4,6)        for (int row = 2; row < size; ++row)          {            for (int col = 0; col < size - 2; ++col)              {                if (board[row][col] == board[row - 1][col + 1] && board[row - 2][col + 2] == board[row][col] && board[row][col] != ' ')                  {                    //    System.out.println("-ve Diagonal Win");                    stat = -1;                  }              }          }        return stat;      }    public void play()//Main method for handlng of the game.      {        int player = 1;        int no = 1;        int moves = 1;        while (status != -1 && moves < 10)          {            no = player % 2;            switch (no)              {                case 1:                  {                    Computer();                  }                break;                case 0:                    Player2();                    break;              }            status = check_Win();            if (status == -1)              {                System.out.println("Game Over - Player " + player + " Wins ");              }            moves++;            if (moves > 9 && status != -1)              {                System.out.println("Draw");              }            player = 3 - player;            // System.out.println("moves= " + moves);          }      }    public void Display()//Displays the board.      {        System.out.print(board[0][0] + "  | " + board[0][1] + "  | " + board[0][2] + "\n");        System.out.print("---+----+---\n");        System.out.print(board[1][0] + "  | " + board[1][1] + "  | " + board[1][2] + "\n");        System.out.print("---+----+---\n");        System.out.print(board[2][0] + "  | " + board[2][1] + "  | " + board[2][2] + "\n");      }    public void Player1()// Moves of Player 1.      {        int row, column, square;        System.out.println("Make your move PLAYER1, enter the square number,the starting square number is 0");//This is done purposely to show how to conver a 1d array in 2-d array.        square = read.nextInt();        row = square / 3;        column = square % 3;        boolean valid = Condition(row, column);        if (valid == true)          {            if (board[row][column] == ' ')              {                board[row][column] = 'X';              }            System.out.println();            System.out.println();            System.out.println();            System.out.println();            Display();          } else          {            Player1();          }      }    public void Player2()//Moves of Player 2      {        int row, column, square;        System.out.println("Make your move PLAYER2, enter the square number,the starting square number is 0");//This is done purposely to show how to conver a 1d array in 2-d array.        square = read.nextInt();        row = square / 3;        column = square % 3;        boolean valid = Condition(row, column);        if (valid == true)          {            if (board[row][column] == ' ')              {                board[row][column] = '0';              }            System.out.println();            System.out.println();            System.out.println();            System.out.println();            Display();          } else          {            Player2();          }      }    public void Computer()      {        int index;        index = get_Move(true);        board[index / 3][index % 3] = 'X';        Display();      }    public int get_Move(boolean turn)      {        int alpha = -2;        int beta = 2;        int index = 0;        int sq;        int eval = 0;        char board1[] = new char[size * size];        for (sq = 0; sq < 9; sq++)          {            board1[sq] = board[sq / 3][sq % 3];          }        for (sq = 0; sq < 9; sq++)          {            if (board1[sq] == ' ')              {                board1[sq] = (turn ? 'X' : 'O');                eval = -negamax(!turn, maxdepth - 1, -beta, -alpha, board1);                if (eval > alpha)                  {                    alpha = eval;                    index = sq;                  }              }          }        return index;      }    int negamax(boolean xTurn, int depth, int alpha, int beta,            char[] board1)      {        int eval;        eval = check_Win(board1);        //System.out.println("eval " + eval);        if ((eval == -1) || (depth == 0))          {            return eval;          }        if (board1[0] != ' ' && board1[1] != ' ' && board1[2] != ' ' && board1[3] != ' ' && board1[4] != ' ' && board1[5] != ' ' && board1[6] != ' ' && board1[7] != ' ' && board1[8] != ' ')          {            return check_Win(board1);          }        for (int sq = 0; sq < 9; sq++)          {            if (board1[sq] == ' ')              {                board1[sq] = (xTurn ? 'X' : 'O');                eval = -negamax(!xTurn, depth - 1, -beta, -alpha, board1);                board1[sq] = ' ';                if (eval >= beta)                  {                    return beta;                  }                if (eval > alpha)                  {                    alpha = eval;                  }              }          }         System.out.println("stat= " + eval);        return alpha;      }    boolean Condition(int row, int column)      {        try          {            if (row > 2 || column > 2)              {                System.out.println("Out of Bounds");              }            if (board[row][column] != ' ')              {                System.out.println("Already Occupied");              } else              {                return true;              }          } catch (Exception e)          {          }        return false;      }    public int check_Win(char[] board1)      {        int stat = 0;        if (board1[0] == board1[1] && board1[0] == board1[2] && board1[0] != ' ' && board1[1] != ' ' && board1[2] != ' ')          {            stat = -1;          }        if (board1[3] == board1[4] && board1[3] == board1[5] && board1[3] != ' ' && board1[4] != ' ' && board1[5] != ' ')          {            stat = -1;          }        if (board1[6] == board1[7] && board1[6] == board1[8] && board1[6] != ' ' && board1[7] != ' ' && board1[8] != ' ')          {            stat = -1;          }        if (board1[0] == board1[3] && board1[0] == board1[6] && board1[0] != ' ' && board1[3] != ' ' && board1[6] != ' ')          {            stat = -1;          }        if (board1[1] == board1[4] && board1[1] == board1[7] && board1[1] != ' ' && board1[4] != ' ' && board1[7] != ' ')          {            stat = -1;          }        if (board1[2] == board1[5] && board1[2] == board1[8] && board1[2] != ' ' && board1[5] != ' ' && board1[8] != ' ')          {            stat = -1;          }        if (board1[0] == board1[4] && board1[0] == board1[8] && board1[0] != ' ' && board1[4] != ' ' && board1[8] != ' ')          {            stat = -1;          }        if (board1[2] == board1[4] && board1[2] == board1[6] && board1[2] != ' ' && board1[4] != ' ' && board1[6] != ' ')          {            stat = -1;          }                  return stat;      }    }

//Main method()

/* * To change this template, choose Tools | Templates * and open the template in the editor. */package consoletictactoe;public class TicTacToe {    /**     * @param args the command line arguments     */    public static void main(String[] args) {        // TODO code application logic here       for(int x=0;x<25;x++)           System.out.println();        Game g=new Game();        g.Display();        g.play();           }}

No it plays moves but does not care for wining or blocking.

[Edited by - mandar9589 on March 31, 2010 12:19:10 PM]

Beyond_Repair

116

March 31, 2010 01:20 PM

Putting member variables in a java interface means they become static IIRC, GameInterface should probably be a base class...

Anyway, do you understand what I said before? At this point you pretty much have enough info to fix it; make check_Win() depend on the actual search position that is kept updated ('board1' in negamax()) rather than the static variable 'board'. What just currently have just checks for a win on the present board state as opposed to the future states in the search tree.

It's pretty weird to keep a different array structure for the search anyway. I'd suggest just using a plain one dimensional char array for the board all the time instead of keeping one two dimensional array and then suddenly change it to a one dimensional array in get_Move().

mandar9589

Author

100

April 01, 2010 11:52 AM

Hi again, I fully agree to you, however I don't think this hampers any of logical play. The point is I am unable to see where my program is going wrong.
I purposely made that interface as I want to declare all constants and methods used in there.