如何在带Alpha-Beta剪枝的Minimax算法中计算搜索树大小

你需要统计Minimax算法实际访问的搜索树节点数（因为Alpha-Beta剪枝会跳过部分节点，所以不是完整二叉树的大小）。由于原代码是通过递归隐式表示搜索树（没有显式的Node类），可以通过在递归过程中计数每一次minimax函数调用来实现。

修改后的完整代码 #

# Initial values of Alpha and Beta
MAX, MIN = 1000, -1000

# Returns optimal value for current player, and counts visited nodes
def minimax(depth, nodeIndex, maximizingPlayer, values, alpha, beta, node_count):
    # 统计当前节点（每调用一次minimax对应一个节点）
    node_count[0] += 1
    
    # 终止条件：到达叶子节点
    if depth == 3:
        return values[nodeIndex]

    if maximizingPlayer:
        best = MIN
        # 递归遍历左右子节点
        for i in range(0, 2):
            val = minimax(depth + 1, nodeIndex * 2 + i, False, values, alpha, beta, node_count)
            best = max(best, val)
            alpha = max(alpha, best)
            # Alpha-Beta剪枝
            if beta <= alpha:
                break
        return best
    else:
        best = MAX
        # 递归遍历左右子节点
        for i in range(0, 2):
            val = minimax(depth + 1, nodeIndex * 2 + i, True, values, alpha, beta, node_count)
            best = min(best, val)
            beta = min(beta, best)
            # Alpha-Beta剪枝
            if beta <= alpha:
                break
        return best

# 主程序
if __name__ == "__main__":
    values = [3, 5, 6, 9, 1, 2, 0, -1]
    # 用列表存储节点数，方便递归中修改（Python整数不可变）
    node_count = [0]
    optimal_value = minimax(0, 0, True, values, MIN, MAX, node_count)
    print("最优值为:", optimal_value)
    print("搜索树大小为:", node_count[0])

关键说明 #

1. 节点计数逻辑：每次进入minimax函数就计数一次，不管是内部节点还是叶子节点，因为每个函数调用对应搜索树中的一个节点。
2. 可变对象传参：使用列表node_count而非普通整数，因为Python中整数是不可变类型，递归函数内部无法直接修改外部整数变量；列表是可变类型，修改其内部元素会同步到外部。
3. 剪枝的影响：Alpha-Beta剪枝会跳过部分子节点，因此统计的是实际被访问的节点数，而非完整二叉树的节点数（完整4层二叉树总节点数为15，此例中剪枝后实际访问11个节点）。

内容的提问来源于stack exchange，提问作者Go GO