Java 中的 miniMax 算法

Question

我目前对我正在编写的 AI 不满意。 AI 应该在 3x3 棋盘 (TicTacToe) 中的每一步都获得最高分。

可能的分数是 -1（输）、0（平）和 1（赢）。

首先调用方法 makeTurn()，然后调用包含 miniMax 算法的方法。

public void makeTurn(Button[][] currentBoard) {                                                 // Calculating best move using miniMax algorithm
        AIcheck = new Check(currentBoard);
        int bestScore = Integer.MIN_VALUE;
        int[] bestMove = new int[2];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (currentBoard[i][j].getText().equals("")) {
                    currentBoard[i][j].setText("O");
                    int score = calcScore(currentBoard, 0, false);
                    System.out.println(score);
                    currentBoard[i][j].setText("");
                    if (score > bestScore) {
                        bestScore = score;
                        bestMove = new int[]{i, j};

                    }
                }
            }
        }
        Board.getInstance().getField(bestMove[0], bestMove[1]).performClick();
    }

private int calcScore(Button[][] currentBoard, int depth, boolean isMax) {                      // MiniMax Algorithm, calculating score for each branch via recursive execution
        int score;
        if (AIcheck.checkWin()) {
            return (Util.getInstance().getTurnCounter() % 2) == 0 ? 1 : -1;
        } else if (AIcheck.checkTie()) {
            return 0;
        }
        int bestScore = isMax ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (currentBoard[i][j].getText().equals("")) {
                    if (isMax) {
                        currentBoard[i][j].setText("O");
                    } else {
                        currentBoard[i][j].setText("X");
                    }
                    score = calcScore(currentBoard, depth + 1, !isMax);
                    currentBoard[i][j].setText("");
                    bestScore = isMax ? Math.max(bestScore, score) : Math.min(bestScore, score);
                }
            }
        }
        return bestScore;
    }

我正在使用 isMax 来确定是否轮到最大化者，还使用 turnCounter % 2 来确定轮到哪个玩家，因为他们轮流。

然而 AI 仍然没有阻止我获胜，它更像是从一个领域到下一个领域，而不是选择最佳领域。我怎样才能正确实施 miniMax 算法？非常感谢！

示例：

[]|[]|[]

[X]|[]|[]

[O]|[]|[]

[]|[]|[]

[X]|[]|[]

[O]|[]|[]

[]|[]|[]

[X]|[]|[X]

[O]|[O]|[]

[]|[]|[]

[X]|[]|[X]

[O]|[O]|[X]

[]|[]|[]

[X]|[]|[X]

[O]|[O]|[X]

[O]|[]|[]

[X]|[]|[X]

[O]|[O]|[X]

[O]|[X]|[] 我赢了，这也显示了 AI 似乎只是占据了下一个位置（从左到右）

[X]|[]|[X]

Answer 1

我认为问题出在 calcScore()

中的这一行

if (currentBoard[i][j].getText().equals("")) {

你只在棋盘为空时才计算分数，但在调用函数之前总是将其设置为“0”，因此永远不会执行该 if 的代码块。

makeTurn() 类似，但我猜你是在两回合之间清理棋盘？如果不是，你也需要更新它。

编辑：在主函数中：

                    currentBoard[i][j].setText("O");
                    int score = calcScore(currentBoard, 0, false);

在 calcScore 中：

// this will always evaluate to false
if (currentBoard[i][j].getText().equals("")) {

Answer 2

您的 bestScore 作业有问题。对于每个空框，您都这样做：

int bestScore = isMax ? Integer.MIN_VALUE : Integer.MAX_VALUE;

如果你这样计算，你总是会得到相同的分数，这可能是它只 select 下一个空框的原因。在 minimax 算法中，您需要一种方法为每个动作分配不同的分值，以便您可以通过比较找到最佳动作。在象棋游戏或类似游戏中，这些分数通常是通过一些启发式算法给出的。由于您的游戏要简单得多，因此这应该更容易。一个简单的解决方案可能是为每个棋盘状态分配不同的分数，您可以简单地 select 导致此所需状态的移动。您可以轻松地做到这一点，因为这些状态的数量在您的游戏中非常有限。

Answer 3

我认为问题在于您如何确定谁在 calcScore 中获胜。您使用 Util.getInstance().getTurnCounter()，但您似乎没有在递归调用中更新计数器。您可以改为只使用 depth % 2 或 isMax：

if (AIcheck.checkWin()) {
    return isMax ? -1 : 1;
}

Java 中的 miniMax 算法

miniMax algorithm in Java

java

recursion

artificial-intelligence

tic-tac-toe

minimax