高级 AI

June 25, 2023About 20 min

高级 AI

高级AI这个章节主要是介绍更接近人类思考的AI模型。

Hierarchical Tasks Network

层次任务网络(hierarchial tasks network, HTN)是经典的游戏AI技术，和基础AI中介绍过的行为树相比HTN可以更好地表达AI自身的意志和驱动力。
Behaviour Tree 的问题是不够直观，往往需要注释的表达子树的目的(Goal).

HTN的思想是把总体目标分解成若干个步骤，其中每个步骤可以包含不同的选项。
AI在执行时需要按照顺序完成每个步骤，并且根据自身的状态选择合适的行为。

比如上图，当人去学习一门课的时，会先把学习过程Demopose成具体的步骤，并且每步可以Select不同的完成方式。

HTN Framework

下面通过流程图分析HTN的框架

HTN的World State并不是对真正客观世界的表达，而是AI对于游戏世界的认知。
HTN的sensor负责从游戏环境中抓取各种状态，是AI从游戏世界获取信息的渠道。

HTN的Domain(域)用来存放层次化，树状结构的Task, 以及之间的关联关系。
HTN的Planner根据sensor感知的世界状态，从Domain中规划出要完成的Task事件。
HTN的Plan Runner会依次执行Planner制定的Task，还会监听Task的执行状态。

要注意的是 Task执行会受外部世界影响，可能会产生Replan。

HTN Task Types

首先需要定义世界的任务类型，HTN定义了两种Task，primitive task和compound task。

primitive task(原子型任务)一般表示一个具体的动作或行为。

HTN中每个primitive task需要包含precondition、action以及effects三个要素。
Precontition: 读取世界状态，当某些Work States满足，才会执行Action, 否则返回False.
Action: 原子型任务要执行的操作。
Effects: 修改器，改变世界状态

例子：定义使用解药的primitive task

Precontition: 有一瓶解药
Action: 消耗解药的动作
Effects：(移除中毒状态 + 解药数量-1) --> 对世界的修改

compound task(复合任务)包含很多的Method.

Compound task的Method构建类似于行为树的Selector, 按照优先级把这些方法排序。
Compound task的Method执行顺序类似于行为树的Sequence, 子任务要依次执行完才成立.
Method可以是子任务链，每个子任务都可以是primitive task或compound task。

例子：通过自身资源来获取解药并使用

Info

策划只需要理解单一任务和复合任务，就很方便去构建游戏逻辑。

HTN DoMain

通过单一和复合任务就能构建HTN DoMain空间，并需要确认Root Task.
Root Task: 一个复合任务，定义了AI的核心关键行为。

例子：由多个Root Task构成的一个AI行为

Planning

基于Domain进行计划安排，步骤如下：

根据当前的World State, 选择Root task(Goal)，并展开为 Methods。

把Method展开成Task，同时需要假定Task成功执行(推演), 并更新为世界临时状态。
如果计划时发现Task会失败，会回到父级找到下一个可执行的Task.

因为存在失败的情况，Designer设计的时候需要加入 Default Task确保AI行为更鲁棒，比如不会出现在原地傻站着的情况。

完成计划后最终会输出一串原子任务。
如右图的例子，最后输出的任务是Buy Potion + Use Potion.

Replan

多个的AI在一起，整个系统为混沌状态，Output不可预期。比较经典的例子就是三体问题。
受环境变化影响，执行plan过程任务可能会失败，这就需要重新进行规划，这一过程称为replan。

黑魂1的蘑菇人就会遇到NavMesh寻路找不到导致卡住的问题，之前是通过Replan简单解决的。

需要重新计划的情况：

