1.5 评估函数与走子排序（小游戏预演）

前两节留下两个悬而未决的难题：搜不到底怎么办、走子顺序怎么定。这一节我们把这两件工具——评估函数和走子排序——在井字棋上先预演一遍。说“预演”是因为井字棋太小，根本用不着它们；但正因为它小，我们能把这两件工具的样子看得清清楚楚，等第二章五子棋一上来，它们就是决定胜负的主力了。

一、动机：搜不到底，就得在“半路上”估个分

回顾一下困境：五子棋、国际象棋的博弈树太大，搜索不可能抵达终局，于是 winner() 那种“非黑即白”的确定结果根本读不到。怎么办？办法朴素得近乎直白——搜到一定深度就停下，然后凭经验给当前这个“半截局面”估一个分，当作它的近似价值。

这个“凭经验估分”的函数，就叫评估函数（evaluation function），也叫启发式（heuristic）。它回答的问题是：“先别管最终谁赢，就现在这个局面，谁更占优、占多少？”有了它，我们的搜索就从“一路算到底”改成了“算到第 D 层，到点就用评估函数收尾”：

def search(game, depth_limit, depth=0):
    """带深度上限的搜索：到达上限就用 evaluate 估分，不再往下。"""
    if game.is_terminal() or depth == depth_limit:
        return evaluate(game), None          # 到底 或 到点 → 用评估函数收尾

    results = []
    for move in game.legal_moves():
        child = copy.deepcopy(game); child.make_move(move)
        score, _ = search(child, depth_limit, depth + 1)
        results.append((score, move))

    chooser = max if game.current_player == 1 else min   # 先手求大、后手求小
    return chooser(results, key=lambda p: p[0])

和上一节的 Minimax 比，唯一的实质变化就是终止条件多了一句 depth == depth_limit，以及到点时返回的是 evaluate(game) 而非 winner()。搜索的“形状”没变，只是把“算到底”换成了“算到一半，剩下交给经验”。（这里为聚焦概念省去了 α-β，实战中两者当然要叠在一起用。）

二、给井字棋写一个玩具评估函数

评估函数怎么写？它的好坏全靠领域知识。对井字棋，一个简单又合理的想法是数“还有多少条线有希望连成”：一条线如果只有我的子、没有对手的子，它就还是我的机会；线上我占的子越多，这条线越值钱。反过来，对手的机会就给负分。

def evaluate(game):
    """给非终局局面估分：正数利好先手(+1)，负数利好后手(-1)。"""
    if game.is_terminal():
        return game.winner() * 100       # 终局给个大分，压过一切中间估分

    score = 0
    for a, b, c in LINES:                # LINES 就是 1.2 里那八条线
        line = [game.board[a], game.board[b], game.board[c]]
        if -1 not in line:               # 这条线没有后手的子 → 还是先手的机会
            score += line.count(1)       # 先手占得越多越值钱
        if 1 not in line:                # 这条线没有先手的子 → 还是后手的机会
            score -= line.count(-1)
    return score

注意那句 winner() * 100：终局是“铁一般的事实”，必须让它的分数远远盖过中间局面的估分，否则程序可能为了多占一条虚的线，而放过眼前真正的胜负。“确定的结果永远压过估计的结果”，这是写评估函数的一条通则。把 search 的 depth_limit 设小一点（比如 2），它就会基于这个评估函数下棋——棋力当然不如算到底，但这正是大棋盘上我们唯一可行的办法。

三、走子排序：让 α-β 剪得更狠

第二件工具来自上一节的教训：α-β 剪枝剪得多不多，全看你先试哪一步。把好棋排在前面，钳子早早合拢，剪得就狠；把坏棋排前面，几乎剪不动。所以我们希望在搜索每个节点前，先按某种廉价的猜测把走法排个序，让“可能更好”的排在前头。

井字棋有个人尽皆知的经验：中心最值钱、四角次之、四条边最次。我们就用它来排序——这不需要精确，只要“大致靠谱”就能帮上 α-β：

def ordered_moves(game):
    """把更有希望的走法排在前面：中心最优、角次之、边最后。"""
    priority = {4: 0, 0: 1, 2: 1, 6: 1, 8: 1}   # 值越小越靠前；没列出的(边)默认 2
    return sorted(game.legal_moves(), key=lambda m: priority.get(m, 2))

然后在搜索里，把 game.legal_moves() 换成 ordered_moves(game) 即可。这里还藏着一个更一般的概念——候选生成（candidate generation）：井字棋格子少，所有空格都是候选；但到了五子棋，棋盘有 225 个点，绝大多数远离战场、根本不值得考虑，那时我们会只把“已有棋子附近”的点当候选。排序决定“先看谁”，候选生成决定“看不看”，两者都是为了让搜索把力气花在刀刃上。

四、反思：井字棋太小，反而显不出它们的本事

说句大实话：这一节做的两件事，在井字棋上其实都没必要。井字棋整棵树一瞬间就能搜完，既不需要“半路估分”，也不在乎那点剪枝快慢。我们做它们，纯粹是趁着棋小、看得清，先把工具的样子认熟。

它们真正的舞台在大棋盘。到第二章五子棋你会看到一件漂亮的事：同一套“棋型”知识——活四、冲四、活三——会同时撑起评估函数和走子排序这两件工具。评估函数靠数棋型给局面打分，走子排序靠棋型把“能成冲四”的强手提到最前。届时这两件今天看起来“多此一举”的工具，会从配角一跃成为决定棋力的主力。这就是为什么我们要趁现在把它们认清楚。

五、小结与下一节

评估函数：搜不到底时，搜到固定深度就用它给中间局面估分；好坏取决于领域知识；确定结果要远压过估计结果。
走子排序 + 候选生成：排序让 α-β 剪得更狠，候选生成让搜索只看值得看的点；两者都让算力花在刀刃上。
预演而已：井字棋太小用不上它们，但五子棋的“棋型”会让同一套思路同时驱动评估与排序。

到这里，我们已经把“搜索 + 评估”这条经典路线讲完整了。但它有个隐含的前提——你得会写评估函数。可如果一个游戏复杂到你根本不知道怎么给局面打分呢？下一节 1.6 迭代加深会给出一个脑洞大开的答案：干脆不写评估函数，靠“随机试下很多盘”来判断局面好坏。