1.3 Minimax：把下棋变成搜索

上一节我们的引擎只会“瞎走”。这一节就给它装上第一颗大脑——Minimax（极小化极大）。它是几乎所有传统下棋 AI 的基石，思想朴素却有力：把未来推演到底，并且始终假设对手会全力跟你作对。学完这节，你的井字棋程序将变得无法被战胜。

一、动机：只看一步的“贪心”为什么会输

在写搜索之前，先说服你“为什么非搜索不可”。一个最朴素的下法是贪心（greedy）：能赢就直接赢，否则就堵住对手眼前的威胁。听起来很合理，但它有个致命盲区——它只看眼前一步，看不见对手在布局。

看下面这个局面（X 是先手）。轮到 O 走，此刻 X 还没有任何“下一步就连成线”的直接威胁，所以贪心的 O 觉得高枕无忧，随手走了个边：

X . .          X . .
. O .    →     O O .      ← O 贪心地占了个边，没意识到危险
. . X          . . X

可接下来 X 轻轻一落角，局面变成这样：

X . X
O O .
. . X     ← X 同时威胁“顶行(差中间)”和“右列(差中间)”两条线

现在 X 一口气支起了两个威胁（顶行差一个、右列差一个），这叫双威胁 / 叉（fork）。O 只能堵一个，另一个必成——X 赢定了。问题出在哪？O 输不是因为它最后一步走错，而是因为它早几步就没看见 X 在布这个叉。只看一步的贪心，永远学不会“提前破坏对手的布局”，也永远学不会“自己去布一个叉”。

结论很清楚：要下好棋，必须向前多看几步——把“我走这儿、对手会怎么应、然后我再……”推演下去。这件事，就是上一节说的搜索。Minimax 就是把它写成代码的标准方法。

二、Minimax 的核心思想：站在对手的立场想问题

Minimax 的全部精髓就一句话：轮到我，我选对自己最有利的一步；轮到对手，我假设他选对我最不利的一步。一层层交替推演到终局，再把结果倒推回来，就知道现在该走哪。

这里要回收上一节埋的伏笔——+1 / −1 编码。我们让终局的“分数”直接等于 winner()：先手赢是 +1、后手赢是 −1、和棋是 0。于是两个玩家的目标，恰好就是一个要把分数推到最大、一个要把分数压到最小：

先手（+1）= 最大化方（Maximizer）：他喜欢 +1，所以总挑让分数尽量大的走法。
后手（−1）= 最小化方（Minimizer）：他喜欢 −1，所以总挑让分数尽量小的走法。

把这套想法写成一个式子，用 V(s) 表示局面 s 在双方完美对弈下的值，它就是一个分三种情况的递归定义：

        ⎧  winner(s)                        s 是终局：直接读胜负
V(s) =  ⎨  max over a:  V(走 a 之后的局面)     轮到先手（极大方）
        ⎩  min over a:  V(走 a 之后的局面)     轮到后手（极小方）

这个式子看着唬人，其实就是上面那两句话的数学版：终局直接看谁赢，否则轮到谁、就在他的所有走法里取对他最有利的那个值。下一节的代码，逐字就是它的翻译。

为什么可以这样“假设对手专门跟我作对”？因为上一节讲的零和——对手的最优，定义上就是我的最差。所以我做最坏打算算出来的走法，恰恰是最稳妥的。这就是“极小化极大”这个名字的来历：在对手的极小化里，求我的极大化。

三、最小实现：一段递归就够了

思想落成代码，短得惊人。我们写一个函数 minimax(game)，返回“这个局面在双方完美对弈下的最终结果”。逻辑是递归的：终局就直接读结果；否则就把每一种走法都试一遍，看对手接手后会走成什么样，再按“该谁走”决定取最大还是最小。

import copy

def minimax(game):
    """返回该局面在双方完美对弈下的结果：+1 先手胜 / -1 后手胜 / 0 和棋。"""
    if game.is_terminal():
        return game.winner()              # 终局，直接读出胜负

    scores = []
    for move in game.legal_moves():
        child = copy.deepcopy(game)       # 复制一份，在副本上试走，不弄脏原局面
        child.make_move(move)
        scores.append(minimax(child))     # 递归：让对手接着推演下去

    if game.current_player == 1:          # 轮到先手 → 最大化方
        return max(scores)
    else:                                 # 轮到后手 → 最小化方
        return min(scores)

