《游戏人工智能期末复习资料》由会员分享，可在线阅读，更多相关《游戏人工智能期末复习资料（10页珍藏版）》请在金锄头文库上搜索。
1、游戏人工智能期末复习资料第 9 章 有限状态机有限状态机（finite state machine）是一种抽象机制，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型，即处在不同的预定状态下的其中某种状态，而且有限状态机可以定义一组条件，用于状态之间的改变。如果是状态机，肯定体现了两点：首先是离散的，然后是有限的。 有限状态机是由状态（State） 、变换（Transition ）和行动（Action）组成的行为模型。有限状态机在初始状态（Start State）接收输入事件（Input Event ）后转移到下一个状态。通过条件（Guard ）判断是否符合转移条件。可以把一个有限
2、状态机看成一个特殊的有向图。常用的正则表达式就是用有限状态机实现的。State：状态存储关于过去的信息，反映从系统开始到现在时刻的输入变化。Actions & Transitions： 转换指示状态变更，并且用必须满足确使转移发生的条件来描述。动作是在给定时刻要进行的活动的描述。有多种类型的动作: 1).进入动作：在进入状态时进行 2).退出动作：在退出状态时进行 3).输入动作：依赖于当前状态和输入条件进行 4).转换动作：在进行特定转换时进行有限状态机的基本概念。Guards: 检测器出现的原因是为了检测是否满足从一个状态切换到另外一个状态的条件。Event： 对系统重要的某件事情被称为事
3、件。 事件是有生命的，它经历: 1).被产生(被接受，等待被处理，一般放入事件队列 ) 2).被分发(从事件队列取出，分发到响应的状态机处理 ) 3).死亡( 当状态机处理了该事件，它随之死亡) 从一个状态切换到另外一个状态被称为状态转换，而引起它的事件称为触发事件.(可以看到，不是所有的事件都会引起状态的转换). 提到状态转换，不能不提及检测器(Guards)，只有当检测器的值为 TRUE 时候，才能启动转换 。第 10 章 模糊逻辑。模糊逻辑的含义是让计算机以一种接近人类行为的方式解决问题。模糊逻辑的本质是一切都和程度有关。模糊逻辑避开了传统布尔逻辑的非真即假的特性，采用“程度”来衡量。模
4、糊流程步骤：模糊化、通过模糊规则产生模糊输出、反模糊化。模糊化：把明确数据（crisp data ）转化为模糊数据，即在预定的模糊集合中寻找明确数据的归属程度（degree of membership） 。归属函数：归属函数的作用是把输入的变量对应到模糊集合中某个介于 0 和 1 之间的值，求出归属程度。所需的归属度函数的形式常由精确度、考虑问题的性质、经验、是否容易实现以及其他因素决定。1.2.3.藩篱函数：藩篱函数的作用是对归属度函数返回的归属度进行修改，并其提供其他语汇素材，可以在它逻辑运算中结合使用。它可以有效地改变归属度函数的形状。常用的藩篱函数:VERY(), NOT_VERY()
5、 其中 Truth(A)指 A 在模糊集合中的归属程度。模糊规则：将输入变量模糊化后，要构建一组规则，以某种逻辑方式结合模糊数据构成前件（前提，antecedent） ，生成某些模糊结论（后件， consequent） ，即某些预定模糊集合中的归属度。模糊公理：交集（Conjunction）Truth( A or B ) = MAX(Truth(A), Truth(B)联集（Disjunction）Truth( A and B ) = MIN(Truth(A), Truth(B)补集（Negation） Truth( NOT A ) = 1 - Truth(A)以上定义可以根据具体应用的情况更
6、改。例如将 AND 定义为两个归属度的积等。反模糊化：反模糊化将模糊结论转化为精确数值输出。常用的方法：寻找输出模糊集合所占面积的几何中心，并以该中心的水平坐标值作为精确输出值，即输出所有归属程度的加权平均值。实现的手段：用数值积分算出曲线围成的面积，或想象成多边形，然后用几何方法找出中心单值输出归属度函数(singleton output membership function),即用事先已经反模糊化好的输出函数，计算所有输出值聚合起来的结果。假设 是某输出集合为真的程度，而 x 为与此输出集合相关的精确单值，则最后聚合而反模糊化的输出结果是：第 11 章 规则式 AI把一组产生式放在一起,
7、 让它们互相配合, 协同作用, 一个产生式生成的结论可以供另一个产生式作为前提使用, 以这种方式求得问题的解决, 这就叫规则（产生式）系统(Production System) 。产生式系统也可以算作是一种 演绎系统。规则系统最简单的形式由一连串的 if-then 规则组成，用来做推论或行动决策。实际上有限状态机和模糊状态机都是一种规则系统。规则系统有两个主要部分：工作记忆（working memory）和规则记忆（rule memory）工作记忆存储已知的事实，以及由规则所做的断言；规则记忆（简称规则）则含有 if-then形式的规则，能够以储存在工作记忆里的事实运行。当规则被触发（启动，f
8、ire） ，则这些规则就能触发某些行动，或引起状态改变。这些规则也能修改工作记忆的内容，即新增“断言” （assertion）的信息。人工智能产生式系统组成:一个综合数据库(Globle Database)(数据基)一组产生式规则(Set of Rules)(规则库)一个控制系统(规则解释器)。 1、 正向产生式系统(Forward Production System)和正向推理正向产生式系统是从初始状态出发, 朝着目标状态方向来使用规则, 即正推的方式工作的, 我们称这些规则为 F 规则。2、逆向产生式系统(Backward Production System)和逆向推理逆向产生式系统是选取
9、目标状态描述作为初始综合数据库, 逆向进行求解, 即系统从目标状态出发, 朝着初始状态方向来使用规则, 产生子目标状态, 反向朝着初始状态求解, 即递推的方式工作的, 我们称这些规则为 B 规则。演绎法：三个步骤1.把规则和储存在工作记忆里的事实配对，做法是检查每条规则的 if 部分，是否和工作记忆里的某组事实和断言吻合。2.冲突解决（conflict resolution） ，检查所有吻合的规则，按照某种方式找出想要启动的规则。First Best All Random3.当某种规则被选取后，启动该规则，即执行其 then 部分。上述三个步骤执行后，该过程会一直重复，直到没有规则可以启动为止
10、。归纳法：与演绎法刚好相反。不是把规则的 if 部分来和工作记忆配对，而是把 then 部分配对。即有某种结果或目标，然后试着找出某条规则应该启动，才能达到该结果或目标。正向推理方法也称为“数据驱动方法” 、 “自底向上”或“正向键” 。数据驱动方法的优点是简单明了且能求出所有的解。反向推理方法也称为“目标驱动方法” 、 “自顶向下”或“反向链” 。第 12 章 概率概论标准概率标准概率指的是事件和可能性发生的概率或可能的结果。给定一个事件 E，在总数为N 的可能结果中，会发生 n 种结果，则此事件发生的概率 p 为：p=P(E)=n/N客观概率P(E)=n/N 其中 N 主观概率：根据主观判
11、断得到的概率，很难量化。赔率期望值概率规则：规则 1：0=P(A)=1规则 2：如果 S 代表整个样本空间。则 S 的概率为 1规则 3：如果事件 A 发生的概率是 P(A),而 A 不会发生的事件记为 A，则 P(A)=1- P(A)规则 4: 如果事件 A、B 互斥，则P(A U B)= P(A)+ P(B)规则 5:如果事件 A、B 不互斥，则P(A U B)= P(A)+ P(B)- P(A B)规则 6：如果事件 A 和 B 是独立的，则事件 A 和 B 都发生的概率是： P(A B)= P(A)P(B) 条件概率：当事件不独立时，如果事件 A 依赖于事件 B 发生，我们把 B 发生
12、后，A 发生的概率写为P(A|B);反之写为 P(B|A)。A 和 B 同时发生的概率为 P(A B)= P(A)P(B|A) 故 P(B|A)= P(A B )/P(A) 贝叶斯规则：P(B|A)= P(B ) P(A|B)/P(A) 第 13 章 贝叶斯技术贝叶斯网络（ Bayesian network，置信网络，信度网络）是一种概率网络，它是基于概率推理的图形化网络，而贝叶斯公式则是这个概率网络的基础。所谓概率推理就是通过一些变量的信息来获取其他的概率信息的过程。适用于表达和分析不确定性和概率性的事件，应用于有条件地依赖多种控制因素的决策，可以从不完全、不精确或不确定的知识或信息中做出推
13、理。贝叶斯网络的优越性对已有的信息要求低，可以进行信息不完全、不确定情况下的推理具有良好的可理解性和逻辑性专家知识和试验数据的有效结合相辅相成，忽略次要联系而突出主要矛盾，可以有效避免过学习推理结果说服力强，贝叶斯网络对先验概率的要求大大降低贝叶斯决策理论方法是统计模型决策中的一个基本方法，其基本思想是： 1、已知条件概率密度参数表达式和先验概率。 2、利用贝叶斯公式转换成后验概率。 3、根据后验概率大小进行决策分类。 先验概率、后验概率和条件概率先验概率：根据历史的资料或主观判断所确定的各种时间发生的概率后验概率：通过贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率修正后得到的更符合
14、实际的概率条件概率：某事件发生后该事件的发生概率条件概率公式：P(B|A)= P(B)P(A|B)/P(A)其中， P(A|B)表示 “在发生事件 B 的前提下，A 事件发生的概率” 。贝叶斯网络的组成和结构贝叶斯网络是描述随机变量（事件）之间依赖关系的一种图形模式，是一种用来进行推理的模型贝叶斯网络由网络结构和条件概率表两部分组成。网络结构是一个有向无环图 (Directed Acyclic Graph,DAG),由代表变量节点及连接这些节点有向边构成。节点代表随机变量，节点间的有向边代表了节点间的互相关系(由父节点指向其子节点) ，用条件概率表达关系强度，没有父节点的用先验概率进行信息表达
15、。节点变量可以是任何问题的抽象，如：测试值，观测现象，意见征询等。贝叶斯网络的推论：1).因果链(causal chain)2)共通成因网络(common cause network, 简式贝叶斯网络，naive Bayesian network, 贝叶斯分类器， Bayesian classifier)3)诊断推理(diagnostic reasoning,归纳)：已知 A 引起 B，如果知道 B 的值，则可以计算得到 A 的概率。4)共通结果网络(common effect network)5)解释消除(explaining away,解释过去,交互因果推理)：已知 A 和 B 引起 C，
16、如果知道C 的值，则可以计算 A 的改变对 B 概率的影响。d-分割:定理（整体马尔科夫性）设 X 和 Y 为贝叶斯网 N 中的两个变量，Z 为 N 中一个不包含 X 和 Y 的节点集合。如果 Z d-分割 X 和 Y，那么 X 和 Y 在给定 Z 时条件独立，即 d-分割是图论的概念，而条件独立是概率论的概念，所以定理揭示了贝叶斯网络图论侧面和概率论侧面之间的关系。第 14 章 神经网络神经网络结构在结构上，可以把一个神经网络划分为输入层(input)、输出层(output)和隐含层(hidden)。输入层的每个节点对应一个个的预测变量。输出层的节点对应目标变量，可有多个。在输入层和输出层之间是隐含层（对神经网络使用者来说不可见） ，隐含层的层数和每层节点的个数决定了神经网络的复杂度。 前馈神经网络前向传播：数据从输入到输出的过程是一个从前向后的传播过程，后一节点的值通过它前面相连的节点传过来，然后把值按照各个连接权重的大小加权输入活化
