1.7 蒙特卡洛树搜索 MCTS
前面那条“搜索 + 评估函数”的路线有个硬前提：你得会写评估函数。可对围棋这样的游戏，几十年里没人写得出一个像样的评估函数。这一节的 蒙特卡洛树搜索（MCTS, Monte Carlo Tree Search）给出了一个出人意料的破局思路：干脆不写评估函数，靠“随机试下很多盘”来判断局面好坏。它也正是下一节 AlphaZero 的骨架，我们用井字棋把它的四个步骤讲透。
一、动机：要是我连评估函数都不会写呢？
设想你面对一个完全陌生的局面，既不懂什么棋型，也说不清谁占优。有没有办法不靠任何专业知识，也能估出这个局面的好坏？
蒙特卡洛方法的回答近乎“耍赖”却异常有效：从这个局面出发，让双方都瞎走，一路随机走到分出胜负；这样的“随机对局”跑上成百上千盘，统计一下你的胜率。胜率高，说明这个局面大概率对你有利；胜率低，说明它不妙。这种“随机走到底看结果”的过程叫一次模拟（simulation / rollout）。
神奇的是，它完全不需要领域知识——你只要会判断“终局谁赢了”（这正是我们 1.2 写好的 winner()），就能给任意中间局面估出一个分。用随机和统计来估算一个难算的量，这类方法统称蒙特卡洛。先看一眼最朴素的模拟：
import copy, random
def random_playout(game):
"""从当前局面开始，双方都随机落子，一直走到终局，返回 winner()。"""
sim = copy.deepcopy(game)
while not sim.is_terminal():
sim.make_move(random.choice(sim.legal_moves()))
return sim.winner() # +1 先手胜 / -1 后手胜 / 0 和棋二、MCTS 的四个步骤：把模拟用在刀刃上
不过，从根局面无脑地随机模拟太浪费——好棋坏棋都分到一样多的模拟次数。MCTS 的聪明之处在于：它一边模拟，一边长出一棵树，并把越来越多的模拟集中到“看起来更有希望”的走法上。具体是把下面四步重复成千上万次：
- ① 选择（Selection）：从根出发，按一个公式（下面的 UCT）一路挑“最值得看”的子节点往下走，直到走到一个还没充分展开的节点。
- ② 扩展（Expansion）：给它新长出一个还没试过的子节点（对应一步还没探索的走法）。
- ③ 模拟（Simulation）：从这个新节点开始，做一次随机 playout，走到底拿到胜负。
- ④ 回传（Backpropagation）：把这次的胜负结果，沿着刚才走下来的路径一路更新回去（每个节点记一笔“访问 +1、收益 +结果”）。
第①步的“按公式挑”，用的是大名鼎鼎的 UCT 公式。它要解决一个两难：到底该多去试那些目前胜率高的走法（利用），还是去试那些还没怎么试过的走法（探索，万一是潜力股呢）？UCT 把这两者加在一起权衡：
UCT(i) = wi / ni + c · √( ln N / ni )
式子里：ni 是这个走法被访问过的次数、wi 是它历次模拟累计的收益、N 是父节点的总访问次数，c 是调节探索强弱的系数。等号右边的两项，正好对应“利用”和“探索”这对两难：
- wi / ni（利用项）：这个走法过去的平均收益——历史表现越好，这一项越大。
- c · √( ln N / ni )（探索项）：被试得越少（ni 越小），这一项越大，等于给冷门走法一份“该去看看”的加成。
两项一加，c 控制谁占的分量更重（井字棋取 1.4 左右即可）。正是这个简单的加法，让 MCTS 自动地“多花时间研究好棋、又不彻底冷落生棋”。
三、写成代码，并与 α-β 对比
把四步落成代码，核心是一个记录“访问次数、累计收益”的 Node，外加一个重复四步的主循环。下面是结构化的写法（聚焦骨架，省略部分细节）：
import math
class Node:
def __init__(self, game, parent=None, move=None):
self.game, self.parent, self.move = game, parent, move
self.children = []
self.wins = 0.0 # 累计收益
self.visits = 0 # 被访问次数
self.untried = game.legal_moves() # 还没扩展的走法
def uct_select(node, c=1.4):
"""① 选择：用 UCT 从已扩展子节点里挑最值得看的一个。"""
def uct(ch):
return ch.wins / ch.visits + c * math.sqrt(math.log(node.visits) / ch.visits)
return max(node.children, key=uct) # 用 max+key，省去手写比较
def mcts(root, iterations=2000):
for _ in range(iterations):
node = root
while not node.untried and node.children: # ① 一路 UCT 下行
node = uct_select(node)
if node.untried: # ② 扩展一个新走法
move = node.untried.pop()
g = copy.deepcopy(node.game); g.make_move(move)
node = Node(g, parent=node, move=move)
node.parent.children.append(node)
result = random_playout(node.game) # ③ 随机模拟到底
while node is not None: # ④ 沿路回传
node.visits += 1
node.wins += result # 注意：实战要按“该节点站在谁的视角”调整正负号
node = node.parent
return max(root.children, key=lambda ch: ch.visits).move # 选最常被访问的走法这里有个 MCTS 最容易踩的坑，提醒你一句：回传那行的正负号其实要看“这个节点轮到谁”。一次模拟结果对先手是好事，对后手就是坏事，所以严谨实现里要根据节点对应的行棋方翻转结果的符号。上面为了讲清骨架先略过了它，你自己实现时务必处理好，否则 AI 会越下越糊涂。
跑完 iterations 次后，我们选根节点下访问次数最多的那个走法（被反复验证过、最稳），而不是胜率最高的（可能只试过一两次，是侥幸）。和上一节的 α-β 摆在一起，差别很能说明问题：
| 对比项 | α-β（搜索 + 评估） | MCTS（蒙特卡洛） |
|---|---|---|
| 要不要评估函数 | 要，且好坏决定一切 | 不要，只需会判终局胜负 |
| 给出的结果 | 精确的极小化极大值 | 统计意义上的估计 |
| 能否随时叫停 | 要搜完一层才靠谱 | 可以，跑得越久越准（anytime） |
| 领域知识依赖 | 高 | 低 |
在井字棋上，只要迭代次数够多，MCTS 也能下到完美——当然这是杀鸡用牛刀，纯为演示。它真正大放异彩的地方，是像围棋那种“写不出评估函数”的游戏。
四、反思：随机的代价，以及那个改变一切的补救
但纯随机的 MCTS 有个明显软肋：模拟是瞎走的，噪声很大。在战术尖锐的棋里（比如五子棋有“连续冲四”的必杀），瞎走的模拟经常把一个其实必胜的局面走输，于是估值严重失真。事实上，纯随机 rollout 的 MCTS，在五子棋、国际象棋上往往还打不过一个浅层的 α-β——这点可能和你的直觉相反。
问题出在两个“太笨”的地方：其一，模拟时双方瞎走（rollout 策略是随机的）；其二，选择时对没试过的走法一视同仁（没有任何先验偏好）。要是能让这两处“变聪明”，MCTS 就能脱胎换骨。
那个改变了整个领域的答案是：用一个神经网络来同时补上这两处。让网络的价值输出替代“随机走到底”，直接估出局面好坏；让网络的策略输出替代“一视同仁”，告诉 MCTS 哪些走法更值得优先探索。这，就是 AlphaZero。我们下一节就在井字棋上把它亲手训出来。
五、小结与下一节
- 蒙特卡洛思想：不写评估函数，靠大量随机模拟的胜率来估局面，只需会判终局。
- MCTS 四步：选择（UCT）→ 扩展 → 模拟 → 回传，反复成千上万次；UCT 平衡“利用”与“探索”。
- 与 α-β 互补：α-β 精确但依赖评估函数，MCTS 不需领域知识、可随时叫停但有噪声。
- 软肋与出路：纯随机模拟噪声大；用神经网络替代随机 rollout 与均匀先验，就升级成了 AlphaZero。
铺垫到此为止，激动人心的部分来了。下一节 1.8 迷你 AlphaZero，我们要在井字棋这个小沙盘上，用你的 5070 Ti 把一个“会自我对弈、从零学棋”的神经网络几分钟训练出来——这是理解 AlphaZero 最好的方式。