作者：苏博览  腾讯IEG高级研究员

| 导语 在一定程度上，人工智能都可以认为是"搜索问题"， 其本质上都是在一个高维的空间上，搜索到一条可行的路径。只是在很多复杂的问题上，求解的空间过于庞大，而解的空间又特别狭窄，造成了无法遍历所有的可能性，而很大概率上无法找到解的空间。

在一定程度上，人工智能都可以认为是"搜索问题"， 其本质上都是在一个高维的空间上，搜索到一条可行的路径。只是在很多复杂的问题上，求解的空间过于庞大，而解的空间又特别狭窄，造成了无法遍历所有的可能性，而很大概率上无法找到解的空间。

在游戏业界常用的搜索算法是基于"树搜索"的, 其本质都是构建一颗搜索树，其节点(Node)代表游戏中的某一个状态。节点之间的连线(Edge)代表游戏中的状态节点A通过某个动作转移到状态节点B。通常从一个节点有多个动作可以到达不同的子节点（状态），因此用不同的方式去选择搜索子节点的顺序就可以区分出不同的搜索算法：

盲目搜索（Un-informed Search): 其实称为 Brute-force Search （暴力搜索）更加合理一些。就是完全不考虑AI的目标和效用，纯粹的去以某种固定的方式去遍历游戏的状态树，以求找到一种合理的路径。这里最常用的两种搜索就是 广度优先（Breadth-first)和深度优先(Depth-first)。具体就不详细展开了，应该是任何一本讲数据结构的书上都会讲到的。

显然这样的算法效率是很低的，基本上是不实用的。但是其一些变体（iterative width search， Sentient Sketchbook) 还是能在游戏的某些方面上应用的。更多的关于Uninformed Search的内容可以参考第四章的内容。

一种改进的算法称为 最佳优先搜索(Best-First Search)。在Best-First Search中，我们通过用AI的目标以某种方式来指导AI的搜索过程，让AI尽可能的优先搜索那些更有可能到达我们目标的节点。这中间，在业界中被广泛应用的是A*算法。在基本的A*算法中，从当前的节点 S可以通过选择不同的动作来进入不同的状态：（S′1,S′2,...,S′n) .那么选择不同状态的cost由当前状态到下一状态的距离dis(S,S′i) 和下一状态到目标的距离 dis(S′i,G) 决定。然后AI会选择cost最低的一个动作来进入对应的新的状态。在这上面，怎么定义距离，以及怎么组合这两个距离都是可以作文章的地方。

A* Planner算法赢得了2009年马里奥AI大赛的冠军，图中的红线表示可能的路线

