2.4 走子排序与候选生成

这一节短而关键。还记得 1.4 那个教训吗——α-β 剪得多不多，几乎完全取决于你先试哪一步。在井字棋上这无所谓，但在五子棋上，它直接决定引擎能搜多深。好消息是：我们上一节刚定义的棋型，正好是给走法排序的最佳依据。

一、动机：排序好不好，能差出几个数量级

先把 1.4 的道理在五子棋的尺度上重说一遍。α-β 的钳子（α、β）只有在“先看到好棋”时才会早早合拢、剪掉大片分支。理想情况下，如果每个节点都恰好先搜最佳着法，α-β 访问的节点数约是朴素 Minimax 的平方根——这意味着同样的时间能多搜近一倍的深度。反过来，要是把最差的走法排在最前面，α-β 几乎一个分支都剪不掉，退化成朴素 Minimax。

在五子棋这种分支几十、要搜十几层的棋里，“多搜一倍深度”往往就是“能算到杀棋”和“算不到”的区别。所以排序不是锦上添花，而是雪中送炭。

二、用棋型给走法打分，强手排前面

怎么猜哪一步“可能更好”？答案就在上一节：一步棋的价值，看它能造出多强的棋型、或挡掉对手多强的棋型。能直接成五的当然第一个试，其次是成活四、冲四、活三的……我们给每个候选走法快速估个“棋型分”，然后从高到低排序：

def order_moves(engine, moves):
    """给候选走法按'这一步能造出的威胁强弱'排序，强的排前面。"""
    def move_score(m):
        # 试下这一步，看它给我方造出的最强棋型 + 挡掉对方的最强棋型
        attack = best_pattern_if_i_play(engine, m, engine.to_move)
        defend = best_pattern_if_i_play(engine, m, -engine.to_move)
        return PATTERN_SCORES.get(attack, 0) + PATTERN_SCORES.get(defend, 0)
    return sorted(moves, key=move_score, reverse=True)   # 分高的排前面

注意这里进攻和防守一起算：一步棋既可能帮我成冲四（进攻），也可能堵住对手的活三（防守），两者都让它值得优先考虑。把 order_moves 套在 α-β 每个节点的候选生成之后，剪枝立刻凶猛起来。这一步用的全是上一节的棋型，可谓“一套棋型知识，评估和排序两头都吃”。

三、再加两味经典调料：杀手启发与历史启发

棋型排序之外，还有两个不依赖领域知识、纯靠搜索经验的通用技巧，几乎所有强引擎都用：

杀手启发（Killer Heuristic）：如果某一步棋在同一层的别的分支里曾经引发剪枝（说明它是个很强的反击），那么在当前分支也优先试它。直觉是：能在隔壁把对手打崩的棋，在这儿多半也很猛。
历史启发（History Heuristic）：给每个走法维护一个“历史功劳分”，每当它在任何地方引发剪枝就加分；排序时让历史分高的靠前。它积累的是整盘搜索中“哪些点经常是好棋”的统计经验。

再加上 2.2 提过的迭代加深红利——把上一轮（浅一层）搜出的最佳着法，在这一轮第一个试——三者叠加，排序质量就相当高了。它们互相补充：棋型分懂“五子棋的道理”，杀手/历史分懂“这盘棋的临场经验”，迭代加深给“最可信的那一手”。

四、小结与下一节

排序的分量：理想排序让 α-β 降到 Minimax 的平方根级，约等于深度翻倍——在五子棋上常常决定能否算到杀棋。
棋型排序：按一步棋造出/挡掉的最强棋型打分，进攻防守一起算，强手排前面；复用上一节的棋型知识。
杀手 + 历史 + 迭代加深：三味通用调料，分别贡献“临场经验”和“最可信首选”，与棋型排序叠加。

到这里，我们的经典引擎已经“能搜、会评、剪得狠”了，对付一般局面相当强。但 2.3 末尾那个硬骨头还在：它仍可能漏算藏在深处的“连续冲四”强制杀。下一节 2.5 威胁空间搜索与 VCF/VCT，我们就造一把专门的“算杀”利器，把这类必胜线一网打尽——这也是五子棋引擎最有特色的一块。