我的Negamax算法有阿尔法-贝塔修剪的问题吗？

Question

我正在尝试建立一个国际象棋AI。我的带有 alpha-beta 修剪的 negamax 函数 （ABP） 比使用 ABP 的单独最小和最大函数运行得慢得多（约 8 倍），尽管返回的移动是相等的.

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

我的Netamax函数：

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;
}

根分别调用红色和黑色玩家：

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

我猜 Negamax 函数中的截止有一个错误，尽管我从这里遵循了伪代码。任何帮助不胜感激，谢谢！

编辑：alphaBeta（）的调用量大约是min（）和max（）的总和的6倍，而beta截止的数量只有2倍左右。

Answer 1

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

更新了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;

很抱歉我的问题中缺乏信息——我没想到会有这个错误。