很自然的，A*算法可以用来做游戏和其他领域的寻路算法。因为在寻路(pathfinding)上，目标和当前状态的距离很好定义，可以简单的定义为当前点和终点的物理意义上的距离，因此可以很好的定义在当前状态下的最好的下一个状态。当然，为了提高在游戏庞大的状态空间中的寻路效率，也有很多A*算法的改进，如grid-based pathfinding，在不少游戏上都有公开的benchmarks (http://movingai.com/benchmarks): 星际争霸(StarCraft),魔兽世界3: 混乱之治(Warcraft III Reign of Chaos)，龙腾世纪:起源（Dragon Age: Origins)。

此外，在某些特定游戏中，只要我们能够很好的定义游戏中的状态之间，以及最终的目标的距离，A*算法也可以构建出非常不错的NPC。比如像超级马里奥(Super Mario Bros)这样的横版或者竖版过关游戏，其当前状态都是和Agent在当前关卡所处的坐标相关的，而最终的目标永远是关卡最右端的结束点，因此可以在这个基础上加入一些当前的障碍物，怪物等的信息，就能比较准确的估计出当前状态的好坏。

而多人之间的对抗性的游戏中，双方的目标是零和的，因此一方的最优状态并不是另一方的最优状态。因此在这样的博弈树(Game Tree)上，尤其是两人对弈的完美信息博弈游戏中，极小化极大搜索(Minimax Search)应用的非常广泛。

一个简单的Minmax树的例子，红色的是玩家行动节点，蓝色是对手行动节点

Minimax的主要思路是，在完整的一个Game Tree上，假定每个玩家都是理性和聪明的，都走其中最好的走法。那么取其中一个玩家的视角，在他行动的时候，选取对其收益最大的Node,也即是在对手下一步行动所有最大收益的最小值，具体的可以由以下的递归伪代码决定。在叶子结点的值(Value)是由终局的状态决定的，如获胜收益为1，失败收益为-1。最终，每个状态节点上都会有一个值。对于玩家来说，每次行动的时候都选取值最大的节点。

def minimax(node, acting_player)
    if node is terminal: #Leaf node        return node.value    if acting_player == opponent: #Mininum Node
        v = MAX_VALUE        for child in node.childs:
            v = min(v, minimax(child,player))
    if action_player == player: #Maximum Node
        v = MIN_VALUE        for child in node.childs:
            v = max(v, minimax(child, opponent))
    return v

但是对于复杂的游戏来说，构建和搜索一颗完整的Game Tree是很困难的，因此对于大部分使用的Minimax算法，都会增加一个参数Depth，来限制树的搜索深度，当达到一定的搜索深度的时候，直接返回一个估计的该节点的Value,这个节点的Value估计可以用规则来实现，也可以用模型来预估。

另外一个提高搜索效率的方法是alpha-beta剪枝，从算法原理上来说，当我们在博弈树第L层（轮到玩家行动）的时候，我们需要搜索玩家可能的N个动作节点 (Node1,Node2,...,Noden) 的时候，如果我们在搜索前t个Node的时候，可以得到当前最大的Value值 α=max(V(Node1),V(Node2),...,V(Noden)) ,那么在搜索 Nodet+1的时候，因为该节点的Value值由其子节点的最小值决定，因此在我们搜索 Nodet+1 的m个子节点 (ChildNodet+11,ChildNodet+12,...,ChildNodet+1m) 的时候，如果搜索到第k个子节点的时候，其子节点的Value 已经小于第L层当前最大的Value值 α 的时候，那么就不用继续搜索k+1个子节点之后的子树了，因为我们知道 V(Nodet+1)=min(ChildNodet+11,...,ChildNodet+1m)⩽V(ChildNodet+1k)<α 。同理可得在搜索对手的极值的时候，也可以用类似的方法来剪枝。只是最小值变成了最大值。

可以看到，即使加上一些剪枝和规则判断的过程，Minimax搜索的过程效率还是不高的。并且Minimax搜索也不能应用到一些非完全信息博弈游戏（如扑克，桥牌）和非确定性的游戏（如大富翁，双陆棋）上。到了2007年的时候，一种新的树搜索方法被发明和应用到游戏中：蒙特卡洛树搜索 Monte Carlo Tree Search(MCTS) ，并取得了极大的成功。

MCTS的四个步骤

和minimax搜索相比，虽然也同样缺乏对于状态的评估函数，但是MCTS通过对不同的子树给予不同的搜索次数和深度来解决树的分支过多的问题。其本质的思想是，在搜索树的某个节点上，通过快速走子(Roll Out)的方式来快速走到终局，从而得到关于该节点的是否能获胜的一点信息，然后基于此信息来修正当前的搜索策略，来决定是否要提高还是降低该节点的权重。这样就规避了要定义一个比较好的State Evaluation的函数的问题，事实上，对于一般的MCTS来说，只有两个信息是需要的：游戏的规则（定义怎么走子和合法动作） 和 终局状态（定义游戏结束的状态）,其起始状态是根节点，然后随着算法的运行，不断的Expand新的节点。通常MCTS是由四个步骤组成的：

Selection: 在这一步中，MCTS从根节点出发，选取一个Score值最大的子节点，直到该子节点有Child Node都没有在之前被访问过。这个Score的定义可以有很多不同的方式，最经典的UCB公式： UCB1=¯Xj+2Cp√2ln(n)nj

, 其中 ¯Xj 是当前Node的所有子节点的平均Reward，这个reward是每次探索的时候都可以通过Back-propagation得到的, n 是该节点的父节点的访问次数， nj 是该节点的访问次数， Cp 是一个固定的系数，控制MCTS探索的权重。可以看到，当 Cp 趋近于0的时候，整个MCTS就倾向于已经探索过的节点的收益(Exploitation); 反之，那些很少被访问过的节点的Score会变得更高，也更倾向于探索(Exploration)。

Expansion: 当MCTS到达一个节点，其有没有访问过的子节点,MCTS就进入了Expansion状态。在该步骤下，MCTS随机选取一个新的子节点加入到已有的搜索树中。

Simulation(Roll Out): 然后，MCTS在这个新的子节点下，使用现有的策略来快速的走到终局，得到一个终局的结果（输或者赢或者一个值）。

Back-propagation: 最后，这个值会作为这些新加入节点的当前Reward, 这Reward同时会向上传递，添加到它的父节点，祖父节点，一直到根节点上。

一个MCTS 在 吃豆人上的应用（Maastricht MCTS Controller)

