规划、博弈与约束求解

导读：动作序列、整组赋值和应对策略不是同一种答案

上一章的搜索回答“先检查哪条可能路径”。本章再加三种结构：仓库机器人要找一串会改变世界的动作；数独要给所有格子同时找到相容取值；围棋还要把对手的反制算进去。它们都可能调用搜索，却不是“搜索”三个字的同义反复。

经典规划（classical planning）通常从已知初始状态出发，在确定、离散、完全可观察的动作模型中求达到目标的动作序列。约束满足求一组同时满足关系的赋值；对抗博弈求面对另一决策者时的动作或策略。随机后果、状态看不全和模型未知又是另外三条轴，不能统称“环境复杂”。

案例边界　本章仓库状态、数独网络、博弈树与取石模拟均为原创教学构造。现实仓库涉及连续运动、碰撞安全、人员、故障和新订单；围棋系统也不能外推为一般规划器。

6.1 从状态空间搜索到计划、赋值与策略

状态空间搜索是许多求解器的底层方法；问题结构决定节点和答案是什么。经典规划的节点可是一组事实，边是动作，答案是动作序列。CSP 的节点常是部分赋值，回溯顺序只是求解过程，答案是完整赋值。博弈树节点是局面，边是双方合法着法，答案常是当前动作或覆盖多种局面的策略（policy）。

离线计划（offline plan）在执行前算出整段序列；动态重规划（replanning）执行一段、读取新状态，再求后续。后者利用反馈，却不等于预先求得覆盖所有情况的最优策略；观测延迟、计算预算、模型误差和安全回退仍会改变结果。

6.2 STRIPS 式动作：何时能做，做完什么变了

STRIPS是 Fikes 与 Nilsson 1971 年提出的机器人问题求解系统及其影响下的动作表示传统。原论文在“世界模型”空间搜索操作符序列，世界模型包含一阶谓词逻辑公式；现代教材常用更简化的命题事实集合讲其核心，不能把简化版倒称为原论文全部语义。[1, Abstract; pp. 189–192]

在本章简化仓库中，状态含“机器人在 A”“货架在 A”“夹具空闲”“A 与 B 相连”等为真的事实。动作 Move(A,B) 有三部分：前置条件（precondition）说明何时可执行；增加效果（add effect）说明动作后哪些事实为真；删除效果（delete effect）说明哪些原事实不再为真。图 6-1 展示一次更新。

窄屏提示：图可横向滚动；删除和增加同时用文字、减号/加号与线型区分。

求解器先检查前置条件是否都在当前事实集合中，再移除删除效果、加入增加效果，生成后继状态。目标“机器人在 B”成立时，计划可返回 [Move(A,B)]。这种紧凑表示让机器检验动作，却只对写进模型的事实正确：基本命题小例没有连续时间、电量、抓取失败、并发机器人或碰撞动力学。扩展语言可表示其中一部分，但不是免费把现实装进去。

PDDL 1.2 是为 AIPS-98 规划竞赛等场景建立的共用问题描述语言，吸收 STRIPS、ADL 等传统；PDDL 不等于原始 STRIPS，也不是规划算法本身。[2, Introduction; §§2–3]

6.3 CSP：让全部选择同时相容

约束满足问题（constraint satisfaction problem，CSP）由变量（variable）、每个变量的候选取值域（domain）和必须同时成立的约束（constraint）组成；解是给全部变量赋值且不违反任何约束。Mackworth 的经典论文以变量、域和谓词关系描述这类网络。[3, pp. 99–103]

数独可把 81 个格子作为变量，域为 1 至 9；题面数字把某些域固定为单值；每行、每列、每个 3×3 宫的格子必须互不相同。求得一个解不自动证明题目唯一；求解器的赋值次序也不是人类必须照做的现实动作。

回溯搜索（backtracking search）选一个未赋值变量、尝试一个值，冲突时撤销最近选择。它能在部分赋值已冲突时剪掉整片候选，却仍可能指数增长。约束传播（constraint propagation）则用已知约束缩小邻居的域。对二元约束，弧一致要求一个变量域中的每个值，都能在相邻变量域中找到至少一个相容支持；AC-3 用队列反复检查受域缩小影响的弧。[3, pp. 103–106]

局部一致不等于全局有解。图 6-2 中 X、Y、Z 的域都是 {1,2}，约束是三者两两不同。每条边单看都有支持，例如 X=1 可配 Y=2；但三个变量不可能只用两个值两两不同。

