Sign in to follow this  
mandar9589

TicTacToe error in alpha beta pruning.

Recommended Posts

mandar9589    100
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;


      }


Share this post


Link to post
Share on other sites
Beyond_Repair    116
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.

Share this post


Link to post
Share on other sites
mandar9589    100
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;
}

Share this post


Link to post
Share on other sites
Beyond_Repair    116
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.

Share this post


Link to post
Share on other sites
mandar9589    100
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[i][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;
}
}

Share this post


Link to post
Share on other sites
Beyond_Repair    116
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.)

Share this post


Link to post
Share on other sites
mandar9589    100
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[i][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]

Share this post


Link to post
Share on other sites
Beyond_Repair    116
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().

Share this post


Link to post
Share on other sites
mandar9589    100
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this