可以看到，在Roll-Out的时候，通过随机的从某个子节点往下走子，实际上在次数足够多的情况下，是对该节点对应的状态的好坏的一种无偏估计。因此对于像棋牌类游戏这些有很明确的终局状态的游戏，都很适合用MCTS来做。但是对很多游戏（类似吃豆人游戏来说，很难说有一个比较明确的终局状态，或者到达终局状态的深度很深。因此，我们还是要限制树的深度，然后类似Minimax树一样，用一个State Evaluation的Function来返回估计的当前节点会导致的终局情况。

前面讲到，树搜索算法是从初始状态开始，基于合法的动作来生成一颗树，树的叶子节点是终止状态，然后通过搜索，来找到一条最佳的从初始状态到终止状态的路径。而优化算法(optimization algorithm)则是基于任务来构造一个目标函数(Objective function），然后在整个解法空间中，来寻找一个可以最大化目标函数的效用（Utility)的策略(Strategy)。

一. Local Search: 爬山算法和模拟退火

Local Search 是其中最简单的一种优化算法，顾名思义，假设一个solution是N维向量，那么当前给定一个solution s0 （N维空间上的一个点）, 我们就在 s0 附近的区间内寻找一个更好的解法 s1  ,然后再从 s1 出发寻找下一个解法。Local Search在每一代都只保留一个解法，每次都从该解法出发去找寻下一个解法。这个方式其实有点像爬山的过程，因此又叫hill climber算法。但是如下图所示，这个算法很可能会终止在一个local maximum里面。

一维 Hill Climber算法，从当前的状态出发往更好的状态转移（通常是基于梯度的方向），但是到达了一个local maximumn或者半山腰的时候，会发现没法继续找到更好的状态。

为了解决Local Maximum的问题，人们参考突变(mutation)的思想设计了随机爬山算法(Randomized Hill Climber), 从当前的状态 s0 开始，不再是基于梯度的方式，而是随机的改变 s0 的某些维度来得到一个新的状态 s′ ，看是否能到达一个更好的状态，这样，上图中的状态就有机会向左边转变，然后跑到global maximum去。这个算法还是要求突变后的状态要比原理的状态好，因此也不能保证一定能找到最优解。

另外一种方法是模拟退火算法（Simulated Annealing）， 和爬山算法相比，它的搜索过程引入了随机因素。这个退火也是来自于对材料退火的原理。

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。https://zh.wikipedia.org/wiki/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB

