DYNAMIC EXPLAINER / ARTICLE FLOW

把章节变成可单步观察的过程

01 / 18
STEP 01 / CODE / LOGIC

先说结论

HTN 从设计者给出的任务分解规则生成可执行计划，MCTS 通过多次模拟估计行动结果。HTN 更依赖明确的领域知识，MCTS 更依赖可快速复制和推进的状态模型。

HTN 任务：取得食物
方法 1：有钱 -> 去商店 -> 购买（预计成本 4）
方法 2：有工具 -> 去森林 -> 采集（预计成本 7）
当前有钱，选择方法 1

MCTS 根节点有 3 个动作，每个先模拟 100 次
A 胜率 62%，B 胜率 48%，C 胜率 55%
当前选择 A，并继续把更多模拟预算投向有希望的分支

分类：游戏 AI 与逻辑建模 / 规划与搜索

先说结论

HTN 从设计者给出的任务分解规则生成可执行计划，MCTS 通过多次模拟估计行动结果。HTN 更依赖明确的领域知识，MCTS 更依赖可快速复制和推进的状态模型。

两种“想下一步”的数字

HTN 任务：取得食物
方法 1：有钱 -> 去商店 -> 购买（预计成本 4）
方法 2：有工具 -> 去森林 -> 采集（预计成本 7）
当前有钱，选择方法 1

MCTS 根节点有 3 个动作，每个先模拟 100 次
A 胜率 62%，B 胜率 48%，C 胜率 55%
当前选择 A，并继续把更多模拟预算投向有希望的分支

这些数字只说明决策过程。HTN 的成本来自领域定义，MCTS 的胜率来自采样，二者都不自动保证现实游戏中的全局最优。

两种完全不同的“想下一步”

想象两个生活场景。

第一个场景是准备一顿晚餐：

目标：完成晚餐

如果食材齐全：
  处理食材 -> 烹饪 -> 装盘

如果食材不全：
  列清单 -> 购买食材 -> 处理食材 -> 烹饪 -> 装盘

这类问题有熟悉的步骤结构。我们知道“大任务通常怎样拆成小任务”，只需根据当前条件选择合适的拆法。这接近 HTN。

第二个场景是在复杂棋局中选择落子：

可选动作很多
对手会回应
越往后分支越多
无法完整搜索到终局

这时可以把计算预算集中到看起来更有希望的分支，通过多次模拟估计动作价值。这接近 MCTS。

一句话区分：

HTN 用领域知识把任务逐层分解成可执行步骤。
MCTS 用反复采样在巨大决策树中估计更好的动作。

先运行两个最小例子

先不要同时理解整套算法。下面让 HTN 和 MCTS 各自解决一个很小的问题，并观察代码实际改变了什么。

HTN 第一步：根据状态选择任务列表

using System;
using System.Collections.Generic;

static List<string> PlanDinner(WorldState world)
{
    if (world.HasFood)
    {
        return new List<string>
        {
            "PrepareFood",
            "Cook",
            "Serve"
        };
    }

    return new List<string>
    {
        "BuyFood",
        "PrepareFood",
        "Cook",
        "Serve"
    };
}

WorldState world = new(HasFood: false, MealReady: false);
Console.WriteLine(string.Join(" -> ", PlanDinner(world)));

record WorldState(bool HasFood, bool MealReady);

输出是：

BuyFood -> PrepareFood -> Cook -> Serve

这已经包含 HTN 的最小思想：PlanDinner 是复合任务，根据世界状态选择一种分解方法，返回的字符串是尚未真正执行的原子任务序列。

HTN 第二步：不能只看第一个条件

第一版的问题是：它只在选方法时检查 HasFood，没有验证后面的每一步是否真的可执行。加入原子任务和状态模拟：

