我喜欢玩星际争霸，当我操作我的部队用快捷键A进攻敌人时，部队就会自动避开障碍物attack目标。当时我就对为什么部队能自动选择最短的路进攻产生了兴趣，它是用什么算法实现的。而且当你的对手是电脑时，是用什么方法使电脑能实现人工智能在决策点决定自己的行为的。

      我在网上搜索了一下，有一种叫A*（启发式搜索算法）能实现人工智能中的路径搜索问题，启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。

在《人工智能技术导论》一书中，提到了状态空间搜索，状态空间搜索就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。也就是在解一个问题时，找到一条解题的过程可以从求解的开始到问题的结果。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

但是光寻路还不行，有的时候让计算机考虑出当前最好的决策是不够的，我们必须要考虑到每一个行动对以后的全局的影响。实际上，我们的目的是要能算出从当前状态开始到最终目标为止整个过程的最佳决策序列。在确定的环境中，可以用A*这类搜索算法来实现。但是如果一个动作产生的结果不是唯一的，而是有几种可能之一，此时就这种随机性就破坏了A*算法的要求，在游戏中随机现象随处可见：攻击次序，咒语的结果，技巧的运用等等，

而动态规划算法（DP）能解决这一问题，DP算法能够在一张随机地图上找出两点的最短路径，随机地图是相对于确定地图而言，因为随机地图上的每一步操作的结果都是随机的，所以即使是同样的操作序列也会产生不同的结果。

          以一个简单的二维随机地图上的寻路问题为例来说明这种算法。如图：

一个机枪兵从D4出发到A6去攻击对手，他不能很好地控制自己的行动：如果他本意是向前走，结果会有0.5的可能性向右拐，0.25的可能性向左拐，具体点就是，如果他从D4向北走，走到C4，D3，D5的概率分别为0.5，0.25，0.5.任何时候他撞到障碍物（比如是墙）都要回到原来的格子。

        我们从D4到A6寻找最短路径。当然A*算法可以实现，但是由于随机性因素的存在，A*算法会做大量庸余的计算。除此之外，用A*可能会产生完全错误的路径，如假如在C5上有一个狂热者，他会杀死任何撞到他身上的机枪兵。A*算法，就会认为只要机枪兵只要不走狂热者的格子，在狂热者旁边溜走也行（C4,B4,B5和D5,D6,B6），实际上，机枪兵如果选择刚才所说的任何一条路，他都有0.5的概率被杀死。

       DP算法就可以很好的解决这类问题。它可以很容易的找到途中问题的最优路线。当然相对于A*，它需要更多一些数据来设置。因为在确定地图中，从起点到终点找到一条最短路径就可以了，但是在随机地图中，我们需要计算出每一种起始状态到终点的最佳路径。

      我们来具体解决这个问题。起始任何一种搜寻最短路径的算法都必须有比较路径好坏的方法。比较路径长短是一种很自然的方法，路径的长短可以想象成每一步长度的累加和。但是，现实问题却不是这样的，如果地图上有不同地形怎么办，如在魔兽中有高地，森林，水地等，过各种地形的代价也是不同的。所以我们应该把过高地的代价啊设为5，过平地的代价为1，过水地的代价为8等等。所以我们不能在说最短路径的概念，而是最佳路径。

      在这个图中，我们可以用代价100表示狂热者所在的格子，我们要寻找一条绕开它的路线，DP算法首先就要知道目标格子，每个格子的代价，每个操作产生结果的概率表。如图，当然目标格子用代价0代替，一旦到那，机枪兵就陷在那不做任何动作，是算法不至于陷入死循环。如图：

还要明确一点就是没有起始格子了，因为算法要把所有格子到目标格子的最佳路径都算出来。这是必须的，因为机枪兵有可能走到途中任何一个格子上，那时就知道从那个格子该怎么走。所以它没有A*算法那么快，但是可以进一步优化这一步。

    下面说一下概括的算法实现。算法始终维护着一个装有代价值的数组，数组的长度等于地图上的格子数，DP算法不断更新数组，每个格子到目标格子的代价累计估计值被记录下来。当算法结束时，数组中的每个元素就是每个格子到目标格子的最少代价。如

1.       初始化数组中的各个元素。

2.       对每个格子首先计算所有在这个格子中可选择动作的代价值。接着选择一个代价最小的代价。最后把该格子的代价值设为被选择动作的代价加上格子本身的代价。

3.       重复（开始下一个周期，回到第二步骤）

        比如我们可以设上叙第二步中，每个动作的代价等于各个邻接格子的代价值与各自对应概率乘积的累加。

在这个过程中，我们要考虑到底需要多少个周期才够用。根据DP算法可知数组中的代价值会收敛，但是可能会花很长时间。我们关心的是是否得到了最优的路径。明确了目标，我们就不需要那么多的周期数。最理想的情况是，我们就让程序运行能得到最佳路径的最短周期，但是要真正实现却很难，因为我们事先并不知道这个周期数，所以DP算法是一种依奈细节层次的算法。

最后我们还必须考虑一下如何从格子代价值数组中获得最佳路径，假设最佳路径的结果保存在数组A中，如

1.       用一个可能的动作来初始化结果数组A。

2.       对每个在该格子上可能的动作计算出该动作的代价值，把最小代价的动作保存到结果数组A中，如果几个动作代价值相同，取缺省的一个或或随机取一个。

 

下面是我自己给出的框架图来描叙这个过程。

实际上上面的DP算法实现在大地图上效率是不高的，但是我们可以采取优化的方法来改进，如我们可以先以一个包含起点和终点的子图为基准单位，运行DP算法，不包括大多数离它们很远的部分，如果某些原来没有包括进子图的资源变得可以计算了，我们就扩大范围，并把计算好的子图作为新子图的初始信息，以新子图为基准单位继续下去，因为在这个过程中我们利用了以前的计算结果，无疑会身很多处理。

DP算法的应用不以上寻路，还有很多应用。比如有个电脑的火焰兵要找你决斗，应用DP算法，我们要设置目标状态，动作，状态空间和代价。目标状态就是玩家战死；动作可以简单的分进攻，防守，移动；状态必须把所有关于决斗的东西描叙出来，如玩家位置，生命值，火焰兵的位置等等，我们可以把状态用一个数组表示如（a(玩家位置),b（生命值）,c（火焰兵的位置）），DP的搜索状态空间就是以上几个变量的所有组合，各个状态用动作连接起来的。代价值数组的大小就等于状态空间的大小，DP算法会计算出每一个状态上，每一个可用动作的代价值，选出其中最小的，然后更新代价值数组，当算法收敛时，我们就根据代价值数组输出最佳动作序列。在这个过程中我们还可以加如更多的细节，如喷火的量级，还可以用更多的变量来扩展空间。

       以DP算法为基础应该有很多扩展的算法，实现更多的功能，而且有更优的改进，如可以在DP算法中加入学习和采样能力变成一种DP算法的变种等等。因为我没有找到相关游戏的源代码，不知道这类游戏是否是采用的这种方式。在以后的学习中将查找更多的资料来更深的认识相关算法，实现人工智能。