1、授课人：张勇授课人：张勇 AI的基本概念的基本概念 游戏中简单的游戏中简单的AI模式模式 游戏中常用的游戏中常用的AI技术技术有限状态机模糊逻辑等A*算法神经网络遗传算法 AI的基本概念的基本概念 游戏中简单的游戏中简单的AI模式模式 游戏中常用的游戏中常用的AI技术技术有限状态机模糊逻辑等A*算法神经网络遗传算法 AI的定义的定义计算机或其他机器有能力执行那些通常认为需要智慧才能做的事。创建拥有智慧的机器的过程或科学。Game AI使得游戏表现出与人的智能行为/活动相类似，或者与玩家的思维/感知相符合的特性。融合娱乐性。有限状态机有限状态机基于规则的系统，有限个状态连接成一有向图，每一条边称
2、为一个转移。专家系统专家系统知识表示专家的经验，并在此基础上作自动推理。案例式推理案例式推理将输入与数据库中已有的案例进行比较，选取最为相近的案例，其已有的解决方法即为输出。产生式系统产生式系统包含多个产生式，每一条产生式由条件和动作两部分组成，当产生式的条件满足时，系统就执行相应的动作。决策树决策树给定输入，从树的根部开始，将输入与当前结点相比较，选择当前结点的某一个子结点作为下一次比较的对象。当到达树的叶子时，则给出相应的决策。搜索方法搜索方法找到一列动作（或状态转移），使得最终的结果满足某一特定目标。多多Agent研究在多个相互竞争相互合作的智能体之间所产生的交互智能行为。人工生命人工生
3、命多agent系统一种，试图将生命系统中一些普遍规律应用到虚拟世界的人工智能体上。群组行为群组行为(Flocking)人工生命的一类，研究协同移动技术，例如人工智能体如何在大量的羊群中移动。Robotics 让机器在自然环境下交互的工作遗传算法遗传算法 直接模拟生物进化过程，通过随机选择、杂交和突变等对程序、算法或者一系列参数进行操作神经网络神经网络 模拟动物神经系统功能的机器学习方法 通过反复调节系统内部中各个神经元之间的连接参数，使得训练得到的系统在大多数情况下作出优或者近似优的反应模糊逻辑模糊逻辑 与传统二值（对-错）逻辑不同，模糊逻辑用实数表示物体隶属于某一类的可能性置信网络置信网络
4、提供建立不同现象之间内在因果关系的工具，并利用概率理论处理未知的和不完全的知识 对当前状态作出判断，并决定下一步可能的动作以及其带来的后果定性定性 定性行为或其表现是特定的，并且可预测，没有不确定性。非定性非定性 非定性行为有某种不确定性，有点不可预测。具体实例是，让NPC学习到适应玩家的作战战术。AI的基本概念的基本概念 游戏中简单的游戏中简单的AI模式模式 游戏中常用的游戏中常用的AI技术技术有限状态机模糊逻辑等A*算法神经网络遗传算法 确定性算法指预先编入代码当中的可预测的行为 从最简单的算法开始 例如，系统中有一颗小行星，以某一速度作匀速直线运动，它在任意时刻的位置由下列公式决定：某种
5、程度上，它们是智能的，但是这种智能是确定的，可预测的 当智能体找到目标后，一心一意向其移动，而不考虑任何其他的因素，例如障碍物、另外的目标等 非常机械化 在每一帧中，智能体计算其到目标的前进方向，并根据其速度，前进一段距离砖块环境 基本追逐算法基本追逐算法if(predatorX preyX)predatorX-;else if(predatorX preyY)predatorY-;else if(predatorY predatorX)preyX+;else if(preyX predatorY)preyY+;else if(preyY predatorY)prey-;改进的改进的Track
6、ing算法：算法：在每一帧中，智能体仍然首先计算其到目标的前进方向这时，智能体的速度允许发生变化，并根据更新后的速度，计算下一帧的位置速度有一个上限，超过这个上限，智能体的速度将减慢，直到重新加速为止连续环境 连续环境连续环境运动=几何变换（2D?）1987年，Craig Reynolds在SIGGRAPH论文Flocks,Herbs,and Schools:A Distributed Behavioral Model中第一次提到了群聚算法，这个算法在日后广泛地被人们使用，用来仿真整群的鸟、鱼或其他生物群。Reynolds的鸟群运动的鸟群运动三条规则三条规则是：是：（1）凝聚：每只鸟都向它邻近
7、同伴的平均位置移动。（2）对齐：每只鸟都把自己前进的方向和它邻近同伴的平均方向保持一致。（3）分隔：每只鸟在飞行时都要避免碰上身边其它同伴。就这么简单!然而简单的规则却保证了鸟群纷繁地、优雅地飞行而队形不散。为了分析我们这个群聚算法，我们需要理解一些为了分析我们这个群聚算法，我们需要理解一些基本的概念：基本的概念：（1）单位的视野，我们以r为单位的视野半径，以为视野角度，落在这个圆弧内的所有物体都是可见的。（2）避开规则（Avoidance rule），单位不会被彼此撞上。（3）凝聚规则，单位离得太远就应该靠近一点，这个规则和避开规则合在一起，从而形成了群聚。单位的视野单位的视野宽视野宽视野V
8、S窄视野窄视野 Lenard-Jones势函数势函数 代表分子间的吸引和排斥的势能，取该势函数的导数，可得代表力的函数。追逐、闪躲、避碰、群聚 追逐、追逐、闪躲闪躲 避开障碍物避开障碍物 引力强度A设置为0，只保留斥力分量。同时调整B，决定斥力强度，以及m来决定衰减。群聚群聚 通过引力分量控制。AI的基本概念的基本概念 游戏中简单的游戏中简单的AI模式模式 游戏中常用的游戏中常用的AI技术技术有限状态机模糊逻辑等A*算法神经网络遗传算法 状态（要采取的行为）状态（要采取的行为）追击随机走动巡逻吃 转移（发生转移的原因）转移（发生转移的原因）时间片结束发生某个事件完成某个行为伐木将木头运往最近的
9、仓库足够多木材放下木头:返回林场到仓库到林场 条件条件定义发生转移的先决条件 输入和事件输入和事件允许状态机对环境变化作出反应 动作动作作为状态的一部分，或者伴随转移出现 有向图有向图 每个结点表示系统状态模型，每条弧表示状每个结点表示系统状态模型，每条弧表示状态转移所伴随的动作行为态转移所伴随的动作行为 结点可以是无穷多个结点可以是无穷多个 有些结点之间可能没有弧相连接有些结点之间可能没有弧相连接 状态的设置。状态的设置。设置一个开始状态。设置一个开始状态。创建一个映射，每个输入对应一个状态间转创建一个映射，每个输入对应一个状态间转换函数。换函数。编写状态转换函数。编写状态转换函数。传统逻辑
10、把思维过程绝对化，从而达到精确、严格的目的 举例：一个被讨论的对象X，要么属于某一个集合A，要么不属于该集合，两者比居其一，而且两者仅居其一，决不模棱两可 对于命题：张三的性格稳重，如何判断这一命题的真假？对于上述的例子，模糊逻辑允许我们用一个0,1的实数表示X属于A的隶属程度。传统逻辑即隶属程度只能从0和1之间选择的情况 对于“性格稳重”这个模糊概念，能够用“一点而也不稳重”、“不太稳重”、“不好说”、“有点稳重”、“挺稳重”、“很稳重”等没有明确界限的词语形容 将重心转移至物体属于某个集合的隶属程度将重心转移至物体属于某个集合的隶属程度上上 在在AI领域的主要应用为领域的主要应用为 决策
11、行为选择 输入、输出过滤 设设A,B,C均为均为U中的模糊集中的模糊集 模糊并模糊并 若对8x2U，均有c=max(A(x),B(x)，则称C为A与B的模糊并 模糊交模糊交 若对8x2U，均有c=min(A(x),B(x)，则称C为A与B的模糊交 1 5 feet 6 feet 7 feet 1 5 feet 6 feet 7 feet 大约6英尺长的高的人归属度函数归属度函数 1 5 feet 6 feet 7 feet 1 5 feet 6 feet 7 feet 1 5 feet 6 feet 7 feet 举例：车辆驾驶举例：车辆驾驶 前提：两辆车之间不能相撞前提：两辆车之间不能相撞
12、在模糊逻辑中的实现：在模糊逻辑中的实现：用两个变量描述每一辆车用两个变量描述每一辆车 当前时刻，车与前面一辆车之间的距离当前时刻，车与前面一辆车之间的距离d 当前时刻与前一时刻距离的差当前时刻与前一时刻距离的差 d If d=0且且d=两个车位长，保持现有速度两个车位长，保持现有速度 If d0且且d0且且d两个车位长，加快速度两个车位长，加快速度 将模糊逻辑和有限状态机结合将模糊逻辑和有限状态机结合 状态之间的迁移不再是确定的 同时有多个状态FSMFSMFuSM 状态状态智能体在空间的位置其他离散空间 体素 室内位置 局部区块（tile）操作操作从一个位置移动到其他位置 必须对状态空间进行搜
13、索，才能转移至目标必须对状态空间进行搜索，才能转移至目标状态状态 完全性完全性如果目标状态存在，算法是否能够将其找到？如果目标状态存在，算法是否能够将其找到？时间复杂度时间复杂度 空间复杂度空间复杂度 能够找到最优解能够找到最优解 如何评价搜索算法如何评价搜索算法时间：多长时间能够找到解找到的解是最优、次优还是其他 盲目搜索盲目搜索没有先验知识仅仅知道目标状态是什么 经验搜索经验搜索用经验公式表示拥有的先验知识“经验”只能作相对简单、低级的决策 利用所处理问题的启发信息引导搜索，称为启发式搜索，利用所处理问题的启发信息引导搜索，称为启发式搜索，可以达到减少搜索范围，降低问题复杂度的目的。可以达
14、到减少搜索范围，降低问题复杂度的目的。启发式图搜索算法启发式图搜索算法A A基本思想：如果既考虑从起始节点到节点n的路径费用，又考虑从节点n到达目标节点的费用，即定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。其形式为：f(n)=g(n)+h(n)n为被评价的节点。用此函数来排列Open表中节点顺序的图搜索算法称为A算法。在算法A中，当h(n)h*(n)时，我们把这个算法称为A*算法，A*算法具有如下的性质：完备性：如果问题有解，则算法一定能找到解。可采纳性：如果问题有解，则算法一定能找到最佳解。即算法总能找到一条从S到目标节点的最佳路径。最优性：对两个算法A*算法
15、A1和A2，若对所有非目标节点均有 h1(n)h2(n)h*(n)则算法 A1展开的节点数目至少和A2一样多。（启发函数和A*算法的关系）下表为不同启发函数，应用下表为不同启发函数，应用A A*算法求最佳解时算法求最佳解时所扩展和生成的节点数。所扩展和生成的节点数。启发式函数的选取影响搜索效率。启发式函数的选取影响搜索效率。假设从A点移动到一墙之隔的B点，绿色的是起点A，红色是终点B，蓝色方块是中间的墙。lf(n)=g(n)+h(n)f(n)=g(n)+h(n)g(n)为从起点A沿着产生的路径，移动到网格上指定方格的移动耗费（水平或者垂直移动的耗费为10，对角线方向耗费为14）h(n)为从网格
16、上那个方格移动到终点B的预估移动耗费（曼哈顿距离）对于行为简单的物体，使用简单的确定性对于行为简单的物体，使用简单的确定性AI技术技术 对于不是主要角色，但是需要一点智能行为的物体，可以对于不是主要角色，但是需要一点智能行为的物体，可以对其设定几种模式，并加上一点随机的因素扰动即可对其设定几种模式，并加上一点随机的因素扰动即可 对于比较重要的角色，可以使用有限状态机技术，加上另对于比较重要的角色，可以使用有限状态机技术，加上另外一些辅助技巧外一些辅助技巧 对于最最重要的角色，你需要利用一切可能利用的技术对于最最重要的角色，你需要利用一切可能利用的技术 状态驱动，使用条件逻辑、概率、以及经历过的
17、状态等控制状态转移 如果状态转移条件满足，物体要能够发生强制性状态转移动作 使用更小的地图或者更少的寻路者。不要同时给多个对象寻路。路径规划的层次细节模型。预处理地图。平滑路径。不规则区域。监督学习 输入学习样本，随机给定初始值，根据目标输出，使用反向传播算法对网络的权值和偏置进行反复的调整训练，使输出的向量与期望向量尽可能地接近，当网络输出层的误差平方和小于指定的误差时训练完成。自动控制自动控制感应到前方、两侧的障碍物作为输入，输出履带的移动。威胁评估威胁评估以对方地面单位数量、空中单位数量、地面单位是否有移动机箱、空中单位是否有移动机箱等为输入，输出空中威胁、地面威胁、陆空威胁或者无威胁作为 攻击或者逃离攻击或者逃离友军个数、敌人状况等遗传算法遗传算法模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。敌人的优化组合敌人的优化组合场景的自动生成场景的自动生成游戏中防守游戏中防守/攻击位置的选择攻击位置的选择路径规划路径规划
