RedMoon / 训练日志

· 人工智能导论 / 启发式搜索 / 博弈树

人工智能导论 Day3:启发式搜索、与或图与博弈决策

RedMoon · 2026-09-22 · 课堂笔记

上节课比较了 BFS、DFS 和 UCS,这次我想弄清楚:已经知道一点目标的信息,能不能少搜一些节点?A* 从这个问题出发。之后的问题逐渐变了:一个目标需要多个子任务共同完成,该怎样表示?如果下一步由对手决定,又该怎样选择?

一、从找路径到做决策

问题 核心表示 如何选择下一步 解的形式
找一条低代价路线 状态空间图 UCS 看已走代价,A* 加入剩余估计 动作或状态序列
完成有依赖的任务 与或图 在备选方案与共同义务之间回传代价 解树或解子图
应对理性对手 博弈树 按双方目标交替取最大、最小 针对回应的策略
在巨大博弈空间中有限计算 带统计量的搜索树 网络先验、价值估计与模拟统计引导搜索 当前局面的行动选择

“如何表示问题”和“如何分配搜索资源”是两个层面。表中几类方法面对的结构不同,选择时需要先确定求解对象是一条路线、一组相互依赖的任务,还是应对对手的策略。

二、启发式搜索:不仅看走了多远,还要估计剩多少

1. UCS、贪心最佳优先与 A*

课堂从路径规划引出评价函数。记 $g(n)$ 为从起点沿当前记录路径到节点 $n$ 的累计代价,$h(n)$ 为从 $n$ 到目标的估计剩余代价:

\[f(n)=g(n)+h(n).\]
策略 优先队列的排序依据 主要取舍
UCS,一致代价搜索 $g(n)$ 不借助目标方向;在相应条件下求最低代价路径
贪心最佳优先搜索 $h(n)$ 朝估计接近目标的方向搜索,但不保证最低总代价
A* $g(n)+h(n)$ 同时考虑已付成本和后续估计,最优性取决于启发函数及重复状态处理

BFS 按层次、DFS 按栈式次序,UCS 按累计代价排序。贪心最佳优先会保留 frontier 中的备选节点,这与只沿局部选择前进的爬山法不同。在有限图上正确去重,它可以具有完备性,但仍不保证最优;无限空间或不处理环的实现则可能无法终止。

A* 每次从整个 OPEN/frontier 取最小 $f$ 节点,不是只比较刚展开节点的几个孩子。$g(n)$ 也不是一经发现就等于最短路:后来可能找到更便宜的路径,需要松弛更新。

2. 课件地图例子:近目标不等于总代价小

Arad 到 Bucharest 的两条候选路线为:

  • 经 Sibiu、Fagaras:$140+99+211=450$。
  • 经 Sibiu、Rimnicu Vilcea、Pitesti:$140+80+97+101=418$。

只看“下一座城市离目标的直线距离”容易先偏向 Fagaras;A* 还会比较其他 frontier 节点的已走代价与剩余估计。正确停止条件下,它不会因为第一次生成了一条到目标的路线,就认定搜索结束。第二条路线比第一条少 32 个距离单位。

估计距离可以忽略障碍,为剩余代价提供下界;实际选出的路线仍须遵守地图上的通行条件。两者分别承担评价与行动的作用。

3. 最优性究竟需要什么

记真实最小剩余代价为 $h^*(n)$。常见非负启发函数满足:

\[0\le h(n)\le h^*(n),\qquad h(G)=0.\]

这叫可采纳性,即不高估剩余最优代价。一致性要求每条边满足:

\[h(n)\le c(n,n')+h(n').\]

它像三角不等式,也使路径上的 $f$ 值不会下降。两者在不同实现中的职责不同:

  • 树搜索版 A* 在通常的终止条件下,以可采纳启发函数保证最优性。
  • 图搜索若对 CLOSED 节点永不重开,通常需要一致性。
  • 可采纳但不一致时,发现更优 $g$ 后正确重开节点,可以恢复相应的最优性保证。