我们如果把一个解法(solution)看作空间中的一个原子，那么“加热”的过程相当于随机的改变当前的解法，然后得到一个新的解法。这个时候我们就基于Metropolis准则来判断是否接受新解法：1. 如果新的解法比原来的解法好，我们会接受该解法；2. 如果新的解法比原来的解法差，我们还是有一定的概率来接受新的解法。这个概率是由两个参数决定的: 1. 两个解法的Fitting Function的差值（“能量差”） 和 2. 当前的“温度”（也即是算法的迭代次数）。 因此如果两个解法的差距不大，接受新解法的概率越大；在算法迭代开始的时候，接受新解法的概率也更大一些。参考热力学定律，在温度为 T 时，出现能量差为 ΔU的降温的概率为 exp(−ΔU/T)  , 这个也是我们是否接受新解法的概率。整个模拟退火的伪代码如下：

def simulated_anneling():
  s = s0 #initial solution
  T = T0 #initial temperature  while T > Tmin and E(s) > Emax:
    s_n = random_new_state(s) #get a new state based on s    if E(s_n) > E(s): #get the "energy"(fitness score) of solution
      s = s_n    else:
      dE = abs(E(s_n) - E(s))
      if random(0,1) < exp(dE/T): #accept new solution
        s = s_n
    T = r * T # reduce the temperature, 0<r<1

模拟退火算法与初始值无关，算法求得的解与初始解状态S（是算法迭代的起点）无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。https://zh.wikipedia.org/wiki/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB

演化算法的例子：1和2 crossover 生成3 和4， 3突变生成6， 4突变生成5

二. 遗传算法(Genetic Algorithm)

而如果我们初始化的时候，不是只初始化一个种子，而是同时保留多个不同的solutions,同时更新。每次优化的时候，也不是只保留一个新的解法，而是丢掉比较差的算法，但保留多个不同的解法，我们就得到了演化算法的基本思路。

遗传算法（Genetic Algorithm，简称GA）是一种最基本的演化算法(Evolutionary Algorithm)，它是模拟达尔文生物进化理论的一种优化模型，是全局的随机优化算法（Randomized Global Optimization Algorithms)。遗传算法中从一个或多个初始策略开始（称为初代）, 每一代成为一个种群, 种群中每个个体都是解空间上的一个可行解，通过模拟生物的进化过程，随机的改变部分策略（突变）或者随机的合并多个策略（杂交）来得的新的策略（下一代），从而在解空间内搜索最优解。遗传算法一般是通过Utility Function(或者在演化算法中通常叫Fitness Function)来保留当前更好的策略，而去除一些较差的策略（天择），有些算法还会随机的消灭掉部分的策略，而不管它是不是当前比较好的策略（来模拟自然界中的灾变，比如毁灭恐龙的小行星 和 打个响指的灭霸）。

应该很快某个算法框架的某个模块就叫Thanos了~~

在有些时候，我们的解法是有一定的限制(constraint)的，因此随机的crossover和mutation可能都会产生很多的不合法的解法。但是如果我们给演化的过程增加限制，去除很多的不合法解法的话，很可能我们的演化算法没法找到一个很好的solution，因为初期大部分的演化solution都被杀死了。因此人们提出了feasible-infeasible 2-population(FI-2pop)算法来缓解这个问题。在演化的过程中，算法维护两个队列，一个队列里只包含可用的解法（feasible),另一个队列则没有限制(infeasible)，只要infeasible的队列中产生了可用解法(feasible solution)，这个解法就会放入feasible的队列中。通过这样的方式，FI-2pop找到不同的feasible solution的概率增大了。

三. 进化策略(Evolution Strategy)

在传统的遗传算法中，一般是使用二进制编码（DNA）来编码种群中的个体的，这样最大的好处是做crossover 和 Mutation特别方便，mutation 就是某个位置上的0变成1 或者 1变成0， crossover就可以简单的定义为异或，或者随机选取父辈对应位置的编码就可以了。

