Sherfiter's wiki for fun

第 3 章 · 对抗搜索

前一章的搜索里环境是「死的」(迷宫不会反击你);现在加入对手。博弈(游戏)搜索的核心变化:你的最优决策取决于对手的最优应对。极小极大算法给出数学上最稳妥的答案(假设对手理性),alpha-beta 剪枝把它提速到可实用——1997 年深蓝战胜卡斯帕罗夫,靠的就是这套框架 + 海量硬件。本章从两人零和博弈出发,直到蒙特卡洛树搜索(AlphaGo 的骨架)。

3.1 博弈的形式化:MIN 与 MAX 交替的树

两人零和博弈(你赢我输,总账为零)的形式化:初始状态、谁走(MAX 先)、动作集合、终止状态与效用值(赢 +1 输 −1 和棋 0)、以及玩家交替的规则。棋局展开成一棵博弈树:MAX 层和 MIN 层交替,叶子上挂效用值。

井字棋的树全展开约 549946 个节点,国际象棋的博弈树约 10^40——穷举永远不可能,对抗搜索的全部智慧就是「不看完也能下对」。

3.2 极小极大:假设对手最优

极小极大(minimax)递归定义:MAX 节点取子节点的最大值,MIN 节点取最小值:

         MAX: max(3, 5) = 5
        /                \
   MIN: min(3,12)     MIN: min(5,2)
      /    \             /    \
     3     12           5      2

解读:MAX 站在根,若走左路,对手(MIN)会在下一层把局面压到 3;走右路对手压到 5。MAX 选 5。这套值叫后备值(backup value):叶子的效用沿树向上「MIN 取最小、MAX 取最大」地传播,根上的值就是「双方都理性时的最终结果」。井字棋的极小极大值是 0(双方完美对弈必和棋)——这是数学定理,不是经验。

极小极大是深度优先的(先算完一条线再回来),空间线性;时间 O(b^m),b 平均分支、m 深度——象棋必死,所以需要剪枝与截断。

3.3 alpha-beta 剪枝:同样的答案,快一个数量级

核心洞察:有些分支根本不用看。在上面的例子里,MAX 看完左路知道「至少能得 3」(α = 3);进入右路,MIN 的第一个孩子是 5,MIN 立刻知道「我这一路最多让它 5」;但 MAX 手里已有 3……关键场景是 MIN 某个孩子 ≤ α 时,MIN 的最终值必 ≤ α,MAX 在左路已有 ≥ α,这条右路对 MAX 毫无吸引力,剩下的兄弟全部跳过。

两个哨兵:α(MAX 目前能保证的下界)、β(MIN 目前能保证的上界),α ≥ β 时剪枝(β 截断/α 截断)。效果:最好情况时间复杂度从 O(b^m) 降到 O(b^(m/2)) ——等效于「搜索深度翻倍」,一个剪枝换来两倍的棋力,这就是深蓝敢往前算 12 层以上的底气。剪枝顺序决定效率:先检查「看起来最好」的走法(用启发式排序,如吃子优先),剪枝率最高;随机顺序时 alpha-beta 退化为接近裸 minimax。

3.4 不完全搜索:评估函数与截断

搜不到底怎么办?在深度 d 截断,用评估函数(evaluation function)给中间局面打分,把分数当叶子值向上传播:

国际象棋经典评估:局面分 = 己方子力 + 位置分 − 对方子力
(兵 100 分,马/象 300,车 500,后 900;王安全、控制中心另加)

评估函数是对弈程序的灵魂,它把「棋感」变成数字。它的两个陷阱:评估的误差会沿树放大(浅层截断的「视野」问题,著名的水平线效应:截断点之后的大灾难看不见);评估函数越复杂单次越慢(算得准 vs 算得多的权衡)。深蓝的配方 = 快而糙的评估(专用芯片每秒 2 亿局面)+ 极深搜索 + 开局库 + 残局库。『搜索 + 评估』的框架统治了棋类 AI 直到 2017 年——AlphaGo 换掉了评估的来源(神经网络学出来的),搜索的骨架(MCTS)仍在。

3.5 蒙特卡洛树搜索(MCTS):随机性换确定性

围棋分支因子 361²,评估函数没人写得出来(棋盘太复杂,「子力」直觉失效)。AlphaGo 前身(Monte Carlo Go)给出新思路:不用评估函数,直接随机对局(playout)到终局数胜负。MCTS 的四步循环:

① 选择:从根出发,按 UCB 公式选子节点走到叶
   UCB = 平均胜率 + C·√(ln 父访问次数 / 本节点访问次数)
   (利用「常赢的路多走」与「没试过的路也要试」的平衡,多臂老虎机的解法)
② 扩展:给叶加一个新节点
③ 模拟:从新节点随机下到终局
④ 反向传播:胜负沿路径回传,更新每节点的统计

跑得越久,树向「有希望的分支」倾斜得越精准(UCB 的探索-利用平衡)。AlphaGo = MCTS + 两个神经网络(策略网络:代替「随机 playout」给出像样的落子;价值网络:代替「对局到底」直接估计胜率),AlphaZero 再进一步:完全不用人类棋谱,自我对弈从零学会围棋、国际象棋、将棋,且碾压所有人类与旧程序。「学习 + 搜索」的组合在 2017 年完成了对「手工评估 + 暴力搜索」的接力。

常见认知误区

  • 「minimax 是下棋 AI 的全部」。它是价值框架;工程上评估函数、走法排序、置换表(缓存重复局面)占代码量九成。
  • 「对手最优假设过于悲观」。对手乱下时 minimax 值偏保守;应对有 max^n、期望极小极大(对手按概率走)等变体,扑克这类「不完全信息博弈」要另起炉灶(Counterfactual Regret Minimization,2019 年击败德扑顶尖选手的 Libratus 用它)。
  • 「alpha-beta 改变了搜索结果」。它只砍「不影响决策」的分支,返回值与裸 minimax 完全一致(正确性证明的核心),只是快。
  • 「MCTS 优于 minimax」。分场景:围棋(评估难写)MCTS 完胜;国际象棋(评估成熟、分支可剪)经典 minimax + 剪枝仍然最强之一。工具没有王座,只有匹配。

练习

  1. 动手:实现井字棋的 minimax(带 alpha-beta),双人对战验证「AI 从不输」;统计开启剪枝前后的节点访问数(预期差一个数量级)。
  2. 手算:给一棵四层博弈树(自己标叶值),手工跑一遍 alpha-beta,标出每处剪枝(α/β 截断),验证与裸 minimax 的根值一致。
  3. 动手:给 2.5 的迷宫 A* 加一个「怪物会追你」的机制:每步怪物沿 BFS 逼近,玩家用 minimax 搜 3 层(玩家一步、怪物一步、玩家一步),体会「对抗搜索」与「单人搜索」的状态空间差异。
  4. 思考:AlphaZero 不看任何人类棋谱却超越人类,这被当作「搜索 + 学习」范式的胜利。结合第 4 章将学的知识推理,讨论:这类「从零自学」的系统能学到「人类未发现的棋理」吗?它对「知识从何而来」这个古老问题给出什么启示?
豫ICP备2026027944号