static bool TryBuildPlan(
    WorldState start,
    IReadOnlyList<PrimitiveTask> tasks,
    out List<string> plan)
{
    WorldState simulated = start;
    plan = new List<string>();

    foreach (PrimitiveTask task in tasks)
    {
        if (!task.CanRun(simulated))
        {
            plan.Clear();
            return false;
        }

        plan.Add(task.Name);
        simulated = task.Apply(simulated);
    }

    return true;
}

record PrimitiveTask(
    string Name,
    Func<WorldState, bool> CanRun,
    Func<WorldState, WorldState> Apply);

关键是 simulated：规划器不修改真实世界，而是在副本上推演。假设 BuyFood 成功后把 HasFood 设为 true，后面的 Cook 才能通过前置条件。

一次失败跟踪可能是：

BuyFood     -> 可执行，模拟状态 HasFood = true
PrepareFood -> 可执行
Cook        -> 炉灶损坏，CanRun = false
整条方法失败，清空临时计划，再尝试其他方法

这解释了为什么 HTN 不能“找到第一个看起来适用的方法就立刻执行”：必须先完整分解并验证，失败时还要回退临时状态。

MCTS 第一步：先保存每个动作的统计

MCTS 不预先写死完整任务列表。假设 NPC 有三个动作：进攻、防守、治疗。每次模拟后记录访问次数和累计奖励：

ActionStats attack = new("Attack");
attack.Record(1.0);  // 第一次模拟获胜
attack.Record(0.0);  // 第二次模拟失败

Console.WriteLine(
    $"{attack.Name}: visits={attack.Visits}, " +
    $"average={attack.AverageReward:F2}");

sealed class ActionStats
{
    public string Name { get; }
    public int Visits { get; private set; }
    public double TotalReward { get; private set; }
    public double AverageReward =>
        Visits == 0 ? 0 : TotalReward / Visits;

    public ActionStats(string name) => Name = name;

    public void Record(double reward)
    {
        Visits++;
        TotalReward += reward;
    }
}

输出：

Attack: visits=2, average=0.50

MCTS 最终不是问“某次模拟赢了吗”，而是比较计算预算内积累的统计结果。

MCTS 第二步：既利用好动作，也探索少试的动作

如果只选平均奖励最高的动作，一个早期碰巧获胜的动作可能永远霸占搜索。选择阶段通常加入探索项。下面是常见 UCB1 形式的最小代码：

static double UcbScore(
    ActionStats action,
    int parentVisits,
    double exploration = 1.414)
{
    if (action.Visits == 0)
        return double.PositiveInfinity;

    double exploit = action.AverageReward;
    double explore = exploration * Math.Sqrt(
        Math.Log(parentVisits) / action.Visits);

    return exploit + explore;
}

给出一组具体统计：

根节点共访问 20 次
Attack：访问 10 次，平均奖励 0.70
Defend：访问  2 次，平均奖励 0.55

Attack 的利用价值更高，但 Defend 因为尝试次数少，会获得更大的探索加成。搜索继续后，统计会逐渐说明它是真的有潜力，还是仅仅没被充分验证。

两段代码的根本差别

HTN：代码先定义“任务怎样分解”，运行时生成一条可执行计划。
MCTS：代码先定义“动作、状态转移和奖励”，运行时反复模拟并更新统计。

后文的 HTN 分解栈和 MCTS 四阶段，都是对这两个最小例子的扩展。阅读时可以持续追问：HTN 当前在验证哪条任务链；MCTS 当前在更新哪个节点的访问次数与奖励。

HTN：分层任务网络

HTN 是 Hierarchical Task Network，核心对象通常包括：

复合任务 Compound Task
方法 Method
原子任务 Primitive Task
世界状态 World State

复合任务

复合任务描述“想完成什么”，但本身还不能直接执行：

准备晚餐
到达目的地
恢复队伍状态
取得某件物品

方法

方法描述在特定前提下，复合任务可以怎样分解：

