Search code examples
javatic-tac-toeminimax

Minimax Algorithm behaving unexpectedly


I am trying to implement the Minimax algorithm for Tic Tac Toe, and just can't seem to get it run correctly. I have tried re-writing it several times, but it is not giving correct output.

Here is the code for MinimaxGame.java, that implements the game-

public class MinimaxGame {
    public MinimaxResult play(MinimaxBoard board)   {
        ArrayList<Position> possibleMoves = board.getAllPossibleMoves();
        MinimaxBoard bestChild = null;
        int bestScore= Integer.MIN_VALUE;

        for (Position position : possibleMoves) {
            MinimaxBoard child = new MinimaxBoard((MinimaxBoard)board.clone(), position, 'O');
            int moveScore = max(child);

            if (moveScore > bestScore)  {
                bestChild = child;
                bestScore = moveScore;
            }
        }

        MinimaxResult result = new MinimaxResult(bestChild, bestScore);
        return result;
    }

    private int max(MinimaxBoard child) {
        ArrayList<Position> possibleMoves = child.getAllPossibleMoves();
        if (possibleMoves.isEmpty())    {
            int score = evaluateScore(child);
            return score;
        }

        int bestScore = Integer.MIN_VALUE;
        for (Position position : possibleMoves) {
            MinimaxBoard currentChild = new MinimaxBoard((MinimaxBoard)child.clone(), position, 'X');
            int moveScore = min(currentChild);

            if (moveScore > bestScore ) {
                bestScore = moveScore;
            }
        }

        return bestScore;
    }

    private int min(MinimaxBoard child) {
        ArrayList<Position> possibleMoves = child.getAllPossibleMoves();
        if (possibleMoves.isEmpty())    {
            int score = evaluateScore(child);
            return score;
        }

        int bestScore = Integer.MAX_VALUE;
        for (Position position : possibleMoves) {
            MinimaxBoard currentChild = new MinimaxBoard((MinimaxBoard)child.clone(), position, 'O');
            int moveScore = max(currentChild);

            if (moveScore < bestScore ) {
                bestScore = moveScore;
            }
        }

        return bestScore;
    }

    private boolean hasWon(MinimaxBoard board, char player) {
        boolean status = false;
        char [][] boardArray = board.boardArray;

        // Check rows
        for (int i = 0; i < 3; i++) {
            status |= (boardArray[i][0] == player) && (boardArray[i][1] == player) && (boardArray[i][2] == player);
            if (status) {
                return true;
            }
        }

        // Check columns
        for (int i = 0; i < 3; i++) {
            status |= (boardArray[0][i] == player) && (boardArray[1][i] == player) && (boardArray[2][i] == player);
            if (status) {
                return true;
            }
        }

        // Check left diagonal
        status |= (boardArray[0][0] == player) && (boardArray[1][1] == player) && (boardArray[2][2] == player);
        if (status) {
            return true;
        }

        // Check right diagonal
        status |= (boardArray[0][2] == player) && (boardArray[1][1] == player) && (boardArray[2][0] == player);
        if (status) {
            return true;
        }

        return false;
    }


    // The function simply returns a score of +1 if computer wins, -1 if the user wins,
    // and 0 in case of a draw.
    private int evaluateScore(MinimaxBoard board)   {
        if (hasWon(board, 'X')) {
            return -1;
        }
        else if (hasWon(board, 'O'))    {
            return 1;
        }

        return 0;
    }

    // Main method included for debugging purposes
    public static void main(String args[])  {
        Board sampleBoard = new Board();
        sampleBoard.setState("----X----");
        MinimaxBoard minimaxBoard = new MinimaxBoard(sampleBoard);

        MinimaxGame game = new MinimaxGame();
        MinimaxResult result = game.play(minimaxBoard);

        Board updatedBoard = result.getUpdatedBoard().getBoard();
        System.out.println(updatedBoard.getState());
    }
}

As is evident, I am trying to execute it with this initial string-

"----X----"

And the output which I am getting is this-

"OOOOXOOOO"

Instead of responding with the most optimal move, it is behaving in this super strange way and putting an 'O' at every empty location. I have tried debugging the code, but I still don't know what's going wrong with the code. I simply can't figure out where is the problem arising.

Can somebody help me out? Thanks in advance.

EDIT-

Here is the code for MinimaxBoard.java, in which I have implemented the clone() method as well. But still, the ouput is the same. Can anybody tell me why?

public class MinimaxBoard implements Cloneable {
public char[][] boardArray;

public MinimaxBoard(Board board)    {
    boardArray = convertBoardTo2D(board.getState());
}

public MinimaxBoard(MinimaxBoard board, Position position, char player) {
    this.boardArray = board.boardArray;
    boardArray[position.row][position.coloumn] = player;
}

public Board getBoard() {
    Board board = new Board();

    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < boardArray.length; i++) {
        builder.append(String.valueOf(boardArray[i]));
    }

    board.setState(builder.toString());
    return board;
}

public char[][] convertBoardTo2D(String boardString)    {
    char[][] boardArray = new char[3][3];
    char[] chars = boardString.toCharArray();
    if (chars.length == 9) {
      for (int i = 0; i < chars.length; i++) {
        boardArray[i/3][i%3] = chars[i];
      }
    }

    return boardArray;
}

public ArrayList<Position> getAllPossibleMoves() {
    ArrayList<Position> allMoves = new ArrayList<Position>();

    for(int i = 0; i < 3; i++)  {
        for(int j = 0; j < 3; j++)  {
            if(boardArray[i][j] == '-') {
                allMoves.add(new Position(i, j));
            }
        }
    }

    return allMoves;
}

@Override
public Object clone()   {
    try {
        return (MinimaxBoard)super.clone();
    }
    catch(CloneNotSupportedException e) {
        return null;
    }
}

}

Solution

  • I think you must clone your board. In your's case you set '0' at all possible position

    MinimaxBoard child = new MinimaxBoard(board, position, 'O');
    

    you must change to

    MinimaxBoard child = new MinimaxBoard(board.clone(), position, 'O');
    

    and implement clone() method in your Board class

    Example of clone implementation:

    @Override
    public Object clone()   {
        try {
            MinimaxBoard cloned = (MinimaxBoard)super.clone();
            cloned.boardArray = (char[][])boardArray.clone();
            for(int row=0; row< cloned.boardArray.length;row++)
                cloned.boardArray[row] = (char[])boardArray[row].clone();
            return cloned;
        }
       catch(CloneNotSupportedException e) {
            return null;
        }
    }
    
    }