1 绪论

人工智能（Artificial Intelligence，AI）是以机器为载体所展示出来的人类智能，因此人工智能也被称为机器智能（Machine Intelligence）。

本章介绍人工智能的起源与发展，以及实现人工智能的五大核心方法：以符号主义为核心的逻辑推理、以问题求解为核心的探寻搜索、以数据驱动为核心的机器学习、以行为主义为核心的强化学习、以博弈对抗为核心的决策智能。

1.1 人工智能的起源

1955年8月，John McCarthy、Marvin Minsky、Claude Shannon和Nathaniel Rochester四位学者在一份题为《人工智能达特茅斯夏季研究项目提案》的项目建议书中，首次使用了“Artificial Intelligence（人工智能）”这个术语。

1956年夏天，这批学者在达特茅斯学院召开研讨会，研究“让机器能像人那样认知、思考和学习的机器”，标志着人工智能正式登上人类历史舞台。

该提案列举了人工智能需要研究的七个方面问题：

编号	研究问题
1	自动计算模拟人脑高级功能
2	使用通用语言进行计算机编程以模仿人脑推理
3	神经元相互连接形成概念
4	对计算复杂性的度量
5	算法自我提升
6	算法的抽象能力
7	随机性与创造力

人工智能的定义：人工智能是以机器为载体所实现的人类智能或生物智能。

从人工智能的计算性和智能性角度，产生了两个核心问题：

• 承载计算之能的器械如何产生：推动了从手工计算到自动计算的迈进。
• 如何利用计算之器来模拟人类智能：形成了符号逻辑（以推理为核心）、联结主义（以统计机器学习为手段）和行为学派（从环境交互中进行策略学习）等不同研究方法。

1.2 可计算载体：形式化与机械化

早期数学概念（如公理或定理）一般通过自然语言描述，但自然语言难以精确表达数学概念。因此，研究人员开始用符号来表达数学概念，即通过形式化语言来刻画数学概念。

形式化系统

如果所有数学概念都可被形式化描述，给定一组推理规则后，就可从已有知识（公理、定理、命题等）出发，推导出新的知识。这样的系统被称为形式化系统。

形式化系统需要具有的三个性质：

性质	说明
完备性	所有能够被推导出来的知识，都可以从这个形式化系统推导出来
一致性	所有可推导出来的知识不会同时推导出其否定，即形式化系统是自洽的、非矛盾的
可判定性	对于形式化系统推导得到的任何知识，存在算法可在有限步内判定其为真或为假

哥德尔不完备定理

1931年，哥德尔发表了论文《论数学原理及有关系统中不可判定命题》，提出哥德尔不完备定理：

• 任何表达力足够强的（递归可枚举）形式系统都不可能同时具有一致性和完备性。
• 这个系统本身的一致性不能在系统内被证明。

哥德尔不完备定理触及了不可计算这一难题，即有些数学问题是不可求解的（不可判定问题）。

图灵机模型

1937年，图灵发表了《论数字计算在决断难题中的应用》论文，提出了现代计算机的理论模型——图灵机模型。

图灵机的组成：

• 一条两端无限长的纸带，纸带上为可擦写小方格
• 程序控制器存储若干指令集
• 读写控制指针从左到右依次读入信息，触发指令执行操作，将计算结果写入纸带

邱奇-图灵论题：凡是可计算的函数都可以用图灵机计算。原始递归函数、λ-演算和图灵机在功能上是等效的。

计算模型	特点	与人工智能的关系
原始递归函数	从数学角度研究可计算问题	无法成为“机器载体”
λ-演算	从数理逻辑角度研究可计算问题	无法成为“机器载体”
图灵机	通过机械化机制进行“计算”	成为现代计算机的理论模型，是人工智能的“机器载体”

图灵机模型成为现代计算机的理论模型，推动了自动计算时代的到来。图灵也被誉为理论计算机之父，计算机界最高奖图灵奖即以他的名字命名。

1.3 智能计算方法

以机器为载体来模拟人类智能，可通过五种核心方法实现。

五种智能计算方法对比

