人工智能-4与或图搜索.ppt

《人工智能-4与或图搜索.ppt》由会员分享，可在线阅读，更多相关《人工智能-4与或图搜索.ppt（62页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第三章 与或图的搜索目标目标初始节点与或图（树）表示问题三解梵塔问题ABC123三解梵塔问题(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,C3.1 与或图初始节点与或图目标目标初始节点基本概念与或图是一个超图，节点间通过连接符连接。K-连接符：.K个与或耗散值的计算k(n,N)=Cn+k(n1,N)+k(ni,N)其中：N为终节点集 Cn为连

2、接符的耗散值.i个nn1n2ni目标目标初始节点 解图：能解节点终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。不能解节点没有后裔的非终节点是不能解节点。若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才能解。3.2 与或图启发式搜索算法AO*目标目标初始节点与或图的启发式搜索算法AO*算法 105-106两个过程：图生成过程，即扩展节点计算耗散值的过程AO*算法举例其中：h(n0)=

3、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目标目标初始节点n0n1n2n3n4n5n6n7n8目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4=1+1+1+1黑色：3=2+1目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1)n5(1)红色：4黑色：6n1n2(4)n3(4)5目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黑色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2

4、)n7(0)n8(0)2目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黑色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)213.3 博弈树(Game tree)搜索3.3 博弈树(Game tree)搜索20世纪60年代，研制出的西洋跳棋和国际象棋的博弈程序达到了大师级的水平。1958约翰麦卡锡提出博弈树搜索算法1997年，IBM公司研制的“深蓝”国际象棋 程序，采用博弈树搜索算法，该程序战胜了国际象棋世界冠军卡斯帕罗夫。1.1.概述概述博弈问题特点：博弈问题特点：双人对弈，轮流走步。双人对弈，轮流走步。信息完备，双方所得到的信息是一

5、样的。信息完备，双方所得到的信息是一样的。零和，即对一方有利的棋，对另一方肯定零和，即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利或无利的是不利的，不存在对双方均有利或无利的棋。棋。1.1.概述概述博弈的特性博弈的特性两个棋手交替地走棋两个棋手交替地走棋 ；比赛的最终结果，是赢、输和平局中的比赛的最终结果，是赢、输和平局中的一种；一种；可用图搜索技术进行，但效率很低；可用图搜索技术进行，但效率很低；博弈的过程，是寻找置对手于必败态的博弈的过程，是寻找置对手于必败态的过程；过程；双方都无法干预对方的选择。双方都无法干预对方的选择。1.1.概述概述2.Grundy2.Grundy博弈博

6、弈下棋的双方是对立的，命名博弈的双方，下棋的双方是对立的，命名博弈的双方，一方为一方为“正方正方”，这类节点称为，这类节点称为“MAX”节节点；另一方为点；另一方为“反方反方”，这类节点称为，这类节点称为“MIN”节点。正方和反方是交替走步的，节点。正方和反方是交替走步的，因此因此MAX节点和节点和MIN节点会交替出现。节点会交替出现。2.Grundy2.Grundy博弈博弈Grundy博弈是一个分钱币的游戏。有博弈是一个分钱币的游戏。有 一堆数目为一堆数目为N的钱币，由两位选手轮流进的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某行分堆，要求每个选手每次只把其中某一堆分成数目不等的

7、两小堆。例如，选一堆分成数目不等的两小堆。例如，选手甲把手甲把N分成两堆后，轮到选手乙就可以分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去，直到挑其中一堆来分，如此进行下去，直到有一位选手无法把钱币再分成不相等的有一位选手无法把钱币再分成不相等的两堆时就得认输。两堆时就得认输。2.Grundy2.Grundy博弈博弈设初始状态为设初始状态为(7，MIN)，建立问题的状，建立问题的状态空间图，图中所有终结点均表示该选态空间图，图中所有终结点均表示该选手必输的情况，取胜方的目标是设法使手必输的情况，取胜方的目标是设法使棋局发展为结束在对方走步时的终结点棋局发展为结束在对方走步时的终结点上

8、。上。（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胜ABC2.Grundy2.Grundy博弈博弈有向图中有四个出度为零的结点有向图中有四个出度为零的结点:A,B,C结点结点A是是MAX(我方我方)的搜索目标，而结的搜索目标，而结点点B，C则为则为MIN(对方对方)的搜索目标。的搜索目标。2.Grundy2.Grundy博弈博弈搜索策略要考虑的问题是：搜索策略要考虑的问题是：对对MIN走步后的每一

