单击此处编辑母版标题样式,,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 与或图搜索问题,目标,目标,初始节点s,a,b,c,,1,,2.1 基本概念,与或图是一个超图，节点间通过连接符连接K-连接符：,,…...,K,个,,2,,耗散值的计算,k(n, N) = C,n,+k(n,1,, N)+…+k(n,i,, N),其中：N为终节点集,C,n,为连接符的耗散值,…...,i,个,n,n,1,n,2,n,i,,3,,目标,目标,初始节点,解图：,,4,,能解节点,终节点是能解节点,若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解5,,不能解节点,没有后裔的非终节点是不能解节点若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解6,,普通图搜索的情况,f(n) = g(n) + h(n),对n的评价实际是对从s到n这条路径的评价,n,s,,7,,与或图: 对局部图的评价,目标,目标,初始节点,a,b,c,,8,,两个过程,图生成过程，即扩展节点,从最优的局部途中选择一个节点扩展,计算耗散值的过程,对当前的局部图从新计算耗散值,,9,,AO*算,法,法举例,其中：,h(n,0,)=3,h(n,1,)=2,h(n,2,)=4,h(n,3,)=4,h(n,4,)=1,h(n,5,)=1,h(n,6,)=2,h(n,7,)=0,h(n,8,)=0,,设：K连,接,接符,的耗散值,为,为K,,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,,10,,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,初始节点,n,0,n,1,(2),n,4,(1),n,5,(1),红色：4,黄色：3,,11,,初始节点,n,0,,n,4,(1),n,5,(1),红色：4,黄色：6,n,1,n,2,(4),n,3,(4),5,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,,12,,红色：5,黄色：6,初始节点,n,0,,n,4,(1),n,5,(1),n,1,n,2,(4),n,3,(4),5,n,6,(2),n,7,(0),n,8,(0),2,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,,13,,红色：5,黄色：6,2,1,初始节点,n,0,,n,4,(1),n,5,(1),n,1,n,2,(4),n,3,(4),5,n,6,(2),n,7,(0),n,8,(0),目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,,14,,博弈,是一类具,有,有竞争性,的,的智能活,动,动,双人博弈,：即两位,选,选手对垒,，,，轮流依,次,次走步，,其,其中任何,一,一方都完,全,全知道对,方,方过去已,经,经走过的,棋,棋步和今,后,后可能的,走,走步，其,结,结果是一,方,方赢,(,而另一方,则,则输,),，或双方,和,和局,2.3,博,博弈树搜,索,索,,15,,博弈的例,子,子,：,一字棋,跳棋,中国象棋,围棋,五子棋,,16,,2.3,博,博弈树搜,索,索,博弈问题,双人对弈,，,，对垒的,双,双方轮流,走,走步；,信息完备,，,，对垒双,方,方所得到,的,的信息是,一,一样的，,不,不存在一,方,方能看到,，,，而另外,一,一方看不,到,到的情况,；,；,零和，即,对,对一方有,利,利的棋，,对,对另一方,肯,肯定是不,利,利的，不,存,存在对双,方,方均有利,或,或均无利,的,的棋，对,弈,弈的结果,是,是一方赢,，,，而另一,方,方输，或,者,者双方和,棋,棋。
17,,双方的智,能,能活动，,任,任何一方,都,都不能单,独,独控制博,弈,弈过程，,而,而是由双,方,方轮流实,施,施其控制,对,对策的过,程,程博弈的特,点,点：,,18,,如何根据,当,当前的棋,局,局，选择,对,对自己最,有,有利的一,步,步棋 ？,,人工智能,中,中研究的,博,博弈问题,：,中国象棋,,19,,用博弈树,来,来表示，,它,它是一种,特,特殊的,与或树,节点代,表,表博弈的,格,格局（即,棋,棋局），,相,相当于状,态,态空间中,的,的状态，,反,反映了博,弈,弈的信息,，,，,并且与节,点,点、或节,点,点隔层交,替,替出现博弈问题,（,（求解过,程,程）的表,示,示,：,,20,,假设博弈,双,双方为：MAX和MIN,在博弈过,程,程中，规,则,则是双方,轮,轮流走步,在博弈,树,树中，相,当,当于博弈,双,双方轮流,扩,扩展其所,属,属节点为什么与,节,节点、或,节,节点隔层,交,交替出现,？,,21,,从,MAX,方的角度,来,来看,：,所有MIN方节点都,是,是,与节点,理由,：,因为MIN方必定选,择,择最不利,于,于MAX方的方式,来,来扩展节,点,点，只要MIN方节点的,子,子节点（,下,下出棋局,）,）中有一,个,个对MAX方不利，,则,则该节点,就,就对MAX方不利，,故,故为“,与节点,”。
MIN,好招,,22,,从,MAX,方的角度,来,来看,：,所有属于,MAX,方的节点,都,都是,或节点,理由,：,因为扩展,MAX,方节点时,，,，,MAX,方可选择,扩,扩展最有,利,利于自己,的,的节点，,只,只要可扩,展,展的子节,点,点中有一,个,个对已有,利,利，则该节点,就,就对已有,利,利MAX,好招,,23,,总之：,从,MAX,方来说，,与,与节点、,或,或节点交,替,替出现；,反,反之，从,MIN,方的角度,来,来看，情,况,况正好相,反,反24,,在博,弈,弈树,中,中，,先,先行,一,一方,的,的初,始,始状,态,态对,应,应着,树,树的,根节,点,点,，而,任,任何,一,一方,获,获胜,的,的最,终,终格,局,局为,目,目标,状,状态,，,，对,应,应于,树,树的,终叶,节,节点,（可,解,解节,点,点或,本,本原,问,问题,）,）但是,，,，从,MAX,的角,度,度出,发,发，,所,所有,使,使,MAX,获胜,的,的状,态,态格,局,局都,是,是本,原,原问,题,题，,是,是,可解,节,节点,，而,使,使,MIN,获胜,的,的状,态,态格,局,局是,不可,解,解节,点,点。
25,,博弈,树,树特,点,点,(1)博,弈,弈的,初,初始,状,状态,是,是初,始,始节,点,点；,(2)博,弈,弈树,的,的“,与,与”,节,节点,和,和“,或,或”,节,节点,是,是逐,层,层交,替,替出,现,现的,；,；,(3)整,个,个博,弈,弈过,程,程始,终,终站,在,在某,一,一方,的,的立,场,场上,，,，所,以,以能,使,使自,己,己一,方,方获,胜,胜的,终,终局,都,都是,本,本原,问,问题,，,，相,应,应的,节,节点,也,也是,可,可解,节,节点,，,，所,有,有使,对,对方,获,获胜,的,的节,点,点都,是,是不,可,可解,节,节点,26,,例,Grundy,博弈,：,：分,配,配物,品,品的,问,问题,如果,有,有一,堆,堆数,目,目为,N,的钱,币,币，,由,由两,位,位选,手,手轮,流,流进,行,行分,配,配，,要,要求,每,每个,选,选手,每,每次,把,把其,中,中某,一,一堆,分,分成,数,数目,不等,的两,小,小堆,，,，直,至,至有,一,一选,手,手不,能,能将,钱,钱币,分,分成,不,不等,的,的两,堆,堆为,止,止，,则,则判,定,定这,位,位选,手,手为,输,输家,。
27,,用数,字,字序,列,列加,上,上一,个,个说,明,明来,表,表示,一,一个,状,状态,：,：,(,3,2,1,1,MAX,),数字序,列,列,：表示,不,不同堆,中,中钱币,的,的个数,说明,：表示,下,下一步,由,由谁来,分,分，即,取,取,MAX,或,MIN,,28,,现在取,N,＝,7 的,简,简单情,况,况,，并由,MIN,先分,注,：如果MAX走,红,红箭头,的,的分法,，,，必定,获,获胜所有可,能,能的分,法,法,(7,MIN),(6,1,MAX),(5,2,MAX),(4,3,MAX),(5,1,1,MIN),(4,2,1,MIN),(3,2,2,MIN),(3,3,1,MIN),(4,1,1,1,MAX),(3,2,1,1,MAX),(2,2,2,1,MAX),(2,2,1,1,1,MIN),(3,1,1,1,1,MIN),(2,1,1,1,1,1,MAX),,29,,分钱币,问,问题,（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,）,）,对方先,走,走,我方必,胜,胜,,30,,对于比,较,较复杂,的,的博弈,问,问题，,只,只能模,拟,拟人的,思,思维“,向前看,几,几步,”，然后,作,作出决,策,策，选,择,择最有,利,利自己,的,的一步,。
即,只能给,出,出几层,走,走法，,然,然后按,照,照一定,的,的估算,办,办法，,决定走,一,一好招,31,,中国象,棋,棋,一盘棋,平,平均走50步,，,，总状,态,态数约,为,为10,的,的161次方,假设1,毫,毫微秒,走,走一步,，,，约需10的145,次,次方年,结论：,不,不可能,穷,穷举32,,在人工,智,智能中,可,可以采,用,用搜索,方,方法来,求,求解博,弈,弈问题,，,，下面,就,就来讨,论,论博弈,中,中两中,最,最基本,的,的搜索,方,方法33,,对于复,杂,杂的博,弈,弈问题,，,，要规,定,定搜索,深,深度与,时,时间，,以,以便于,博,博弈搜,索,索能顺,利,利进行,假设由,MAX,来选择,走,走一步,棋,棋，问,题,题是：,MAX,如何来,选,选择一,步,步好棋,？,极大极,小,小过程,,34,,极大极,小,小过程,极大极,小,小过程,是,是考虑,双,双方对,弈,弈若干,步,步之后,，,，从可,能,能的走,法,法中选,一,一步相,对,对好的,走,走法来,走,走，即,在,在有限,的,的搜索,深,深度范,围,围内进,行,行求解,需要定,义,义一个,静,静态估,价,价函数e,以,便,便对棋,局,局的态,势,势做出,评,评估。
35,,①,对于每,一,一格局,（,（棋局,）,）给出,（,（定义,或,或者倒,推,推）一,个,个静态,估,估价函,数,数值值,值越大,对,对MAX越有,利,利，反,之,之越不,利,利；,极大极,小,小过程,的,的基本,思,思路,：,,36,,②,对于给,定,定的格,局,局，,MAX,给出可,能,能的走,法,法，然,后,后,MIN,对应地,给,给出相,应,应的走,法,法，这,样,样重复,若,若干次,，,，得到,一,一组端,节,节点（,必,必须由,MIN,走后得,到,到的，,等,等待,MAX,下的棋,局,局）这,这一过,程,程相当,于,于节点,扩,扩展；,注,：博弈,树,树深度,或,或层数,一,一定是,偶,偶数37,,③,对于每,一,一个端,节,节点，,计,计算出,它,它们的,静,静态估,价,价函数,，,，然后,自,自下而,上,上地逐,层,层计算,倒,倒推值,，,，直到MAX,开,开始的,格,格局在,在MIN下的,格,格局中,取,取估值,的,的最小,值,值，在MAX,下,下格局,中,中取估,值,值的最,大,大值；,④,取估值,最,最大的,格,格局作,为,为,MAX,要走的,一,一招棋,38,,例,：,向前看,一,一步的,两,两层博,弈,弈树,,39,,定义静,态,态函数e(P)的一,般,般原则,：,,40,,OPEN,：存放,待,待扩展,的,的节点,，,，此时,为,为队列,，,，即以,宽,宽度优,先,先的策,略,略扩展,节,节点。
CLOSED,：存放,已,已扩展,的,的节点,，,，此时,为,为堆栈,，,，即后,扩,扩展的,节,节点先,计,计算符号,：,,41,,极大极,小,小过程,的,的基本,思,思想：,(1),当,当轮到MIN,走,走步的,节,节点时,，,，MAX应考,虑,虑最坏,的,的情况,（,（即f(p),取,取极小,值,值）；,(2),当,当轮到MAX,走,走步的,节,节点时,，,，MAX应考,虑,虑最好,的,的情况,（,（即f(p),取,取极大,值,值）；,(3),评,评价往,回,回倒推,时,时，相,应,应于两,位,位棋手,的,的对抗,策,策略，,交,交替使,用,用（1,）,）和（2）两,种,种方法,传,传递倒,推,推值42,,1,、将初,始,始节点S放入OPEN表中，,开,开始时,搜,搜索树T由初始,节,节点S构成；,2,、若OPEN表为空,（,（,节点扩,展,展结束,），则,转,转5；,3,、将OPEN表中第,一,一个节,点,点,n,移出放入CLOSED表的前,端,端；,极大极,小,小搜索,过,过程,为,：,,43,,4,、若,n,可直接,判,判定为,赢,赢、输,、,、或平,局,局，则,令,令对应,的,的,e,(,n,)=∞,，,，-∞,或,或 0,，,，并转2；否,则,则扩展,n,，产生,n,的后继,节,节点集{,n,i,}，将{,n,i,}放入,搜,搜索树T,中,中。
此,时,时，若,搜,搜索深,度,度,d,{,n,i,}小于,预,预先设,定,定的深,度,度,k,，则将{,n,i,}放入OPEN表的,末,末端，,转,转2；,否,否则，,n,i,达到深,度,度,k,，计算,e,(,n,i,)，并,转,转2；,,44,,5,、若CLOSED表为空,，,，则转8；否,则,则取出CLOSED表中的,第,第一个,节,节点，,记,记为,n,p,；,Open为空,，,，即已,经,经扩展,完,完节点,步2,,45,,6,、若,n,p,属于MAX层，且,对,对于它,的,的属于MIN层的子,节,节点,n,ci,的,e,(,n,ci,)有值,，,，则：,e,(,n,p,) =max{,n,ci,},,46,,（续）,若,n,p,属于MIN层，且,对,对于它,的,的属于MAX层的子,节,节点,n,ci,的,e,(,n,ci,)有值,，,，则：,e,(,n,p,)=min{,n,ci,},,47,,7,、转5,；,；,8,、根据,e,(S)的值，,标,标记走,步,步或者,结,结束（-∞，,∞,∞或0）48,,第一阶,段,段,为1、2、3,、,、4步,，,，用宽,度,度优先,算,算法生,成,成规定,深,深度,k,的全部,博,博弈树,，,，然后,对,对其所,有,有端节,点,点计算e(P)；,第二阶,段,段,为5、6、7,、,、8步,，,，是自,下,下而上,逐,逐级求,节,节点的,倒,倒推估,价,价值，,直,直至求,出,出初始,节,节点的e(S),为,为止，,再,再由e(S) 选,得,得相对,较,较好的,走,走法，,过,过程结,束,束。
算法分,成,成两个,阶,阶段,：,,49,,等对手,走,走出相,应,应的棋,，,，再以,当,当前的,格,格局作,为,为初始,节,节点，,重,重复此,过,过程，,选,选择对,自,自己有,利,利的走,法,法50,,极大极小过,程,程,,51,,例,：,一字棋的极,大,大极小搜索,过,过程,约定,：,每一方只向,前,前看一步,（扩展出二,层,层）,记,MAX,的棋子为“,×,”，,MIN,的棋子为“,O,”,规定,MAX,先手,,52,,①,若格局 P,对,对任何一,方,方都不能获,胜,胜，则,e(P)=（所有空格上,都,都放上MAX的棋子后,，,，MAX的,三,三个棋子所,组,组成的行、,列,列及对角线,的,的总数）-（所有空格上,都,都放上MIN的棋子后,，,，MIN的,三,三个棋子所,组,组成的行、,列,列及对角线,的,的总数）,静态估计函,数,数e(P),定,定义为,：,,53,,②,若 P 是MAX获胜,，,，则,e(P)=+∞,③,若 P 是MIN获胜,，,，则,e(P)=,－∞,,54,,例：,计算下列棋,局,局的静态估,价,价函数值,e(P)=6-4=2,棋局,,O,×,×,O,×,×,×,×,×,×,×,O,O,O,O,×,O,O,O,O,行=2,列=2,对角=2,行=2,列=2,对角=0,,55,,利用棋盘的,对,对称性，有,些,些棋局是等,价,价的,,,O,×,,,×,O,O,,×,,,×,O,,56,,,,,,,,,,,×,,,,,,,,,,,,×,,,,,,,,,,×,,,,,×,,,O,,,,,,×,,,,,,O,,,×,,,,,,,O,,×,,,,,,,,O,×,,,,O,,,,,O,,,,×,,,,,,,,O,×,,,,,O,,,×,,,,,,,O,,×,,,,,,,,O,×,,,,,,,,,×,,O,,,,,,,×,O,,,,,1,0,1,0,-1,-1,0,-1,0,-2,1,2,1,-2,-1,1,MAX,MIN,MAX,MAX的走,步,步,,57,,第二步,,O,,,X,,,,,X,O,,,X,,,,,,O,,X,X,,,,,,O,,,X,,X,,,,O,,,X,,,X,,X,O,,O,X,,,,,X,O,O,,X,,,,,X,O,,,X,,O,,,X,O,,,X,,,,O,X,O,,,X,O,,,,2,1,3,2,1,1,O,O,,X,X,,,,,,O,,X,X,,O,,,,O,,X,X,,,O,,,O,,X,X,,,,O,,O,,X,X,O,,,,1,0,2,0,1,,O,O,X,X,,,,,1,0,O,O,,,X,,X,,,,O,,O,X,,X,,,,O,O,,X,,X,,,,O,,,X,O,X,,,,O,,,X,,X,,O,,O,,,X,,X,O,,2,2,3,1,2,2,1,O,O,,,X,,,X,,,O,,,X,,O,X,,,O,,O,X,,,X,,1,1,0,0,1,,58,,第三步,,O,O,,X,,X,,,X,O,O,,X,,X,,,,O,O,X,X,,X,,,,O,O,,X,,X,X,,,O,O,,X,,X,,X,,O,O,,X,X,X,,,X,O,O,O,X,,X,,,X,O,O,,X,,X,O,,X,O,O,,X,,X,,O,X,O,O,,X,O,X,,,O,O,O,,X,X,X,,,,O,O,O,X,X,X,,,,O,O,,X,X,X,O,,,O,O,,X,X,X,,O,O,O,O,X,X,,X,,,,O,O,X,X,,X,O,,,O,O,X,X,,X,,O,,O,O,X,X,O,X,,,O,O,O,,X,,X,,X,,O,O,O,X,,X,,X,,O,O,,X,,X,O,X,,O,O,,X,O,X,,X,O,O,O,,X,,X,X,,,O,O,O,X,,X,X,,,O,O,,X,,X,X,O,,O,O,,X,O,X,X,,-,0,2,1,-,-,-,1,2,2,1,0,1,-,-,-,1,1,1,1,1,1,2,-,1,1,,59,,×,O,O,,×,,×,,,MAX,MIN,,60,,MAX,MIN,×,O,×,×,O,,61,,极大极小搜,索,索过程由两,个,个完全分离,的,的两个步骤,组,组成：,第一,、用宽度优,先,先算法生成,一,一棵博弈搜,索,索树,第二,、估计值的,倒,倒推计算,缺点,：这种分离,使,使得搜索的,效,效率比较低,,62,,极小极大过,程,程,0,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,0,3,1,6,0,1,1,极大,极小,a,b,注：用□表,示,示MAX，,用,用○表示MIN，端节,点,点上的数字,表,表示它对应,的,的估价函数,的,的值。
极大,极小,,63,,极大极小过,程,程是先生成,与,与/或树，,然,然后再计算,各,各节点的估,值,值，这种生,成,成节点和计,算,算估值相分,离,离的搜索方,式,式，需要生,成,成规定深度,内,内的所有节,点,点，因此搜,索,索效率较低,改进,：在博弈树生,成,成过程中同,时,时计算端节,点,点的估计值,及,及倒推值，,以,以减少搜索,的,的次数，这,就,就是α-β,过,过程的思想,，,，也称为α-β剪枝法,剪枝的概念:,如果能边生,成,成节点边对,节,节点估值，,并,并剪去一些,没,没用的分枝,，,，这种技术,被,被称为α-,β,β剪枝64,,-剪枝,极大节点的,下,下界为,极小节点的,上,上界为剪枝的条件,：,：,后辈节点的,,值≤祖先,节,节点的值,时,时， 剪,枝,枝,后辈节,点,点的,值,值≥,祖,祖先节,点,点的,值,值时，,,剪,枝,枝,简记为,：,：,极小≤,极,极大，,,剪,枝,枝,极大≥,极,极小，,,剪,枝,枝,,65,,一个α-β剪,枝,枝的具,体,体例子,，,，如下,图,图所示,其中,最,最下面,一,一层端,节,节点旁,边,边的数,字,字是假,设,设的估,值,值。
在该图,中,中，L,、,、M、N的估,值,值推出,节,节点F,的,的倒推,值,值为4,，,，即F,的,的β值,为,为4，,由,由此可,推,推出节,点,点C的,倒,倒推值,≥,≥4记C的,倒,倒推值,的,的下界,为,为4，,不,不可能,再,再比4,小,小，故C的α,值,值为4,由节点N的估,值,值推知,节,节点G,的,的倒推,值,值小于,≤,≤1,,无,无论G,的,的其它,子,子节点,的,的估只,是,是多少,，,，G的,倒,倒推值,都,都不可,能,能比1,大,大因,此,此，1,是,是G的,倒,倒推值,的,的上界,，,，所以G的值,≦,≦1,另已,知,知C的,倒,倒推值,≥,≥4，G的其,它,它子节,点,点又不,可,可能使C的倒,推,推值增,大,大因,此,此对G,的,的其它,分,分支不,必,必再搜,索,索，相,当,当于把,这,这些分,枝,枝剪去,由F、G的倒,推,推值可,推,推出节,点,点C的,倒,倒推值,≥,≥4,，,，再由C可推,出,出节点A的倒,推,推值≤4，即A的β,值,值为4,另外，,由,由节点P、Q,推,推出的,节,节点H,的,的倒推,值,值为5,，,，因此D的倒,推,推值,≥,≥5，,即,即D的,α,α值为5。
此,时,时，D,的,的其它,子,子节点,的,的倒推,值,值无论,是,是多少,都,都不能,使,使D及A的倒,推,推值减,少,少或增,大,大，所,以,以D的,其,其他分,枝,枝被减,去,去，并,可,可确定A的倒,推,推值为4 以,以此类,推,推，最,终,终推出S,0,的倒推,值,值为4,≥4,S,0,≤4,A,≦0,11,≥4,≥,5,≥0,C,D,E,0,-6,×,I,J,4,≦1,K,L,N,4,6,1,×,F,G,5,P,5,8,H,×,M,8,β,值,α,值,β,值,α,值,Q,R,×,≤0,≦-6,S,×,×,,66,,8,6,-3,1,4,5,3,-3,5,0,-,剪,剪枝（,续,续）,3,-3,0,2,2,-3,0,-2,3,9,-3,0,0,-3,0,3,3,0,5,4,1,1,-3,1,6,6,1,a,b,c,d,e,f,g,h,i,j,k,m,n,0,剪枝,剪枝,剪枝,剪枝,,67,,-,剪,剪枝的,其,其他应,用,用,故障诊,断,断,,,ABCD,,风险投,资,资,,,68,,演讲完,毕,毕，谢,谢,谢观看,！,！,。