无限状态空间的完备性还需要条件,例如有限分支、存在有限代价目标、边代价有正下界。有限非负加权图中,$h=0$ 的 A* 就按 UCS/Dijkstra 的方式排序。一份实现是否保证最优,取决于启发函数的性质与 CLOSED 的处理方式。

课件中的不一致启发案例说明了后一点。边为 $S\to A:1$、$S\to B:1$、$A\to C:1$、$B\to C:2$、$C\to G:3$;启发值为 $h(S)=2,h(A)=4,h(B)=1,h(C)=1,h(G)=0$。这些值不高估,但 $A\to C$ 不满足一致性。搜索可能先经 $B$ 以 $g(C)=3$ 展开 $C$,随后才经 $A$ 发现 $g(C)=2$。不重开 $C$ 就可能返回代价 6,而最优解代价为 5。

4. 启发函数与实现检查

四邻接、每步代价为 1 的网格可以用曼哈顿距离:

\[h(n)=|x_n-x_G|+|y_n-y_G|.\]

欧式距离适合提供直线距离下界。允许对角移动且其代价为 $\sqrt{2}$ 时,曼哈顿距离可能高估;可考虑欧式距离或与移动规则匹配的 octile distance。曼哈顿距离与马氏距离也要分清:后者即 Mahalanobis distance,考虑的是协方差结构。

A* 实现有四个检查点:保留每个状态的最佳 $g$ 与父指针;更优路径到来时更新;跳过优先队列中的过期条目;在目标以合适的最小优先级出队时停止,而不是生成目标时停止。不一致启发式还需要重开逻辑。

更接近真实代价的启发函数通常能减少无效扩展,但计算 $h$ 本身有开销,平局顺序也影响展开数量。不能据此断言运行时间必然更短。A* 需要保存大量节点,最坏情形仍可能有指数级时间、空间需求。

三、问题规约:一个任务可能要求多个子任务共同成立

1. OR 是备选方案,AND 是共同义务

路径搜索问“下一步走哪里”;问题规约问“完成这个目标,需要先完成什么”。把一个复杂目标分解为子目标,就得到与或关系:

  • OR 节点:有多个可替代方案,至少一个成功即可。
  • AND 节点:某个方案提出多个共同要求,必须全部成功。
  • 已解决终止节点:对应可直接确认完成的本原问题。

“没有展开”不等于“不可解”。只有根据规则证明无法解决,才应标为失败或无穷代价。已解决节点的状态向上回传:OR 只需一个可解孩子;AND 要求所有必需孩子都可解。OR 失败要所有方案失败,AND 则只要一个必需子问题失败就不能成立。

解不一定是一条路径,而是从根出发,在 OR 处选择方案、在 AND 处保留所有义务的解树。若有共享子问题,底层更准确地说可能是解子图。

2. 代价回传与希望树

为避免与 A* 的已走代价混淆,用 $J(n)$ 表示解决子问题 $n$ 的估计代价。在可加、没有重复计算共享成本的模型下:

\[J_{\mathrm{OR}}(n)=\min_i\{c(n,n_i)+J(n_i)\},\] \[J_{\mathrm{AND}}(n)=\sum_i\{c(n,n_i)+J(n_i)\}.\]

已解决本原问题可取 0,确认无解的节点取 $\infty$。若衡量的是可并行任务的完成时间,AND 聚合才可能取最大值,并需要资源与依赖假设;不能不加说明地把求和换成最大值。共享子问题和环也需要专门处理,否则可能重复计费或循环展开。

课堂中的“希望树”可以理解为当前估计下最有希望的候选解:先在 OR 处标记当前最优方案,在 AND 处保留全部必需分支;沿该结构选择尚未解决的叶子展开;再自底向上更新代价和可解状态。新信息可能使一个 OR 节点改选另一方案,因此修正不只发生在刚展开的节点。AO* 的关键就在于生成和回传交替进行。