准备晚餐
  方法 A：食材齐全
    处理食材 -> 烹饪 -> 装盘

  方法 B：食材不足且商店可用
    购买食材 -> 处理食材 -> 烹饪 -> 装盘

一个方法通常包含：

适用条件
子任务列表
子任务顺序或偏序约束

原子任务

原子任务是规划器不再继续分解的步骤：

移动到商店
购买指定食材
启动烹饪

原子任务通常要声明：

前置条件：执行前必须成立。
效果：执行后世界状态怎样变化。
代价：用于比较方案时的成本信息。

具体系统是否让原子任务直接绑定运行时动作，是实现选择。规划和执行也可以分离。

HTN 怎样逐步生成计划

初始状态：

有主食 = true
有配菜 = false
商店开放 = true

初始任务：

准备晚餐

第一步：选择适用方法

检查“食材齐全”方法：

有主食 && 有配菜
结果：false

检查“食材不足且可购买”方法：

缺少食材 && 商店开放
结果：true

于是分解为：

购买配菜 -> 处理食材 -> 烹饪 -> 装盘

第二步：验证原子任务

规划器按顺序模拟每个原子任务：

购买配菜
  前置条件：商店开放
  效果：有配菜 = true

处理食材
  前置条件：食材齐全
  效果：食材已处理 = true

这里的“模拟”只修改规划器内部的预测状态，不应提前改变真实世界。

第三步：得到可执行计划

购买配菜
处理食材
烹饪
装盘

运行时再逐步执行原子任务，并观察真实状态是否仍满足前置条件。

HTN 的最小伪代码

Plan(task, state):
    if task is Primitive:
        if PreconditionsMet(task, state):
            nextState = ApplyEffects(task, state)
            return [task], nextState

        return Failure

    for method in ApplicableMethods(task, state):
        plan = []
        simulatedState = Copy(state)

        for subtask in method.subtasks:
            partialPlan, simulatedState =
                Plan(subtask, simulatedState)

            if partialPlan failed:
                break and try next method

            append partialPlan to plan

        if every subtask succeeded:
            return plan, simulatedState

    return Failure

这段伪代码表达的是顺序任务的深度优先分解。是否：

回溯到其他方法
寻找成本最低计划
支持偏序任务
缓存中间结果
限制搜索深度

都属于具体规划器的能力与策略，不能从“HTN”三个字自动推出。

HTN 的关键状态

调试 HTN 时至少要区分：

真实世界状态：执行系统当前确认的事实。
模拟世界状态：规划过程中应用预测效果后的副本。
待分解任务栈：还没有完成规划的任务。
候选方法：当前复合任务可尝试的分解方式。
已生成计划：已经确定的原子任务序列。
执行游标：运行时执行到计划的哪一步。

把模拟状态直接写回真实状态，会让“计划成功”看起来像“动作已经完成”，这是严重的状态边界错误。

HTN 的正常、边界与失败路径

正常路径：第一个方法可完整分解

方法条件成立
所有原子任务前置条件成立
得到完整计划
执行时世界状态与预测一致

边界路径：方法前半段可行，后半段失败

购买食材成功进入模拟计划
但后续任务发现设备不可用

如果规划器支持回溯，应撤销该方法在模拟状态上的效果，再尝试其他方法。

是否支持回溯是实现能力；如果不支持，应明确报告“选择的方法无法完成”，而不是返回残缺计划冒充成功。

边界路径：执行时状态变化

规划阶段商店开放，走到一半商店关闭：

当前原子任务前置条件失效

合法策略可能包括：

从当前真实状态重新规划
把失败交给上层决策
执行预先定义的补偿任务

采用哪一种是执行协议选择。补偿或回退行为不能凭空添加，必须有明确规则。

失败路径：没有任何适用方法

规划器应保留可诊断信息：

哪个复合任务无法分解
检查过哪些方法
每个方法缺少什么前提
当时的世界状态版本

返回空计划可能同时表示“什么都不必做”和“规划失败”，因此需要明确区分。

