java - 在 Java 中为 Connect 4 实现 Minimax 算法

Question

我正在尝试构建一个带有极小极大(和 alpha beta 修剪)的 Connect 4 游戏，主要是为了向自己证明我可以做到。然而，我遇到的一个大概念问题是如何实际利用极小极大算法。我这样做的方法是，我有一个 AI 类，它有一个函数，即执行返回 int 的极小极大算法。

public int minimax(Board board, int depth, int alpha, int beta, String player) {

    if(depth == 0 || board.getScore() >= 512) {
        return board.getScore();
    }

    else if(player.equals("computer")) {
        int temp = -1000000;
        for(Integer[] moves : board.availableMoves) {
            board.putPiece(player, moves[0]);
            temp = Math.max(temp, minimax(board, depth-1, alpha, beta, "human"));
            board.removePiece(moves[0], moves[1]);
            alpha = Math.max(alpha, temp);
            if (alpha >= beta) {
                break;
            }

        }
        return temp;
    }

    else {
        int temp = 1000000;
        for(Integer[] moves : board.availableMoves) {
            board.putPiece(player, moves[0]);
            temp = Math.min(temp, minimax(board, depth+1, alpha, beta, "computer"));
            board.removePiece(moves[0], moves[1]);
            beta = Math.min(beta, temp);
            if(alpha >= beta) {
                break;
            }
        }
        return temp;
    }
}

这由 Game 类中名为computerMove() 的函数调用。

public int computerMove() {
    Board tempBoard = board;
    int bestMove = 0;
    AI ai = new AI();
    ai.minimax(board, difficulty, -1000000, 1000000, "computer");

    return bestMove;
}

但是，我该如何处理返回的 int 呢？我如何利用它来实际移动棋子？返回的 int 就是我能得到的最好的板子，对吧？它没有告诉我任何关于我应该做什么的位置或板的具体信息。

非常感谢任何和所有帮助。

谢谢

Answer 1

书上都说只返回分数，但这对于实际玩游戏来说是不切实际的。当然，在任何地方维护最佳移动的开销确实会减慢程序的速度，因此通常您使用驱动程序函数来执行第一级扩展，并另外跟踪最佳移动。这有效地将实现包装在 argmax function 中。 ，这只是一种奇特的说法，它返回顶级的最佳 Action 而不是分数。您可以在 a little project I worked on last year 中看到这样的示例。代码是用 C# 编写的，但它与 Java 足够接近，您可以理解。

或者，您可以修改代码以返回包含分数和最佳 Action 的元组(具有多个字段的类)。这比编写 argmax 包装器更容易(而且在我看来更干净)，但如果没有一些额外的工程，这可能会导致 minimax 函数明显减慢，因为它将导致更多的分配。如果性能不是您的首要任务，这可能是您的最佳选择。

我还应该指出，您的实现至少有一个错误。无论谁在玩，深度都应该始终减少，而在人类分支中，您会为人类玩家增加深度。这意味着深度永远不会达到 0，并且只有当玩家被确定为获胜者时才会达到基本情况。此外，在使用 alpha beta 时，重要的是董事会评估知道轮到谁以及谁是最大化玩家，否则您将遇到许多难以发现的错误。您没有在此处显示该代码，但我想指出这一点，因为它每次都让我着迷。