Java Tic-Tac-Toe minimax 算法无法正常工作

Question

我正在尝试使用极小极大搜索算法为 tic-tac-toe 游戏实现“HARD”难度级别。

它有一个问题，我正在努力寻找这个问题，因为算法没有选择最佳的移动，并且几乎是随机的。

以下是计算机类的代码

    private Cell hard() {
    Cell[][] boardCopy = game.getBoard().clone();
    int bestScore = Integer.MIN_VALUE;
    Cell bestMove = null;

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            Cell currentCell = boardCopy[i][j];
            if (currentCell.isFree()) {
                currentCell.setSymbol(getSymbol()); // place marker
                int score = minimax(boardCopy, 0, true);
                currentCell.setSymbol('_'); // remove marker

                
                if (score > bestScore) {  //! This only gets updated once... why?
                    bestScore = score;
                    bestMove = currentCell;
                }
            }
        }
    }

    // Cell X, Y has a score of Z, and total depth of ...;
    System.out.printf("Best move: (%d, %d)\n", bestMove.getX(), bestMove.getY());
    return bestMove;
}

private int minimax(Cell[][] board, int depth, boolean isMaximising) {
    
    // are we at terminal state?
    char winner = game.checkWinner(board);
    
    if (winner != 'R') {    // R = still running
        if (winner == getSymbol()) {    // ai is winner
            return 10 - depth;
        }
        if (winner == getOpponent()) {  // opponent is winner
            return -10 + depth;
        }
        return 0; // draw
    }

    if (isMaximising) {
        int bestScore = Integer.MIN_VALUE;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                Cell currentCell = board[i][j];
                if (currentCell.isFree()) {
                    currentCell.setSymbol(getSymbol());
                    bestScore = Math.max(bestScore, minimax(board, depth + 1, false));
                    currentCell.setSymbol('_'); // reset cell
                }
            }
        }
        return bestScore;
    } else {
        int bestScore = Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                Cell currentCell = board[i][j];
                if (currentCell.isFree()) {
                    currentCell.setSymbol(getOpponent());
                    bestScore = Math.min(bestScore, minimax(board, depth + 1, true));
                    currentCell.setSymbol('_'); // reset cell
                }
            }
        }
        return bestScore;
    }
}

该算法检查当前状态是否为最终状态，即

game.checkWinner(board)

返回“D”（平局）、“X”（X 获胜）和“O”（O 获胜），如果是，则返回该状态的分数。

可能的分数是：

     win current player (max) =  10 - depth
     win opponent (min)       =  -10 + depth
     draw                     =  0

我了解算法应该如何表现，但我遗漏了一些东西，并且我的人工智能代码无法正常工作。我很感激任何提示，因为我已经为此绞尽脑汁了几个小时，并且在解决此问题之前无法正常工作:(

完整的代码可以在我的github上找到：https://github.com/mac0201/TicTacToeTemp/tree/main/tictactoe

Answer 1

这个问题已经解决了。事实证明，将

true

传递到

minimax()

内的

hard()

是问题所在，并通过传递

false

来解决。