1.6 迭代加深（Iterative Deepening）

到上一节为止，“搜索 + 评估 + 排序”这套经典组合的思想已经齐了。但要把它做成一个真能上场的引擎，还差一块工程拼图：到底该往下搜多深？这一节的 迭代加深（Iterative Deepening）给出一个优雅得近乎“作弊”的答案——别急着定深度，从 1 层开始，一层层反复地往深里搜，直到时间用完为止。它一举解决两件事：(1) 让引擎随时都有一个可用的着法、给多少时间就用多狠；(2) 把上一节那个“先搜哪一步”的难题，几乎免费地解决掉。

一、动机：搜多深？“定一个深度”其实是个两难

在井字棋里我们从没纠结过深度——树小，一路搜到终局就行。可一旦换上五子棋、国际象棋，树大到搜不到底，1.5 教的办法是：搜到固定深度 d，停下来用评估函数估个分。问题立刻来了：这个 d 该填几？

你会发现怎么填都不对：

填小了，比如 d=4，对手一个 5 步杀你根本看不见，引擎会一脚踩进陷阱。
填大了，比如 d=12，开局阶段分支多，一盘棋还没走两步，时钟先到点判负了。
更要命的是，“合适的深度”根本不是个定值。残局空旷、可走的子少，同样的时间能搜得很深；中局犬牙交错，搜浅一点就到时间了。它还取决于你的硬件、对手给你的时限——这些你写代码时根本不知道。

而真实对弈几乎总是带钟的：“每步限你 5 秒”“整盘限你 10 分钟”。这意味着我们要的不是一个“算到第 d 层”的算法，而是一个“随时叫停、随时能交出一个像样答案”的算法——学名叫 anytime 算法（随时算法）：你让它想得越久，它给的答案越好；但无论何时打断它，它手里都已经攥着一个不算差的结果。

二、核心思想：从浅到深，一层一层来

迭代加深的想法朴素得让人起疑：既然不知道该搜多深，那就别选了——从 1 层开始，搜完一层就把深度加一，再从头搜一遍，循环往复，直到时间耗尽。每完成一轮，就把这一轮算出的最佳着法记下来；时钟一响，就拿最后一轮完整跑完的那个着法去走。

给定局面，时限 5 秒：

  搜深度 1  →  最佳着法 = b   (花了 0.001 秒)
  搜深度 2  →  最佳着法 = b   (花了 0.003 秒)
  搜深度 3  →  最佳着法 = e   (花了 0.02 秒)
  搜深度 4  →  最佳着法 = e   (花了 0.1 秒)
  搜深度 5  →  最佳着法 = h   (花了 0.6 秒)
  搜深度 6  →  ……搜到一半，5 秒到了！ ←─ 丢弃这半截结果
  ──────────────────────────────────
  交出深度 5 的答案：走 h

注意两个关键点。第一，每一轮都是一次完整、独立的定深度搜索——就是把 1.4 的 α-β 改成“搜到第 d 层就用评估函数收尾”，没有任何新算法。第二，没跑完的那一轮要整轮丢掉：它只看了一部分着法，结论不可信；我们只信“完整跑完”的最深一轮。这样一来，给 1 秒它能交出深度 5 的答案，给 1 分钟它能交出深度 10 的答案——时间花得越多，棋力越强，且永远不会超时。

三、“重复搜索”几乎是免费的

讲到这儿，你大概已经皱起眉头了：“为了搜第 5 层，先把第 1、2、3、4 层重新搜了一遍——这不是把功夫白费了好几次吗？” 这是每个人第一次听到迭代加深时都会有的疑虑，而答案出人意料：这点重复开销小到几乎可以忽略。

道理藏在“树是指数膨胀”的算术里。设每个局面平均有 b 个走法（分支因子），那么第 d 层大约有 b^d 个节点。一次普通的定深度搜索要访问从第 1 层到第 d 层的所有节点，而最深那一层 b^d 本身，就比上面所有层加起来还要多。迭代加深无非是把“上面那些浅层”又重走了几遍，可浅层的节点数本来就微不足道：

把深度 1..d 全部重搜一遍的总节点数
   = b + b² + … + b^d              （迭代加深的总开销）
   ≈ b^d · b/(b−1)                  （等比数列求和）

而只搜一次深度 d 的开销 ≈ b^d。

  ⇒ 多出来的开销倍数 = b/(b−1)
       b = 2   → 2.0×    （最坏情况，也才翻一倍）
       b = 10  → 1.11×   （只多 11%）
       b = 35  → 1.03×   （国际象棋，多 3%）

换句话说，分支因子越大，重复搜索的“浪费”反而越可忽略。对国际象棋（b≈35）这种大树，迭代加深到深度 d 的总成本，比直接一把搜到 d 只贵了 3% 左右——为了换“随时能停 + 永不超时”，这点代价简直是白送。井字棋分支小、树也小，这笔账无所谓，但请记住：到了大棋盘上，这个结论依然成立，而且正是它让迭代加深成为可能。

四、真正的红利：上一轮的答案，就是这一轮最好的排序

如果说“anytime”只是迭代加深的明面好处，那它还有个暗藏的、甚至更值钱的红利。回想 1.4 结尾那句反复强调的话：α-β 剪枝的威力，几乎完全取决于你“先试哪一步”——好棋越靠前，剪得越狠。可这就成了“鸡生蛋”：要想把好棋排前面，你得先知道哪步是好棋，而这恰恰是搜索本身要回答的问题。