请你重点体会两处。第一，那句 copy.deepcopy：搜索是“在脑子里试走”，绝不能真的改动当前棋盘，所以每试一步都在一份副本上进行。第二，最后的 max / min 分支：它把“先手求大、后手求小”原样翻译了出来——正负号编码让这件事干净到不需要任何额外判断。这短短十几行，就是一个能把整局棋算到底的完美对弈者。

四、实用化：我们要的是“走哪一步”，而且要赢得干脆

上面的 minimax 只告诉我们“这个局面值多少分”，可实战要的是“到底该落哪一子”。而且还有个细节：如果有好几步都能赢，我们希望它赢得越快越好；如果注定要输，则希望拖得越久越好（多给对手犯错的机会）。

这两件事一起解决。我们让函数同时返回最优分数和对应的走法；再引入一个 depth（推演了多少层），用它给终局分数打个折扣——越晚到达的胜利，分数越小，于是程序自然偏爱速胜、抗拒速败：

def minimax(game, depth=0):
    """返回 (最优分数, 最优走法)。用 depth 实现“快赢、慢输”。"""
    if game.is_terminal():
        # 终局分数 = 胜负 ×(10 - 层数)：赢得越早分越高，输得越晚“扣分”越少
        return game.winner() * (10 - depth), None

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

    # 先手取最大、后手取最小；key 让比较只看分数那一项
    chooser = max if game.current_player == 1 else min
    return chooser(results, key=lambda pair: pair[0])

最后，把它接回上一节留的那个口子 best_move()——还记得吗，接口形态完全不用改，大脑造好了直接插上：

class TicTacToe:
    # ……（前面的 board / legal_moves / winner 等都不变）……

    def best_move(self):
        """开放信息接口：返回引擎认为最好的一步。"""
        _, move = minimax(self)
        return move

现在你可以和它对弈了：人走一步、调一次 best_move() 让它应一步。试多少局都一样——你赢不了它，最好的结果是和棋。这就是“完美对弈”四个字落到实处的样子，而它背后不过是一段会把未来推演到底的递归。

五、反思：能“算到底”是井字棋的特权

请别被这份顺利冲昏头。Minimax 在井字棋上之所以天下无敌，是因为它真的把整棵博弈树走完了——而井字棋的树只有十万量级的节点，普通电脑一瞬间就跑完。可一旦换成更大的棋，这份奢侈立刻破产。

回想 1.1 那张复杂度表：博弈树的大小大致是“分支数”的“步数”次方，会指数级爆炸。五子棋开局每步约 225 种选择，国际象棋平均 35 种、一局约 80 回合——把整棵树走完需要的时间，远超宇宙的年龄。“算到底”在它们身上根本不可能。于是摆在我们面前的，是两个必须解决的难题：

难题一：树里有大量分支根本不必看。很多走法稍微一想就知道是坏棋，可朴素 Minimax 还是老老实实把它们全搜了一遍，纯属浪费。→ 下一节 1.4 Alpha-Beta 剪枝 专治这个，它能在不改变结果的前提下砍掉大片无用搜索。
难题二：根本到不了底，怎么办？既然搜不到终局，那就搜到一定深度先停下，再给那个中间局面估个分。这就需要一个“评估函数”。→ 这条线我们在 1.5 预演、到第二章五子棋上正式发力。

六、小结与下一节

这一节你收获了整门课最重要的一块基石：

为什么要搜索：只看一步的贪心看不见“叉”这样的布局，必输给会向前看的对手。
Minimax 思想：我求最大、假设对手求最小，靠的是“零和”这个前提；+1/−1 编码让 max/min 直接对应两个玩家。
实现与升级：十几行递归即可完美对弈；再用 depth 折扣实现“快赢慢输”，并接回 best_move() 接口。
它的天花板：完美的代价是搜完整棵树，这只在井字棋这种小游戏成立。

带着“树太大、算不完”这个问题，我们去下一节 1.4 Alpha-Beta 剪枝，看看怎么在不损失任何正确性的情况下，让 Minimax 少做大量无用功。