根被标为可解,表示有了可用方案;要进一步声称最低代价,还需启发估计、回传与终止规则满足最优性条件。与或图是更明确的结构表示,不意味着逻辑问题绝对不能编码成普通状态空间搜索。

3. 课堂例子:汉诺塔与共享子问题

把 $n$ 个盘从 A 移到 C,需要顺序完成:将上面 $n-1$ 个盘从 A 移到 B;把最大盘移到 C;将 $n-1$ 个盘从 B 移到 C。这是带顺序依赖的共同义务,不是三个可以任意并行的动作。

\[T(n)=2T(n-1)+1,\quad T(1)=1,\quad T(n)=2^n-1.\]

三个盘需要 7 步。它既能用“每个合法摆放是状态”的状态空间描述,也能用递归子任务分解描述;前者强调状态转移,后者强调解决方案的结构。

课堂还用兔子繁殖引出递推。按课件的编号方式可写 $F_0=F_1=1$,$F_{n+2}=F_{n+1}+F_n$。朴素递归会反复计算相同子问题,记忆化或动态规划则共享这些结果。因此,含共享节点的解图不能直接当作树处理。

四、博弈树:把对方的回应放进自己的决策

1. 极大极小的适用前提

双人、零和、确定性、完全信息、轮流行动的棋类是标准 Minimax 模型的典型对象,但不是所有博弈都具有这些性质。课堂提到的囚徒困境通常是非零和、同时行动的模型,适合讨论个体激励与均衡,不能直接当成轮流落子的零和棋局。

固定以 MAX 一方为收益视角,终局给定收益 $U(s)$,则:

\[V(s)=\begin{cases} U(s), & s\text{ 是终局},\\ \max_{a}V(T(s,a)), & \text{轮到 MAX},\\ \min_{a}V(T(s,a)), & \text{轮到 MIN}. \end{cases}\]

MAX 选择在对方最佳回应下收益仍然最大的行动;MAX 层与 MIN 层代表不同决策者,分别取最大值与最小值。若只搜到固定深度,叶子使用启发式评估,其值不再是完整终局证明。

从 MAX 的胜负证明看,这与 AND-OR 有联系:轮到 MAX 时,存在一个获胜走法即可;轮到 MIN 时,必须保证其所有合法回应都不能破坏 MAX 的胜利。但带数值效用的 Minimax 仍应按最大/最小回传,而不是直接套用任务成本求和。

2. Alpha-Beta:不再计算已经影响不了选择的分支

$\alpha$ 是当前搜索上下文中 MAX 已能保证的下界,$\beta$ 是 MIN 已能保证的上界。当 $\alpha\ge\beta$,这条分支的进一步探索不能改变祖先的相关选择,可以剪枝。

以一棵小树为例:根为 MAX,两个孩子为 MIN。左孩子的叶值为 3、5,回传 3,于是根已有下界 3。右孩子先看到一个叶值 2,其最终最小值至多为 2;再看另一个叶值 9 也不可能使它优于左边的 3,因此 9 可以不访问。

在同一深度、同一评估函数下,正确 Alpha-Beta 保留 Minimax 的根值;相同最优值的行动可能因遍历次序不同而选得不同。对于近似均匀、分支因子为 $b$、深度为 $d$ 的树,良好排序下最好约为 $O(b^{d/2})$,最坏仍为 $O(b^d)$。“平方根级别”是特定理想口径,不是每棵树都有的固定收益。

课件的一字棋评估用双方仍可能获胜的线路数之差表达局势,即 $e(+P)-e(-P)$。这是深度截断时的启发评价,不是必胜证明。走法排序、对称局面合并与评估函数,都能改变有限计算预算下的效果。

五、AlphaGo:学习提供判断,搜索组织计算

围棋的难点既有大量合法走法,也有难以短视判断的长期后果。AlphaGo 的核心不是把 A* 或 Alpha-Beta 直接放大,而是神经网络引导的蒙特卡洛树搜索(MCTS)。

