第一讲 · AlphaGo 与博弈搜索

围棋每一步看起来只是“在棋盘上落一颗子”，为什么长期被认为是计算机极难攻克的游戏？AlphaGo 的关键也不是单独发明了一种更大的神经网络，而是让两类能力互相补足：

搜索负责向未来推演：“现在走这一步，后面可能发生什么？”
学习负责把计算集中到值得搜索的方向：“哪些棋更像好棋，这个局面大概有多大胜率？”

整条技术路线可以先记成

\text{极小极大搜索} \to \text{Alpha-Beta 剪枝} \to \text{蒙特卡洛树搜索} \to \text{策略网络与价值网络} \to \text{AlphaGo Zero}.

一、为什么围棋不能靠暴力枚举

围棋已有两千五百年以上的历史，课件列出的爱好者规模超过四千万。它在 $19\times19$ 的棋盘上由黑白双方轮流落子，目标是控制尽可能多的地盘。它的困难不只来自棋盘大：

一个局面常有几百个看似合理的候选落点；
一盘棋需要许多步才能结束，当前选择的后果可能很晚才显现；
相近局面的最终结果可能不同，难以手写一个准确评估函数；
判断好棋高度依赖局部与全局模式。

把游戏未来展开为树，设平均分支因子为 $b$ 、搜索深度为 $d$ ，叶节点数量大约是

b^d.

课件用数量级对比：国际象棋约为 $b\approx35,d\approx80$ ，围棋约为 $b\approx250,d\approx150$ 。后者的完整树约有

250^{150}\approx10^{360}

个叶节点。这个估算不是在要求精确计数，而是在说明：哪怕计算机每秒检查海量局面，也不可能把整棵围棋树走完。

课件给出的计算机围棋脉络也反映了方法变化：

时间	课件中的里程碑
1997	Alpha-Beta 搜索与高速计算推动计算机国际象棋达到超人水平
2006	蒙特卡洛树搜索开始用于 $9\times9$ 围棋
2007	$9\times9$ 系统达到人类大师水平
2008	$9\times9$ 系统达到人类特级大师水平
2012	Zen 在 $19\times19$ 棋盘、让四子的条件下战胜前世界冠军
2015	AlphaGo 以 $5:0$ 战胜欧洲冠军
2016	AlphaGo 以 $4:1$ 战胜李世石
2017	AlphaGo Zero 以 $100:0$ 战胜早期 AlphaGo

两份课件对 2005 年的表述一处写成“计算机围棋不可能”，另一处中文转写成“计算机围棋成功”，语义互相冲突；因此这里不把它列为已确定的里程碑。

二、先把博弈形式化

博弈论研究多个主体相互影响时的决策。人工智能中的经典博弈搜索通常先研究一个较干净的子类：

两名参与者；
完全可观察；
确定性；
零和；
有限步后结束。

围棋与井字棋都可以放进这个框架。一个博弈由以下对象描述：

初始状态：游戏从什么局面开始；
后继函数：当前局面有哪些合法行动，各自转移到什么局面；
终止测试：什么时候游戏结束；
效用函数：终局对玩家的数值收益。

通常把己方记为 Max，希望最大化收益；对手记为 Min，希望让 Max 的收益最小。

博弈与普通路径搜索的关键差别是对手不会配合。计划不能只写“我下一步怎么走”，而要覆盖对手每一种可能回应，并为每种回应准备后续动作。

三、极小极大算法

若能完整展开有限博弈树，极小极大算法会给出双方都采用最佳策略时的结果。

对终局状态 $s$ ，其值就是效用：

V(s)=U(s).

对 Max 节点，选择价值最大的孩子：

V(s)=\max_{a\in A(s)}V(\operatorname{Result}(s,a)).

对 Min 节点，假设对手会选择对 Max 最不利的孩子：

V(s)=\min_{a\in A(s)}V(\operatorname{Result}(s,a)).

这不是在说 Min 一定“恶意”，而是在用最佳对手作为最稳健的决策标准。

一个完整小树

设根节点由 Max 决策，它有三个 Min 子节点；六个叶子的 Max 收益依次为

                    Max
             /       |       \
           Min      Min      Min
          /  \      /  \     /  \
         3    9    0    7   2    6

三个 Min 节点分别取

