2.2 搜索框架工程化（α-β 实战）

上一节我们论证了“五子棋搜不到底”。这一节就把第一章的 α-β 老老实实搬过来，亲眼看它在大盘上慢到不可用，然后动两刀工程化改造：先用“候选生成”把分支从 225 砍到几十，再用“迭代加深”把搜索装进一个时间预算里。这两刀是后面一切的前提——评估函数、威胁搜索都要架在这个跑得动的框架上。

一、把第一章的 α-β 搬过来，亲眼看它崩

第一章的 α-β 几乎能直接用，只需两个来自 1.4、1.5 的小改动：其一，五子棋到不了终局，所以必须配一个评估函数（下一节细讲，这里先假设有个 evaluate()）；其二，必须设深度上限，搜到就用评估收尾。

改完一跑，问题立刻暴露：它慢得令人发指。根子在 legal_moves()——在五子棋里它返回所有空点，开局就是 225 个。α-β 每一层都要在一两百个分支里打转，于是哪怕只想搜 3、4 层，节点数也轻松上亿，一步棋要算好几分钟。第一章那个在井字棋上眨眼出招的引擎，到这儿基本动不了。我们必须先解决“分支太多”这个最致命的瓶颈。

二、第一刀：只在已有棋子附近落子

这一刀靠的是一条朴素却极有效的领域知识：在五子棋里，把子下在远离所有棋子的空旷角落，几乎永远是废棋。有意义的着法，必然是在已有棋子的附近——要么接着自己的连子进攻，要么贴着对手的棋防守。

于是我们不再把 225 个空点都当候选，而是只考虑“距离某个已有棋子一两格以内”的空点。这一刀下去，分支因子常常从 200 多直接掉到几十，搜索量呈指数级缩小：

def candidate_moves(board, radius=1):
    """只考虑'已有棋子附近'的空点，大幅缩小分支。"""
    N = len(board)
    stones = list(zip(*np.nonzero(board)))      # 所有已落子的位置
    if not stones:
        return [(N // 2, N // 2)]               # 空盘：直接下天元（正中）

    cand = set()
    for (r, c) in stones:
        for dr in range(-radius, radius + 1):
            for dc in range(-radius, radius + 1):
                rr, cc = r + dr, c + dc
                if 0 <= rr < N and 0 <= cc < N and board[rr, cc] == 0:
                    cand.add((rr, cc))          # 邻域里的空点才算候选
    return list(cand)

把搜索里的 legal_moves() 换成 candidate_moves()，引擎立刻“活”了过来——同样的时间，它能搜得深得多。这是我们对“树太大”动的第一刀，也是最立竿见影的一刀。当然它略有取舍：极少数“脱先”到远处的妙手会被漏掉，但在 v1 里这点损失完全值得。（radius 设 1 还是 2 是个权衡：大一点更安全、但分支更多。）

三、第二刀：迭代加深，把搜索装进时间预算

还有个现实问题：到底该搜几层？局面有简有繁，写死一个深度并不好——简单局面本可以搜更深，复杂局面搜浅一点才不超时。更聪明的办法叫迭代加深（Iterative Deepening）：先搜 1 层，再搜 2 层，再 3 层……一旦时间用完，就返回目前搜得最深的那次给出的最佳着法。

import time

def best_move(engine, time_budget=2.0):
    """迭代加深：从浅到深逐层搜，时间一到就返回目前最好的一步。"""
    start = time.time()
    best = None
    depth = 1
    while time.time() - start < time_budget:
        best = alphabeta_root(engine, depth)    # 搜 depth 层，返回最佳走法
        depth += 1                              # 没超时就再往深搜一层
    return best

你可能会担心：从 1 层重搜不是白费功夫吗？其实几乎不浪费——因为搜索量随深度指数增长，最深的那一次就占了绝大部分开销，前面那些浅层搜索的成本加起来都微不足道。而迭代加深换来两个大好处：一是随时可叫停（anytime），给多少时间就用多少；二是个意外之喜——上一层搜出的最佳着法，可以在下一层优先尝试，这恰好喂给了 α-β 它最爱的“好棋先搜”，让剪枝更狠。这条线，我们下下节（2.4 走子排序）会继续做文章。

四、小结与下一节

• 瓶颈：朴素 α-β 在五子棋上因 legal_moves() 返回 ~225 个空点而慢到不可用。
• 候选生成：只在已有棋子邻域内取候选，分支从 200+ 砍到几十，最立竿见影的一刀。
• 迭代加深：逐层加深、超时即返回；几乎不浪费，还带来 anytime 特性和“上层最佳着法优先”的排序红利。

现在引擎跑得动了，但它还很“蠢”——因为我们一直假装有个 evaluate()，却还没真正写它。而评估函数正是五子棋的灵魂：它决定了引擎到底懂不懂棋。下一节 2.3 启发式评估函数，我们就来认识“活四、冲四、活三”这些棋型，把它们变成分数。