方法	核心思想	代表性算法/方法
符号主义为核心的逻辑推理	将概念符号化，从若干判断（前提）推出新判断（结论）	归纳推理、演绎推理、因果推理、专家系统
问题求解为核心的探寻搜索	依据已有信息寻找满足约束条件的待求解问题答案	无信息搜索、启发式搜索、对抗搜索
数据驱动为核心的机器学习	从数据出发，发现数据中承载语义的内在模式，用于识别和分类	监督学习、无监督学习、半监督学习、深度学习
行为主义为核心的强化学习	根据环境提供的奖罚反馈学习最佳行动，平衡探索与利用	Q学习、深度强化学习（DRL）
博弈对抗为核心的决策智能	多个主体为达到各自目标和利益采取的对抗行为，求取均衡解	纳什均衡、博弈策略求解、博弈规则设计

1.3.1 符号主义为核心的逻辑推理

推理是进行思维模拟的基本形式之一，是从一个或几个已知的判断（前提）推出新判断（结论）的过程。在人工智能发展初期，脱胎于数理逻辑的符号主义人工智能是主流学派。

核心思想：概念不再用自然语言描述，而是通过所定义的“符号”及符号之间的关系来表示，解决问题即构造一个证明来阐释其成立或不成立。

三种主要推理方法：

推理方法	基本逻辑	说明
归纳推理	从特殊到一般	从个别事实出发，推演出一般性知识作为结论
演绎推理	从一般到特殊	从一般性前提出发，通过推导得出具体陈述或个别结论
因果推理	因为A，所以B	判断事物间存在的原因和结果的关系，A是B的唯一前提

推理的三个层次（由易到难，Judea Pearl提出）：

1. 关联：可直接从数据中计算得到的统计相关
2. 干预：无法直接从观测数据得到的关系
3. 反事实：某个事情已经发生，在相同环境中若此事不发生会带来怎样的新结果

应用：逻辑推理在人工智能领域的应用推动了专家系统的产生。专家系统存储问题求解所需的领域知识（事实、规则等），根据用户提交的问题应用推理规则得到解决方案。

1.3.2 问题求解为核心的探寻搜索

搜索是人工智能求解中的一种主要技术，依据已有信息寻找满足约束条件的待求解问题答案。

搜索算法的分类：

类型	说明	代表算法
无信息搜索	盲目搜索方法，按照搜索策略扩展结点次序分类	广度优先搜索、深度优先搜索
有信息搜索	启发式搜索，利用与所求解问题相关的辅助信息	贪婪最佳优先搜索、A*搜索
对抗搜索	在竞争环境中，智能体之间通过竞争实现相反利益	最小最大搜索、Alpha-Beta剪枝搜索、蒙特卡洛树搜索

1.3.3 数据驱动为核心的机器学习

与逻辑推理直接定义公理、命题和规则不同，数据驱动方法从数据出发，从承载表达某一概念的数据中直接学习该概念所涉及的模式。

核心思想：如果说逻辑推理可视为“从知识到知识”，那么机器学习完成了“从数据到知识”的过程。

按数据利用方式的分类：

类型	特点
监督学习	收集 $n$ 个标注数据作为训练集，从假设空间中学习最优映射函数 $f$
无监督学习	数据本身不包含标注信息
半监督学习	一部分数据有标注信息，一部分没有

深度学习作为联结主义方法的代表，通过构造逐层抽象的“端到端”机制来学习隐含在数据内部的模式，得到更强表达力和泛化能力的特征表达。

理论基础：赫布理论指出“神经元之间持续重复经验刺激可导致突触传递效能增加”，为联结主义人工智能研究提供了认知神经心理学基础。

1.3.4 行为主义为核心的强化学习

强化学习赋予智能体自监督学习能力，使其能够自主与环境交互，做出序列决策，完成序列化形式的任务。

核心机制：

• 智能体通过与环境的交互，根据环境给出的奖惩反馈来不断改进策略
• 运用 “尝试-试错” 与平衡 “探索与利用” 等机制不断进步
• 目标是获得最大的累积奖惩

监督学习、无监督学习与强化学习的差异：

维度	监督学习	无监督学习	强化学习
学习依据	基于监督信息	基于对数据结构的假设	基于评价（evaluative）
数据来源	一次性给定（含标注信息）	一次性给定（无标注信息）	在序列交互中产生，序列结束才反馈明确奖惩值
决策过程	根据标注信息做出单步静态决策	无	根据环境给出的滞后回报做出序列决策
学习目标	样本空间到高级语义空间的映射	同一类数据的分布模式	选择能获取最大收益的状态到动作的映射

Q学习：学习智能体的 $q$ 函数，记录某个状态下采取某一动作所能够收到的奖励值。将 $q$ 函数参数化，用神经网络来拟合 $q$ 函数，即可形成深度强化学习。

