使用最小最大值和Alpha-Beta修剪寻找最佳移动

Question

我正在为游戏开发AI，我想使用MinMax算法和Alpha-Beta修剪。

我对它的工作原理有一个粗略的想法，但我仍然无法从头开始编写代码，所以我花了最近两天的时间在网上寻找某种伪代码。

我的问题是，我在网上找到的每个伪代码似乎都是基于找到最佳移动的值，而我需要返回最佳移动本身而不是数字。

我现在的代码是基于这个伪代码（源代码）

minimax(level, player, alpha, beta){  // player may be "computer" or "opponent"
    if (gameover || level == 0)
       return score
    children = all valid moves for this "player"
    if (player is computer, i.e., max's turn){
       // Find max and store in alpha
       for each child {
          score = minimax(level - 1, opponent, alpha, beta)
          if (score > alpha) alpha = score
          if (alpha >= beta) break;  // beta cut-off
       }
       return alpha
    } else (player is opponent, i.e., min's turn)
       // Find min and store in beta
       for each child {
          score = minimax(level - 1, computer, alpha, beta)
          if (score < beta) beta = score
          if (alpha >= beta) break;  // alpha cut-off
       }
       return beta
    }
}

// Initial call with alpha=-inf and beta=inf
minimax(2, computer, -inf, +inf)

如您所见，这段代码返回一个数字，我想这是使一切正常工作所必需的（因为在递归期间使用了返回的数字）。

所以我认为我可以使用外部变量来存储最佳移动，这就是我更改之前代码的方式：

minimax(level, player, alpha, beta){  // player may be "computer" or "opponent"
    if (gameover || level == 0)
       return score
    children = all valid moves for this "player"
    if (player is computer, i.e., max's turn){
       // Find max and store in alpha
       for each child {
          score = minimax(level - 1, opponent, alpha, beta)
          if (score > alpha) {
              alpha = score
              bestMove = current child // ROW THAT I ADDED TO UPDATE THE BEST MOVE
          }
          if (alpha >= beta) break;  // beta cut-off
       }
       return alpha
    } else (player is opponent, i.e., min's turn)
       // Find min and store in beta
       for each child {
          score = minimax(level - 1, computer, alpha, beta)
          if (score < beta) beta = score
          if (alpha >= beta) break;  // alpha cut-off
       }
       return beta
    }
}

// Initial call with alpha=-inf and beta=inf
minimax(2, computer, -inf, +inf)

现在，这对我来说就是这样有意义的，因为只有轮到玩家并且该动作比前一个更好时，我们才需要更新最佳移动。

因此，虽然我认为这个是正确的(即使我不是100%确定)，源代码也有一个java实现，它甚至在< code >分数中更新< code>bestMove

尝试使用该实现导致我的代码从对方玩家中选择一个移动作为最佳移动，这似乎不正确（假设我是黑人玩家，我正在寻找我能做出的最佳移动，所以我期待的是“黑色”移动，而不是“白色”移动）。

我不知道我的伪代码（第二个）是否是使用带有alpha beta修剪的MinMax找到最佳移动的正确方法，或者我是否需要更新最佳移动，即使在分数中

如果您愿意，请随时建议任何新的更好的伪代码，我不受任何约束，如果它比我的好，我不介意重写一些代码。

编辑：

由于我无法理解答案，我想也许这个问题并没有问我想知道什么，所以我想在这里写得更好。

假设我只想为一个玩家获得最佳移动，并且每次我需要新移动时，该玩家（最大化器）都会传递给 MinMax 函数（因此 minmax（2， 黑色， a， b） 返回黑色玩家的最佳移动，而 minmax（2， 白色， a ，b） 返回白人玩家的最佳移动）， 您将如何更改第一个伪代码（或源代码中的 Java 实现）以将此给定的最佳移动存储在某个地方？

编辑2：

让我们看看是否可以这样做。

这是我的实现，你能告诉我它是否正确吗？

//PlayerType is an enum with just White and Black values, opponent() returns the opposite player type
protected int minMax(int alpha, int beta, int maxDepth, PlayerType player) {        
    if (!canContinue()) {
        return 0;
    }
    ArrayList<Move> moves = sortMoves(generateLegalMoves(player));
    Iterator<Move> movesIterator = moves.iterator();
    int value = 0;
    boolean isMaximizer = (player.equals(playerType)); // playerType is the player used by the AI        
    if (maxDepth == 0 || board.isGameOver()) {
        value = evaluateBoard();
        return value;
    }
    while (movesIterator.hasNext()) {
        Move currentMove = movesIterator.next();
        board.applyMove(currentMove);
        value = minMax(alpha, beta, maxDepth - 1, player.opponent());
        board.undoLastMove();
        if (isMaximizer) {
            if (value > alpha) {
                selectedMove = currentMove;
                alpha = value;
            }
        } else {
            if (value < beta) {
                beta = value;
            }
        }
        if (alpha >= beta) {
            break;
        }
    }
    return (isMaximizer) ? alpha : beta;
}

编辑3：

基于@Codor的答案/评论的新实现

private class MoveValue {
    public Move move;
    public int value;

    public MoveValue() {
        move = null;
        value = 0;
    }

    public MoveValue(Move move, int value) {
        this.move = move;
        this.value = value;
    }

