,*,單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,第二章 與或圖搜索問題,目標(biāo),目標(biāo),初始節(jié)點(diǎn)s,a,b,c,,1,,2.1 基本概念,與或圖是一個超圖，節(jié)點(diǎn)間通過連接符連接。,K-連接符：,,…...,K,個,,2,,耗散值的計(jì)算,k(n, N) = C,n,+k(n,1,, N)+…+k(n,i,, N),其中：N為終節(jié)點(diǎn)集,C,n,為連接符的耗散值,…...,i,個,n,n,1,n,2,n,i,,3,,目標(biāo),目標(biāo),初始節(jié)點(diǎn),解圖：,,4,,能解節(jié)點(diǎn),終節(jié)點(diǎn)是能解節(jié)點(diǎn),若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)時，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一能解時，該非終節(jié)點(diǎn)才能解。,若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)均能解時，該非終節(jié)點(diǎn)才能解。,,5,,不能解節(jié)點(diǎn),沒有后裔的非終節(jié)點(diǎn)是不能解節(jié)點(diǎn)。,若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)，當(dāng)且僅當(dāng)所有子節(jié)點(diǎn)均不能解時，該非終節(jié)點(diǎn)才不能解。,若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時，當(dāng)至少有一個子節(jié)點(diǎn)不能解時，該非終節(jié)點(diǎn)才不能解。,,6,,普通圖搜索的情況,f(n) = g(n) + h(n),對n的評價實(shí)際是對從s到n這條路徑的評價,n,s,,7,,與或圖: 對局部圖的評價,目標(biāo),目標(biāo),初始節(jié)點(diǎn),a,b,c,,8,,兩個過程,圖生成過程，即擴(kuò)展節(jié)點(diǎn),從最優(yōu)的局部途中選擇一個節(jié)點(diǎn)擴(kuò)展,計(jì)算耗散值的過程,對當(dāng)前的局部圖從新計(jì)算耗散值,,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,,設(shè)：K連,接,接符,的耗散值,為,為K,,目標(biāo),目標(biāo),初始節(jié)點(diǎn),n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,,10,,目標(biāo),目標(biāo),初始節(jié)點(diǎn),n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,初始節(jié)點(diǎn),n,0,n,1,(2),n,4,(1),n,5,(1),紅色：4,黃色：3,,11,,初始節(jié)點(diǎn),n,0,,n,4,(1),n,5,(1),紅色：4,黃色：6,n,1,n,2,(4),n,3,(4),5,目標(biāo),目標(biāo),初始節(jié)點(diǎn),n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,,12,,紅色：5,黃色：6,初始節(jié)點(diǎn),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,目標(biāo),目標(biāo),初始節(jié)點(diǎn),n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,,13,,紅色：5,黃色：6,2,1,初始節(jié)點(diǎn),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),目標(biāo),目標(biāo),初始節(jié)點(diǎn),n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,,14,,博弈,是一類具,有,有競爭性,的,的智能活,動,動,雙人博弈,：即兩位,選,選手對壘,，,，輪流依,次,次走步，,其,其中任何,一,一方都完,全,全知道對,方,方過去已,經(jīng),經(jīng)走過的,棋,棋步和今,后,后可能的,走,走步，其,結(jié),結(jié)果是一,方,方贏,(,而另一方,則,則輸,),，或雙方,和,和局,2.3,博,博弈樹搜,索,索,,15,,博弈的例,子,子,：,一字棋,跳棋,中國象棋,圍棋,五子棋,,16,,2.3,博,博弈樹搜,索,索,博弈問題,雙人對弈,，,，對壘的,雙,雙方輪流,走,走步；,信息完備,，,，對壘雙,方,方所得到,的,的信息是,一,一樣的，,不,不存在一,方,方能看到,，,，而另外,一,一方看不,到,到的情況,；,；,零和，即,對,對一方有,利,利的棋，,對,對另一方,肯,肯定是不,利,利的，不,存,存在對雙,方,方均有利,或,或均無利,的,的棋，對,弈,弈的結(jié)果,是,是一方贏,，,，而另一,方,方輸，或,者,者雙方和,棋,棋。,,17,,雙方的智,能,能活動，,任,任何一方,都,都不能單,獨(dú),獨(dú)控制博,弈,弈過程，,而,而是由雙,方,方輪流實(shí),施,施其控制,對,對策的過,程,程。,博弈的特,點(diǎn),點(diǎn)：,,18,,如何根據(jù),當(dāng),當(dāng)前的棋,局,局，選擇,對,對自己最,有,有利的一,步,步棋 ？,,人工智能,中,中研究的,博,博弈問題,：,中國象棋,,19,,用博弈樹,來,來表示，,它,它是一種,特,特殊的,與或樹,。節(jié)點(diǎn)代,表,表博弈的,格,格局（即,棋,棋局），,相,相當(dāng)于狀,態(tài),態(tài)空間中,的,的狀態(tài)，,反,反映了博,弈,弈的信息,，,，,并且與節(jié),點(diǎn),點(diǎn)、或節(jié),點(diǎn),點(diǎn)隔層交,替,替出現(xiàn)。,博弈問題,（,（求解過,程,程）的表,示,示,：,,20,,假設(shè)博弈,雙,雙方為：MAX和MIN,在博弈過,程,程中，規(guī),則,則是雙方,輪,輪流走步,。,。在博弈,樹,樹中，相,當(dāng),當(dāng)于博弈,雙,雙方輪流,擴(kuò),擴(kuò)展其所,屬,屬節(jié)點(diǎn)。,為什么與,節(jié),節(jié)點(diǎn)、或,節(jié),節(jié)點(diǎn)隔層,交,交替出現(xiàn),？,,21,,從,MAX,方的角度,來,來看,：,所有MIN方節(jié)點(diǎn)都,是,是,與節(jié)點(diǎn),理由,：,因?yàn)镸IN方必定選,擇,擇最不利,于,于MAX方的方式,來,來擴(kuò)展節(jié),點(diǎn),點(diǎn)，只要MIN方節(jié)點(diǎn)的,子,子節(jié)點(diǎn)（,下,下出棋局,）,）中有一,個,個對MAX方不利，,則,則該節(jié)點(diǎn),就,就對MAX方不利，,故,故為“,與節(jié)點(diǎn),”。,MIN,好招,,22,,從,MAX,方的角度,來,來看,：,所有屬于,MAX,方的節(jié)點(diǎn),都,都是,或節(jié)點(diǎn),理由,：,因?yàn)閿U(kuò)展,MAX,方節(jié)點(diǎn)時,，,，,MAX,方可選擇,擴(kuò),擴(kuò)展最有,利,利于自己,的,的節(jié)點(diǎn)，,只,只要可擴(kuò),展,展的子節(jié),點(diǎn),點(diǎn)中有一,個,個對已有,利,利，則該節(jié)點(diǎn),就,就對已有,利,利。,MAX,好招,,23,,總之：,從,MAX,方來說，,與,與節(jié)點(diǎn)、,或,或節(jié)點(diǎn)交,替,替出現(xiàn)；,反,反之，從,MIN,方的角度,來,來看，情,況,況正好相,反,反。,,24,,在博,弈,弈樹,中,中，,先,先行,一,一方,的,的初,始,始狀,態(tài),態(tài)對,應(yīng),應(yīng)著,樹,樹的,根節(jié),點(diǎn),點(diǎn),，而,任,任何,一,一方,獲,獲勝,的,的最,終,終格,局,局為,目,目標(biāo),狀,狀態(tài),，,，對,應(yīng),應(yīng)于,樹,樹的,終葉,節(jié),節(jié)點(diǎn),（可,解,解節(jié),點(diǎn),點(diǎn)或,本,本原,問,問題,）,）。,但是,，,，從,MAX,的角,度,度出,發(fā),發(fā)，,所,所有,使,使,MAX,獲勝,的,的狀,態(tài),態(tài)格,局,局都,是,是本,原,原問,題,題，,是,是,可解,節(jié),節(jié)點(diǎn),，而,使,使,MIN,獲勝,的,的狀,態(tài),態(tài)格,局,局是,不可,解,解節(jié),點(diǎn),點(diǎn)。,,25,,博弈,樹,樹特,點(diǎn),點(diǎn),(1)博,弈,弈的,初,初始,狀,狀態(tài),是,是初,始,始節(jié),點(diǎn),點(diǎn)；,(2)博,弈,弈樹,的,的“,與,與”,節(jié),節(jié)點(diǎn),和,和“,或,或”,節(jié),節(jié)點(diǎn),是,是逐,層,層交,替,替出,現(xiàn),現(xiàn)的,；,；,(3)整,個,個博,弈,弈過,程,程始,終,終站,在,在某,一,一方,的,的立,場,場上,，,，所,以,以能,使,使自,己,己一,方,方獲,勝,勝的,終,終局,都,都是,本,本原,問,問題,，,，相,應(yīng),應(yīng)的,節(jié),節(jié)點(diǎn),也,也是,可,可解,節(jié),節(jié)點(diǎn),，,，所,有,有使,對,對方,獲,獲勝,的,的節(jié),點(diǎn),點(diǎn)都,是,是不,可,可解,節(jié),節(jié)點(diǎn),。,。,,26,,例,Grundy,博弈,：,：分,配,配物,品,品的,問,問題,如果,有,有一,堆,堆數(shù),目,目為,N,的錢,幣,幣，,由,由兩,位,位選,手,手輪,流,流進(jìn),行,行分,配,配，,要,要求,每,每個,選,選手,每,每次,把,把其,中,中某,一,一堆,分,分成,數(shù),數(shù)目,不等,的兩,小,小堆,，,，直,至,至有,一,一選,手,手不,能,能將,錢,錢幣,分,分成,不,不等,的,的兩,堆,堆為,止,止，,則,則判,定,定這,位,位選,手,手為,輸,輸家,。,。,,27,,用數(shù),字,字序,列,列加,上,上一,個,個說,明,明來,表,表示,一,一個,狀,狀態(tài),：,：,(,3,2,1,1,MAX,),數(shù)字序,列,列,：表示,不,不同堆,中,中錢幣,的,的個數(shù),說明,：表示,下,下一步,由,由誰來,分,分，即,取,取,MAX,或,MIN,,28,,現(xiàn)在取,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,,對于比,較,較復(fù)雜,的,的博弈,問,問題，,只,只能模,擬,擬人的,思,思維“,向前看,幾,幾步,”，然后,作,作出決,策,策，選,擇,擇最有,利,利自己,的,的一步,。,。即,只能給,出,出幾層,走,走法，,然,然后按,照,照一定,的,的估算,辦,辦法，,決定走,一,一好招,。,。,,31,,中國象,棋,棋,一盤棋,平,平均走50步,，,，總狀,態(tài),態(tài)數(shù)約,為,為10,的,的161次方,。,。,假設(shè)1,毫,毫微秒,走,走一步,，,，約需10的145,次,次方年,。,。,結(jié)論：,不,不可能,窮,窮舉。,,32,,在人工,智,智能中,可,可以采,用,用搜索,方,方法來,求,求解博,弈,弈問題,，,，下面,就,就來討,論,論博弈,中,中兩中,最,最基本,的,的搜索,方,方法。,,33,,對于復(fù),雜,雜的博,弈,弈問題,，,，要規(guī),定,定搜索,深,深度與,時,時間，,以,以便于,博,博弈搜,索,索能順,利,利進(jìn)行,。,。,假設(shè)由,MAX,來選擇,走,走一步,棋,棋，問,題,題是：,MAX,如何來,選,選擇一,步,步好棋,？,極大極,小,小過程,,34,,極大極,小,小過程,極大極,小,小過程,是,是考慮,雙,雙方對,弈,弈若干,步,步之后,，,，從可,能,能的走,法,法中選,一,一步相,對,對好的,走,走法來,走,走，即,在,在有限,的,的搜索,深,深度范,圍,圍內(nèi)進(jìn),行,行求解,。,。,需要定,義,義一個,靜,靜態(tài)估,價,價函數(shù)e,以,便,便對棋,局,局的態(tài),勢,勢做出,評,評估。,,35,,①,對于每,一,一格局,（,（棋局,）,）給出,（,（定義,或,或者倒,推,推）一,個,個靜態(tài),估,估價函,數(shù),數(shù)值。,值,值越大,對,對MAX越有,利,利，反,之,之越不,利,利；,極大極,小,小過程,的,的基本,思,思路,：,,36,,②,對于給,定,定的格,局,局，,MAX,給出可,能,能的走,法,法，然,后,后,MIN,對應(yīng)地,給,給出相,應(yīng),應(yīng)的走,法,法，這,樣,樣重復(fù),若,若干次,，,，得到,一,一組端,節(jié),節(jié)點(diǎn)（,必,必須由,MIN,走后得,到,到的，,等,等待,MAX,下的棋,局,局）。,這,這一過,程,程相當(dāng),于,于節(jié)點(diǎn),擴(kuò),擴(kuò)展；,注,：博弈,樹,樹深度,或,或?qū)訑?shù),一,一定是,偶,偶數(shù)。,,37,,③,對于每,一,一個端,節(jié),節(jié)點(diǎn)，,計(jì),計(jì)算出,它,它們的,靜,靜態(tài)估,價,價函數(shù),，,，然后,自,自下而,上,上地逐,層,層計(jì)算,倒,倒推值,，,，直到MAX,開,開始的,格,格局。,在,在MIN下的,格,格局中,取,取估值,的,的最小,值,值，在MAX,下,下格局,中,中取估,值,值的最,大,大值；,④,取估值,最,最大的,格,格局作,為,為,MAX,要走的,一,一招棋,。,。,,38,,例,：,向前看,一,一步的,兩,兩層博,弈,弈樹,,39,,定義靜,態(tài),態(tài)函數(shù)e(P)的一,般,般原則,：,,40,,OPEN,：存放,待,待擴(kuò)展,的,的節(jié)點(diǎn),，,，此時,為,為隊(duì)列,，,，即以,寬,寬度優(yōu),先,先的策,略,略擴(kuò)展,節(jié),節(jié)點(diǎn)。,CLOSED,：存放,已,已擴(kuò)展,的,的節(jié)點(diǎn),，,，此時,為,為堆棧,，,，即后,擴(kuò),擴(kuò)展的,節(jié),節(jié)點(diǎn)先,計(jì),計(jì)算。,符號,：,,41,,極大極,小,小過程,的,的基本,思,思想：,(1),當(dāng),當(dāng)輪到MIN,走,走步的,節(jié),節(jié)點(diǎn)時,，,，MAX應(yīng)考,慮,慮最壞,的,的情況,（,（即f(p),取,取極小,值,值）；,(2),當(dāng),當(dāng)輪到MAX,走,走步的,節(jié),節(jié)點(diǎn)時,，,，MAX應(yīng)考,慮,慮最好,的,的情況,（,（即f(p),取,取極大,值,值）；,(3),評,評價往,回,回倒推,時,時，相,應(yīng),應(yīng)于兩,位,位棋手,的,的對抗,策,策略，,交,交替使,用,用（1,）,）和（2）兩,種,種方法,傳,傳遞倒,推,推值。,,42,,1,、將初,始,始節(jié)點(diǎn)S放入OPEN表中，,開,開始時,搜,搜索樹T由初始,節(jié),節(jié)點(diǎn)S構(gòu)成；,2,、若OPEN表為空,（,（,節(jié)點(diǎn)擴(kuò),展,展結(jié)束,），則,轉(zhuǎn),轉(zhuǎn)5；,3,、將OPEN表中第,一,一個節(jié),點(diǎn),點(diǎn),n,移出放入CLOSED表的前,端,端；,極大極,小,小搜索,過,過程,為,：,,43,,4,、若,n,可直接,判,判定為,贏,贏、輸,、,、或平,局,局，則,令,令對應(yīng),的,的,e,(,n,)=∞,，,，-∞,或,或 0,，,，并轉(zhuǎn)2；否,則,則擴(kuò)展,n,，產(chǎn)生,n,的后繼,節(jié),節(jié)點(diǎn)集{,n,i,}，將{,n,i,}放入,搜,搜索樹T,中,中。此,時,時，若,搜,搜索深,度,度,d,{,n,i,}小于,預(yù),預(yù)先設(shè),定,定的深,度,度,k,，則將{,n,i,}放入OPEN表的,末,末端，,轉(zhuǎn),轉(zhuǎn)2；,否,否則，,n,i,達(dá)到深,度,度,k,，計(jì)算,e,(,n,i,)，并,轉(zhuǎn),轉(zhuǎn)2；,,44,,5,、若CLOSED表為空,，,，則轉(zhuǎn)8；否,則,則取出CLOSED表中的,第,第一個,節(jié),節(jié)點(diǎn)，,記,記為,n,p,；,Open為空,，,，即已,經(jīng),經(jīng)擴(kuò)展,完,完節(jié)點(diǎn),步2,,45,,6,、若,n,p,屬于MAX層，且,對,對于它,的,的屬于MIN層的子,節(jié),節(jié)點(diǎn),n,ci,的,e,(,n,ci,)有值,，,，則：,e,(,n,p,) =max{,n,ci,},,46,,（續(xù)）,若,n,p,屬于MIN層，且,對,對于它,的,的屬于MAX層的子,節(jié),節(jié)點(diǎn),n,ci,的,e,(,n,ci,)有值,，,，則：,e,(,n,p,)=min{,n,ci,},,47,,7,、轉(zhuǎn)5,；,；,8,、根據(jù),e,(S)的值，,標(biāo),標(biāo)記走,步,步或者,結(jié),結(jié)束（-∞，,∞,∞或0）。,,48,,第一階,段,段,為1、2、3,、,、4步,，,，用寬,度,度優(yōu)先,算,算法生,成,成規(guī)定,深,深度,k,的全部,博,博弈樹,，,，然后,對,對其所,有,有端節(jié),點(diǎn),點(diǎn)計(jì)算e(P)；,第二階,段,段,為5、6、7,、,、8步,，,，是自,下,下而上,逐,逐級求,節(jié),節(jié)點(diǎn)的,倒,倒推估,價,價值，,直,直至求,出,出初始,節(jié),節(jié)點(diǎn)的e(S),為,為止，,再,再由e(S) 選,得,得相對,較,較好的,走,走法，,過,過程結(jié),束,束。,算法分,成,成兩個,階,階段,：,,49,,等對手,走,走出相,應(yīng),應(yīng)的棋,，,，再以,當(dāng),當(dāng)前的,格,格局作,為,為初始,節(jié),節(jié)點(diǎn)，,重,重復(fù)此,過,過程，,選,選擇對,自,自己有,利,利的走,法,法。,,50,,極大極小過,程,程,,51,,例,：,一字棋的極,大,大極小搜索,過,過程,約定,：,每一方只向,前,前看一步,（擴(kuò)展出二,層,層）,記,MAX,的棋子為“,×,”，,MIN,的棋子為“,O,”,規(guī)定,MAX,先手,,52,,①,若格局 P,對,對任何一,方,方都不能獲,勝,勝，則,e(P)=（所有空格上,都,都放上MAX的棋子后,，,，MAX的,三,三個棋子所,組,組成的行、,列,列及對角線,的,的總數(shù)）-（所有空格上,都,都放上MIN的棋子后,，,，MIN的,三,三個棋子所,組,組成的行、,列,列及對角線,的,的總數(shù)）,靜態(tài)估計(jì)函,數(shù),數(shù)e(P),定,定義為,：,,53,,②,若 P 是MAX獲勝,，,，則,e(P)=+∞,③,若 P 是MIN獲勝,，,，則,e(P)=,－∞,,54,,例：,計(jì)算下列棋,局,局的靜態(tài)估,價,價函數(shù)值,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,,極大極小搜,索,索過程由兩,個,個完全分離,的,的兩個步驟,組,組成：,第一,、用寬度優(yōu),先,先算法生成,一,一棵博弈搜,索,索樹,第二,、估計(jì)值的,倒,倒推計(jì)算,缺點(diǎn),：這種分離,使,使得搜索的,效,效率比較低,,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，端節(jié),點(diǎn),點(diǎn)上的數(shù)字,表,表示它對應(yīng),的,的估價函數(shù),的,的值。,極大,極小,,63,,極大極小過,程,程是先生成,與,與/或樹，,然,然后再計(jì)算,各,各節(jié)點(diǎn)的估,值,值，這種生,成,成節(jié)點(diǎn)和計(jì),算,算估值相分,離,離的搜索方,式,式，需要生,成,成規(guī)定深度,內(nèi),內(nèi)的所有節(jié),點(diǎn),點(diǎn)，因此搜,索,索效率較低,。,。,改進(jìn),：在博弈樹生,成,成過程中同,時,時計(jì)算端節(jié),點(diǎn),點(diǎn)的估計(jì)值,及,及倒推值，,以,以減少搜索,的,的次數(shù)，這,就,就是α-β,過,過程的思想,，,，也稱為α-β剪枝法,。,。,剪枝的概念:,如果能邊生,成,成節(jié)點(diǎn)邊對,節(jié),節(jié)點(diǎn)估值，,并,并剪去一些,沒,沒用的分枝,，,，這種技術(shù),被,被稱為α-,β,β剪枝。,,64,,?-?剪枝,極大節(jié)點(diǎn)的,下,下界為,?。,極小節(jié)點(diǎn)的,上,上界為?。,剪枝的條件,：,：,后輩節(jié)點(diǎn)的,?,?值≤祖先,節(jié),節(jié)點(diǎn)的?值,時,時， ?剪,枝,枝,后輩節(jié),點(diǎn),點(diǎn)的?,值,值≥,祖,祖先節(jié),點(diǎn),點(diǎn)的?,值,值時，,?,?剪,枝,枝,簡記為,：,：,極小≤,極,極大，,?,?剪,枝,枝,極大≥,極,極小，,?,?剪,枝,枝,,65,,一個α-β剪,枝,枝的具,體,體例子,，,，如下,圖,圖所示,。,。其中,最,最下面,一,一層端,節(jié),節(jié)點(diǎn)旁,邊,邊的數(shù),字,字是假,設(shè),設(shè)的估,值,值。,在該圖,中,中，L,、,、M、N的估,值,值推出,節(jié),節(jié)點(diǎn)F,的,的倒推,值,值為4,，,，即F,的,的β值,為,為4，,由,由此可,推,推出節(jié),點(diǎn),點(diǎn)C的,倒,倒推值,≥,≥4。,記C的,倒,倒推值,的,的下界,為,為4，,不,不可能,再,再比4,小,小，故C的α,值,值為4,。,。,,,由節(jié)點(diǎn)N的估,值,值推知,節(jié),節(jié)點(diǎn)G,的,的倒推,值,值小于,≤,≤1,,無,無論G,的,的其它,子,子節(jié)點(diǎn),的,的估只,是,是多少,，,，G的,倒,倒推值,都,都不可,能,能比1,大,大。因,此,此，1,是,是G的,倒,倒推值,的,的上界,，,，所以G的值,≦,≦1,。,。另已,知,知C的,倒,倒推值,≥,≥4，G的其,它,它子節(jié),點(diǎn),點(diǎn)又不,可,可能使C的倒,推,推值增,大,大。因,此,此對G,的,的其它,分,分支不,必,必再搜,索,索，相,當(dāng),當(dāng)于把,這,這些分,枝,枝剪去,。,。,由F、G的倒,推,推值可,推,推出節(jié),點(diǎn),點(diǎn)C的,倒,倒推值,≥,≥4,，,，再由C可推,出,出節(jié)點(diǎn)A的倒,推,推值≤4，即A的β,值,值為4,。,。另外，,由,由節(jié)點(diǎn)P、Q,推,推出的,節(jié),節(jié)點(diǎn)H,的,的倒推,值,值為5,，,，因此D的倒,推,推值,≥,≥5，,即,即D的,α,α值為5。此,時,時，D,的,的其它,子,子節(jié)點(diǎn),的,的倒推,值,值無論,是,是多少,都,都不能,使,使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,?-?,剪,剪枝（,續(xù),續(xù)）,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,,?-?,剪,剪枝的,其,其他應(yīng),用,用,故障診,斷,斷,,,ABCD,,風(fēng)險投,資,資,,,68,,演講完,畢,畢，謝,謝,謝觀看,！,！,