游戏人工智能 读书笔记 （五） AI算法简介——树搜索

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

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

作者： fled

本文内容包含以下章节：

Chapter 2 AI Methods

Chapter 2.3 Tree Search

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

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

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

在游戏业界常用的搜索算法是基于"树搜索"的, 其本质都是构建一颗搜索树，其节点(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个动作节点 (Node_1,Node_2,...,Node_n) 的时候，如果我们在搜索前t个Node的时候，可以得到当前最大的Value值 \alpha = max(V(Node_1),V(Node_2),...,V(Node_n)) ,那么在搜索 Node_{t+1} 的时候，因为该节点的Value值由其子节点的最小值决定，因此在我们搜索 Node_{t+1} 的m个子节点 (Child^{Node_{t+1}}_1,Child^{Node_{t+1}}_2,...,Child^{Node_{t+1}}_m) 的时候，如果搜索到第k个子节点的时候，其子节点的Value 已经小于第L层当前最大的Value值 \alpha 的时候，那么就不用继续搜索k+1个子节点之后的子树了，因为我们知道 V(Node_{t+1}) = min(Child^{Node_{t+1}}_1,...,Child^{Node_{t+1}}_m)\leqslant V(Child^{Node_{t+1}}_k)<\alpha 。同理可得在搜索对手的极值的时候，也可以用类似的方法来剪枝。只是最小值变成了最大值。

可以看到，即使加上一些剪枝和规则判断的过程，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 = \bar X_j + 2C_p \sqrt{\frac{2ln(n)}{n_j}}

, 其中 \bar X_j 是当前Node的所有子节点的平均Reward，这个reward是每次探索的时候都可以通过Back-propagation得到的, n 是该节点的父节点的访问次数， n_j 是该节点的访问次数， C_p 是一个固定的系数，控制MCTS探索的权重。可以看到，当 C_p 趋近于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来返回估计的当前节点会导致的终局情况。