    @Override
    public String toString() {
        return "MoveValue{" + "move=" + move + ", value=" + value + '}';
    }

}

protected MoveValue minMax(int alpha, int beta, int maxDepth, PlayerType player) {
    if (!canContinue()) {
        return new MoveValue();
    }
    ArrayList<Move> moves = sortMoves(generateLegalMoves(player));
    Iterator<Move> movesIterator = moves.iterator();
    MoveValue moveValue = new MoveValue();
    boolean isMaximizer = (player.equals(playerType));
    if (maxDepth == 0 || board.isGameOver()) {            
        moveValue.value = evaluateBoard();
        return moveValue;
    }
    while (movesIterator.hasNext()) {
        Move currentMove = movesIterator.next();
        board.applyMove(currentMove);
        moveValue = minMax(alpha, beta, maxDepth - 1, player.opponent());
        board.undoLastMove();
        if (isMaximizer) {
            if (moveValue.value > alpha) {
                selectedMove = currentMove;
                alpha = moveValue.value;
            }
        } else {
            if (moveValue.value < beta) {
                beta = moveValue.value;
                selectedMove = currentMove;
            }
        }
        if (alpha >= beta) {
            break;
        }
    }
    return (isMaximizer) ? new MoveValue(selectedMove, alpha) : new MoveValue(selectedMove, beta);
}

我不知道我是做对了还是做错了什么，但我又回到了我发布问题时的问题：

调用minMax（Integer.MIN_VALUE，Integer_MAX_VALU，1，PlayerType.Black）返回只能由白人玩家完成的移动，这不是我需要的。

我需要对给定玩家的最佳动作，而不是对整个棋盘的最佳动作。

Answer 1

这有点困难，因为给定的代码不是实际的 Java 实现;为了实现您想要的目标，必须有具体的类型来表示游戏树中的移动和位置。通常，游戏树不是显式编码的，而是以稀疏表示形式导航的，其中实现将实际执行有问题的移动，递归评估生成的较小问题并撤消移动，从而使用深度优先搜索通过使用调用堆栈来表示当前路径。

要获得实际的最佳移动，只需从您的html" target="_blank">方法中返回最大化后续评估的实例。首先在没有alpha-beta-pruning的情况下实现最小值算法可能会有所帮助，该算法是在基本结构工作后的后续步骤中添加的。

问题中的链接(第1.5节)的实现实际上返回了最佳的移动，如下面的注释所示。

/** Recursive minimax at level of depth for either
    maximizing or minimizing player.
    Return int[3] of {score, row, col}  */

此处没有使用用户定义的类型来表示移动，但该方法返回三个值，它们是评估的最佳分数和玩家将移动到以实际执行最佳移动的坐标（实现已经这样做以获取分数），它们是实际移动的表示。

Answer 2

在做了一些研究并浪费了大量时间来解决这个问题之后，我想出了这个似乎可行的解决方案。

private class MoveValue {

    public double returnValue;
    public Move returnMove;

    public MoveValue() {
        returnValue = 0;
    }

    public MoveValue(double returnValue) {
        this.returnValue = returnValue;
    }

    public MoveValue(double returnValue, Move returnMove) {
        this.returnValue = returnValue;
        this.returnMove = returnMove;
    }

}


protected MoveValue minMax(double alpha, double beta, int maxDepth, MarbleType player) {       
    if (!canContinue()) {
        return new MoveValue();
    }        
    ArrayList<Move> moves = sortMoves(generateLegalMoves(player));
    Iterator<Move> movesIterator = moves.iterator();
    double value = 0;
    boolean isMaximizer = (player.equals(playerType)); 
    if (maxDepth == 0 || board.isGameOver()) {            
        value = evaluateBoard();            
        return new MoveValue(value);
    }
    MoveValue returnMove;
    MoveValue bestMove = null;
    if (isMaximizer) {           
        while (movesIterator.hasNext()) {
            Move currentMove = movesIterator.next();
            board.applyMove(currentMove);
            returnMove = minMax(alpha, beta, maxDepth - 1, player.opponent());
            board.undoLastMove();
            if ((bestMove == null) || (bestMove.returnValue < returnMove.returnValue)) {
                bestMove = returnMove;
                bestMove.returnMove = currentMove;
            }
            if (returnMove.returnValue > alpha) {
                alpha = returnMove.returnValue;
                bestMove = returnMove;
            }
            if (beta <= alpha) {
                bestMove.returnValue = beta;
                bestMove.returnMove = null;
                return bestMove; // pruning
            }
        }
        return bestMove;
    } else {
        while (movesIterator.hasNext()) {
            Move currentMove = movesIterator.next();
            board.applyMove(currentMove);
            returnMove = minMax(alpha, beta, maxDepth - 1, player.opponent());
            board.undoLastMove();
            if ((bestMove == null) || (bestMove.returnValue > returnMove.returnValue)) {
                bestMove = returnMove;
                bestMove.returnMove = currentMove;
            }
            if (returnMove.returnValue < beta) {
                beta = returnMove.returnValue;
                bestMove = returnMove;
            }
            if (beta <= alpha) {
                bestMove.returnValue = alpha;
                bestMove.returnMove = null;
                return bestMove; // pruning
            }
        }
        return bestMove;
    }   
}