GAMES104课程笔记17-Advanced Artificial Intelligence

这个系列是GAMES104-现代游戏引擎：从入门到实践(GAMES 104: Modern Game Engine-Theory and Practice)的同步课程笔记。本课程会介绍现代游戏引擎所涉及的系统架构、技术点以及引擎系统相关的知识。本节课主要介绍游戏AI的高级技术。

Hierarchical Tasks Network

层次任务网络(hierarchical tasks network, HTN)是经典的游戏AI技术，和上一节介绍过的行为树相比HTN可以更好地表达AI自身的意志和驱动力。

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

HTN Framework

HTN框架中包含两部分，world state和sensor两部分。其中world state是AI对于游戏世界的认知，而sensor则是AI从游戏世界获取信息的渠道。

除此之外HTN还包括domain，planner以及plan runner来表示AI的规划以及执行规划的过程。

HTN Task Types

在HTN中我们将任务分为两类，primitive task和compound task。

primitive task一般表示一个具体的动作或行为。在HTN中每个primitive task需要包含precondition、action以及effects三个要素。

而compound task则包含不同的方法，我们把这些方法按照一定的优先级组织起来并且在执行时按照优先级高到低的顺序进行选择。每个方法还可以包含其它的primitive task或者compound task，当方法内所有的task都执行完毕则表示任务完成。

在此基础上就可以构造出整个HTN的domain，从而实现AI的行为逻辑。

Planning

接下来就可以进行规划了，我们从root task出发不断进行展开逐步完成每个任务。

Replan

执行plan时需要注意有时任务会失败，这就需要我们重新进行规划，这一过程称为replan。

当plan执行完毕或是发生失败，亦或是world state发生改变后就需要进行replan。

总结一下HTN和BT非常相似，但它更加符合人的直觉也更易于设计师进行掌握。

Goal-Oriented Action Planning

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

Structure

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

goal set表示AI所有可以达成的目标。在GOAP中需要显式地定义可以实现的目标，这要求我们把目标使用相应的状态来进行表达。

而action set则接近于primitive task的概念，它表示AI可以执行的行为。需要注意的是action set还包含代价(cost)的概念，它表示不同动作的「优劣」程度。在进行规划时我们希望AI尽可能做出代价小的决策。

Planning

GOAP在进行规划时会从目标来倒推需要执行的动作，这一过程称为反向规划(backward planning)。

在进行规划时首先需要根据优先级来选取一个目标，然后查询实现目标需要满足的状态。为了满足这些状态需求，我们需要从action set中选择一系列动作。需要注意的是很多动作也有自身的状态需求，因此我们在选择动作时也需要把这些需求添加到列表中。最后不断地添加动作和需求直到所有的状态需求都得到了满足，这样就完成了反向规划。

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

总结一下GOAP可以让AI的行为更加动态，而且可以有效地解耦AI的目标与行为；而GOAP的主要缺陷在于它会比较消耗计算资源，一般情况下GOAP需要的计算量会远高于BT和HTN。

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利用当前的策略快速地完成整个游戏过程。

Backpropagate

我们从同一节点出发进行不断的模拟就可以估计该节点的价值(胜率)。

然后把模拟的结果从下向上进行传播就可以更新整个决策序列上所有节点的价值。

Iteration Steps

这样我们就可以定义MCTS的迭代步骤如下：

Selection

在对节点进行选择时，MCTS会优先选择可拓展的节点。

在进行拓展时往往还要权衡一些exploitation和exploration，因此我们可以把UCB可以作为一种拓展的准则。

这样在进行选择时首先需要从根节点出发然后不断选择当前UCB最大的那个节点向下进行访问，当访问到一个没有拓展过的节点时选择该节点进行展开。

Expansion

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

The End Condition

当对树的探索达到一定程度后就可以终止拓展过程，此时我们就得到了树结构上每个节点的价值。

然后只需要回到根节点选择一个最优的子节点进行执行即可。

总结一下，MCTS是一种非常强大的决策算法而且很适合搜索空间巨大的决策问题；而它的主要缺陷在于它具有过大的计算复杂度，而且它的效果很大程度上依赖于状态和行为空间的设计。

Machine Learning Basic

ML Types

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

强化学习(reinforcement learning, RL)是游戏AI技术的基础。在强化学习中我们希望AI能够通过和环境的不断互动来学习到一个合理的策略。

Markov Decision Process

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