(3.3.1)--游戏与AI.pdf

游戏与AI游戏人工智能游戏AI是属于弱AI的范畴，是人工智能科学技术领域的一个新兴的、活跃的学科分支，是计算机游戏和人工智能相结合的产物。游戏AI的定义是非常广泛的和灵活的，凡是能够产生适当水平的智能从而让游戏更加逼真，有挑战性，最重要的是是游戏变得更加有趣的东西都可以被当作为游戏的AI。一般说来就是指游戏中，计算机控制的非玩家角色能够模拟人类思维或者现实中的其他生物，表现出一定的智能行为，好的AI使游戏变得更加逼真，更加接近现实。1、以规则为基础2、以目标为基础3、以代理人为基础4、以人工生命为基础游戏人工智能的模式：游戏AI技术人工智能是多种智能技术的组合体，在电脑游戏中，每一种技术在游戏中都有较固定的应用。有限状态机脚本语言模糊逻辑决策树神经网络遗传算法有限状态机(Finite State Machine，ieFSM)也是计算机游戏中应用普遍的人工智能模型。通常，这类系统描述了一个事件驱动系统模型，易于规则表达。一般的，状态机可以用状态转移图的方式描绘。其中的节点表示不同的状态，不同状态之问由于触发条件而发生转换，用弧线表示。有限状态机死亡逃离玩家追逐玩家（主状态）复活四处游走玩家再生玩家死亡玩家吃掉能量球能量球耗尽玩家吃掉Ghost变成阴暗返回中央走出房间模糊逻辑（Fuzzy Logic），模仿人脑的不确定性概念判断、推理思维方式，对于模型未知或不能确定的描述系统，以及强非线性、大滞后的控制对象，应用模糊集合和模糊规则进行推理，表达过渡性界限或定性知识经验，模拟人脑方式，实行模糊综合判断，推理解决常规方法难于对付的规则型模糊信息问题。模糊逻辑决策树一般都是自上而下的来生成的。每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。树决策树类似于一系列IF-THEN形式的条件判断。这种技术在游戏中可用于分类、预测和学习。决策树遗传算法是近年来发展起来的一种崭新的全局优化算法。它借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等机制，实现各个个体的适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。遗传算法神经网络是一种模范动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。神经网络11状态空间法是将问题转换到对应状态空间，以状态空间的分析方法来分析问题，是解决简单问题常用的有效方法。大型的游戏智能系统的局部智能表象模拟通常是采用状态空间法。状态（state）状态是描述某类不同事物间的差别而引入的一组最少变量的有序集合，表示为：Q=q0，q1，qnT，其中Q中的每个变量qn称为状态变量。算符使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可以是过程、规则、数学算子、运算符号或逻辑符号等。状态空间法12状态空间（state space）状态空间表示问题的全部可能状态及其关系图，它有各自的起始状态，还有一个目标状态，而每一种走法都是一种状态，所有可能的状态组成了状态空间。它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。可把状态空间记为三元状态（S，F，G）。状态图状态图是把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组成的图。状态空间法13“状态空间法”实例分析猴子取香蕉问题：在房间内有一只猴子、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到香蕉，猴子需要踩到箱子上才能取得香蕉。问题：猴子如何才能取得香蕉？14分析题目，得到两个重要的状态空间：初始状态、目标状态。猴子取得香蕉的步骤如下：（1）猴子要取得香蕉，需要走到箱子的后面。（2）推动箱子到香蕉的下面。（3）猴子跳上箱子。（4）取得香蕉。15设置状态，用一个四元表列（W，x，Y，z）来表示这个问题的状态：W：猴子的水平位置；X：当猴子在箱子顶上时取x=1；否则取x=0；Y：箱子的水平位置；Z：当猴子摘到香蕉时取z=1；否则取z=0。状态转换过程：（1）猴子的初始状态（W，0，Y，0），将猴子和箱子的坐标加入到初始状态（a，0，b，0）。（2）猴子走到盒子的位置，判断香蕉的位置，决定箱子向右还是向左移动。状态由（a，0，b，0）（b，0，b，0），猴子和箱子的状态如图所示。（3）猴子将箱子推到香蕉的正下面，状态由（b，0，b，0）（c，0，c，0），猴子和箱子的状态如图所示。（4）猴子爬上箱子，状态由（c，0，c，0）（c，1，c，0），猴子和箱子的状态如图所示。（5）猴子站在箱子上取到香蕉，状态由（c，1，c，0）（c，1，c，1）。17A*算法是目前最快的一种计算最短路径的算法，它结合了启发式方法和形式化方法。它通过一个估价函数f（h）来估计当前点到终点的距离，并由此决定它的搜索方向，当这条路径失败了，就尝试其他路径。启发式搜索启发式搜索算法是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。评估函数评估函数是一个状态描述的一个实数值函数，用来确定下一个要扩展的最优节点。A*算法18A*算法是一种“最好优先搜索”算法，也是一种启发式的算法。A*算法在搜索的时候，在每一步的评估中都把当前的节点和以前的节点的评估值进行比较，得到一个“最佳的节点”。A*算法的评估函数表示为：f（n）g（n）h（n）f（n）：评估函数；g（n）：从起始点到地点n的最短距离；h（n）：n到目标的最短路径的启发值。从数学上证明：如果从地点n到目的地的实际最短距离总是大于或等于h（n）的话，则A*算法是全局最优的，也就是说A*算法总能找到最短的路径。A*寻径算法19“A*算法”实例分析二维地图的寻径A*算法在游戏的应用体现在对游戏地图的路径的选择上，以简单的二维地图作为例子，二维地图从另一个角度来看是一个拼接地图，由大小相同的图片拼接而成。游戏的主角从左下角走到右上角，其中障碍和树木是不能通过的，A*算法如何解决这个问题？首先，创建一个空list，命名为open，用此list来存储还需要考察的格子；然后创建再另一个空list，命名为Closed，用此list来存储已经考察过的格子并创建格子的数据结构，可以使用结构体（struct）或类（class），需要包括下面几个属性：g：用来存储从起始点到这个格子的距离；h：用来存储从这个格子到目的地的路径的距离；f：用来存储评估函数的数值，也就是gh；parent：指针，用来记录上一步的格子，最后形成总路径时从目的地回溯时用；loc：可以使用结构体或类，用来存储坐标信息。定义数据结构21算法过程将起始点的格子存入Open，计算起始点的h，g，f，parentnull。while（open=空）从open中所存储的所有格子中，取出f值最小的格子if（此格子是目的地）then寻径成功；回溯输出路径；else考察此格子上下左右的四个邻居if（此邻居不是障碍物）计算其新g值；if（该邻居已在open或closed，并其新g值j旧g值）else更新其g，h，f，parent值if（该邻居在closed中）将其从closed中删除if（该邻居不在open中）将其存入open中将该单元格存入closed中；