MCTS：蒙特卡洛树搜索

MCTS 是 Monte Carlo Tree Search。它通常反复执行四个阶段：

Selection：沿当前搜索树选择一个节点。
Expansion：为未完全展开的节点加入新分支。
Simulation：从新节点继续模拟一段过程。
Backpropagation：把模拟结果沿路径回传。

每个搜索节点通常记录：

状态或状态引用
从父节点到这里采取的动作
访问次数
累计价值
子节点
尚未展开的动作

MCTS 返回的是计算预算下的估计结果，不保证找到全局最优动作。

MCTS 怎样逐步搜索

假设当前有三个可选动作：

A：稳妥推进
B：快速尝试
C：保守等待

第一轮

根节点还没有展开：

Expansion：选择 A，创建子节点。
Simulation：从 A 后随机或按轻量策略模拟。
Backpropagation：将结果回传给 A 和根节点。

如果模拟收益为正：

A.visitCount += 1
A.totalValue += reward
root.visitCount += 1

后续轮次

搜索树逐渐拥有 A、B、C 三个子节点。Selection 要平衡：

利用：多访问当前平均收益高的分支。
探索：给访问较少的分支更多机会。

常见选择公式之一是 UCT：

score =
    averageValue
    + explorationConstant
      * sqrt(ln(parentVisits) / childVisits)

公式结构是常见算法知识；探索常数取多少、奖励怎样归一化、零访问节点怎样处理，都是实现与问题建模选择。

达到预算后

根节点选择最终动作时，常见做法包括：

选择访问次数最多的子节点
或选择平均价值最高的子节点

两者不总是等价。最终选择规则必须明确，而不能只说“使用 MCTS”。

MCTS 最小伪代码

Search(rootState, budget):
    root = CreateNode(rootState)

    repeat until budget exhausted:
        node = root
        state = Copy(rootState)

        while node is fully expanded and not terminal:
            node = SelectChild(node)
            state = Apply(node.action, state)

        if state is not terminal and node has untried actions:
            action = ChooseUntriedAction(node)
            state = Apply(action, state)
            node = AddChild(node, action, state)

        reward = Simulate(state)

        while node exists:
            node.visitCount += 1
            node.totalValue += reward from node's perspective
            node = node.parent

    return ChooseFinalAction(root)

需要特别注意“从谁的视角回传价值”。在双方对抗问题中：

轮到另一方行动时，价值视角可能需要翻转或重新解释。

具体处理取决于奖励定义和节点视角。

MCTS 的关键状态

一次搜索至少涉及：

根状态快照
搜索树节点统计
未尝试动作集合
模拟状态
随机数状态或种子
剩余时间、迭代次数或其他预算
奖励值及其视角

为了复现问题，调试记录应包含：

根状态标识
随机种子
预算
每个根动作的访问次数和平均价值
最终选择规则

MCTS 的正常、边界与失败路径

正常路径：预算内形成统计差异

A：访问 120 次，平均价值 0.58
B：访问 35 次，平均价值 0.41
C：访问 15 次，平均价值 0.22

如果最终规则是“访问次数最多”，则选择 A。

这些数字只是说明统计形态的示例，不是任何系统应硬编码的阈值。

边界路径：根节点只有一个合法动作

仍可以直接返回唯一动作，不必进行无意义搜索。是否仍运行模拟来估计后续风险，是调用方需求。

边界路径：模拟在深度限制处结束

真实终局太远时，Simulation 可能在预算或深度上限处停止，转而使用估值函数。

深度上限与估值函数属于具体实现选择。估值偏差会直接影响搜索结果。

边界路径：不确定或随机转移

如果同一动作可能产生不同结果，模拟器必须按问题模型采样这些转移。若状态转移概率未知，MCTS 不会自动创造可信概率。

失败路径：奖励尺度不一致

如果某些模拟返回：