现在没有计划
当前计划执行完毕或失败
AI认知的world state发生改变 – 当大环境改变后计划必须重新置顶(如图）

优点: HTN和行为树非常相似，但它易于Designer规划长期行为，效率更高。
缺点:
设计好的Task因为环境无法形成而无效。
高度不确定的环境会导致行为不稳定性。

Goal-Oriented Action Planning 基于目标的行为规划

goal-oriented action planning(GOAP)是一种基于规划的AI技术，和前面介绍过的方法相比GOAP一般会更适合动态的环境，不需要做预先的Action梳理。

GOAP的结构解析

GOAP的整体结构与HTN非常相似，不过在GOAP中domain被替换为Goal set和Action set。

Goal Set 会按期待达成的优先级存放Goal序列, 和HTN的复杂任务存放相似.

每个Goal都有Precondition, Precondition会根据优先级形成一个有效序列.
和HTN最不同的差异是每个Goal需要用不同的State状态去定义.
即希望完成一系列动作后，World State会更新为想要的设定
State一般会用bool值表达

Info

在HTN和行为树中，目标大部分时候是隐含在树状结构中
在GOAP中，目标是由一序列世界达成的状态去定量表达的

例子：通过GOAP系统定义的AI驱动.

Action Set 和HTN的一般任务很像。

每个Action都有Precondition, 当满足的时候才执行。
每个Action完成由Effect去改变世界状态。
加入的额外属性是Cost, 通过Designer来评估行为的好坏。

GOAP的规划

GOAP在进行规划时会从目标来倒推需要执行的动作，这一过程称为反向规划(backward planning)。
这个和人类思考方式相同，如图就是一个解毒的Action的反向推导，最后推到出来的Action先执行。
下面会列出GOAP的规划流程:

根据优先级检查Goal，找到前置条件满足(和World State匹配)的Goal.

检查Goal完成后的所有States, 如果State没有都满足(和World State不匹配),
将未满足的State依次插入栈(stack of unsatisfied states)保存。

从Action Set中筛选出Action, 并确保Action执行后的Effect可以满足栈顶的State.

将找到的Action插入Plan Stack, 并移除刚才的会满足的State.
然后检查当前Action的前置条件是否满足，未不满足的Precondtion会反向记录为栈中新的State.
→ 循环执行最后确保所有状态需求都得到了满足，这样就完成了反向规划.

Info

核心目标是规划出一条路径，当按着Action依次去执行的时候，最后会让Unsatisfied states的栈全清空。
额外的需求是所有action的cost加在一起最小。

GOAP的难点在于如何从action set进行选择，我们要求状态需求都能够得到满足而且所添加动作的代价要尽可能小。
显然这样的问题是一个动态规划(dynamic programming)问题，我们可以利用图这样的数据结构来进行求解。
在构造图时把状态的组合作为图上的节点，不同节点之间的有向边表示可以执行的动作，边的权重则是动作的代价。
这样整个规划问题就等价于在有向图上的最短路径问题。

如上图: 将Goal的所有state作为起始节点，当前的State作为目标节点，从节点通过Action的变化(边代表Action, 边的数字代表开销)会更新到另外一个状态节点。
这样的图构成后，最后的结果就是变成最短路径搜索问题.
→ 这样可以通过A*算法求解出一个近似解，虽然不是最优解，但是会让AI感觉更精彩(具有变化性)。

总结一下GOAP可以让AI的行为更加动态，而且可以有效地解耦AI的目标与行为；
而GOAP的主要缺陷在于它会比较消耗计算资源，一般情况下GOAP需要的计算量会远高于BT和HTN.
另外一个挑战是需要对游戏的状态进行定量表达，对于高度复杂游戏很复杂(比如RTS), 适合单机和顺序刷关游戏。

Monte Carlo Tree Search 蒙托卡罗搜素树

蒙特卡洛树搜索(Monte Carlo tree search, MCTS)也是经典的AI算法，AlphaGo和全战就是基于MCTS来实现的。

简单来说，MCTS的思路是在进行决策时首先模拟大量可行的动作，然后从这些动作中选择最好的那个来执行。

MCTS的核心是Monte Carlo方法(Monte Carlo method)，它指出定积分可以通过随机采样的方法来进行估计。

以围棋为例，MCTS会根据当前棋盘上的状态来估计落子的位置。
评估遵循落子规则，可以筛掉大量无效的落子, 节约算力。

在计算机里面做所有的东西首先要建模---把一个问题抽象成数学模型，计算机只能处理数学模型。
从数学的角度来看，我们把棋盘上棋子的位置称为状态(state)，同时把落子的过程称为动作(action)。
这样整个游戏可以建模为从初始节点出发的状态转移过程，而且所有可能的状态转移可以表示为一棵树。

显然构造出完整的树结构可能是非常困难的，不过实际上我们并不需要完整的树。
在使用MCTS时，完成每一个行为后只需要重新以当前状态构造一棵新树即可。

Simulation 模拟

模拟(simulation)是MCTS中的重要一环，这里的”模拟”是指AI利用当前的策略快速地完成整个游戏过程。
Default Policy 是AI可参考的缺省策略，放到围棋中就是预先输入的各种棋谱。
模拟仅是一条探索而已，不代表这个节点下所有的state base都是成功的。

怎么判断下一步的好坏？通过定量的Q和N来评估价值(胜率)

Q -- 这么多次模拟成功了多少次
N -- 做了多少次模拟

Backpropagate 反向传播

在通过定量评估后，需要反向更新整个决策序列上所有节点的价值直到根节点。

Iteration Steps 迭代步骤

首先选择一个最有希望且没有完全展开的节点(Selection)
展开进行新的探索(Expanslon)
模拟探索过程并判断结果(Simulation)
反向更新探索结果(Backpropagate)

这个是MCTS的一次核心迭代，下面会介绍前面两步以及循环结束处理。

Selection 选择

在对节点进行选择时，MCTS会优先选择可拓展的节点。
expandable node: 可拓展的节点指所有的可能性并没有被穷尽，简单来说周围还可以走。

选择从哪里开始有两种策略：

Exploitation: 开发，优先探索模拟次数多，胜率高的点。
希望一个确定性的结果，比如反复去最喜欢和熟悉的餐馆。
Exploration: 探索，优先探索模拟次数少。
冒着风险去尝试，比如优先考虑没去过的餐馆。

实际选择会在这两者找一个平衡，基于UCB(上致信空间).
当对一个随机的世界进行采样时，如果已经采样过一些数值，
如果采样的数量比较少的结果并不认为真实的，通过满足高斯分布的数学方法来平衡。
另外常量C越大，访问少的节点会更大可能被选中。

MCTS在选择下一个要探索的节点时，每次都会从根节点出发。
然后不断选择当前UCB最大的那个节点向下进行访问，当访问到一个没有完全展开过的节点时选择该节点进行展开。

Expansion 展开

对节点进行展开时我们需要根据可执行的动作选择一组进行模拟，然后把模拟的结果自下而上进行传播。

The End Condition 停止条件

当对树的探索达到一定程度后就可以终止拓展过程，此时我们就得到了树结构上每个节点的价值。
比如内存消耗多少，Simulation多少次。

最后只需要回到根节点选择一个最优的子节点进行执行即可。
图上提出了选择根节点的几种策略。

MCTS是一种非常强大的决策算法而且很适合搜索空间巨大的决策问题；
而它的主要缺陷在于它具有过大的计算复杂度，而且它的效果很大程度上依赖于状态和行为空间的设计。
MCTS适合输出和结果非常明确的游戏，其他类型游戏可能要结合前面的算法。
比如全战大世界里面各个NPC势力对其他实例的策略决策。

Machine Learn Basic 机械学习基础

ML Types

近几年在机器学习(machine learning, ML)技术的不断发展下有越来越多的游戏AI开始使用机器学习来进行实现。
根据学习的方式，机器学习大致可以分为监督学习、无监督学习、半监督学习以及强化学习等几类。

监督学习本质上是一个分类器，学习的数据都是有标签的。比如猫的图和不是猫的图。

无监督学习是一个聚类，自动在数据中找到规律进行划分。比如通过数据定义用户习惯.

**半监督学习等于少量学习后就能得到规律。**比如人类通过简单图画学习就能识别动物。

强化学习(reinforcement learning, RL)是游戏AI技术的基础。
在强化学习中我们希望AI能够通过和环境的不断互动来学习到一个合理的策略。
如图，需要注意的是老鼠走出迷宫获得的奖励是有延迟的，那么这样情况下确保它能正确学习是很难的问题。

Markov Decision Process 马尔可夫决策过程

强化学习的理论基础是Markov决策过程(Markov decision process, MDP)。

在MDP中Agent(智能体)对Environment的感知称为状态(state)，
Environment对于Agent的反馈称为奖励(reward)。
MDP的目标是让智能体通过和环境不断的互动来学习到如何在不同的环境下进行决策，这样的一个决策函数称为策略(policy)。

如图：state包含马里奥的位置，场景的布局等等。

如图：左右移动和向上跳跃都是在场景中的交互Action.

如图：奖励可以是收集金币，胜利，失败等等。

Probablilty of transition 是用来表达概率的一个量，因为环境是变化不可靠的。
Policy 策略也是一个随机量，表示各种可能。有状态的输入就有动作的输出。
Total reward 要评估短期目标和长期目标。

如图：输出各种动作的策略，用Π表示Policy

Build Advanced Game AI

目标：怎么使用机器学习让游戏AI更聪明。

HTN,GOAP这些策略不会超过设计师的预期，想象力决定了AI的上限。
强化学习(机器学习)可以让AI自己进化，适合无限可能的世界。

这些基于深度强化学习(deep reinforcement learning, DRL)的游戏AI都是使用一个深度神经网络来进行决策，
整个框架包括接收游戏环境的观测(observation)，利用神经网络(policy)获得行为，以及从游戏环境中得到反馈(reward)。

这里通过DRL深度强化学习模型来说明：

State -- 对世界状态的描述，通过量化的方式表达给AI系统
Action -- AI的输出，模拟人类的操作和输出
Reward -- AI不同动作的奖励
NN design -- 根据游戏结构和逻辑构建网络拓扑结构
Training Strategy -- 训练策略

要注意的是这种游戏是信息不对称的博弈，存在战争迷雾。

游戏模型解析

State

以AlphaStar为例，AI可以直接从游戏环境获得的信息包括地图、统计数据、场景中的单位以及资源数据等。
这些信息记录为世界的State.

游戏态势的表达可以通过很多层的Map来表达，如上图中的寻路区域和建筑区域。

游戏中的各种单位信息

Actions

Action定义基于State能完成什么事情。
如图中Unit，Action的定义要非常清楚，还可能由Planing创建一组Actions.

Rewards

奖励函数的设计对于模型的训练以及最终的性能都有着重要的影响。
在AlphaStar中使用了非常简单的奖励设计，智能体获胜+1,失败-1，还会加入模仿人类行为的奖励权重。

在OpenAI Five中则采用了更加复杂的奖励函数，可以看到右边的表。
通过变量的调整可以让AI更具攻击性，或者保守获取胜利。

Info

使用Deep reinforcement learning的方法去做游戏AI时，Rewards的获取方式和获取频率的设计都会影响最后的产出。

Network

在AlphaStar中使用了不同种类的神经网络来处理不同类型的输入数据.
如图，最下面是输入和数据，通过不同神经网络产生一段神秘数，最后Decoder翻译成具体操作。
现在Encoder的决策模型就黑盒的，就像炼丹，不确定原理但最终可以work。
在原理不清楚的情况下，只需要确定训练模型能处理什么问题，并搭建起来。