9、个走步后的每一个MAX结点，必须证结点，必须证明明MAX对对MIN可能走的每一个棋局对弈后可能走的每一个棋局对弈后能获胜，即能获胜，即MAX必须考虑应付必须考虑应付MIN的所有的所有招法，这是一个与的含意，因此含有招法，这是一个与的含意，因此含有MAX符符号的结点可看成与结点。号的结点可看成与结点。2.Grundy 2.Grundy 博弈博弈对对MAX走步后的每一个走步后的每一个MIN结点，只须证结点，只须证明明MAX有一步能走赢就可以，即有一步能走赢就可以，即MAX只要只要考虑能走出一步棋使考虑能走出一步棋使MIN无法招架就成，无法招架就成，因此含有因此含有MIN符号的结点可看成或结点。符号

10、的结点可看成或结点。2.Grundy 2.Grundy 博弈博弈对弈过程的搜索图呈现出与或图表示的形式。对弈过程的搜索图呈现出与或图表示的形式。实现一种取胜的策略就是搜索一个解图的问实现一种取胜的策略就是搜索一个解图的问题，解图就代表一种完整的博弈策略。题，解图就代表一种完整的博弈策略。2.Grundy 2.Grundy 博弈博弈中国象棋中国象棋一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。结论：不可能穷举。3.3.极小极大搜索过程极小极大搜索过程对各个局面进行评估对各个局面进行评估评估的目的：对后面的状态提前进行考虑，评估的目的：对后面的状态提

11、前进行考虑，并且以各种状态的评估值为基础作出最好的并且以各种状态的评估值为基础作出最好的走棋选择。走棋选择。评估的方法：用评价函数对棋局进行评估。评估的方法：用评价函数对棋局进行评估。赢的评估值设为赢的评估值设为+，输的评估值设为，输的评估值设为-，平局的评估值设为平局的评估值设为0。评估的标准：由于下棋的双方是对立的，只评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。能选择其中一方为评估的标准方。3.3.极小极大搜索过程极小极大搜索过程MAX节点和节点和MIN节点节点命名博弈的双方，一方为命名博弈的双方，一方为“正方正方”，对每，对每个状态的评估都是对应于该方的输赢的。个

12、状态的评估都是对应于该方的输赢的。例如，赢例如，赢2个，输个，输1个等，都是指正方的。个等，都是指正方的。正方每走一步，都在选择使自己赢得更多正方每走一步，都在选择使自己赢得更多的节点，因此这类节点称为的节点，因此这类节点称为“MAX”节点；节点；3.3.极小极大搜索过程极小极大搜索过程另一方为另一方为“反方反方”，对每个状态的评估，对每个状态的评估都是对应于对手的输赢的。例如，赢都是对应于对手的输赢的。例如，赢2个，个，输一个，其实是指自己输输一个，其实是指自己输2个，赢个，赢1个的。个的。反方每走一步，都在选择使对手输得更反方每走一步，都在选择使对手输得更多的节点，因此这类节点称为多的节点

13、，因此这类节点称为“MIN”节节点。点。3.3.极小极大搜索过程极小极大搜索过程由于正方和反方是交替走步的，因此由于正方和反方是交替走步的，因此MAX节点和节点和MIN节点会交替出现。节点会交替出现。3.3.极小极大搜索过程极小极大搜索过程正方（正方（MAX节点）从所有子节点中，选节点）从所有子节点中，选取具有最大评估值的节点。取具有最大评估值的节点。反方（反方（MIN节点）从其所有子节点中，节点）从其所有子节点中，选取具有最小评估值的节点。选取具有最小评估值的节点。反复进行这种选取，就可以得到双方各反复进行这种选取，就可以得到双方各个节点的评估值。这种确定棋步的方法，个节点的评估值。这种确定

14、棋步的方法，称为称为极小极大搜索法极小极大搜索法。3.3.极小极大搜索过程极小极大搜索过程3.3.极小极大搜索过程极小极大搜索过程5-333-3022-30-235 41-30 68 9-3MINMAX0MAXMIN3.3.极小极大搜索过程极小极大搜索过程015-333-3022-30-235 41-30 68 9-30-33-3-3-21-36-3031601MAXMINMAXMIN3.3.极小极大搜索过程极小极大搜索过程 在九宫格棋盘上，两位选手轮流在棋盘上摆各自的在九宫格棋盘上，两位选手轮流在棋盘上摆各自的 棋子棋子(每次一枚每次一枚)，谁先取得三线的结果就取胜。，谁先取得三线的结果就取