胜负值：-1 到 1

另一些却返回：

资源分：0 到 10000

搜索统计会被尺度主导。奖励的含义、范围与视角必须统一。

失败路径：模拟器与真实规则不一致

MCTS 的结论依赖模拟器。如果模拟阶段漏掉关键约束，即使迭代很多次，也只会更确信一个建立在错误模型上的答案。

HTN 与 MCTS 的核心差异

维度 HTN MCTS
主要输入 任务、方法、世界状态 状态、合法动作、转移与奖励模型
核心过程 分解任务 采样搜索
领域知识 显式写在方法和任务层级中 可写在选择、模拟和估值策略中
主要输出 可执行任务序列或网络 当前状态下建议的动作
可解释性 通常较强，可说明用了哪个方法 需要查看访问次数、价值和模拟统计
计算形态 受分解方法与回溯影响 可随预算渐进改善估计
典型风险 方法覆盖不全、状态预测失真 模拟器偏差、奖励偏差、预算不足

进阶：能否组合使用

HTN 与 MCTS 并不互斥。

一种组合方式是：

HTN 负责把长期任务拆成结构化候选方案。
MCTS 负责在某个高分支局部决策中选择当前动作。

另一种方式是：

HTN 方法生成合法的高层动作。
MCTS 只在这些高层动作之间搜索。

组合会减少某些搜索分支，但也会引入新的边界：

HTN 如果漏掉方法，MCTS 永远看不到对应方案。
MCTS 的统计价值怎样反馈给 HTN，需要统一代价语义。
重新规划时，旧搜索树能否复用需要验证状态一致性。

具体组合架构属于实现选择，不是通用算法必然要求。

代价与适用边界

HTN 适合

领域步骤结构明确
设计者能提供可靠的任务分解知识
希望计划具有较强可解释性
动作前置条件和效果可以建模

HTN 的代价：

维护方法库需要持续领域建模
未覆盖的情形可能直接无法规划
回溯与成本优化会增加搜索复杂度
执行世界与模拟世界不一致时需要重新规划协议

MCTS 适合

合法动作与状态转移可以模拟
分支很多，完整搜索不可行
允许用预算换取逐渐改善的估计
结果可通过重复模拟评价

MCTS 的代价：

需要大量模拟
结果受随机性、奖励与模拟策略影响
实时预算很小时统计可能不稳定
连续动作空间通常还需要专门的动作生成策略

不适合硬套的情况

HTN 不擅长凭空发现领域方法之外的新分解结构。

MCTS 不擅长：

没有可信模拟器的问题
一次错误探索代价不可接受且不能离线模拟的问题
奖励极其稀疏、很难在预算内观察到的问题

通用算法与实现选择

可验证的通用机制

HTN 通过方法把复合任务递归分解为原子任务。
方法具有适用条件，原子任务具有可执行条件与效果模型。
MCTS 反复执行选择、扩展、模拟和回传。
MCTS 使用访问与价值统计在探索和利用之间取得平衡。
两种模型的结论都依赖输入状态与领域模型的正确性。

必须由具体实现确定

HTN 是否回溯、是否优化代价、是否支持偏序
HTN 计划失效后的重规划协议
MCTS 的预算单位与大小
MCTS 的探索常数、模拟策略和奖励尺度
最终动作按访问次数还是平均价值选择
随机种子与并行搜索方式
两种模型组合时的状态和价值接口

最后总结

HTN 的问题是：

按照我们掌握的领域步骤，这个任务应该怎样拆解？

MCTS 的问题是：

在有限计算预算内，哪些动作经过更多模拟后更值得选择？

判断使用哪一种，不应只看系统是否“智能”，而应确认：

是否存在可靠的层级任务知识
是否能够可信地模拟动作结果
需要完整计划还是当前动作
更看重可解释结构还是预算内搜索
失败时能否说明是无方法、无动作、模型错误还是预算不足