实现alpha-beta剪枝算法时，一个函数表现出奇怪的行为

Question

我已经使用alpha-beta剪枝实现了minimax算法。为了获得最佳移动，我调用了rootAlphaBeta函数中的alpha-beta算法。然而，在rootAlphaBeta函数中，我发现了一些非常奇怪的行为。当我使用4个ply调用rootAlphaBeta函数时，它会进行大约20,000次调用，但是当我直接调用alphaBeta函数时，它只会进行大约2000次调用。我似乎找不到问题所在，因为调用次数应该是相同的。

这两种算法最终找到的移动应该是相同的，对吗？至少移动的得分是相同的，当我在没有rootAlphaBeta的情况下直接调用alphaBeta时，我无法知道alphaBeta选择的移动。

def alphaBeta(self, board, rules, alpha, beta, ply, player):
    """Implements a minimax algorithm with alpha-beta pruning."""
    if ply == 0:
        return self.positionEvaluation(board, rules, player)

    move_list = board.generateMoves(rules, player)
    for move in move_list:
        board.makeMove(move, player)
        current_eval = -self.alphaBeta(board, rules, -beta, -alpha, ply - 1,
                                       board.getOtherPlayer(player))
        board.unmakeMove(move, player)

        if current_eval >= beta:
            return beta

        if current_eval > alpha:
            alpha = current_eval

    return alpha


def rootAlphaBeta(self, board, rules, ply, player):
    """Makes a call to the alphaBeta function. Returns the optimal move for a 
    player at given ply."""
    best_move = None
    max_eval = float('-infinity')

    move_list = board.generateMoves(rules, player)
    for move in move_list:
        board.makeMove(move, player)
        current_eval = -self.alphaBeta(board, rules, float('-infinity'),
                                       float('infinity'), ply - 1,
                                       board.getOtherPlayer(player))
        board.unmakeMove(move, player)

        if current_eval > max_eval:
            max_eval = current_eval
            best_move = move

    return best_move

- stensootla

Answer 1

您的rootAlphaBeta没有更新alpha值。它使用范围为(-inf, inf)的完整范围调用所有子节点，当它可以缩小除第一个子节点以外的所有子节点的范围。这将防止对一些分支进行修剪，而这些分支对最终得分没有影响，并增加节点计数。

- interjay