启发式评估函数 · aiwiki.page

启发式评估函数是一种函数，它为状态或搜索节点赋予估计的数值，使人工智能系统无需探索每一种可能的后续发展，就能比较不同选择。它体现了启发式方法：利用信息引导计算，优先考虑有前景的选择。这一术语尤其常见于博弈程序，用于估计局面的优劣；寻路中的相关函数则用于估计到达目标的剩余代价。这两种用途在评分约定和数学要求上有所不同。(inst.eecs.berkeley.edu)

博弈中的评估

在大型博弈树中，逐一考察所有后续变化直至博弈结束，通常在计算上并不可行。因此，限定深度的极小化极大算法搜索会在指定深度停止，并用 $E(s)$ 近似非终局局面的真实极小化极大值，从而评估这些局面。对于指定的最大化一方，分数越高，局面越有利。终局局面的效用值则由博弈结果决定。(inst.eecs.berkeley.edu)

区分评估与搜索十分重要：评估函数估计局面的价值，搜索算法则沿着可能的走法传递这些估计值，以选出行动。Alpha–Beta剪枝可以跳过不影响极小化极大结果的分支，但不能使叶节点的近似评估变成精确值。因此，限定深度的极小化极大搜索通常不再具备将整棵树搜索至终局时所能获得的最优博弈保证。(inst.eecs.berkeley.edu)

基于特征的评估函数与学习得到的评估函数

一种常见的人工设计评估函数是数值特征的线性组合：

E(s)=\sum_{i=1}^{k}w_i\phi_i(s),

其中， $\phi_i(s)$ 描述状态 $s$ 的某种属性， $w_i$ 决定该属性对评估值的贡献。特征工程用于识别相关属性，权重则体现这些属性的相对重要性。例如，一个简单的西洋跳棋评估函数可以统计双方普通棋子和王棋的数量，为最大化一方的棋子赋予正贡献，为对手的棋子赋予负贡献。这类公式只是近似估计，并不是确定局面真实价值的规则。(inst.eecs.berkeley.edu)

评估函数不一定是线性的，也不一定需要人工指定。人工神经网络可以通过机器学习学得非线性的局面评估。在 AlphaZero 方法中，网络同时输出各走法的概率，以及对预期博弈结果的标量估计。这些量通过自我对弈的强化学习学得，并用于引导搜索。其中，标量输出充当学习得到的评估值，而走法概率则引导搜索探索哪些行动。(arxiv.org)

寻路中的评估

对于最短路径问题，启发式函数 $h(n)$ 估计从节点 $n$ 到目标的最小剩余代价。估计值越低越好，这与博弈局面评估中常见的“越高越好”约定不同。贪心最佳优先搜索仅依据这一剩余代价估计来确定节点的优先级。(artint.info)

A星搜索将启发式估计与总体评估区分开来：

f(n)=g(n)+h(n),

其中， $g(n)$ 是已经找到的、从起点到 $n$ 的某条具体路径的代价。因此， $h(n)$ 估计的是一个解尚未完成部分的代价，而 $f(n)$ 估计的是沿当前路径继续到达目标的总代价。将这两个量都称为“启发式评估函数”，可能会掩盖这一差别。(artint.info)

可采纳性与一致性

代价估计可以满足某些形式化条件，从而支持最优搜索：

**可采纳启发式：**在通常的非负代价约定下，满足 $0\leq h(n)\leq h^*(n)$ ，其中 $h^*(n)$ 是实际的最小剩余代价。启发式估计绝不高估该代价。
**一致性：**对于从 $n$ 到 $n'$ 的每一次转移，若其代价为 $c(n,n')$ ，则满足
$h(n)\leq c(n,n')+h(n'),$
且目标节点处 $h=0$ 。

对于能够到达目标的节点，一致性蕴含可采纳性，并保证 A星搜索的评估值沿路径不会下降。一致性支持在图搜索实现中将已扩展状态永久关闭；如果启发式函数可采纳但不一致，那么发现代价更低的路径时，可能需要重新开放这些状态。最优性还取决于搜索过程及其终止条件，而不只是启发式函数的名称。(inst.eecs.berkeley.edu)

这些下界条件针对的是剩余代价估计，通常并不是博弈局面评估函数必须满足的要求。后者的目的是近似估计局面的战略价值，而不是为到达目标的代价提供界限。(inst.eecs.berkeley.edu)

构造方法与计算权衡

搜索启发式函数可以通过求解问题的松弛版本来构造，即移除原问题的部分约束。松弛问题的最优代价为原问题的代价提供一个下界。如果多个启发式函数都可采纳，那么在每个节点处取它们的最大值，得到的函数也可采纳，且其信息量不低于其中任何一个函数。(inst.eecs.berkeley.edu)

评估函数是否有用，既取决于它提供的信息，也取决于其计算开销。信息更充分的可采纳启发式函数可以减少 A星搜索扩展的路径数量，但总开销还包括计算该启发式函数的成本。在博弈搜索中，更准确的评估和更深的前瞻搜索可以改善决策，但近似评估仍然是误差的来源。因此，必须结合搜索方法和可用计算资源来衡量评估质量。(artint.info)

参考来源

2 Minimax | Introduction to Artificial Intelligenceinst.eecs.berkeley.edu
6 Summary | Introduction to Artificial Intelligenceinst.eecs.berkeley.edu
CS 188 Introduction to Artificial Intelligence, Fall 2022, Note 5inst.eecs.berkeley.edu
6 Informed (Heuristic) Search — Artificial Intelligence: Foundations of Computational Agents, 3rd Editionartint.info
4 Informed Search | Introduction to Artificial Intelligenceinst.eecs.berkeley.edu
Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmarxiv.org