但是在很多场景中，个体的特性不是固定的，而是服从某种分布的。比如人的能力，就不是一个固定值，而是会在一定的范围内波动。通过我们假设这个分布是高斯分布，这样我们就可以用均值和方差来表示这个分布了，因此和GA相比，进化策略(ES)的算法表示是两组实数值的编码(DNA)，一组代表该维的均值，另一组代表方差。这样在进化的时候(crossover 和 mutation)也和GA稍有不同，crossover相当于合并两个高斯分布，通常可以考虑合并高斯分布的均值；mutation则可以改变高斯分布的方差。这个改变的幅度也可以用一个权重来控制。基于不同的合并策略，我们可以得到不同的ES的变种。

四. 多目标演化算法

另一方面，演化算法很可能是多目标的(multiobjective)，演化算法要找到一个帕累托最优（Pareto Optimality)的solution,这个解法要满足“不可能再改善某些目标的境况，而不使任何其他的目标受损”。通常来说这个解法不是唯一的。在游戏AI的设计中，我们经常会碰到这样的问题，比如在设计策略游戏的过程中，我们希望设计各方的兵种是各有特色的，同时各方的实力又比较平衡的，这方面的比较好的例子有《星际争霸》。

通常这样的多目标的优化问题很难用数学的方法来进行优化，但是演化算法在这上面比较有优势。 因为演化算法每代都随机的全局搜索，可以产生多个候选的解，构成近似问题的Pareto最优解集；同时在种群中，不同的个体可以满足不同类型的目标函数和约束。常用的多目标演化算法有GA, 蚁群算法等，这里就不详细的阐述了。

星际争霸最大的不平衡点

五. 神经进化算法（Neuroevolution）

前面几篇文章分别讨论了不同类型的AI算法。但是在实际应用中，我们经常会把不同的AI技术混在一起使用，以期获得更好的效果。例如，我们可以用演化算法(GA)来学习行为树的参数，我们也可以像Deepmind那样用神经网络来对MCTS做更有效的剪枝(Pruning)。我们通常称这样的算法为混合算法(Hybrid algorithm)。这里把神经网络和演化算法结合的混合算法就叫做：Neuroevolution。

神经演化算法（Neuroevolution）主要是用演化学习的思想来调整神经网络的结构和权重。通常我们是用梯度下降的方法来更新神经网络的结构，但是如果我们不能很好的用监督学习的方法来训练神经网络的时候（例如训练的神经网络的loss function没法微分(differentiable)，或者我们没有一个很好的标注的训练样本），这个时候我们就要考虑演化学习的框架了。这个在游戏AI中经常能够遇到，比如我们很难定义一个行为是不是好的（如王者荣耀中，一个英雄在某个场景中使用某个技能是好的还是坏的）。而在演化学习的框架下，我们只需要考虑一个对Solution（某个训练好的神经网络）的度量（fitness function)。其中基于NEAT算法(NeuroEvolution of Augmenting Topologies 增强拓扑的神经网络进化), 人们开发了可以玩马里奥的AI，具体的代码实现可以看下面的链接。

Mar I/O : AI玩转马里奥

当然，演化学习需要在每一代都保留多个可用的模型，然后在随机进行crossover 或者 mutation。可想而知，这是一件非常耗费计算能力的事情，所以目前为止能得到的网络规模也不大、完成的任务也不够复杂。不过去年底的时候， Uber AI Lab一连发了5篇文章来证明Neuroevolution 也可以高效的训练大规模的神经网络。这里就不具体的描述其算法啦，有兴趣的可以到Uber 公开的Github去看它的源码和论文。

本文来自《游戏人工智能》 读书笔记，作者：苏博览

作者： fled

本文内容包含以下章节：

Chapter 2 AI Methods

Chapter 2.3 Tree Search

本书英文版： Artificial Intelligence and Games - A Springer Textbook

原文链接：https://zhuanlan.zhihu.com/p/36479131