java - 使 Minimax 返回最佳移动而不是最佳移动产生的分数

Question

从我见过的所有示例中，minimax 算法将返回一个 int 值，表示最佳分数或最佳棋盘状态。我怎样才能返回与这个分数相关的最佳 Action ？谢谢

private Integer minimax(Board board, Integer depth, Color current, Boolean maximizingPlayer, Integer maxPlayerBestVal, Integer minPlayerBestVal) {
    Integer bestValue;
    if (0 == depth)
        return ((current == selfColor) ? 1 : -1) * this.evaluateBoard(board, current);

    Integer val;
    if (maximizingPlayer) {
        bestValue = -INF;
        for (Move m : board.getPossibleMoves(current)) {
            board.apply(m);
            val = minimax(board, depth - 1, Boolean.FALSE, 
                      minPlayerBestVal, maxPlayerBestVal); // swap here 
            bestValue = Math.max(bestValue, val);
            board.revert(m);
            if (bestValue >= minPlayerBestVal) // too good for the minPlayer
                return bestValue;              // so cut here (pruning)
            }
        return bestValue;
    } else {
        [...] min player
    }
}

the evaluate function

private Integer evaluateBoard(Board board, Color player) {
    return board.pawns(player) - board.pawns(player.other());
}

Answer 1

一种策略是使用类范围的实例变量存储最佳着法(另一种方法可能是返回一对值，即值和关联的着法)。每当你发现自己处于顶层递归调用深度并有一个新的更好的移动时，设置这个最佳移动变量(在初始深度，我们正在检查每一个可能的移动并选择最终导致具有最佳评估的节点的那个) .

因为我们只希望我们的最佳移动是从原始状态可以到达的东西，我们可以跟踪深度并只在第一次递归调用时设置最佳移动，或者在我们找到最佳移动时设置它child(当新的最佳返回给调用者时它将被覆盖，因此我们最终将从原点获得可用的移动之一)。

请注意，如果起始板的路径在此之前只遇到终端状态，则您可能永远不会到达深度 0。例如，探索深度可能为 8，但必须捕获所有棋子并且游戏在接下来的 2 步内结束，因此调用 board.getPossibleMoves() 会返回一个空数组。这将使最好的举动悬而未决。添加对类似 isTerminal(board) 的检查将处理这种情况。

我注意到 minPlayerBestVal 和 maxPlayerBestVal(alpha-beta pruning 边界)在提供的实现中似乎没有更新。您的递归调用也缺少 Color current 参数。

不需要使用原始数据类型的盒装版本；使用 int 和 boolean。

最后，在不知道您正在编程的游戏的情况下(我想像只有棋子的国际象棋)，您为评估提供的启发式可能不完整，可能需要考虑下一次没有捕获的位置depth 移动(如果游戏足够简单，例如 hexapawn ，则可以进行完整搜索，完全跳过深度限制)。

下面是以上几点的一个例子。由于我没有您的支持类，您可能需要稍微调整一下:

private Move bestMove;

public Move getBestMove(Board board) {
    minimax(board, 42, selfColor, true, -INF, INF);
    return bestMove;
}

private int minimax(Board board, int depth, Color current, 
                    boolean maximizing, int alpha, int beta) {
    if (depth == 0/* || isTerminal(board)*/) {
        return ((current == selfColor) ? 1 : -1) * 
                   this.evaluateBoard(board, current);
    }
    else if (maximizing) {
        int best = -INF;

        for (Move m : board.getPossibleMoves(current)) {
            board.apply(m);
            int childVal = minimax(board, depth - 1, current, 
                                   false, alpha, beta);
            board.revert(m);

            if (childVal > best) {
                best = childVal;
                alpha = Math.max(alpha, best);
                this.bestMove = m;

                if (alpha >= beta) {
                    break;
                }
            }
        }

        return best;
    }

    int best = INF;

    for (Move m : board.getPossibleMoves(current)) {
        board.apply(m);
        best = Math.min(best, minimax(board, depth - 1, current, 
                                      true, alpha, beta));
        board.revert(m);
        beta = Math.min(beta, best);

        if (alpha >= beta) {
            break;
        }
    }

    return best;
}