14-游戏中的人工智能-249

游戏中的人工智能技术学习内容和目标游戏AI的基本概念游戏中常用的AI技术有限状态机模糊逻辑A*寻径棋类游戏AI游戏AI任天堂8位机ACT游戏，不存在AI，敌人的招式都是固定好的。FPS和RTS类游戏出现后，AI技术开始发扬光大游戏中实际使用的AI(ArtificalIntelligence)和学术上的AI不完全相同游戏业AI的指导思想：用最简单的方法、占用最少的资源，去愚弄玩家，造成假象，让他们觉得游戏AI水平很高。（“能骗就骗”）游戏AIGAMEAI的描述使得游戏表现出与人的智能行为/活动相类似，或者与玩家的思维/感知相符合的特性。GAMEAI的实现技术实现利用充分的领域知识和常识客观世界的运动规律(gamephysics)利用已有的AI技术融合娱乐性确定型AI算法确定性算法指预先编入代码当中的可预测的行为从最简单的算法开始例如，系统中有一颗小行星，以某一速度作匀速直线运动，它在任意时刻的位置由下列公式决定：某种程度上，它们是智能的，但是这种智能是确定的，可预测的Tracking/ChasingAI当智能体找到目标后，一心一意向其移动，而不考虑任何其他的因素，例如障碍物、另外的目标等非常机械化在每一帧中，计算智能体到目标的前进方向，并根据其速度，前进一段距离Evading算法与前面的chasing算法基本相同，唯一区别是智能体沿着远离物体的方向移动有限状态机FSM(FiniteStateMachine,有限状态机)最古老最普遍状态（要采取的行为）追击随机走动巡逻战斗转移（发生转移的原因）时间片结束发生某个时间完成某个行为简单而实用例如：某NPC等待警戒追逐战斗死亡伐木将木头运往最近的仓库足够多木材放下木头:返回林场到仓库到林场模糊逻辑传统逻辑把思维过程绝对化，从而达到精确、严格的目的举例：一个被讨论的对象X，要么属于某一个集合A，要么不属于该集合模糊逻辑允许我们用一个[0,1]的实数表示X属于A的隶属程度。传统逻辑即隶属程度只能从0和1之间选择的情况对于命题：张三的性格稳重，如何判断这一命题的真假？“一点而也不稳重”、“不太稳重”、“不好说”、“有点稳重”、“挺稳重”、“很稳重”模糊逻辑的应用在AI领域的主要应用为决策行为选择输入、输出过滤15feet6feet7feet15feet6feet7feet大约6英尺长的高的人模糊状态机FSM太规范了，只处理确定性的事，容易被玩家识破FuSM(Fuzzystatemachine，模糊状态机)-将模糊逻辑和有限状态机结合状态之间的迁移不再是确定的同时有多个状态警戒躲避追逐一定概率下决定躲避还是追逐基本AI技术介绍AI脚本和可扩展性AI：让游戏设计师（不是程序员！！）决定NPC的AI游戏设计师的力量和时间是有限的，玩家的数目和热情是无限的，让玩家决定NPC的AIQuakeHalfLife博得之门等需要玩家有一定的编程基础，需要相应的接口手册、技术服务等基本AI技术介绍-寻径算法简单：朝着目标前进，不通，顺/逆时针方向拐(Ch6-4)深度优先搜索策略，广度优先搜索策略Dijkstra算法，A*算法的最简化版本（严格意义上不是A*算法）启发式A*算法搜索策略如何评价搜索算法时间：多长时间能够找到解找到的解是最优、次优还是其他盲目搜索没有先验知识仅仅知道目标状态是什么经验搜索用经验公式表示拥有的先验知识广度优先搜索根结点-儿子结点-孙子结点缺点：内存消耗大RootRootChild1Child2RootChild1Child2GChild1GChild2GChild3GChild4(1)(2)(3)深度优先搜索先儿子结点，后兄弟RootChild1GChild1GChild2RootChild1RootChild1GChild1(1)(2)(3)启发式搜索定义目标函数，反映拥有的先验知识估计离目标的距离估计到达目标的花费用上述估计指导路径的搜索，加快搜索过程A¤启发搜索考虑到贪婪搜索法不能保证找到最优解改进－目标函数由两个部分组成从初始状态到当前状态的“花费”从当前状态到目标状态的“花费”（估计）基本想法目标函数由两个部分组成从初始状态到当前状态的“花费”从当前状态到目标状态的“花费”（估计）对可能的后继状态n’，计算其目标函数f(n’)，并置于优先队列中f(n’)=g(n’)+h(n’)，其中g(n’)是从初始状态到n’的“花费”选择下一步状态n，使得f(n)是队列中最小的如果h(n)估计准确的话，方法是可行的A¤算法优先队列PQ－初始为空V（一系列三元组(状态，f，回溯指针)集合，表示访问过的结点）－初始为空将初始结点S置于PQ中，V中放入(S,f(s),NULL)算法：如果V为空，退出程序，没有解否则，从PQ中取出第一项，记为n如果n就是目标结点，则搜索结束否则，产生n的后继结点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’路径的规划和寻找演示Astardemo最短路经战术最短路经暴露时间有效火力视野A*寻径算法在更复杂情况下的应用：更好的划分地图的方法分层寻径其他地形分析角色属性战术性、策略性更加复杂的移动问题更加自然的移动（不求最短、但求自然）路径锁定优先权系统团队寻径限制同时选定的移动单位个数把寻路工作在时间上分散进行探路兵保持队形-畜群算法：间距性齐向性内聚性群体行为的模拟（1）物群的行为物群聚集在一起飞行，遇到另一物群时，他们将避开和分散，必要时分成多群分开后，将寻找伙伴，形成新的物群，并最终恢复原来的物群物群能够对付突发行为，能否对不断变化的环境做出实时的反应，并作为一个整体行动。。。。。。群体行为的模拟（2）物群模拟的简单规则分离（separation）：同物群中的其他成员若即若离。列队(alignment)：与物群中的其他成员保持相同的航向内聚(cohesion)：不掉队避开（avoidance）：避开障碍物和天敌生存（survival）:必要时进行捕食或者逃脱被吃……..群体行为的模拟（3）示例前进方向不确定，但整体行动避开障碍物神经网络简化的人脑模型人脑大概有1012个神经元每一个神经元都能够处理和发送信息神经元的三个主要组成部分：细胞体，神经元新陈代谢的中心树突，接收来自其他神经元的信号轴突，向其他神经元发送信号神经网络生物学发现神经元是人脑的基本组成部分如果将神经元看作结点，它们之间的连接看作弧，则这些神经元组成一个稠密连接的图虽然单个神经元的工作过程较简单，当大量神经元连成一个网络并动态运行时，系统是非常复杂的人工神经元模型是人类大脑神经元的简化N个输入1个输出作用函数一个处理单元将接收的信息x0,x1,,xn-1通过用W0,W1,,Wn-1表示互联强度，以点积的形式合成自己的输入，并将输入与以某种方式设定的阈值相比较，再经某种形式的作用函数f的转换，得到该单元的输出yf可以是阶梯函数、线性或者是指数形式的函数训练神经网络初始化：随机设定各条边的W值给定一对（输入，输出），已有神经网络根据输入计算输出，将其与预计输出相比较，并根据两者之间的差值调整各条边的W值神经网络也可以自动学习，但是相比训练，收敛速度要慢很多神经网络应用当我们没办法明确给出一个算法解时当我们有充足的样本时当我们需要从数据中获得一点什么时我们可以使用神经网络神经网络应用对于那些传统计算解决不了的问题，神经网络也无法解决神经网络可以简化某些特定问题的解答，例如，从数据中提炼一个模型对于数据形成过程未知或者复杂的问题而言，神经网络能够帮助我们从一定程度上理解内在的规律神经网络与游戏判断所处的环境决定下一步的动作用于表示积累的经验神经网络与游戏神经元网络：机器学习教计算机自己玩《吃豆》：输出:上下左右、不动，输入：幽灵数量各自速度各自距离等等游戏高手充当师父曾被寄予厚望，quake2中的bot目前的问题：师父难找，游戏中的神经元网络一旦确定，往往固化在游戏中，不是无休止的学习会出现不可理喻的错误黑箱，难以改正遗传算法遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的适者生存原理基因遗传原理（基因突变和基因杂交）遗传算法一般用于在难易预测其中各个因素之间相互作用的大型系统上作非线性优化遗传算法工作原理选择初始群体观察每个个体对环境的适应能量选择重复1.杂交2.变异3.观察每个个体对环境的适应能量4.选择直到满足某些结束条件选择＋杂交＋突变＝遗传算法的力量遗传算法与游戏遗传算法：一群个体中，通过突变、交配、繁殖，再通过进化过程，最终获得更适合环境的个体。怪兽们（NPC），有不同的属性，并有繁殖功能，在和玩家的对抗过程中，能够存活并成功逃走的怪兽们，将有可能生育更机智、更难对付的下一代耗费CPU资源，宠物类型的游戏中经常采用AI引擎设计AI引擎可以帮助解决很多问题使得游戏角色之间交流更为容易提供实现AI行为的解决方法协助保留每一个错误报告技巧对于行为简单的物体，使用简单的确定性AI技术对于不是主要角色，但是需要一点智能行为的物体，可以对其设定几种模式，并加上一点随机的因素扰动即可对于比较重要的角色，可以使用有限状态机技术，加上另外一些辅助技巧对于最最重要的角色，你需要利用一切可能利用的技术状态驱动，使用条件逻辑、概率、以及经历过的状态等控制状态转移如果状态转移条件满足，物体要能够发生强制性状态转移动作什么是好的AI用户觉得游戏角色挺聪明的感觉到游戏角色的确随着经历而在成长一层层的揭开面纱，知道最后才恍然大悟CASE-人机博弈类游戏棋盘表示（BoardRepresentations）走法产生（MoveGeneration）搜索技术（SearchTechniques）估值（Evaluation）操作界面棋盘表示（BoardRepresentations）走法产生（MoveGeneration）以中国象棋中的象为例，象的走法是田字格，并且象眼要空白。一般的做法是这样：先检查该棋子周围与该棋子横纵坐标差的绝对值均为2的位置是否落在己方半边棋盘上，如某个点超出己方半边棋盘，将其去除。检查剩下的位置上是否有己方棋子，如有将其去除。检查剩下的位置方向上与该棋子横纵坐标差的绝对值均为1的象眼上是否有棋子，如有将其去除。剩下的位置即是合法走步。搜索技术（SearchTechniques）在博弈的任何一个中间阶段，站在博弈双方其中一方的立场上，可以构想一个博弈树。这个博弈树的根节点是当前时刻的棋局，它的儿子节点是假设再行棋一步以后的各种棋局，孙子节点是从儿子节点的棋局再行棋一步的各种棋局，以此类推，构造整棵博弈树，直到可以分出胜负的棋局。整棵的博弈树非常庞大，且不同的棋类有所不同。搜索技术（SearchTechniques）α-β剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：(1)对于一个节点MIN，若其倒推值β=MIN的父节点MAX的估计倒推值α，即α≥β，则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为α剪枝。(2)对于一个节点MAX，