1.3.5 博弈对抗为核心的决策智能

博弈行为是多个带有相互竞争性质的主体，为达到各自目标和利益，采取的带有对抗性质的行为，即“两害相权取其轻，两利相权取其重”。

核心转变：推动机器学习从“数据拟合”过程中以“求取最优解”为核心，向博弈对抗过程中“求取均衡解”为核心的转变。

重要概念：

• 博弈论：研究博弈行为中最优的对抗策略及其稳定局势
• 纳什均衡：约翰·纳什于1950年提出，非合作博弈的均衡解一定存在

五种方法各有优劣：

• 逻辑推理方法解释性强，但难以拓展
• 搜索方法从已有答案中查找，但受困于机械式匹配
• 数据驱动模型擅于预测识别，但过程难以理解
• 强化学习能探索未知空间，但依赖于策略学习
• 博弈对抗在完全信息条件下表现优良，但难以找到非完全信息条件下的通用框架

因此，需要有机协调知识指导下演绎、数据驱动中归纳、行为强化内规划等不同方法，建立知识、数据和反馈于一体的人工智能理论和模型。

1.4 本书内容介绍

本书主要从数据智能角度介绍人工智能，共9章：

章节	内容	核心知识点
第2章	逻辑与推理	命题逻辑、谓词逻辑、知识图谱推理、因果推理
第3章	搜索求解	启发式搜索、对抗搜索、蒙特卡洛树搜索
第4章	机器学习：监督学习	回归分析、决策树、LDA、AdaBoosting、SVM
第5章	统计机器学习：无监督学习	K-means、PCA、特征人脸、LSA、EM算法
第6章	深度学习	前馈神经网络、CNN、RNN、GAN
第7章	强化学习	MDP、策略优化、Q学习、深度强化学习
第8章	人工智能博弈	纳什均衡、博弈策略求解、博弈规则设计
第9章	人工智能未来发展和趋势	类脑计算、AutoML、模型压缩、AI芯片、伦理

1.5 小结

1955年提出人工智能概念时，其“初心”是“仿真”人类行为。经过长期发展，已形成五大核心方法：逻辑推理、搜索求解、机器学习、强化学习和博弈对抗。

当前人工智能的局限性：

• 现有算法或系统属于“领域人工智能”或“弱人工智能”的研究范畴
• 与具有自我学习、直觉推理、自适应和能力迁移等特点的通用人工智能仍存在差距
• 图灵机模型所能完成的可计算任务都是可递归的，而人类面临的许多现实问题具有不确定性、脆弱性和开放性等特点

未来方向：需要将人类智能与机器智能进行有效协同，形成混合-增强智能形态，这是发展人工智能的可行之道。正如大卫·希尔伯特所言：“我们必须知道，我们必将知道。”这种“可认知”乐观主义态度将鼓舞人工智能研究者和实践者不断探索。

2 逻辑与推理

逻辑与推理是人工智能的核心问题。符号主义人工智能脱胎于逻辑推理，所有概念通过符号及其关系表示，对符号进行逻辑推理以实现对知识的辨析。本章从命题逻辑、谓词逻辑、知识图谱推理和因果推理四个方面展开。

2.1 命题逻辑

命题逻辑是数理逻辑的基础，应用形式化规则对以符号表示的命题进行推理。

基本概念

概念	定义
命题	一个能确定为真或为假的陈述句。
原子命题	不包含其他命题作为组成部分的命题（简单命题）。
复合命题	通过命题联结词组合原子命题得到的新命题。

命题联结词

联结词	符号	含义	真值表（$p,q:F/T$）
与	$p\wedge q$	合取，“$p$ 且 $q$”	F, F, F, T
或	$p\vee q$	析取，“$p$ 或 $q$”	F, T, T, T
非	$\neg p$	否定，“非 $p$”	T, T, F, F（对应 $p$ 的真值取反）
条件	$p\to q$	蕴含，“如果 $p$，则 $q$”	T, T, F, T
双向条件	$p\leftrightarrow q$	双向蕴含，“$p$ 当且仅当 $q$”	T, F, F, T

重要：$p\to q$ 为假仅当 $p$ 真而 $q$ 假；当 $p$ 为假时，$p\to q$ 恒为真（空集是任何集合的子集）。

常用逻辑等价式

