java - 在 Minimax 期间我们实际上在哪里分配最佳移动？

Question

我对极小极大和 alpha beta 剪枝如何返回“最佳值”有很好的理解。但是我不确定“最佳 Action ”应该分配在哪里。

我知道最好的移动需要来自传入的原始棋盘，并且由于我正在寻找最大值，因此必须将其分配给最大化玩家。然而，使用我当前的代码会导致最佳操作被一遍又一遍地重新分配。
例如如果原来的棋盘是O--\n---\n---，那么最佳 Action 就变成
OX-\n---\n---，然后重新分配给 O-X\n---\n--- 等等。

public int minimax(Board board, int depth, boolean maximizing,int alpha,int beta) {
    int bestValue;
    if (board.isTerminal()) {
        bestValue = board.calculateValue();
    } else if (maximizing) {
        bestValue = alpha;
        for (Action action : board.makePossibleActions()) {
            int childValue = minimax(board.makeCopy().takeAction(action),depth+1,false,bestValue,beta);
            if (bestValue <= childValue) {
                bestValue = childValue;
                if (board.equals(originalBoard)) {
                    bestAction = action;
                }
            }
            bestValue = Math.max(bestValue,childValue);
            if (beta <= bestValue) {
                break;
            }
        }
    } else {
        bestValue = beta;
        for (Action action : board.makePossibleActions()) {
            int childValue = minimax(board.makeCopy().takeAction(action),depth+1,true,alpha,bestValue);
            bestValue = Math.min(bestValue,childValue);
            if (bestValue <= alpha) {
                break;
            }
        }
    }
    return bestValue;
}

Answer 1

1. 你知道 root 是一名 max 玩家。
2. 您还知道深度(0 或 1，具体取决于您如何进行初始调用)。

因此，如果要玩最大玩家，则您位于树的根部，并且更新最大移动的值，然后还将该移动存储在类变量中以返回。 (不要取最大值，而是测试该值是否更大，然后一起更新最大值和最佳移动。)