Bug in Minimax Algorithm for Tic Tac Toe

Question

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.

Answer 1

Looks to me like you mixed up parts of min and max. Currently, your max returns the value of the worst possible move (for him) the human could take, instead of the optimal move the computer could take. Likewise, min returns the value of the worst move the computer could take, instead of the optimal move for the opponent.

Fix this by switching the PlayerSigns in min and max, and findBestMove should call min, not max.