窄屏提示：约束网络可横向滚动。

6.4 minimax 与 alpha-beta：对手会选择反制

极小化极大（minimax）在双人、零和、轮流行动、确定、完全信息的模型中，把叶节点效用统一从 MAX 视角向上回传：MAX 层取最大，MIN 层取最小。“MIN”表示模型假定对手选择对 MAX 最不利的合法后继，不表示现实中所有人都完美且敌对。隐藏信息、同时行动、多人或非零和收益需要别的模型。

图 6-3 的叶值从左到右为 3、5、6、9、1、4、7、8。完整手算：A1=max(3,5)=5，A2=max(6,9)=9，A=min(5,9)=5；B1=max(1,4)=4，B2=max(7,8)=8，B=min(4,8)=4；根 R=max(5,4)=5，选择 A。

窄屏提示：博弈树可横向滚动；剪枝同时用叉号、虚线和“未访问”标记。

alpha-beta 剪枝（alpha–beta pruning）维护两条界：alpha 是 MAX 沿当前路径已经能保证的下界，beta 是 MIN 已能保证的上界；当 alpha≥beta，剩余孩子不可能改变祖先选择，可停止检查。其正式分析见 Knuth 与 Moore。[4, pp. 293–326]

逐步复核：先读 3、5，A1=5，故 A 的 beta=5；A2 先读 6，已有 alpha=6≥beta=5，叶 9 未访问，但只需知道 A2≥6，A 仍选 5。根于是 alpha=5。B1 读 1、4，精确值4，B 的 beta=4≤根传入的 alpha=5，所以 B2 的 7、8 全部未访问。实际访问叶为 3、5、6、1、4，根值仍为5。剪枝不是近似：同一树、深度和叶值下结果与 minimax 相同；走法排序只改变省下多少工作。若叶值来自深度截止的评价函数，结果只对该深度与评价成立，不保证整局真实最优。

6.5 MCTS：把模拟预算投向部分分支

蒙特卡洛树搜索（Monte Carlo tree search，MCTS）是通过反复模拟逐步扩展树、估计动作价值的一类方法。常见一轮有四部分：选择沿树策略下行；扩展加入未展开动作；模拟或评估走到终局或调用价值估计；回传更新沿途访问次数与回报。四部分是框架，不是所有实现的唯一细节。

UCT 是其中一种选择规则。先定义：子分支 j 的平均回报为 $\bar X_j$，无量纲且本例在0至1；父节点访问次数 $N$、子分支访问次数 $n_j$ 都是正整数计数；$c>0$ 是无量纲探索常数；$\ln$ 是自然对数。下式各项均无量纲，只在 $n_j>0$ 时计算，未访问分支须另定优先规则：

第一项偏向当前平均回报高的分支，第二项偏向访问少的分支。Kocsis 与 Szepesvári 在具有生成模型的有限时域或折扣 MDP 等具体条件下分析 UCT；这不能扩大成任意 MCTS 在任意有限预算必得最优动作。[5, Abstract; §§1–3]

一轮可复算的取石 MCTS

规则：4枚石子，两人轮流取1或2枚，取最后一枚者胜；回报从根玩家 MAX 视角记，胜1、负0。迭代前根 R 为 (访问N=2, 累计回报W=1)；孩子 A“取1”是 (1,1)，B“取2”是 (1,0)；取 $c=\sqrt2$。根是 MAX 节点，两子探索项都为 $\sqrt{2\ln2}\approx1.17741$，所以 A 分数约2.17741，B约1.17741，选择 A。A 尚未扩展“对手取2”，于是加入 C：剩1枚、MAX行动。

模拟阶段 MAX 唯一可取最后一枚，回报1。沿 C→A→R 各更新一次：C 从 (0,0) 到 (1,1)；A 从 (1,1) 到 (2,2)；R 从 (2,1) 到 (3,2)，B不变。一次胜利模拟不证明 A 必胜；有限预算、rollout偏差、价值模型误差和罕见关键分支都会改变结论。若统计统一从根玩家视角保存，MIN 节点不能也最大化根玩家的平均回报；实现必须说明视角转换。最终动作常按根访问次数或均值选，也不一定沿用含探索奖励的 UCT 分数。

6.6 随机、看不全与模型未知是三件事

