游戏中的人工智能技术

游戏中的人工智能技术浙江大学计算机学院学习内容和目标游戏AI的基本概念游戏中简单的AI模式游戏中常用的AI技术◦有限状态机◦A¤，模糊逻辑等实现AI引擎的要点GAMEAI技术简介（1）GAMEAI的描述◦使得游戏表现出与人的智能行为/活动相类似，或者与玩家的思维/感知相符合的特性。GAMEAI的实现◦技术实现利用充分的领域知识和常识客观世界的运动规律(gamephysics)利用已有的AI技术◦融合娱乐性GAMEAI技术简介（2）游戏中涉及的AI技术◦专家系统用知识表示专家的经验，并在此基础上作自动推理◦案例式推理将输入与数据库中已有的案例进行比较，选取最为相近的案例，其已有的解决方法即为输出◦有限状态机基于规则的系统，有限个状态连接成一有向图，每一条边称为一个转移GAMEAI技术简介（3）游戏中涉及的AI技术（续）◦产生式系统包含多个产生式，每一条产生式由条件和动作两部分组成，当产生式的条件满足时，系统就执行相应的动作◦决策树给定输入，从树的根部开始，将输入与当前结点相比较，选择当前结点的某一个子结点作为下一次比较的对象。当到达树的叶子时，则给出相应的决策◦搜索方法找到一列动作（或状态转移），使得最终的结果满足某一特定目标GAMEAI技术简介（4）游戏中涉及的AI技术（续）◦规划系统给定世界的初始状态，以及下一步可能采取的动作的精确定义，找到完成某个特定目标的最优路径◦一阶谓词逻辑谓词逻辑通过定义“物体”、“属性”、“关系”等对当前场景的状态进行推理◦情景演算用一阶逻辑计算在给定情景下AI生命的反应GAMEAI技术简介（5）游戏中涉及的AI技术（续）◦多Agent研究在多个相互竞争相互合作的智能体之间所产生的交互智能行为◦人工生命多agent系统一种，试图将生命系统中一些普遍规律应用到虚拟世界的人工智能体上◦群组行为(Flocking)人工生命的一类，研究协同移动技术，例如人工智能体如何在大量的羊群中移动GAMEAI技术简介（6）游戏中涉及的AI技术（续）◦Robotics让机器在自然环境下交互的工作◦遗传算法直接模拟生物进化过程，通过随机选择、杂交和突变等对程序、算法或者一系列参数进行操作◦神经网络模拟动物神经系统功能的机器学习方法通过反复调节系统内部中各个神经元之间的连接参数，使得训练得到的系统在大多数情况下作出优或者近似优的反应GAMEAI技术简介（7）游戏中涉及的AI技术（续）◦模糊逻辑与传统二值（对-错）逻辑不同，模糊逻辑用实数表示物体隶属于某一类的可能性◦置信网络提供建立不同现象之间内在因果关系的工具，并利用概率理论处理未知的和不完全的知识对当前状态作出判断，并决定下一步可能的动作以及其带来的后果GAMEAI技术简介（8）GAMEAI技术的分类◦确定型基于领域固定领域知识，模拟简单的固定行为◦行为型基于行为模式来模拟智能行为◦战术型策略模拟RTS（realtimestrategy）◦其他确定型AI算法确定性算法指预先编入代码当中的可预测的行为◦从最简单的算法开始例如，系统中有一颗小行星，以某一速度作匀速直线运动，它在任意时刻的位置由下列公式决定：某种程度上，它们是智能的，但是这种智能是确定的，可预测的Tracking/ChasingAI当智能体找到目标后，一心一意向其移动，而不考虑任何其他的因素，例如障碍物、另外的目标等非常机械化在每一帧中，智能体计算其到目标的前进方向，并根据其速度，前进一段距离浙江大学CAD&CG国家重点实验室Tracking/Chasing算法Tracking算法还可以做的更为真实一点，就像红外导弹一样：◦在每一帧中，智能体仍然首先计算其到目标的前进方向◦这时，智能体的速度允许发生变化，并根据更新后的速度，计算下一帧的位置◦速度有一个上限，超过这个上限，智能体的速度将减慢，直到重新加速为止浙江大学CAD&CG国家重点实验室Evading算法与前面的chasing算法基本相同，唯一区别是智能体沿着远离物体的方向移动浙江大学CAD&CG国家重点实验室追逐行为的模拟示例你追我赶GameAI/chasingandavoidingdemo基于行为模式的AI在任一时间点，每一个智能体都按照预先设定的某种模式运动决策系统根据系统当前的状态，为每一个智能体从模式集合中选择适当的模式模式描述了智能体将在下面几帧中所采取的一系列动作特例：scriptedAI，当系统到达某一特定状态（例如，每个回合的结束），系统运行的一段程序（用脚本写），决定系统下一步的动作典型的行为模式基本模式◦用一段指令定义模式◦写一个解释器解释这段指令，并用于控制智能体的行为条件逻辑模式◦更为灵活的控制◦可以通过条件逻辑选择模式◦也可以选择本身带有条件逻辑转移的模式编程技巧非常直观◦Pattern是一列数组◦数组的每一项定义智能体在该帧的速度（方向＋大小）◦在模拟过程中，智能体就按照预先设定的参数在每一帧之间运动◦当移动到数组末尾时，重新选择一个新的模式行为型的AI技术示例ChasingbehaviorAIdemo策略性AI与通用问题求解AI的研究人员试图寻找一个通用的计算模型和方法，解决所有的问题◦感知输入系统◦有一个记忆模拟存储系统◦推理机◦行为输出系统博弈问题◦有限状态机（FSM）◦规划和搜索有限状态机状态（要采取的行为）◦追击◦随机走动◦巡逻◦吃转移（发生转移的原因）◦时间片结束◦发生某个时间◦完成某个行为伐木将木头运往最近的仓库足够多木材放下木头:返回林场到仓库到林场有限状态机机器◦所有部件的总称状态◦对于层次有限状态机而言，状态包括各种子状态转移◦系统从当前活动状态出发，判断下一个活动状态，改变系统当前的格局，并执行相应的操作浙江大学CAD&CG国家重点实验室有限状态机条件◦定义发生转移的先决条件输入和事件◦允许状态机对环境变化作出反应动作◦作为状态的一部分，或者伴随转移出现浙江大学CAD&CG国家重点实验室状态空间图有向图每个结点表示系统状态模型，每条弧表示状态转移所伴随的动作行为结点可以是无穷多个有些结点之间可能没有弧相连接特定状态的查找结点－包含查找目标终点－搜索路径的结束查找空间－所有结点的集合目标－所要到达的结点经验－在一定程度上提示下一步搜索的方向解答路径－从起始结点开始，到目标的一条有向路径模糊的有限状态机将模糊逻辑和有限状态机结合◦状态之间的迁移不再是确定的◦同时有多个状态有限状态机和模糊的有限状态机示例FSM/FuFSM代码示例◦隶属度演示规划Partofintelligenceistheabilitytoplan-MovetoagoalState将系统表示成一系列状态的集合通过操作（Operator）改变状态浙江大学CAD&CG国家重点实验室路径规划状态◦智能体在空间的位置◦其他离散空间体素室内位置局部区块（tile）操作◦从一个位置移动到其他位置浙江大学CAD&CG国家重点实验室路径规划算法必须对状态空间进行搜索，才能转移至目标状态完全性◦如果目标状态存在，算法是否能够将其找到？时间复杂度空间复杂度能够找到最优解浙江大学CAD&CG国家重点实验室搜索策略如何评价搜索算法◦时间：多长时间能够找到解◦找到的解是最优、次优还是其他盲目搜索◦没有先验知识◦仅仅知道目标状态是什么经验搜索◦用经验公式表示拥有的先验知识◦“经验”只能作相对简单、低级的决策浙江大学CAD&CG国家重点实验室广度优先搜索根结点-儿子结点-孙子结点缺点：内存消耗大浙江大学CAD&CG国家重点实验室RootRootChild1Child2RootChild1Child2GChild1GChild2GChild3GChild4(1)(2)(3)深度优先搜索先儿子结点，后兄弟浙江大学CAD&CG国家重点实验室RootChild1GChild1GChild2RootChild1RootChild1GChild1(1)(2)(3)双向搜索同时产生两棵搜索树◦一棵从起点出发◦一棵从目标出发浙江大学CAD&CG国家重点实验室启发式搜索定义目标函数，反映拥有的先验知识◦估计离目标的距离◦估计到达目标的花费用上述估计指导路径的搜索，加快搜索过程浙江大学CAD&CG国家重点实验室贪婪搜索法永远沿着具有最小目标函数值的路径进行搜索不一定能够找到目标可能得到局部最优解，而不是全局最优浙江大学CAD&CG国家重点实验室A*启发搜索考虑到贪婪搜索法不能保证找到最优解改进－目标函数由两个部分组成◦从当前状态到目标状态的“花费”（估计）◦从初始状态到当前状态的“花费”浙江大学CAD&CG国家重点实验室基本想法贪婪搜索法◦对可能的后继状态n’，计算其到目标状态的“花费”h(n’)，并置于一个优先队列中A*◦对可能的后继状态n’，计算其目标函数f(n’)，并置于优先队列中◦f(n’)=g(n’)+h(n’)，其中g(n’)是从初始状态到n’的“花费”浙江大学CAD&CG国家重点实验室基本想法选择下一步状态n，使得f(n)是队列中最小的如果h(n)估计准确的话，方法是可行的浙江大学CAD&CG国家重点实验室结束条件A*算法结束条件是：当且仅当目标状态被从优先队列中挑选出来1h=311h=7h=217h=17h=0SABCGD浙江大学CAD&CG国家重点实验室A*算法优先队列PQ－初始为空V（一系列三元组(状态，f，回溯指针)集合，表示访问过的结点）－初始为空将初始结点S置于PQ中，V中放入(S,f(s),NULL)算法：◦如果V为空，退出程序，没有解◦否则，从PQ中取出第一项，记为n◦如果n就是目标结点，则搜索结束◦否则，产生n的后继结点浙江大学CAD&CG国家重点实验室A*算法对n的每一个后继结点n’◦计算f’=g(n’)+h(n’)=g(n)+cost(n,n’)+h(n’)◦如果n’未被访问过，或者n’曾经被访问过，但是记录的f(n’)f’，或者n’已经在PQ队列中，但是记录的f(n’)f’放置/更新n’于优先队列中，使其对应的目标函数值为f’添加(n’,f’,n)至V当中◦否则忽略n’浙江大学CAD&CG国家重点实验室A*算法能否找到最优路径否SAGh=613h=01浙江大学CAD&CG国家重点实验室A*算法性质令h*(n)=从目标到n最小花费真实值.经验h称为可行的当且仅当对所有的状态n,h(n)＜=h*(n).可行经验确保永不过估计结点到目标的花费具有可行经验的A*算法一定收敛到最优解比较费内存当不存在解时，算法失败◦避免对全空间进行搜索◦作双向搜索路径的规划和寻找演示Astardemo◦最短路经◦战术最短路经暴露时间有效火力视野群体行为的模拟（1）物群的行为◦物群聚集在一起飞行，遇到另一物群时，他们将避开和分散，必要时分成多群◦分开后，将寻找伙伴，形成新的物群，并最终恢复原来的物群◦物群能够对付突发行为，能否对不断变化的环境做出实时的反应，并作为一个整体行动◦。。。。。。群体行为的模拟（2）物群模拟的简单规则◦分离（separation）：同物群中的其他成员若即若离。◦列队(alignment)：与物群中的其他成员保持相同的航向◦内聚(cohesion)：不掉队◦避开（avoidance）：避开障碍物和天敌◦生存（survival）:必要时进行捕食或者逃脱被吃◦……..群体行为的模拟（3）游戏中的物群行为◦RTS游戏的部队的编队模拟◦RPG游戏中的群体行为模拟行为模拟的实现◦无状态◦不纪录任何信息◦每次将重新评估其环境群体行为的模拟（4）示例◦前进方向不确定，但整体行动◦避开障碍物◦飞行动物老鹰：飞行速度快，视野广，吃麻雀麻雀：飞行速度一般，视野一般，吃昆虫昆虫：飞行速度慢，视野小，不捕食，能繁殖◦物群的喂养饿→吃→试图接近猎物昆虫不能灭绝群体行为的模拟（4）演示