AI(二):从聪明的搜索到会推理的智能体

我爱免费

作者：微信文章
盲目搜索费时费力，如果加上约束条件能大幅提高搜索效率。常用的约束算法被称为CSP（约束满足问题），用“变量 + 值域 + 约束” 描述问题，用结构加速搜索。现实中常见的排课表、排考试；任务分配、资源分配；地图着色（相邻区域不同色）都是CSP。CSP分为变量集合，值域集合及约束集合（变量取值约束）。结构化的约束有重大价值，能够提前检查冲突，提前终止节点，约束传播；从盲人过河变成摸着石头过河。约束的形式有很多种，如变量不同，变量不等式。CSP里的核心是约束传播，节点一致性保证单个变量满足一元约束，弧一致性满足X》Y的值域兼容性，删除大量冗余的值域，这个算法的核心是维护一个弧队列，反复检查、删值域，直到没有值可删。所以聪明的搜索常用的标准框架为：回溯搜索（DFS） + MRV（最少剩余值） + LCV（最少约束值） + 弧一致性（前向检查 / AC-3）。

有对手、有敌人、有对抗、有输赢的场景，需要用到博弈算法。在零和博弈，完美信息，确定性博弈的前提条件下，这类问题被称为博弈搜索。博弈算法的核心是α-β 剪枝，两个变量：α：MAX 当前能保证的最好值（下界）β：MIN 当前能保证的最好值（上界）。剪枝规则（最关键）：MAX 层（如果当前值 ≥ β → 剪枝，直接返回）（MIN 不会让你拿到更好的）；MIN 层（如果当前值 ≤ α → 剪枝，直接返回）（你已经有更好的选择了）。通过这种算法可以让搜索量指数级减少，象棋、围棋这类游戏 AI，离开 α-β 根本跑不动。在现实游戏中，不可能搜到终局，所以要加上深度限制，启发式评估函数这两个因子，组成经典AI棋类的框架。在alphaGo中就用到了经典的博弈树搜索，并做了工程化升级，用神经网络替代了手工评估函数，用蒙特卡洛树搜索 MCTS 替代了纯 α-β。

如何用形式化语言表示世界的知识？如何用推理规则从已知知识推出新知识？如何构建一个能用逻辑思考的智能体？能解决这三个问题，意味着AI有了思考和推理的能力，这也是大语言模型的立身之本。未了嫁接AI推理和语言世界，首先需要一套机器可以理解的形式语言，如原子命题（P，Q，R简单事实），连接词（非，与，或，蕴含，等价），真值表，知识库KB等。推理的实践操作是，给定一个知识库，问命题是否为真？常用的方法有穷举真值表，推理规则等。在实际中，最经常用到的是归结推理。1.子句的合取，如(P⇒Q) 等价于 (¬P ∨ Q)。2.归结规则，A ∨ L，B ∨ ¬L；可以推出：A ∨ B。3.归结反证。反证法 + 归结 = 可靠 + 完备的命题逻辑推理。只要有解，归结一定能推出来。这是自动定理证明、逻辑编程语言、早期 AI 系统的基础。这种推理方法也有明显的局限性：表达能力太弱，只能说 “P 真 / Q 假”，不能分对象、不能分个体。