2 views

I am currently trying to teach myself the Minimax algorithm and I have tried to implement it in java in tic tac toe. There is a bug in my algorithm however and I can't figure out what's causing it.

Below is the complete source code (Sorry for the wall of text!):

public class TicTacToe {

private static boolean gameEnded = false;

private static boolean player = true;

private static Scanner in = new Scanner(System.in);

private static Board board = new Board();

public static void main(String[] args){

System.out.println(board);

while(!gameEnded){

Position position = null;

if(player){

position = makeMove();

board = new Board(board, position, PlayerSign.Cross);

}else{

board = findBestMove(board);

}

player = !player;

System.out.println(board);

evaluateGame();

}

}

private static Board findBestMove(Board board) {

ArrayList<Position> positions = board.getFreePositions();

Board bestChild = null;

int previous = Integer.MIN_VALUE;

for(Position p : positions){

Board child = new Board(board, p, PlayerSign.Circle);

int current = max(child);

System.out.println("Child Score: " + current);

if(current > previous){

bestChild = child;

previous = current;

}

}

return bestChild;

}

public static int max(Board board){

GameState gameState = board.getGameState();

if(gameState == GameState.CircleWin)

return 1;

else if(gameState == GameState.CrossWin)

return -1;

else if(gameState == GameState.Draw)

return 0;

ArrayList<Position> positions = board.getFreePositions();

int best = Integer.MIN_VALUE;

for(Position p : positions){

Board b = new Board(board, p, PlayerSign.Cross);

int move = min(b);

if(move > best)

best = move;

}

return best;

}

public static int min(Board board){

GameState gameState = board.getGameState();

if(gameState == GameState.CircleWin)

return 1;

else if(gameState == GameState.CrossWin)

return -1;

else if(gameState == GameState.Draw)

return 0;

ArrayList<Position> positions = board.getFreePositions();

int best = Integer.MAX_VALUE;

for(Position p : positions){

Board b = new Board(board, p, PlayerSign.Circle);

int move = max(b);

if(move < best)

best = move;

}

return best;

}

public static void evaluateGame(){

GameState gameState = board.getGameState();

gameEnded = true;

switch(gameState){

case CrossWin :

System.out.println("Game Over! Cross Won!");

break;

case CircleWin :

System.out.println("Game Over! Circle Won!");

break;

case Draw :

System.out.println("Game Over! Game Drawn!");

break;

default : gameEnded = false;

break;

}

}

public static Position makeMove(){

Position position = null;

while(true){

System.out.print("Select column(x-axis). 0, 1 or 2: ");

int column = getColOrRow();

System.out.print("Select row(y-axis). 0, 1 or 2: ");

int row = getColOrRow();

position = new Position(column, row);

if(board.isMarked(position))

else break;

}

return position;

}

private static int getColOrRow(){

int ret = -1;

while(true){

try{

ret = Integer.parseInt(in.nextLine());

} catch (NumberFormatException e){}

if(ret < 0 | ret > 2)

else break;

}

return ret;

}

}

public enum PlayerSign{

Cross, Circle

}

public enum GameState {

Incomplete, CrossWin, CircleWin, Draw

}

public final class Position {

public final int column;

public final int row;

public Position(int column, int row){

this.column = column;

this.row = row;

}

}

public class Board {

private char[][] board; //e = empty, x = cross, o = circle.

public Board(){

board = new char[3][3];

for(int y = 0; y < 3; y++)

for(int x = 0; x < 3; x++)

board[x][y] = 'e'; //Board initially empty

}

public Board(Board from, Position position, PlayerSign sign){

board = new char[3][3];

for(int y = 0; y < 3; y++)

for(int x = 0; x < 3; x++)

board[x][y] = from.board[x][y];

board[position.column][position.row] = sign==PlayerSign.Cross ? 'x':'o';

}

public ArrayList<Position> getFreePositions(){

ArrayList<Position> retArr = new ArrayList<Position>();

for(int y = 0; y < 3; y++)

for(int x = 0; x < 3; x++)

if(board[x][y] == 'e')

return retArr;

}

public GameState getGameState(){

if(hasWon('x'))

return GameState.CrossWin;

else if(hasWon('o'))

return GameState.CircleWin;

else if(getFreePositions().size() == 0)

return GameState.Draw;

else return GameState.Incomplete;

}

private boolean hasWon(char sign){ //8 ways to win.

if(board[1][1] == sign){

if(board[0][0] == sign && board[2][2] == sign)

return true;

if(board[0][2] == sign && board[2][0] == sign)

return true;

if(board[1][0] == sign && board[1][2] == sign)

return true;

if(board[0][1] == sign && board[2][1] == sign)

return true;

}

if(board[0][0] == sign){

if(board[0][1] == sign && board[0][2] == sign)

return true;

if(board[1][0] == sign && board[2][0] == sign)

return true;

}

if(board[2][2] == sign){

if(board[1][2] == sign && board[0][2] == sign)

return true;

if( board[2][1] == sign && board[2][0] == sign)

return true;

}

return false;

}

public boolean isMarked(Position position){

if(board[position.column][position.row] != 'e')

return true;

return false;

}

public String toString(){

String retString = "\n";

for(int y = 0; y < 3; y++){

for(int x = 0; x < 3; x++){

if(board[x][y] ==  'x' || board[x][y] == 'o')

retString += "["+board[x][y]+"]";

else

retString += "[ ]";

}

retString += "\n";

}

return retString;

}

}

Here is the output when I run the program (Computer is a circle):

[ ][ ][ ]

[ ][ ][ ]

[ ][ ][ ]

Select column(x-axis). 0, 1 or 2: 1

Select row(y-axis). 0, 1 or 2: 1

[ ][ ][ ]

[ ][x][ ]

[ ][ ][ ]

Child Score: 0

Child Score: 0

Child Score: 0

Child Score: 0

Child Score: 0

Child Score: 0

Child Score: 0

Child Score: 0

[o][ ][ ]

[ ][x][ ]

[ ][ ][ ]

Select column(x-axis). 0, 1 or 2: 0

Select row(y-axis). 0, 1 or 2: 1

[o][ ][ ]

[x][x][ ]

[ ][ ][ ]

Child Score: -1

Child Score: 0

Child Score: 0

Child Score: -1

Child Score: -1

Child Score: -1

[o][ ][o]

[x][x][ ]

[ ][ ][ ]

Select column(x-axis). 0, 1 or 2:

As you can see after the first move, the computer thinks that no matter what move it makes it can get a draw (Score = 0).

On the second move, I put a cross on column 0, row 1. For some reason, the computer then thinks that there are two possible moves to reach a draw (Score = 0) and only four moves to lose (Score = -1). It then makes an incorrect move thinking it will get a draw.

I first thought that there was something wrong with the hasWon method, but I have tested all 8 ways of getting three in a row and they all return true.

I suspect that the problem exists somewhere in the findBestMove, max or min methods, but I haven't been able to figure out exactly what is causing it.

I would really appreciate it if someone could tell what is causing the bug or give any suggestions on how to better debug my recursive algorithm.

by (108k points)

Currently, your max returns the value of the worst possible move (for the system) the human could take, instead of the optimal move the computer could take. Furthermore, min returns the value of the worst move the computer could take, instead of the optimal move for the opponent.

You can fix this by changing the PlayerSigns in min and max, and findBestMove should call min function, not max function.

Minimax is a decision rule used in Artificial Intelligence so if you wish to learn more about Minimax Decision Rule then visit this Artificial Intelligence Course.