python - 实现 alpha-beta 修剪算法时函数中的奇怪行为

Question

我已经实现了带有 alpha-beta 剪枝的极小极大算法。为了获得最佳着法，我用 rootAlphaBeta 调用 alpha-beta 算法。功能。然而，在 rootAlphaBeta功能，我发现了一些非常奇怪的行为。当我调用 rootAlphaBeta功能与 ply 4，它发出大约 20 000 个调用，但是当我调用 alphaBeta直接运行，它只进行大约 2000 次调用。我似乎找不到问题所在，因为调用次数应该相同。

两种算法最终找到的走法应该是一样的吧？我想是的，至少这一步的分数是一样的，我不知道这一步alphaBeta当我没有 rootAlphaBeta 直接调用它时选择.

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

Answer 1

您的 rootAlphaBeta 不会更新 alpha 值。当它可以缩小除第一个子节点之外的所有子节点的范围时，它会使用完整范围的 (-inf, inf) 调用其所有子节点。这样可以避免剪掉一些对最终分数没有影响的分支，增加节点数。