马尔可夫决策过程（Markov decision process，MDP）用状态、动作、转移概率和奖励描述序贯决策；在标准表述中，下一状态和奖励只依赖当前状态与动作，系统知道当前状态。部分可观察马尔可夫决策过程（partially observable MDP，POMDP）再加入观测及其概率，系统不能直接知道真实状态。信念状态（belief state）是对可能真实状态的概率分布，不是事实，也不是哲学意义的“相信”。相关定义与把信念作为历史的充分统计量须以模型正确为条件。[6, pp. 101–109]

Bellman 思想只预告一句：长期价值可拆成当前动作的即时结果与后继状态的未来价值。完整公式、折扣、期望与学习方法留到第13章，避免在尚未定义目标准则时制造精确幻觉。

6.7 案例落地：仓库、数独与 AlphaGo

仓库不是“运行一次 A*”

Kiva 系统论文描述小型 drive unit 把库存货架 pod 运到固定工作站，并把资源分配、任务规划、路径规划、运动规划与控制分层；路径层在二维网格图上使用 A*，而中央 Job Manager 分配机器人、pod 与工作站。[7, pp. 11–16; Figure 4] 这说明“订单给谁”“机器人服务哪个货架”“走哪些格点”“怎样避碰控制电机”不是同一问题。论文作者与系统有直接关系，本章不采用其商业生产率自述作为独立效果证据。

离线计划能在静态模型中给出动作序列；新订单、拥堵、设备故障或人员进入区域后，系统须观测、协调并重规划。重规划若来不及或传感器错误，形式上合法的旧计划仍可能不安全。

数独是赋值，不是物理行动计划

标准数独的行、列、宫约束适合 CSP。传播先删去不可能候选，停住后可回溯分支；找到一个完整赋值说明“存在解”，要证明唯一还须排除第二个解。固定9×9谜题是有限实例，不能把推广规模问题的复杂性标签无条件贴给某一题。

AlphaGo 不是纯 MCTS

2016 年 AlphaGo 系统把策略网络、价值网络和树搜索组合：策略网络帮助选择候选着法，价值网络评估局面，MCTS 还结合快速 rollout 更新动作值；搜索结束按根节点访问次数选择着法。网络训练又包含专家棋局监督学习与自我对弈强化学习。[8, Abstract; Figures 1, 3; pp. 486–487]

论文内部程序赛在其约5秒/步等设置下报告494胜/495局（99.8%）；这是指定程序集合、版本、硬件与预算下的论文评测，不是普遍胜率。2015年10月5日至9日对职业二段樊麾的五局正式赛为5∶0，另有短时限非正式赛，口径不应混合。[8, Figure 4; pp. 487–488; Methods] 本节讲的是2016论文系统；后来的 AlphaGo Zero 与 AlphaZero 是不同论文和训练设置，不应把其特征倒写进这里。围棋规则、表示、训练数据、自我对弈、搜索预算和硬件共同构成系统；它既不是纯 MCTS，也不是能接收任意仓库或社会目标的通用规划器。

条件比较

核心概念

• STRIPS：以可检验前置条件和增加/删除效果描述动作的表示传统。
• CSP：给变量从域中赋值，使全部约束同时成立。
• minimax：在特定零和完全信息模型中回传双方最佳选择。
• alpha-beta剪枝：用上下界跳过不能改变minimax结果的分支。
• MCTS：反复选择、扩展、模拟或评估并回传统计的树搜索框架。
• MDP/POMDP：分别描述完全可观察与部分可观察的随机序贯决策。

本章小结

• 搜索是求解机制；计划、CSP和博弈规定不同的状态结构与答案形式。
• STRIPS式动作让前置条件和效果可检验，但正确性只相对于模型，不能代替连续控制与安全工程。
• CSP传播缩小候选，局部一致不保证全局有解；回溯仍可能遭遇组合爆炸。
• alpha-beta在同一树上不改变minimax结果，顺序只影响剪枝量；MCTS则用有限模拟形成经验统计，UCT只是变体之一。
• AlphaGo结合策略网络、价值网络与树搜索。现实动态重规划还要面对随机、观测和模型误差。

相关词条与继续阅读

STRIPS · CSP · minimax · alpha-beta剪枝 · MCTS · MDP与POMDP

上一章：搜索：在可能性空间里找路。下一章：知识表示与推理。

资料截止说明　本章核查至 2026-08-26。所有小图与手算为原创教学构造；历史、仓库和AlphaGo陈述按原论文核对。Bellman正式公式与强化学习留第13章。