等价式	说明
$\alpha \to \beta \equiv \neg \alpha \vee \beta$	蕴涵消除
$\neg (\alpha \wedge \beta )\equiv \neg \alpha \vee \neg \beta$	德摩根律
$\neg (\alpha \vee \beta )\equiv \neg \alpha \wedge \neg \beta$	德摩根律
$\alpha \to \beta \equiv \neg \beta \to \neg \alpha$	逆否命题
$\neg \neg \alpha \equiv \alpha$	双重否定
$(\alpha \wedge \beta )\vee \gamma \equiv (\alpha \vee \gamma )\wedge (\beta \vee \gamma )$	分配律

推理规则

规则	形式
假言推理	$\alpha \to \beta ,\alpha \Rightarrow \beta$
与消解	${\alpha }_1\wedge {\alpha }_2\wedge \cdots \wedge {\alpha }_n\Rightarrow {\alpha }_i$
与导入	${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n\Rightarrow {\alpha }_1\wedge {\alpha }_2\wedge \cdots \wedge {\alpha }_n$
双重否定消去	$\neg \neg \alpha \Rightarrow \alpha$
单项归结	$\alpha \vee \beta ,\neg \beta \Rightarrow \alpha$
归结	$\alpha \vee \beta ,\neg \beta \vee \gamma \Rightarrow \alpha \vee \gamma$

范式

• 析取范式 (DNF)：有限个简单合取式的析取，如 $(\neg {\alpha }_1\wedge {\alpha }_2)\vee {\alpha }_3$。
• 合取范式 (CNF)：有限个简单析取式的合取，如 $({\alpha }_1\vee {\alpha }_2)\wedge \neg {\alpha }_3$。
• 任意命题公式都存在与之等值的 DNF 和 CNF（不唯一）。

2.2 谓词逻辑

命题逻辑无法表达“局部与整体”“一般与个别”的关系（如苏格拉底三段论），因此引入谓词逻辑，将原子命题细分为个体、谓词和量词。

基本元素

元素	定义	示例
个体	研究对象中独立存在的具体或抽象概念，可为常量（如苏格拉底）或变量（$x,y$）	苏格拉底, $x$
谓词	刻画个体属性或个体间关系的元素，值为真/假	$\text{Person}(x)$, $\text{Father}(x,y)$
全称量词 $\forall$	表示“所有的”“每一个”	$(\forall x)P(x)$
存在量词 $\exists$	表示“存在”“某些”	$(\exists x)P(x)$

量词等价关系

关系	说明
$(\forall x)P(x)\equiv \neg (\exists x)\neg P(x)$	所有 $x$ 满足 $P$ 等价于 不存在 $x$ 不满足 $P$
$(\exists x)P(x)\equiv \neg (\forall x)\neg P(x)$	存在 $x$ 满足 $P$ 等价于 并非所有 $x$ 都不满足 $P$
$\neg (\forall x)P(x)\equiv (\exists x)\neg P(x)$	并非所有 $x$ 满足 $P$ 等价于 存在 $x$ 不满足 $P$

推理规则

规则	符号	含义
全称量词消去 (UI)	$(\forall x)A(x)\Rightarrow A(y)$	对所有 $x$ 成立，则对任意 $y$ 成立
全称量词引入 (UG)	$A(y)\Rightarrow (\forall x)A(x)$	若对任意 $y$ 成立，则对所有 $x$ 成立
存在量词消去 (EI)	$(\exists x)A(x)\Rightarrow A(a)$	存在某个 $x$，可指定一个常量 $a$
存在量词引入 (EG)	$A(a)\Rightarrow (\exists x)A(x)$	若某个常量满足，则存在 $x$ 满足

苏格拉底三段论证明示例：

• 前提：$(\forall x)(\text{Person}(x)\to \text{Mortal}(x))$， $\text{Person}(\text{Socrates})$
• 结论：$\text{Mortal}(\text{Socrates})$
• 证明：UI 得 $\text{Person}(\text{Socrates})\to \text{Mortal}(\text{Socrates})$，假言推理即得。

2.3 知识图谱推理

知识图谱是由有向图描述实体及关系的知识表示，三元组 <头实体, 关系, 尾实体> 可表示为一阶逻辑，支持推理以发现新知识。

FOIL 归纳推理

FOIL 通过序贯覆盖学习一阶规则，目标谓词作为规则头，逐步添加前提约束谓词直至不覆盖任何反例。

算法流程：

步骤	操作
1	将目标谓词作为所学规则的结论。
2	逐一将其他谓词作为前提加入，计算FOIL信息增益，选取增益最大的谓词加入规则，并去掉不满足的样例。
3	重复步骤2，直到规则不覆盖任何反例。

信息增益公式：
$$FOIL\_Gain={\hat{m}}_{+}\cdot \left({\log }_2\frac{{\hat{m}}_{+}}{{\hat{m}}_{+}+{\hat{m}}_{-}}-{\log }_2\frac{m_{+}}{m_{+}+m_{-}}\right)$$
其中 $m_{+},m_{-}$ 为原规则覆盖的正反例数，${\hat{m}}_{+},{\hat{m}}_{-}$ 为加入新前提后的正反例数。

路径排序推理 (PRA)

PRA 将实体间的关联路径作为特征，训练关系分类器。

阶段	说明
特征抽取	随机游走、BFS/DFS 生成连接实体对的路径集合。
特征计算	计算特征值，如到达概率、路径频次或布尔存在性。
分类器训练	用特征训练二分类器，预测新实体对是否存在目标关系。

其他知识推理方法

方法	核心思想
基于分布式表示	将实体和关系嵌入低维向量空间，通过向量运算（如 ${\mathbf{e}}_{\text{head}}+\mathbf{r}\approx {\mathbf{e}}_{\text{tail}}$）进行推理。
马尔可夫逻辑网络	结合马尔可夫网络与一阶逻辑，在概率框架下处理不确定性和关系推理。

2.4 因果推理

因果关系是现象间“引起和被引起”的关系。因果推理判断原因与结果间的必然联系，是比相关性更强的推断。

辛普森悖论

在总体样本上成立的关系，在分组样本中可能完全相反。例如：总体不用药恢复率更高，但按性别分组后用药恢复率均更高。这说明了忽略混杂变量可能导致错误结论，需要因果分析。

结构因果模型 (SCM)

• SCM 由外生变量集 $U$、内生变量集 $V$ 和一组函数 $F$ 组成，$X$ 是 $Y$ 的直接原因当且仅当 $X$ 出现在给 $Y$ 赋值的函数中。
• 因果图：有向无环图 (DAG)，结点为变量，边表示直接因果依赖。可用于乘积分解联合概率。

因果图的基本结构

结构	图示	条件独立性
链	$X\to Z\to Y$	给定 $Z$ 时，$X$ 与 $Y$ 条件独立
分连	$X\leftarrow Z\to Y$	给定 $Z$ 时，$X$ 与 $Y$ 条件独立
汇连	$X\to Z\leftarrow Y$	$X$ 与 $Y$ 无条件独立；给定 $Z$（或 $Z$ 的后代）时相关

D-分离：若给定集合 $Z$ 阻塞了 $X$ 与 $Y$ 间的所有路径，则 $X$ 与 $Y$ 条件独立。阻塞条件：路径上的链/分连中间结点在 $Z$ 中，或汇连结点及其后代均不在 $Z$ 中。

干预的因果效应

引入 do 算子 $do(X=x)$ 表示强制固定变量 $X$ 的值为 $x$，消除指向 $X$ 的边后计算 $Y$ 的分布。

• 因果效应差：$P(Y=1|do(X=1))-P(Y=1|do(X=0))$
• 调整公式（已知混杂 $Z$ 时）：
  $$P(Y=y|do(X=x))=\sum _{z}P(Y=y|X=x,Z=z)P(Z=z)$$
  用无干预下的条件概率即可计算因果效应。

反事实模型

反事实回答“如果当时做了不同选择，结果会怎样”的问题。计算步骤：

步骤	操作
1. 溯因	利用证据 $E$ 推断外生变量 $U$ 的值。
2. 动作	修改模型，将原因变量 $X$ 强制设为反事实值 $x$，得到修正模型 $M_x$。
3. 预测	在 $M_x$ 和已推断的 $U$ 下计算结果变量 $Y$ 的值。

因果分析的层次化 (Pearl)

层次	典型问题	表达式
关联	“看到 $A$ 会怎样？”	$P(y
干预	“如果做 $A$ 会怎样？”	$P(y
反事实	“如果当初没做 $A$ 会怎样？”	$P(y’

2.5 小结

逻辑与推理是人工智能的核心支柱。命题逻辑和谓词逻辑为知识表示和自动推理提供了形式化基础；知识图谱推理扩展了从大规模知识中获取新关系的能力；因果推理则超越相关性，揭示变量间的本质因果机制。三者共同构成了智能系统进行演绎、归纳与因果推断的理论框架。

3 搜索求解

搜索是人工智能问题求解的三大方法之一（另两种为推理和约束满足）。搜索算法的本质是在问题的解空间中寻找一条从初始状态到目标状态的最优路径。本章从无信息搜索、启发式搜索、对抗搜索到蒙特卡洛树搜索四个层次展开。

3.1 搜索算法基础

3.1.1 搜索问题的五要素

要素	说明	示例（最短路径搜索）
状态	对智能体和环境当前情形的描述	当前所在城市
动作	智能体从一个状态转移到另一个状态的行为	乘坐一趟列车到下一城市
状态转移	执行动作后状态的变化（本章假设确定性的）	从城市A抵达城市D
路径与代价	状态序列为一条路径，路径对应一个代价（时间开销）	A→E→G→K，代价为总时间
目标测试	判断状态是否为终止状态	若当前状态为K，测试通过

3.1.2 搜索算法的评价指标

指标	含义
完备性	当问题有解时，算法是否能保证找到解
最优性	找到的第一个解是否为最优解
时间复杂度	找到解所需的时间，通常用扩展结点数衡量
空间复杂度	算法运行中需要的内存，通常用同时记录的结点数衡量

3.1.3 搜索算法框架

算法 3.1 树搜索框架：

步骤	操作
1	初始化边缘集合 $\mathcal{F}$，使其只包含根结点。
2	若 $\mathcal{F}\ne \varnothing$，从 $\mathcal{F}$ 中选出一个结点 $n$。
3	将 $n$ 从 $\mathcal{F}$ 中删除，若 $n$ 通过目标测试，返回其路径。
4	将 $n$ 的后继结点加入 $\mathcal{F}$，重复步骤2。

常见结点扩展策略：

策略	说明
广度优先搜索	每次从 $\mathcal{F}$ 中取出最浅的结点
深度优先搜索	每次从 $\mathcal{F}$ 中取出最深的结点

3.1.4 树搜索与图搜索

方法	核心区别	特点
树搜索	同一状态可对应多个结点	依赖剪枝（去除环路）保证完备性
图搜索	同一状态只能对应一个结点	维护闭表 $C$ 记录已扩展状态，效率更高

图搜索流程（算法3.2）：

1. 维护边缘集合 $\mathcal{F}$ 和闭表集合 $C$。
2. 从 $\mathcal{F}$ 取结点 $n$，若其状态不在 $C$ 中，则加入 $C$ 并扩展其后继加入 $\mathcal{F}$。
3. 若状态已在 $C$ 中，则剪枝该结点。

注意：图搜索虽效率更高，但在某些情况下可能破坏原树搜索算法的最优性。

3.2 启发式搜索

启发式搜索利用辅助信息（启发信息）指导搜索方向，提高搜索效率。核心是定义启发函数 $h(n)$（估计结点 $n$ 到目标的代价）和评价函数 $f(n)$（决定扩展优先级）。

两种启发式搜索算法对比

算法	评价函数 $f(n)$	特点
贪婪最佳优先搜索	$f(n)=h(n)$	只考虑距目标的估计代价，可能非最优
A*搜索	$f(n)=g(n)+h(n)$	综合已付出代价 $g(n)$ 和估计剩余代价 $h(n)$，更全面

启发函数的性质

性质	定义	关系
可容性	$h(n)\le h^{\ast }(n)$，且对目标 $h(\text{goal})=0$。不高估代价。	一致性 $\Rightarrow$ 可容性
一致性	$h(n)\le c(n,a,n^{\prime })+h(n^{\prime })$。满足三角不等式。	更强的条件

A* 算法的性能

条件	结论
状态有限，排除环路	图搜索A* 和排除环路的树搜索A* 都是完备的。
树搜索 + 启发函数可容	保证最优性。
图搜索 + 启发函数可容	不一定保证最优性（需额外处理）。
图搜索 + 启发函数一致	保证最优性（且评价函数值沿路径单调非减）。

A*的优势：设计的启发函数越好（越接近 $h^{\ast }$），A* 扩展的结点越少，越接近“最优搜索”。

3.3 对抗搜索

对抗搜索（博弈搜索）研究在信息确定、全局可观察、交替行动、零和的两人博弈中如何找到最优策略。

3.3.1 最小最大搜索

核心思想：玩家 MAX 最大化自身得分，玩家 MIN 最小化 MAX 的得分，交替搜索直至终局。

结点得分计算：
$$\text{minimax}(s)=\{\begin{array}{ll}\text{utility}(s),& \text{若 }s\text{ 是终局状态}\\ {\max }_a\text{minimax}(\text{result}(s,a)),& \text{若 }\text{player}(s)=\text{MAX}\\ {\min }_a\text{minimax}(\text{result}(s,a)),& \text{若 }\text{player}(s)=\text{MIN}\end{array}$$

算法流程（算法3.3）：

• MaxValue(s)：若终局返回得分；否则递归选择子结点中最大值。
• MinValue(s)：若终局返回得分；否则递归选择子结点中最小值。
• MinimaxDecision(s)：选择使 MinValue 最大的动作。

性能：若搜索树有限，算法完备且最优。时间复杂度 $O(b^m)$，空间复杂度 $O(bm)$。

3.3.2 Alpha-Beta 剪枝

在最小最大搜索基础上，Alpha-Beta 剪枝通过追踪 $\alpha$（MAX 层当前最优下界）和 $\beta$（MIN 层当前最优上界）来剪除不可能影响最终决策的分支。

剪枝条件：

• Alpha 剪枝：在 MIN 层，若某子结点返回值 $\le \alpha$，则剪除其兄弟结点。
• Beta 剪枝：在 MAX 层，若某子结点返回值 $\ge \beta$，则剪除其兄弟结点。

算法流程（算法3.4）：

• MaxValue(s, α, β)：扩展子结点时，若出现 $v\ge \beta$，则剪枝返回。
• MinValue(s, α, β)：扩展子结点时，若出现 $v\le \alpha$，则剪枝返回。

性能：

• 最优情况下（结点按“最佳先查”排序）时间复杂度降至 $O(b^{m/2})$。
• 结点顺序对剪枝效率影响极大。

3.4 蒙特卡洛树搜索

当搜索空间极大时（如围棋），蒙特卡洛树搜索 (MCTS) 通过采样而非穷举来评估分支优劣，找到近似最优解。

探索与利用的平衡

以多臂赌博机问题为模型：智能体面对 $K$ 个赌博机，每次选择转动一个臂膀获得随机奖励，目标是最小化悔值。

策略	说明	缺点
贪心算法	总是选当前平均奖励最高的臂	容易陷入局部最优，探索不足
$ϵ$-贪心算法	以 $ϵ$ 概率随机探索，$1-ϵ$ 概率利用	忽略了各臂的探索次数差异

上限置信区间 (UCB1)

UCB1 优先选择置信上界最大的动作，平衡利用（均值高）和探索（不确定性大）。

选择公式：
$$a_t=\arg \underset{i}{\max }\left[{\overline{x}}_{i,T_{(i,t-1)}}+C\sqrt{\frac{2\ln t}{T_{(i,t-1)}}}\right]$$

• $\overline{x}$：平均奖励，$T$：被选次数，$C$：探索权重超参数。

MCTS 的四个步骤

步骤	操作	说明
选择	从根结点开始，用 UCB1 递归选择子结点，直至叶子结点或未完全扩展结点 $L$	平衡探索与利用
扩展	若 $L$ 非终止结点，随机扩展一个未探索的子结点 $M$	扩大搜索树
模拟	从 $M$ 开始，用简单策略（如随机）模拟游戏直至终局	快速评估
反向传播	将模拟结果沿路径回溯，更新结点的总奖励和访问次数	传播信息

MCTS 的优势：基于采样而非穷举，高效且能保证一定准确性，在搜索空间极大的游戏（如围棋）中表现出色。

3.5 小结

本章介绍了搜索求解的核心方法与算法：

• 无信息搜索（BFS、DFS）不利用启发信息，状态有限时完备但效率低。
• 启发式搜索（贪婪最佳优先、A*）利用 $h(n)$ 预估代价指导搜索。A* 在 $h(n)$ 满足可容性/一致性时保证最优。
• 对抗搜索（最小最大、Alpha-Beta 剪枝）解决二人零和博弈，Alpha-Beta 剪枝大幅减少搜索结点。
• 蒙特卡洛树搜索通过采样和 UCB1 策略，解决复杂博弈的近似最优决策问题。