迭代加深一刀劈开了这个死结：上一轮（深度 d−1）算出的最佳着法，正是这一轮（深度 d）该第一个去试的着法。深一层的最优解，绝大多数时候和浅一层的最优解一致或非常接近——这条“当前认为最好的着法链”有个专门的名字，叫主变例（Principal Variation, PV）。把 PV 着法提到候选列表最前面，α-β 的钳子几乎一上来就合拢，海量分支被瞬间剪掉。

于是出现了一个相当反直觉、也相当美妙的结果：“先搜浅层”不但不亏，反而让深层搜得更快。第三节算出的那点重复开销，被“更好的排序所省下的剪枝”不止补了回来——很多时候，带迭代加深的 α-β 搜到深度 d，比不带它、硬搜深度 d 还要快。正因如此，几乎所有正经的 α-β 引擎（无论国象还是五子棋），最外层套的都是迭代加深这个循环。

五、实现：给 α-β 外面套一层循环

实现起来同样没有惊喜——这正是它讨人喜欢的地方。两步：先把 1.4 的 α-β 改成“搜到 depth==0 就调评估函数收尾”的定深度版本，并让它支持“优先搜某一步”；再在外面套一个从 1 往上数、带时间检查的循环。

import time, copy

def alphabeta(game, depth, alpha, beta, first=None):
    """深度受限的 α-β。搜到 depth==0 就用评估函数估分。
    first 是上一轮迭代给出的最佳着法（PV 着法），优先搜它。"""
    if game.is_terminal():
        return game.winner() * 10_000, None     # 确定结果，远压过估计值
    if depth == 0:
        return evaluate(game), None              # 1.5 的评估函数登场

    moves = game.legal_moves()
    if first in moves:                           # 把上一轮的最佳着法提到最前
        moves = [first] + [m for m in moves if m != first]

    best_move = None
    if game.current_player == 1:                 # 最大化方
        value = -float('inf')
        for m in moves:
            child = copy.deepcopy(game); child.make_move(m)
            score, _ = alphabeta(child, depth - 1, alpha, beta)
            if score > value:
                value, best_move = score, m
            alpha = max(alpha, value)
            if alpha >= beta:                    # 钳子合拢，剪枝
                break
        return value, best_move
    else:                                         # 最小化方
        value = float('inf')
        for m in moves:
            child = copy.deepcopy(game); child.make_move(m)
            score, _ = alphabeta(child, depth - 1, alpha, beta)
            if score < value:
                value, best_move = score, m
            beta = min(beta, value)
            if alpha >= beta:
                break
        return value, best_move


def search(game, time_limit=1.0, max_depth=64):
    """迭代加深：从 1 层开始一层层加深，直到时间用尽。"""
    deadline = time.time() + time_limit
    best_move = None
    for depth in range(1, max_depth + 1):
        score, move = alphabeta(game, depth,
                                -float('inf'), float('inf'),
                                first=best_move)   # 用上一轮的结果做排序
        if move is not None:
            best_move = move                       # 记下这一轮的最佳着法
        print(f"  depth {depth:2d}: best={best_move}  score={score}")
        if time.time() > deadline:                 # 时间到，停在已完成的最深一轮
            break
    return best_move

对照 1.4 的 α-β，你会发现核心函数几乎一模一样，只多了两处：多了 depth==0 时调 evaluate 收尾（这是 1.5 的评估函数），以及多了 first 参数把 PV 着法排到最前。真正“新”的只有那个十来行的外层循环 search。把它打印出来的那几行 depth/score——就是你在各种象棋软件里看到的引擎“正在思考”的滚动输出。

一个诚实的细节：上面的代码只在每轮之间检查时间，所以最后那一轮一旦开了头，就得整轮跑完才停——万一这轮特别久，可能略微超时。工业级引擎会更狠：在递归内部埋一个时间检查，时间一到就立即中断当前这轮、丢掉它的半成品，回退到上一轮已经完成的最佳着法。原理完全一样，只是把“丢弃没跑完的一轮”做得更利落。井字棋上我们不必这么讲究，知道有这回事即可。

六、反思与小结

老规矩，得泼盆冷水：在井字棋上，迭代加深的威力几乎显不出来。树太小，一眨眼就搜到底，既谈不上“时间不够”，也谈不上“排序省了多少剪枝”。这和 1.5 评估函数、走子排序的处境一样——它们都是为大棋盘准备的、在小沙盘里先预演一遍的工具。真正让迭代加深大放异彩的，是第二章的五子棋和第三章的国际象棋：那里它会成为搜索的最外层骨架，和走子排序（2.4）、置换表（2.6，上一轮的结果还能跨轮复用）紧紧咬合，撑起整个引擎的算力。

解决的两难：固定深度选不对——浅了看不穿杀棋，深了会超时，而“合适的深度”随局面、硬件、时限而变，根本没法写死。
核心做法：从深度 1 起一层层加深，反复重搜；时钟一响，就交出最后一轮完整跑完的最佳着法（没跑完的整轮丢弃）。
开销可忽略：因为树是指数膨胀的，重搜浅层的代价只有 b/(b−1) 倍——分支越大越可忽略（国象仅约 +3%）。
额外红利：上一轮的最佳着法（PV）是这一轮绝佳的排序提示，剪枝更狠，常常反而比硬搜同样深度更快。
anytime 特性：给多少时间用多少，随时叫停都有可用答案——这正是带钟对弈需要的。

到这里，“搜索 + 评估 + 排序 + 迭代加深”这条经典路线总算工程上闭环了。但请别忘了：它从头到尾都压在一个前提上——你得写得出一个评估函数。可如果碰上围棋那种几十年没人写得出像样评估函数的游戏呢？下一节 1.7 蒙特卡洛树搜索 MCTS 会给出一个脑洞大开的回答：干脆不写评估函数，靠“随机试下很多盘”来判断局面好坏。