java - 我的带有 alpha-beta 剪枝的 Negamax 算法有问题吗？

Question

我正在尝试构建国际象棋 AI。我的带 alpha-beta 修剪 (ABP) 的 negamax 函数运行速度比单独的 min 和 max 函数也用 ABP 慢得多(大约 8 倍)，尽管返回的移动是相等的。

我的棋盘评估函数总是返回一个关于红色玩家的值，即红色越高越好。仅对于 Negamax，当返回深度 0 时，此值乘以黑色玩家的 -1。

我的 Negamax 函数:

int alphaBeta(Board board, int depth, int alpha, int beta) {
    if (depth <= 0 || board.isGameOver()) { // game over == checkmate/stalemate
        int color = board.getCurrPlayer().getAlliance().isRed() ? 1 : -1;
        return BoardEvaluator.evaluate(board, depth) * color;
    }

    int bestVal = Integer.MIN_VALUE + 1;
    for (Move move : MoveSorter.simpleSort(board.getCurrPlayer().getLegalMoves())) {
        MoveTransition transition = board.getCurrPlayer().makeMove(move);
        if (transition.getMoveStatus().isAllowed()) { // allowed == legal && non-suicidal
            int val = -alphaBeta(transition.getNextBoard(), depth - 1, -beta, -alpha);
            if (val >= beta) {
                return val; // fail-soft
            }
            if (val > bestVal) {
                bestVal = val;
                alpha = Math.max(alpha, val);
            }
        }
    }        

    return bestVal;
}

根调用:

-alphaBeta(transition.getNextBoard(), searchDepth - 1,
                        Integer.MIN_VALUE + 1, Integer.MAX_VALUE); // +1 to avoid overflow when negating

我的最小和最大函数:

int min(Board board, int depth, int alpha, int beta) {
    if (depth <= 0 || board.isGameOver()) {
        return BoardEvaluator.evaluate(board, depth);
    }

    int minValue = Integer.MAX_VALUE;
    for (Move move : MoveSorter.simpleSort(board.getCurrPlayer().getLegalMoves())) {
        MoveTransition transition = board.getCurrPlayer().makeMove(move);
        if (transition.getMoveStatus().isAllowed()) {
            minValue = Math.min(minValue, max(transition.getNextBoard(), depth - 1, alpha, beta));
            beta = Math.min(beta, minValue);
            if (alpha >= beta) break; // cutoff
        }
    }

    return minValue; 
}

int max(Board board, int depth, int alpha, int beta) {
    if (depth <= 0 || board.isGameOver()) {
        return BoardEvaluator.evaluate(board, depth);   
    }

    int maxValue = Integer.MIN_VALUE;
    for (Move move : MoveSorter.simpleSort(board.getCurrPlayer().getLegalMoves())) {
        MoveTransition transition = board.getCurrPlayer().makeMove(move);
        if (transition.getMoveStatus().isAllowed()) {
            maxValue = Math.max(maxValue, min(transition.getNextBoard(), depth - 1, alpha, beta));
            alpha = Math.max(alpha, maxValue);
            if (alpha >= beta) break; // cutoff
        }
    }

    return maxValue;
}

root 分别调用红色和黑色玩家:

min(transition.getNextBoard(), searchDepth - 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
max(transition.getNextBoard(), searchDepth - 1, Integer.MIN_VALUE, Integer.MAX_VALUE);

尽管我遵循了 here 中的伪代码，但我猜测 Negamax 函数中的截止值存在错误。 .感谢任何帮助，谢谢!

编辑:alphaBeta() 被调用的次数是 min() 和 max() 加起来的 6 倍，而 beta 的次数截断值仅增加约 2 倍。

Answer 1

已解决。我也应该发布根调用的完整代码——没有意识到我没有传递 beta 的新值。 Alpha/beta 实际上是在根方法中更新的，用于单独的 min-max。

Negamax 的更新根方法:

Move bestMove = null;
int bestVal = Integer.MIN_VALUE + 1;

for (Move move : MoveSorter.simpleSort(currBoard.getCurrPlayer().getLegalMoves())) {
    MoveTransition transition = currBoard.getCurrPlayer().makeMove(move);
    if (transition.getMoveStatus().isAllowed()) {
        int val = -alphaBeta(transition.getNextBoard(), searchDepth - 1, Integer.MIN_VALUE + 1, -bestVal);
        if (val > bestVal) {
            bestVal = val;
            bestMove = move;
        }
    }
}

return bestMove;

对于我的问题中缺少提供的信息，我深表歉意——我没想到错误会在那里。