1. 四步搜索循环

  1. 选择:在已建树中权衡当前价值估计、访问次数和策略先验,沿路径向下走。
  2. 扩展:到达待扩展局面后创建后续搜索结构,并引入合法动作的先验。
  3. 评估:通过价值网络及相应版本的模拟机制,估计该局面的结果。
  4. 回传:沿访问路径更新统计量,供后续迭代选择。

策略网络输出动作概率,帮助分配搜索预算,并不保证概率最大的动作就最优,也不意味着其他合法动作全部被删除。价值网络估计结果,减少必须走到终局才能评价的成本,但估计仍可能出错。

用一种 PUCT 风格的分数,可以看清选择时考虑的几项:

\[Q(s,a)+c\,P(s,a)\frac{\sqrt{\sum_b N(s,b)}}{1+N(s,a)}.\]

$Q$ 表示统计价值,$P$ 是网络先验,$N$ 是访问次数,$c$ 控制探索强度。高估值值得利用,少访问但先验不错的动作也值得探索。这个形式展示了策略先验怎样进入探索项,具体 AlphaGo 版本的实现仍有区别。回传时还要统一收益视角:从根玩家还是当前行动玩家来看结果,决定了是否需要逐层变号。

2. AlphaGo 与 AlphaGo Zero

维度 AlphaGo,2016 年论文 AlphaGo Zero,2017 年论文
训练数据起点 人类棋谱监督学习,再进行自我对弈强化学习 不以人类专家棋谱训练,从规则出发自我对弈
网络角色 策略网络与价值网络等组件协作 联合输出策略和价值的网络
叶子评估 价值网络与快速 rollout 结果结合 网络价值评估,不使用快速 rollout
共通点 神经网络与 MCTS 协作 神经网络与 MCTS 协作

2016 年 AlphaGo 同时使用价值网络和 rollout,AlphaGo Zero 则用网络价值评估叶子。训练与落子承担不同职责:自我对弈用于更新网络,落子时的搜索则把计算分配到当前局面的候选行动上。

MCTS 根据有限采样和估计做决定,结果的含义与穷尽博弈树得到的 Minimax 值不同。网络提供初始判断,搜索再根据当前局面分配计算,避免每次都从头穷举。

这两个版本分别对应 Silver 等的两篇论文:2016 年的 Mastering the game of Go with deep neural networks and tree search,以及 2017 年的 Mastering the game of Go without human knowledge。

六、搜索方法的适用结构与保证

A* 利用不高估剩余代价的启发估计指导搜索;问题规约寻找能够完成所需子任务的方案;对抗搜索将对手的最佳回应纳入决策。它们都在缩小计算范围,但各自保留正确性的理由并不相同。

A* 的 $h$ 是代价估计,Minimax 的叶值是局面收益,MCTS 的 $Q$ 是采样统计。把它们都叫“评分”没有错,却会遮住单位、更新规则和保证条件。工程实现前,应先说明分数代表什么,再讨论分数越大还是越小越好。

“解得出来”和“解得最优”需要区分:与或图的根可解、找到一条到终点的路径、模拟中经常获胜,都不自动等于一个全局最优结论。

七、复习问题

复习时尝试不看笔记回答:

  1. 为什么 UCS 是按 $g$ 排序,而不是所有盲目搜索都按 $g$ 排序?
  2. 可采纳与一致各约束什么?为什么不一致启发式可能需要重开节点?
  3. 为什么 A* 第一次生成目标不能立即结束?四邻接与八邻接的距离估计如何选择?
  4. AND 节点为什么要求全部子问题成功?为什么“全部”不代表“并行”?
  5. 希望树展开后,为什么需要沿祖先回传并允许 OR 节点改选方案?
  6. Alpha-Beta 为什么不改变同一搜索深度下的 Minimax 根值?访问顺序如何影响效率?
  7. 策略网络、价值网络、MCTS 各自负责什么?AlphaGo 与 AlphaGo Zero 的 rollout 有什么不同?