15、胜。设程序方设程序方MAXMAX的棋子用的棋子用()()表示，表示，MAXMAX先走。先走。对手对手MINMIN的棋子用的棋子用(o o)表示。表示。例如：例如：3.3.极小极大搜索过程极小极大搜索过程MIN取胜取胜 估价函数估价函数 f(p)=(f(p)=(所有空格都放上所有空格都放上MAXMAX的的棋子之后，棋子之后，MAXMAX的三子成线数的三子成线数)(所有空所有空格都放上格都放上MINMIN的棋子之后，的棋子之后，MINMIN的三子成的三子成线的总数线的总数)若若P P是是MAXMAX获胜的格局，则获胜的格局，则f(p)=+f(p)=+；若若P P是是MINMIN获胜的格局，则获胜的

16、格局，则f(p)f(p)-。3.3.极小极大搜索过程极小极大搜索过程3.3.极小极大搜索过程极小极大搜索过程估计函数值估计函数值 f(p)=6-4=2估价函数估价函数 f(p)=(f(p)=(所有空格都放上所有空格都放上MAXMAX的棋子之后，的棋子之后，MAXMAX的三子的三子成线成线(行、列、对角行、列、对角)数数)(所有空格都放上所有空格都放上MINMIN的棋子之后，的棋子之后，MINMIN的三子成线的三子成线(行、列、对角行、列、对角)的总数的总数)当前棋局当前棋局f(p)=2空格都放空格都放MAXMAX的棋子的棋子空格都放空格都放MINMIN的棋子的棋子3.3.极小极大搜索过程极小极

17、大搜索过程一字棋第一阶段搜索树一字棋第一阶段搜索树3.3.极小极大搜索过程极小极大搜索过程一字棋第二阶段搜索树一字棋第二阶段搜索树3.3.极小极大搜索过程极小极大搜索过程一字棋第三阶段搜索树一字棋第三阶段搜索树 设设有有一一个个摆摆放放三三个个子子的的棋棋盘盘残残局局，如如下下图图所所示示，和和 在在结结束束前前有有三三步步棋棋可可以以走走，而而且且设设走走第第一一步步的的是是 。这这时时存存在在着着三三个个空空格格A，B，C，用用博博弈弈树树搜搜索算法判断应该把棋子放到哪一格内。索算法判断应该把棋子放到哪一格内。A AB BC C棋盘残局举例棋盘残局举例3.3.极小极大搜索过程极小极大搜索过

18、程A AB BC CB BC CC CB B0A AC CC CA AA A B BB BA A-1-0-10-0MAX节点节点MIN节点节点终端节点终端节点3.3.极小极大搜索过程极小极大搜索过程 对对于于棋棋盘盘残残局局中中的的来来说说，最最好好的的选选择择，是是将将放放在在C C的位置上，这时可以导致平局局面。的位置上，这时可以导致平局局面。3.3.极小极大搜索过程极小极大搜索过程-剪支法的剪支法的引入引入 在在极极小小极极大大法法中中，必必须须求求出出所所有有终终端端节节点点的的评评估估值值，当当预预先先考考虑虑的的棋棋步步比比较较多多时时，计计算算量量会会大大大大增增加加。为为了了提

19、提高高搜搜索索的的效效率率，引引入入了了通通过过对对评评估估值值的的上上下下限限进进行行估估计计，从从而而减减少少需需进进行行评评估估的的节节点范围的点范围的-剪支法。剪支法。4.4.-搜索过程搜索过程 作作为为正正方方出出现现的的MAX节节点点，假假设设它它的的MIN子子节节点点有有N个个，那那么么当当它它的的第第一一个个MIN子子节节点点的的评评估估值值为为 时时，则则对对于于其其它它的的子子节节点点，如如果果有有高高过过 的的，就就取取那那最最高高的的值值作作为为该该MAX节节点点的的评评估估值值；如如果果没没有有，则则该该MAX节节点点的的评评估估值值为为。总总之之，该该MAX节节点点

20、的的评评估估值值不不会会低低于于，这个这个 就称为该就称为该MAX节点的评估下限值。节点的评估下限值。4.4.-搜索过程搜索过程n MAX节点的评估下限值节点的评估下限值 MIN节点的评估上限值节点的评估上限值 作作为为反反方方出出现现的的MIN节节点点，假假设设它它的的MAX子子节节点点有有N个个，那那么么当当它它的的第第一一个个MAX子子节节点点的的评评估估值值为为 时时，则则对对于于其其它它子子节节点点，如如果果有有低低于于 的的，就就取取那那个个低低于于 的的值值作作为为该该MIN节节点点的的评估值；如果没有，则该评估值；如果没有，则该MIN节点的评估值取节点的评估值取。总总之之，该该

21、MIN节节点点的的评评估估值值不不会会高高过过，这这个个 就称为该就称为该MIN节点的评估上限值。节点的评估上限值。4.4.-搜索过程搜索过程 剪支法剪支法 MAX节点节点MIN节点节点=剪支剪支ABCD4.4.-搜索过程搜索过程 设设MAX节点的下限为节点的下限为，则其，则其所有的所有的MIN子节点子节点中，其评估值的中，其评估值的 上限小于等于上限小于等于 的节点，其以下部分的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了的搜索都可以停止了，即对这部分节点进行了 剪支。剪支。设设MIN节点的上限为节点的上限为，则其，则其所有的所有的MAX子节子节点中，其评估值的点中，其评估值的

22、下限大于等于下限大于等于 的节点，其以下的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了部分的搜索都可以停止了，即对这部分节点进行了 剪支。剪支。MAX节点节点MIN节点节点=剪支剪支ABCD4.4.-搜索过程搜索过程n 剪支法剪支法 A B CDEFG H I J K L N O M4.4.-搜索过程搜索过程MAX节点节点MAX节点节点MIN节点节点终端节点终端节点35652164MAX节点节点(5,)35652164(6,)(2,)(-,5,5)(-,2,2)(5,)MIN节点节点终端节点终端节点 剪支剪支 剪支剪支A B CDEFG H I J K L N O MMAX节点节点

23、4.4.-搜索过程搜索过程一字棋第一阶段一字棋第一阶段-剪支方法剪支方法4.4.-搜索过程搜索过程4.4.-搜索过程搜索过程极大节点的下界为极大节点的下界为。极小节点的上界为极小节点的上界为。剪支的条件：剪支的条件：后辈节点的后辈节点的 值值祖先节点的祖先节点的 值时，值时，剪支剪支后辈节点的后辈节点的 值值祖先节点的祖先节点的 值时，值时，剪支剪支简记为：简记为：极小极小极大，极大，剪支剪支极大极大极小，极小，剪支剪支4.4.-搜索过程搜索过程86-31453-3503-30 22-3 0-2 309-300-303305411-31661abcdefghijkmnMAXMINMAXMIN改

24、进方法改进方法 使使用用-剪剪支支技技术术，当当不不满满足足剪剪支支条条件件(即即)时时或或 值值比比 值值大大不不了了多多少少或或极极相相近近时时，这这时时也也可可以以进进行行剪剪支支，以以便便有有条条件件把把搜搜索索集集中中到到会会带带来来更更大大效效果果的的其其他他路路径径上上，这这就就是是中中止止对对效效益益不不大大的的一一些些子子树树的的搜索，以提高搜索效率。搜索，以提高搜索效率。4.4.-搜索过程搜索过程 不不严严格格限限制制搜搜索索的的深深度度。当当到到达达深深度度限限制制时时，如如出出现现博博弈弈格格局局有有可可能能发发生生较较大大变变化化时时，则则应应多多搜搜索索几几层层，使

25、使格格局局进进入入较较稳稳定定状状态态后后再再中中止止，这这样样可可使使倒倒推推值值计计算算的的结结果果比比较较合合理理，避避免免考考虑虑不不充充分分产产生生的的影影响响，这这是是等等候候状状态态平稳后中止搜索的方法。平稳后中止搜索的方法。4.4.-搜索过程搜索过程当算法给出所选的走步后，不要马上停止搜当算法给出所选的走步后，不要马上停止搜索，而是在原先估计可能的路径上再往前搜索，而是在原先估计可能的路径上再往前搜索几步，再次检验会不会出现意外，这是一索几步，再次检验会不会出现意外，这是一种增添辅助搜索的方法。种增添辅助搜索的方法。4.4.-搜索过程搜索过程对某些博弈的开局阶段和残局阶段，往对某些博弈的开局阶段和残局阶段，往往总结了一些固定的对弈模式，因此可往总结了一些固定的对弈模式，因此可以利用这些知识编好走步表，以便在开以利用这些知识编好走步表，以便在开局和结局时使用查表法。只是在进入中局和结局时使用查表法。只是在进入中盘阶段后，再调用其他有效的搜索算法，盘阶段后，再调用其他有效的搜索算法，来选择最优的走步。来选择最优的走步。4.4.-搜索过程搜索过程