《人工智能-4与或图搜索.ppt》由会员分享，可在线阅读，更多相关《人工智能-4与或图搜索.ppt（62页珍藏版）》请在三一办公上搜索。
1、第三章 与或图的搜索,与或图（树）表示问题,三解梵塔问题,A,B,C,1,2,3,三解梵塔问题,(1,1,1)(3,3,3),(1,1,1)(1,2,2),(1,2,2)(3,2,2),(3,2,2)(3,3,3),(1,1,1)(1,1,3),(1,1,3)(1,2,3),(1,2,3)(1,2,2),(3,2,2)(3,2,1),(3,2,1)(3,3,1),(3,3,1)(3,3,3),(1,1,1)A,B,C,3.1 与或图,初始节点,与或图,基本概念,与或图是一个超图，节点间通过连接符连接。K-连接符：,与,或,耗散值的计算,k(n,N)=Cn+k(n1,N)+k(ni,N)其中：N
2、为终节点集 Cn为连接符的耗散值,目标,目标,初始节点,解图：,能解节点,终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。,不能解节点,没有后裔的非终节点是不能解节点。若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才能解。,3.2 与或图启发式搜索算法AO*,目标,目标,初始节点,与或图的启发式搜索算法,AO*算法 105-106两个过程：图生成过程，即扩展节点计算耗散值的过程,AO
3、*算法举例,其中：h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0设：K连接符的耗散值为K,红色：4=1+1+1+1黑色：3=2+1,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色：4黑色：6,n1,5,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色：5黑色：6,2,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色：5黑色：6,2,1,3.3 博弈树(Game tree)搜索,3.3 博弈树(Game
4、tree)搜索,20世纪60年代，研制出的西洋跳棋和国际象棋的博弈程序达到了大师级的水平。1958约翰麦卡锡提出博弈树搜索算法1997年，IBM公司研制的“深蓝”国际象棋 程序，采用博弈树搜索算法，该程序战胜了国际象棋世界冠军卡斯帕罗夫。,1.概述,博弈问题特点：双人对弈，轮流走步。信息完备，双方所得到的信息是一样的。零和，即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利或无利的棋。,1.概述,博弈的特性两个棋手交替地走棋；比赛的最终结果，是赢、输和平局中的一种；可用图搜索技术进行，但效率很低；博弈的过程，是寻找置对手于必败态的过程；双方都无法干预对方的选择。,1.概述,2.Grun
5、dy博弈,下棋的双方是对立的，命名博弈的双方，一方为“正方”，这类节点称为“MAX”节点；另一方为“反方”，这类节点称为“MIN”节点。正方和反方是交替走步的，因此MAX节点和MIN节点会交替出现。,2.Grundy博弈,Grundy博弈是一个分钱币的游戏。有 一堆数目为N的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如，选手甲把N分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去，直到有一位选手无法把钱币再分成不相等的两堆时就得认输。,2.Grundy博弈,设初始状态为(7，MIN)，建立问题的状态空间图，图中所有终结点均表示该选手必输的情况，取
6、胜方的目标是设法使棋局发展为结束在对方走步时的终结点上。,（7）,（6,1）,（5,2）,（4,3）,（5,1,1）,（4,2,1）,（3,2,2）,（3,3,1）,（4,1,1,1）,（3,2,1,1）,（2,2,2,1）,（3,1,1,1,1）,（2,2,1,1,1）,（2,1,1,1,1,1）,对方-min先走,我方-max胜,A,B,C,2.Grundy博弈,有向图中有四个出度为零的结点:A,B,C结点A是MAX(我方)的搜索目标，而结点B，C则为MIN(对方)的搜索目标。,2.Grundy博弈,搜索策略要考虑的问题是：对MIN走步后的每一个MAX结点，必须证明MAX对MIN可能走的每
7、一个棋局对弈后能获胜，即MAX必须考虑应付MIN的所有招法，这是一个与的含意，因此含有MAX符号的结点可看成与结点。,2.Grundy 博弈,对MAX走步后的每一个MIN结点，只须证明MAX有一步能走赢就可以，即MAX只要考虑能走出一步棋使MIN无法招架就成，因此含有MIN符号的结点可看成或结点。,2.Grundy 博弈,对弈过程的搜索图呈现出与或图表示的形式。实现一种取胜的策略就是搜索一个解图的问题，解图就代表一种完整的博弈策略。,2.Grundy 博弈,中国象棋,一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。结论：不可能穷举。,3.极小极大搜
8、索过程,对各个局面进行评估评估的目的：对后面的状态提前进行考虑，并且以各种状态的评估值为基础作出最好的走棋选择。评估的方法：用评价函数对棋局进行评估。赢的评估值设为+，输的评估值设为-，平局的评估值设为0。评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。,3.极小极大搜索过程,MAX节点和MIN节点,命名博弈的双方，一方为“正方”，对每个状态的评估都是对应于该方的输赢的。例如，赢2个，输1个等，都是指正方的。正方每走一步，都在选择使自己赢得更多的节点，因此这类节点称为“MAX”节点；,3.极小极大搜索过程,另一方为“反方”，对每个状态的评估都是对应于对手的输赢的。例如，赢2
9、个，输一个，其实是指自己输2个，赢1个的。反方每走一步，都在选择使对手输得更多的节点，因此这类节点称为“MIN”节点。,3.极小极大搜索过程,由于正方和反方是交替走步的，因此MAX节点和MIN节点会交替出现。,3.极小极大搜索过程,正方（MAX节点）从所有子节点中，选取具有最大评估值的节点。反方（MIN节点）从其所有子节点中，选取具有最小评估值的节点。反复进行这种选取，就可以得到双方各个节点的评估值。这种确定棋步的方法，称为极小极大搜索法。,3.极小极大搜索过程,3.极小极大搜索过程,5,-3,3,3,-3,0,2,2,-3,0,-2,3,5,4,1,-3,0,6,8,9,-3,MIN,MAX
10、,0,MAX,MIN,3.极小极大搜索过程,0,1,5,-3,3,3,-3,0,2,2,-3,0,-2,3,5,4,1,-3,0,6,8,9,-3,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,MAX,MIN,MAX,MIN,3.极小极大搜索过程,在九宫格棋盘上，两位选手轮流在棋盘上摆各自的 棋子(每次一枚)，谁先取得三线的结果就取胜。设程序方MAX的棋子用()表示，MAX先走。对手MIN的棋子用(o)表示。例如：,3.极小极大搜索过程,MIN取胜,估价函数 f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成线数)(所有空格都放上MIN的棋子之后，MIN的
11、三子成线的总数)若P是MAX获胜的格局，则f(p)=+；若P是MIN获胜的格局，则f(p)-。,3.极小极大搜索过程,3.极小极大搜索过程,估计函数值 f(p)=6-4=2,估价函数 f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成线(行、列、对角)数)(所有空格都放上MIN的棋子之后，MIN的三子成线(行、列、对角)的总数),当前棋局f(p)=2,空格都放MAX的棋子,空格都放MIN的棋子,3.极小极大搜索过程,一字棋第一阶段搜索树,3.极小极大搜索过程,一字棋第二阶段搜索树,3.极小极大搜索过程,一字棋第三阶段搜索树,设有一个摆放三个子的棋盘残局，如下图所示，和在结束前有三步棋可
12、以走，而且设走第一步的是。这时存在着三个空格A，B，C，用博弈树搜索算法判断应该把棋子放到哪一格内。,棋盘残局举例,3.极小极大搜索过程,0,-1,-,0,-,1,0,-,-,0,MAX节点,MIN节点,终端节点,3.极小极大搜索过程,对于棋盘残局中的来说，最好的选择，是将放在C的位置上，这时可以导致平局局面。,3.极小极大搜索过程,-剪支法的引入 在极小极大法中，必须求出所有终端节点的评估值，当预先考虑的棋步比较多时，计算量会大大增加。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而减少需进行评估的节点范围的-剪支法。,4.-搜索过程,作为正方出现的MAX节点，假设它的MIN子节
13、点有N个，那么当它的第一个MIN子节点的评估值为时，则对于其它的子节点，如果有高过的，就取那最高的值作为该MAX节点的评估值；如果没有，则该MAX节点的评估值为。总之，该MAX节点的评估值不会低于，这个就称为该MAX节点的评估下限值。,4.-搜索过程,MAX节点的评估下限值,MIN节点的评估上限值 作为反方出现的MIN节点，假设它的MAX子节点有N个，那么当它的第一个MAX子节点的评估值为时，则对于其它子节点，如果有低于的，就取那个低于的值作为该MIN节点的评估值；如果没有，则该MIN节点的评估值取。总之，该MIN节点的评估值不会高过，这个就称为该MIN节点的评估上限值。,4.-搜索过程,剪支
14、法,MAX节点,MIN节点,=,剪支,A,B,C,D,4.-搜索过程,设MAX节点的下限为，则其所有的MIN子节点中，其评估值的上限小于等于的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了剪支。,设MIN节点的上限为，则其所有的MAX子节点中，其评估值的下限大于等于的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了剪支。,MAX节点,MIN节点,=,剪支,A,B,C,D,4.-搜索过程,剪支法,A,B,C,D,E,F,G,H,I,J,K,L,N,O,M,4.-搜索过程,MAX节点,MAX节点,MIN节点,终端节点,3,5,6,5,2,1,6,4,MAX节点,(5,),3,5,
15、6,5,2,1,6,4,(6,),(2,),(-,5),(-,2),(5,),MIN节点,终端节点,剪支,剪支,A,B,C,D,E,F,G,H,I,J,K,L,N,O,M,MAX节点,4.-搜索过程,一字棋第一阶段-剪支方法,4.-搜索过程,4.-搜索过程,极大节点的下界为。极小节点的上界为。剪支的条件：后辈节点的值祖先节点的值时，剪支后辈节点的 值祖先节点的值时，剪支简记为：极小极大，剪支极大极小，剪支,4.-搜索过程,8,6,-3,1,4,5,3,-3,5,0,3,-3,0,2,2,-3,0,-2,3,0,9,-3,0,0,-3,0,3,3,0,5,4,1,1,-3,1,6,6,1,a,b
16、,c,d,e,f,g,h,i,j,k,m,n,MAX,MIN,MAX,MIN,改进方法 使用-剪支技术，当不满足剪支条件(即)时或值比值大不了多少或极相近时，这时也可以进行剪支，以便有条件把搜索集中到会带来更大效果的其他路径上，这就是中止对效益不大的一些子树的搜索，以提高搜索效率。,4.-搜索过程,不严格限制搜索的深度。当到达深度限制时，如出现博弈格局有可能发生较大变化时，则应多搜索几层，使格局进入较稳定状态后再中止，这样可使倒推值计算的结果比较合理，避免考虑不充分产生的影响，这是等候状态平稳后中止搜索的方法。,4.-搜索过程,当算法给出所选的走步后，不要马上停止搜索，而是在原先估计可能的路径上再往前搜索几步，再次检验会不会出现意外，这是一种增添辅助搜索的方法。,4.-搜索过程,对某些博弈的开局阶段和残局阶段，往往总结了一些固定的对弈模式，因此可以利用这些知识编好走步表，以便在开局和结局时使用查表法。只是在进入中盘阶段后，再调用其他有效的搜索算法，来选择最优的走步。,4.-搜索过程,
