在 Java 中为 Connect 4 实施 Minimax 算法

Question

我正在尝试使用 minimax（和 alpha beta 修剪）构建一个 Connect 4 游戏，主要是为了向自己证明我可以做到。然而，我遇到的一个大的概念性问题是如何实际利用 minimax 算法。我这样做的方法是，我有一个 AI class，它具有一个功能，即执行 minimax 算法，returns 一个 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;
    }
}

这是由名为 computerMove() 的游戏 class 函数调用的。

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

    return bestMove;
}

但是，我该如何处理返回的整数？我如何利用它来实际移动这件作品？返回的 int 只是我能得到的最好的板，对吧？它没有特别告诉我应该做什么的位置或板。

非常感谢任何帮助。

谢谢，

Answer 1

书上都说 return 只是分数，但这对于实际玩游戏来说是不切实际的。当然，到处维护最佳着法的开销确实会减慢程序的速度，因此通常您使用驱动程序函数进行第一级扩展，并另外跟踪最佳着法。这有效地将实现包装在 argmax function, which is just a fancy way of saying it returns the best move at the top level instead of the score. You can see an example of this in a little project I worked on last year 中。代码是用 C# 编写的，但它足够接近 Java 让你理解这个想法。

或者，您可以将代码修改为 return 具有分数和最佳着法的元组（class 具有多个字段）。这比编写 argmax 包装器更容易（并且在 IMO 上更简洁），但是如果没有一些额外的工程，这可能会导致 minimax 函数明显变慢，因为它会导致更多的分配。如果性能不是您的首要任务，这可能是可行的方法。

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

在 Java 中为 Connect 4 实施 Minimax 算法

Implementing a Minimax Algorithm in Java for Connect 4

java

artificial-intelligence

minimax