\min(3,9)=3, \qquad \min(0,7)=0, \qquad \min(2,6)=2.

根节点再取

\max(3,0,2)=3.

所以 Max 应选择第一条分支，并按对手最佳回应后的保底收益 $3$ 评价它。

性质与限制

对有限树，极小极大算法是完备的；若对手也采用最佳策略，它给出的决策是最优的。若分支因子为 $b$ 、最大深度为 $m$ ，完整搜索时间复杂度为

O(b^m).

用深度优先方式逐层生成后继时，空间复杂度可控制为 $O(bm)$ 。真正卡住算法的是指数级时间。

无法搜索到终局时，只能在某个深度截断，并用评估函数代替终局效用。评估函数越不可靠，向上传回的极小极大值就越可能误导决策。

四、Alpha-Beta 剪枝

极小极大搜索会查看很多不可能影响最终选择的分支。Alpha-Beta 剪枝一边搜索，一边维护两个界：

$\alpha$ ：沿当前路径，Max 已经能够保证的最好下界；
$\beta$ ：沿当前路径，Min 已经能够保证的最好上界。

当出现

\alpha\ge\beta

时，后面的子树不可能改变祖先的选择，可以停止搜索。

用刚才的小树演示剪枝

按从左到右的顺序搜索：

第一组叶子为 $3,9$ ，Min 返回 $3$ ，根节点得到 $\alpha=3$ ；
第二组先看到 $0$ ，该 Min 节点至多返回 $0$ ；即使再看叶子 $7$ ，Min 仍会选不超过 $0$ 的已有分支，因此整组不可能超过根的 $3$ ，叶子 $7$ 可剪掉；
第三组先看到 $2$ ，同理 $2\le\alpha=3$ ，叶子 $6$ 可剪掉。

最终仍得到 $3$ ，与完整极小极大搜索完全相同。

剪枝不会改变结果，只减少计算量。移动顺序越好，越早检查到可能的最佳行动，就越早形成紧的 $\alpha$ 和 $\beta$ 。在理想排序下，时间可降到约

O(b^{m/2}),

相当于在相同计算预算下把可搜索深度提高一倍。

但围棋的平均分支因子仍然太大，而且难以手工写出稳定的局面评估函数。仅靠 Alpha-Beta 还不够。

五、蒙特卡洛树搜索

如果没有可靠评估函数，可以从当前局面随机走到终局，用输赢结果反过来估计当前行动。蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）不会一次展开整棵树，而是让计算集中在更有希望的分支上。

每轮包含四步。

1. 选择

从根节点出发，根据选择策略反复选择孩子，直到到达尚未完全展开的节点。

2. 扩展

为一个或多个尚未尝试的合法行动创建新子节点。

3. 模拟

从新节点继续走一局，直到终止状态，得到胜负或其他终局收益。

4. 反向传播

沿访问路径返回根节点，更新每个节点的访问次数和累计收益。

重复多轮后，一个行动的平均收益

Q_i=\frac{W_i}{n_i}

会越来越稳定，其中 $W_i$ 是累计收益， $n_i$ 是访问次数。

为什么不能只选当前胜率最高的行动

单次模拟只有很嘈杂的 $0/1$ 信号。如果永远选择当前平均收益最高的分支，某个早期碰巧失败、实际很好的行动可能再也没有机会被探索；若平均分配计算，又会把大量时间浪费在明显较差的行动上。

这就是多臂老虎机中的探索与利用矛盾：

利用：多试当前看来收益高的行动；
探索：也给尝试次数少、估计仍不确定的行动机会。

六、UCB 如何平衡探索与利用

课件给出的 Upper Confidence Bound 选择分数为

\operatorname{UCB}_i =v_i +C\sqrt{\frac{\ln N}{n_i}}.

其中

$v_i$ 是行动 $i$ 的当前平均收益估计；
$N$ 是父节点总访问次数；
$n_i$ 是该行动被访问的次数；
$C$ 控制探索强度。

第一项偏爱高回报行动，第二项偏爱尝试较少的行动。随着 $n_i$ 增大，探索奖励逐渐减小。

一个选择算例

设父节点已访问 $N=100$ 次，取 $C=0.5$ 。行动 A 的平均收益为 $0.60$ 、访问 $25$ 次；行动 B 的平均收益为 $0.50$ 、只访问 $5$ 次。

