用Java实现连接4的Minimax算法

Question

我正在尝试用minimax (和alpha beta剪枝)构建一个连接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;
    }
}

这是由一个名为computerMove()的Game函数调用的。

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

书上都说要把分数还回去，但这对玩游戏来说是不切实际的。当然，在任何地方维护最佳移动的开销确实会减缓程序的运行速度，因此通常您会使用驱动程序函数进行第一级扩展，并跟踪最佳移动。这实际上是将实现封装在函数中，这只是一种奇特的方式，可以说它返回的是最高级别的最佳移动，而不是得分。在我去年做的一个小项目中可以看到这方面的一个例子。代码是用C#编写的，但是它与Java非常接近，可以让您了解这个概念。

或者，您可以修改代码以返回具有得分和最佳移动的元组(具有多个字段的类)。这比编写argmax包装器更容易(而且更干净一些)，但是如果没有额外的工程，这可能会导致极小极大函数的一些明显的减速，因为它会导致更多的分配。如果性能不是你最优先考虑的，那么这可能是你要走的路。

我还应该指出，您的实现至少有一个错误。无论是谁在玩，深度应该总是在减少，在你的人类分支中，对于人类玩家来说，它会增加。这意味着深度永远不会达到0，并且只有当一个球员被确定为胜利者时，基本情况才会被击中。另外，当使用alpha beta时，董事会评估必须知道该由谁来做，以及谁是最大的玩家，否则您会遇到很多很难发现的bug。您没有在这里显示代码，但我想指出这一点，因为它每次都让我抓狂。