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 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))
System.out.println("Position already marked!");
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)
System.out.print("\nIllegal input... please re-enter: ");
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')
retArr.add(new Position(x, y));
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 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.