游戏人工智能期末复习资料.doc

游戏人工智能期末复习资料第9章 有限状态机有限状态机（finite state machine）是一种抽象机制，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型，即处在不同的预定状态下的其中某种状态，而且有限状态机可以定义一组条件，用于状态之间的改变。如果是状态机，肯定体现了两点：首先是离散的，然后是有限的。 有限状态机是由状态（State）、变换（Transition）和行动（Action）组成的行为模型。有限状态机在初始状态（Start State）接收输入事件（Input Event）后转移到下一个状态。通过条件（Guard）判断是否符合转移条件。可以把一个有限状态机看成一个特殊的有向图。常用的正则表达式就是用有限状态机实现的。State：状态存储关于过去的信息，反映从系统开始到现在时刻的输入变化。Actions & Transitions： 转换指示状态变更，并且用必须满足确使转移发生的条件来描述。动作是在给定时刻要进行的活动的描述。有多种类型的动作: 1).进入动作：在进入状态时进行 2).退出动作：在退出状态时进行 3).输入动作：依赖于当前状态和输入条件进行 4).转换动作：在进行特定转换时进行有限状态机的基本概念。 Guards: 检测器出现的原因是为了检测是否满足从一个状态切换到另外一个状态的条件。Event： 对系统重要的某件事情被称为事件。 事件是有生命的，它经历: 1).被产生(被接受，等待被处理，一般放入事件队列) 2).被分发(从事件队列取出，分发到响应的状态机处理) 3).死亡(当状态机处理了该事件，它随之死亡) 从一个状态切换到另外一个状态被称为状态转换，而引起它的事件称为触发事件.(可以看到，不是所有的事件都会引起状态的转换). 提到状态转换，不能不提及检测器(Guards)，只有当检测器的值为TRUE时候，才能启动转换 。第10章 模糊逻辑。模糊逻辑的含义是让计算机以一种接近人类行为的方式解决问题。模糊逻辑的本质是一切都和程度有关。模糊逻辑避开了传统布尔逻辑的非真即假的特性，采用“程度”来衡量。模糊流程步骤：模糊化、通过模糊规则产生模糊输出、反模糊化。模糊化：把明确数据（crisp data）转化为模糊数据，即在预定的模糊集合中寻找明确数据的归属程度（degree of membership）。归属函数：归属函数的作用是把输入的变量对应到模糊集合中某个介于0和1之间的值，求出归属程度。所需的归属度函数的形式常由精确度、考虑问题的性质、经验、是否容易实现以及其他因素决定。1.2.3.藩篱函数：藩篱函数的作用是对归属度函数返回的归属度进行修改，并其提供其他语汇素材，可以在它逻辑运算中结合使用。它可以有效地改变归属度函数的形状。常用的藩篱函数:VERY(), NOT_VERY() 其中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)以上定义可以根据具体应用的情况更改。例如将AND定义为两个归属度的积等。反模糊化：反模糊化将模糊结论转化为精确数值输出。常用的方法：寻找输出模糊集合所占面积的几何中心，并以该中心的水平坐标值作为精确输出值，即输出所有归属程度的加权平均值。实现的手段：用数值积分算出曲线围成的面积，或想象成多边形，然后用几何方法找出中心单值输出归属度函数(singleton output membership function),即用事先已经反模糊化好的输出函数，计算所有输出值聚合起来的结果。假设是某输出集合为真的程度，而x为与此输出集合相关的精确单值，则最后聚合而反模糊化的输出结果是：第11章 规则式AI把一组产生式放在一起, 让它们互相配合, 协同作用, 一个产生式生成的结论可以供另一个产生式作为前提使用, 以这种方式求得问题的解决, 这就叫规则（产生式）系统(Production System) 。产生式系统也可以算作是一种演绎系统。规则系统最简单的形式由一连串的if-then规则组成，用来做推论或行动决策。实际上有限状态机和模糊状态机都是一种规则系统。规则系统有两个主要部分：工作记忆（working memory）和规则记忆（rule memory）工作记忆存储已知的事实，以及由规则所做的断言；规则记忆（简称规则）则含有if-then形式的规则，能够以储存在工作记忆里的事实运行。当规则被触发（启动，fire），则这些规则就能触发某些行动，或引起状态改变。这些规则也能修改工作记忆的内容，即新增“断言”（assertion）的信息。人工智能产生式系统组成:一个综合数据库(Globle Database)(数据基) 一组产生式规则(Set of Rules)(规则库) 一个控制系统(规则解释器)。 1、 正向产生式系统(Forward Production System)和正向推理正向产生式系统是从初始状态出发, 朝着目标状态方向来使用规则, 即正推的方式工作的, 我们称这些规则为F规则。2、逆向产生式系统(Backward Production System)和逆向推理逆向产生式系统是选取目标状态描述作为初始综合数据库, 逆向进行求解, 即系统从目标状态出发, 朝着初始状态方向来使用规则, 产生子目标状态, 反向朝着初始状态求解, 即递推的方式工作的, 我们称这些规则为B规则。演绎法：三个步骤1.把规则和储存在工作记忆里的事实配对，做法是检查每条规则的if部分，是否和工作记忆里的某组事实和断言吻合。2.冲突解决（conflict resolution），检查所有吻合的规则，按照某种方式找出想要启动的规则。First Best All Random3.当某种规则被选取后，启动该规则，即执行其then部分。上述三个步骤执行后，该过程会一直重复，直到没有规则可以启动为止。归纳法：与演绎法刚好相反。不是把规则的if部分来和工作记忆配对，而是把then部分配对。即有某种结果或目标，然后试着找出某条规则应该启动，才能达到该结果或目标。正向推理方法也称为“数据驱动方法”、“自底向上”或“正向键”。数据驱动方法的优点是简单明了且能求出所有的解。反向推理方法也称为“目标驱动方法”、“自顶向下”或“反向链”。第12章 概率概论标准概率标准概率指的是事件和可能性发生的概率或可能的结果。给定一个事件E，在总数为N的可能结果中，会发生n种结果，则此事件发生的概率p为：p=P(E)=n/N客观概率 P(E)=n/N 其中N 主观概率：根据主观判断得到的概率，很难量化。赔率期望值概率规则：规则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发生后，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，置信网络，信度网络）是一种概率网络，它是基于概率推理的图形化网络，而贝叶斯公式则是这个概率网络的基础。所谓概率推理就是通过一些变量的信息来获取其他的概率信息的过程。适用于表达和分析不确定性和概率性的事件，应用于有条件地依赖多种控制因素的决策，可以从不完全、不精确或不确定的知识或信息中做出推理。贝叶斯网络的优越性对已有的信息要求低，可以进行信息不完全、不确定情况下的推理具有良好的可理解性和逻辑性专家知识和试验数据的有效结合相辅相成，忽略次要联系而突出主要矛盾，可以有效避免过学习推理结果说服力强，贝叶斯网络对先验概率的要求大大降低贝叶斯决策理论方法是统计模型决策中的一个基本方法，其基本思想是： 1、已知条件概率密度参数表达式和先验概率。 2、利用贝叶斯公式转换成后验概率。 3、根据后验概率大小进行决策分类。 先验概率、后验概率和条件概率先验概率：根据历史的资料或主观判断所确定的各种时间发生的概率后验概率：通过贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率修正后得到的更符合实际的概率条件概率：某事件发生后该事件的发生概率条件概率公式：P(B|A)= P(B)P(A|B)/P(A)其中， P(A|B)表示 “在发生事件B的前提下，A事件发生的概率”。贝叶斯网络的组成和结构贝叶斯网络是描述随机变量（事件）之间依赖关系的一种图形模式，是一种用来进行推理的模型贝叶斯网络由网络结构和条件概率表两部分组成。网络结构是一个有向无环图 (Directed Acyclic Graph,DAG),由代表变量节点及连接这些节点有向边构成。节点代表随机变量，节点间的有向边代表了节点间的互相关系(由父节点指向其子节点)，用条件概率表达关系强度，没有父节点的用先验概率进行信息表达。节点变量可以是任何问题的抽象，如：测试值，观测现象，意见征询等。贝叶斯网络的推论： 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，如果知道C的值，则可以计算A的改变对B概率的影响。d-分割:定理（整体马尔科夫性）设X和Y为贝叶斯网N中的两个变量，Z为N中一个不包含X和Y的节点集合。如果Z d-分割X和Y，那么X和Y在给定Z时条件独立，即 d-分割是图论的概念，而条件独立是概率论的概念，所以定理揭示了贝叶斯网络图论侧面和概率论侧面之间的关系。第14章 神经网络神经网络结构在结构上，可以把一个神经网络划分为输入层(input)、输出层(output)和隐含层(hidden)。输入层的每个节点对应一个个的预测变量。输出层的节点对应目标变量，可有多个。在输入层和输出层之间是隐含层（对神经网络使用者来说不可见），隐含层的层数和每层节点的个数决定了神经网络的复杂度。 前馈神经网络前向传播：数据从输入到输出的过程是一个从前向后的传播过程，后一节点的值通过它前面相连的节点传过来，然后把值按照各个连接权重的大小加权输入活化函数再得到新的值，进一步传播到下一个节点。 回馈：当节点的输出值与预期的值不同，也就是发生错误时，神经网络就要 “学习”（从错误中学习）。可以把节点间连接的权重看成后一节点对前一节点的“信任” 程度（向下一节点的输出更容易受前面那个节点输入的影响）。学习的方法是采用惩罚的方法权重权重会影响特定输入数据的强度。它决定神经网络的行为。训练神经网络的目的就是求出每个神经元与另一个神经元相连时匹配的权重。神经元的输入值就是每个输入值与该神经元相连的权重乘以自身的输入值的总和再加上偏差值。活化函数活化函数接收神经元的总输入值，进行处理，产生神经元的输出值。基本上活化函数是非线性的。logistic函数(S型函数(sigmoid function)阶跃函数(step function)双曲正切函数(hyperbolic tangent function)线性活化函数(linear activation function)偏差项偏差项是把总输入值沿活化函数的水平轴移动，有效改变神经元活化的阈值。偏差值总是设为1或-1，其权重经由训练调整。隐匿层决定神经网络拓扑结构（或体系结构）的是隐含层及其所含节点的个数，以及节点之间的连接方式。要从头开始设计一个神经网络，必须要决定隐含层和节点的数目，活化函数的形式，以及对权重做哪些限制等。 每个输出神经元都和某个隐匿神经元连接在一起，每个隐匿神经元都会把输出传到某个输出层的神经元。隐匿层神经元越多，神经网络能处理的特征就越多。一般来说，隐匿神经元的数量要用试误法确定。如果三层神经网络不是用于自动联想，隐匿层神经元的数量大约等于输入和输出神经元数量乘积的平方根，是比较适当的。训练训练的目标是找出连接所有神经元之值的权重，让输入层可以产生所需的输出值。指导训练(supervised training)和无指导训练(unsupervised training)倒传递法、计算误差、调整权重、动量监督式学习网络(Supervised Learning Network)，在学习训练中需要给网络成对的提供一个输入模式，和一个期望网络正确输出的模式，成为“教师信号”。将神经网络的实际输出，同期望输出进行比较，当网络的输出与期望的教师信号不符时，根据差错的方向和大小，按一定的规则调整权值，以示下一步网络的输出更接近期望结果无监督式学习网络(Unsupervised Learning Network) 是网络能根据特有的动态信息和规则，在输入信息流中发现任何可能存在的模式喝个例，同时根据网络的功能和输入信息调整权值，这过程称为网络的自组织，其结果使网络能对是同一类的模式自动分类。灌输式学习网络 灌输式是使将网络设计成能记忆特殊例子以后当给定该例子的特定的信息，例子就能被回忆起来。权重每个权重校正值公式：第15章 遗传算法遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。基本概念交叉概率(pc, probability of performing crossover)：控制着交叉算子的使用频率。交叉操作可以加快收敛，使解达到最有希望的最优解区域，因此一般取较大的交叉概率，但交叉概率太高也可能导致过早收敛。 变异概率(pm, probability of mutation)：控制着变异算子的使用频率。 中止条件(termination criteria) 简单说来就是：繁殖过程，会发生基因交叉( Crossover ) ，基因突变 ( Mutation ) ，适应度( Fitness )低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的，其中很可能包含史上产生的适应度最高的那个个体。遗传算法机理选择一些染色体来产生下一代。一种常用的选择策略是 “比例选择”，也就是个体被选中的概率与其适应度函数值成正比。假设群体的个体总数是M，那么那么一个个体Xi被选中的概率为f(Xi)/( f(X1) + f(X2) + . + f(Xn) ) 。比例选择实现算法就是所谓的“轮盘赌算法”( Roulette Wheel Selection ) ，轮盘赌算法的一个简单的实现如下： /* 按设定的概率，随机选中一个个体， Pi表示第i个个体被选中的概率*/int RWS() m = 0; r =Random(0,1); /r为0至1的随机数 for(i=1;i=N; i+) /* 产生的随机数在mm+Pi间则认为选中了i，因此i被选中的概率是Pi*/ m = m + Pi; if(r=m) return i;一般终止条件有以下几种：进化次数限制； 计算耗费的资源限制（例如计算时间、计算占用的内存等）； 一个个体已经满