\operatorname{UCB}_A =0.60+0.5\sqrt{\frac{\ln100}{25}} \approx0.815,

\operatorname{UCB}_B =0.50+0.5\sqrt{\frac{\ln100}{5}} \approx0.980.

虽然 B 当前平均收益更低，但它的不确定性更大，这一轮会优先探索 B。若后续发现 B 确实差，访问次数增加后，它的探索奖励会下降。

七、AlphaGo 为搜索加入学习

朴素 MCTS 仍有两个瓶颈：每个局面可选行动太多，随机模拟还要走很深才到终局。AlphaGo 用两个网络分别解决它们。

策略网络减少分支

策略网络输入棋盘状态 $s$ ，输出各合法行动成为好棋的概率：

p(a\mid s).

它不会直接证明某一步必胜，而是告诉搜索“先看哪些分支”。课件中的 AlphaGo 先使用约三千万个人类专家棋局局面做监督学习，学习预测专家落子；随后通过超过十二万八千局自我对弈继续进行强化学习，使策略直接朝提高胜率的方向优化。

策略网络的作用是把巨大的候选集合排序，让高先验概率行动获得更多搜索预算。

价值网络减少深度

价值网络输入局面 $s$ ，直接估计当前一方最终获胜的概率或期望结果：

V(s)\approx\mathbb E[z\mid s].

有了它，不必每次都随机走到终局，搜索可以在中间局面得到一个学习出来的评估。课件把价值网络训练描述为基于大规模自我对弈局面，以随机梯度下降最小化预测值与最终结果之间的均方误差。

策略网络主要降低有效分支因子，价值网络主要缩短需要模拟的深度。

八、MCTS 与两个网络怎样协作

AlphaGo 的一轮搜索仍然遵循选择、扩展、模拟、反向传播，但每一步都获得网络帮助。

选择

选择分数可概括为

Q(s,a)+u(s,a;P),

其中 $Q$ 是搜索积累的行动价值， $u$ 根据策略网络先验 $P$ 和访问次数鼓励探索。搜索刚开始时 $Q$ 还没有统计证据，先验概率高且访问少的行动会优先；访问增多后，实际搜索结果逐渐主导。

扩展

遇到新叶节点时，策略网络为合法行动提供先验概率，用于建立和排序子节点。

评估

课件中的 AlphaGo 并行运行多次模拟：一部分使用价值网络估计局面，一部分继续快速 rollout 到终局。二者结合，既利用学习到的局面判断，也保留实际对弈结果。

反向传播

把评估值沿搜索路径传回根节点，更新累计价值与访问次数，再开始下一轮选择。

经过大量重复，最终落子不只取决于网络的一次输出，而是网络先验与搜索证据共同决定。

九、AlphaGo Zero 的变化

课件把两代系统的训练来源概括为：

系统	人类棋谱监督	自我对弈强化学习
AlphaGo	有	有
AlphaGo Zero	无	有

AlphaGo Zero 不再先模仿人类专家，只从棋规和自我对弈出发学习策略与价值。课件列出的结果是 AlphaGo Zero 以 $100:0$ 战胜早期 AlphaGo。

这里最值得带走的不是比分，而是方法论变化：系统可以让当前网络指导搜索，再把搜索得到的更强决策作为新训练目标，通过自我对弈反复提升。

十、把整条路线压缩成一句话

极小极大算法告诉我们如何面对最佳对手；Alpha-Beta 剪掉不影响结果的精确分支；MCTS 用随机模拟处理无法穷举的巨大搜索空间；UCB 分配探索预算；策略网络指出值得搜索的行动；价值网络估计不必走到终局的局面。

最终形成的闭环是

\text{学习提供先验与评估} \longrightarrow \text{搜索改进决策} \longrightarrow \text{自我对弈产生新经验} \longrightarrow \text{继续学习}.

课件最后强调，把搜索与学习结合并不只适用于围棋。只要问题既包含庞大的决策空间，又能从经验中学到“哪里更值得看”，这套思路就具有迁移价值。

课件也提醒，围棋相对开放世界仍属于结构清晰的问题：规则固定、状态可观察、输赢反馈明确。真正复杂的现实任务还会加入隐藏信息、变化规则、多主体合作和难以定义的目标。