人工智能第四章XXXX

1、第四章第四章 可分解產(chǎn)生式系統(tǒng)的搜索策略可分解產(chǎn)生式系統(tǒng)的搜索策略 學(xué)習(xí)目標(biāo)：學(xué)習(xí)目標(biāo)：了解一般的與了解一般的與/或圖搜索問(wèn)題，掌握與或圖搜索問(wèn)題，掌握與/或圖或圖的啟發(fā)式搜索算法的啟發(fā)式搜索算法AO*。 了解博弈樹(shù)搜索問(wèn)題，掌握博弈樹(shù)搜索中的了解博弈樹(shù)搜索問(wèn)題，掌握博弈樹(shù)搜索中的極小極大方法和極小極大方法和-剪枝搜索方法。剪枝搜索方法。重點(diǎn)：重點(diǎn)：AO*算法，算法，-剪枝算法。剪枝算法。 2/21/20221l第二章可分解產(chǎn)生式系統(tǒng)中提到的與第二章可分解產(chǎn)生式系統(tǒng)中提到的與/或樹(shù)表示，其中加或樹(shù)表示，其中加到每一個(gè)節(jié)點(diǎn)上到每一個(gè)節(jié)點(diǎn)上AND或或OR的標(biāo)記是取決于該節(jié)點(diǎn)對(duì)其的標(biāo)記是取決于該節(jié)點(diǎn)

2、對(duì)其父節(jié)點(diǎn)的關(guān)系。如復(fù)合狀態(tài)分解后擁有一組父節(jié)點(diǎn)的關(guān)系。如復(fù)合狀態(tài)分解后擁有一組“與與”關(guān)系的關(guān)系的后繼節(jié)點(diǎn)；而分量狀態(tài)經(jīng)可應(yīng)用規(guī)則作用后，生成一組后繼節(jié)點(diǎn)；而分量狀態(tài)經(jīng)可應(yīng)用規(guī)則作用后，生成一組“或或”關(guān)系的后繼節(jié)點(diǎn)。與關(guān)系的后繼節(jié)點(diǎn)。與/或樹(shù)是本章介紹的與或樹(shù)是本章介紹的與/或圖的或圖的特例。特例。l在一般與在一般與/或圖中，一個(gè)節(jié)點(diǎn)可能是復(fù)合狀態(tài)的組成部分，或圖中，一個(gè)節(jié)點(diǎn)可能是復(fù)合狀態(tài)的組成部分，而同時(shí)又是一個(gè)規(guī)則應(yīng)用的結(jié)果，很難說(shuō)明它是與后繼而同時(shí)又是一個(gè)規(guī)則應(yīng)用的結(jié)果，很難說(shuō)明它是與后繼還是或后繼因此，不再區(qū)別還是或后繼因此，不再區(qū)別AND節(jié)點(diǎn)或節(jié)點(diǎn)或OR節(jié)點(diǎn)但節(jié)點(diǎn)但在稱謂上沿用習(xí)

3、慣，仍把這種結(jié)構(gòu)稱作與在稱謂上沿用習(xí)慣，仍把這種結(jié)構(gòu)稱作與/或圖?；驁D。 4.1 與/或圖搜索2/21/20222 例例. 一個(gè)與/或圖2/21/20223與與/或圖搜索或圖搜索l 定義：定義： 與與/或圖或圖是一種超圖在超圖中父親節(jié)點(diǎn)和一組后是一種超圖在超圖中父親節(jié)點(diǎn)和一組后繼節(jié)點(diǎn)用超弧連接繼節(jié)點(diǎn)用超弧連接 超弧又叫超弧又叫 k-連接符連接符 k-連接符連接符: 一個(gè)父節(jié)點(diǎn)指向一組一個(gè)父節(jié)點(diǎn)指向一組k個(gè)有與關(guān)系的后繼節(jié)點(diǎn)，個(gè)有與關(guān)系的后繼節(jié)點(diǎn)， 這樣一組弧線稱為一個(gè)這樣一組弧線稱為一個(gè)k-連接符連接符 k1時(shí)，用一圓弧標(biāo)記此連接符。時(shí)，用一圓弧標(biāo)記此連接符。Note:若所有的連接符都是若所有

4、的連接符都是1-連接符，連接符， 則得到的就是與則得到的就是與/或圖的特例或圖的特例-普通有向圖。普通有向圖。2/21/20224與與/或圖搜索或圖搜索l與與/或樹(shù)或樹(shù): 每一個(gè)節(jié)點(diǎn)最多只有一個(gè)父親的與每一個(gè)節(jié)點(diǎn)最多只有一個(gè)父親的與/或圖或圖l根節(jié)點(diǎn)根節(jié)點(diǎn): 在在AND/OR樹(shù)或樹(shù)或AND / OR圖中沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)圖中沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn).l葉節(jié)點(diǎn)葉節(jié)點(diǎn): 在在AND/OR樹(shù)或樹(shù)或AND / OR圖中沒(méi)有后繼的節(jié)點(diǎn)圖中沒(méi)有后繼的節(jié)點(diǎn)l終止節(jié)點(diǎn)終止節(jié)點(diǎn): 滿足終止條件的節(jié)點(diǎn)滿足終止條件的節(jié)點(diǎn) 2/21/20225與與/或圖搜索或圖搜索l一個(gè)可分解的產(chǎn)生式系統(tǒng)定義一個(gè)隱含的與一個(gè)可分解的產(chǎn)生式系統(tǒng)

5、定義一個(gè)隱含的與/或或圖圖的根節(jié)點(diǎn)表示產(chǎn)生式系統(tǒng)的初始狀態(tài)描圖圖的根節(jié)點(diǎn)表示產(chǎn)生式系統(tǒng)的初始狀態(tài)描述，連接符表示對(duì)一狀態(tài)描述應(yīng)用產(chǎn)生式規(guī)則述，連接符表示對(duì)一狀態(tài)描述應(yīng)用產(chǎn)生式規(guī)則或把這一狀態(tài)描述分解成若干組成部分或把這一狀態(tài)描述分解成若干組成部分l可分解產(chǎn)生式系統(tǒng)的任務(wù)可分解產(chǎn)生式系統(tǒng)的任務(wù):從隱含的與從隱含的與/或圖出發(fā)或圖出發(fā)找出一個(gè)從根節(jié)點(diǎn)出發(fā)到終止節(jié)點(diǎn)集的解圖。找出一個(gè)從根節(jié)點(diǎn)出發(fā)到終止節(jié)點(diǎn)集的解圖。2/21/20226例例重寫(xiě)規(guī)則：重寫(xiě)規(guī)則：n0 n1n0 n5，n4n1 n2n1 n3n2 n3n2 n5，n4 n3 n5，n6n4 n5n4 n8n5 n7, n8n5 n6 n6

6、 n7, n82/21/20227練習(xí)練習(xí)1：l假定我們有一個(gè)產(chǎn)生式系統(tǒng)，基于如下重寫(xiě)規(guī)則：假定我們有一個(gè)產(chǎn)生式系統(tǒng)，基于如下重寫(xiě)規(guī)則：R1：n0n1, n2 R5：n2n6, n7 R2：n0n2, n3 R6：n3n5, n6 R3：n1n2 R7：n4n2 R4：n1n4 R8：n5n7 請(qǐng)用與請(qǐng)用與/或圖表示此產(chǎn)生式系統(tǒng)。或圖表示此產(chǎn)生式系統(tǒng)。2/21/20228練習(xí)練習(xí)2：一個(gè)產(chǎn)生式系統(tǒng)使用下面一組重寫(xiě)規(guī)則，這些重一個(gè)產(chǎn)生式系統(tǒng)使用下面一組重寫(xiě)規(guī)則，這些重寫(xiě)規(guī)則把左面的數(shù)字轉(zhuǎn)換成右邊的數(shù)字串。寫(xiě)規(guī)則把左面的數(shù)字轉(zhuǎn)換成右邊的數(shù)字串。63,3 43,164,2 32,142,2 21,1

7、使用這些規(guī)則把使用這些規(guī)則把6轉(zhuǎn)換成由轉(zhuǎn)換成由1組成的數(shù)字串。組成的數(shù)字串。請(qǐng)用與請(qǐng)用與/或圖表示此產(chǎn)生式系統(tǒng)。或圖表示此產(chǎn)生式系統(tǒng)。 2/21/20229與與/或圖搜索或圖搜索l定義定義 設(shè)設(shè)N是與是與/或圖或圖G的終止節(jié)點(diǎn)集合，圖的終止節(jié)點(diǎn)集合，圖G中中無(wú)回路，從節(jié)點(diǎn)無(wú)回路，從節(jié)點(diǎn)n出發(fā)到出發(fā)到 N的一個(gè)的一個(gè)解圖解圖是與是與/或或圖圖G的一個(gè)子圖，用的一個(gè)子圖，用G表示，遞歸定義如下：表示，遞歸定義如下： 1. 若若n是是N中的一個(gè)元素，則中的一個(gè)元素，則G只包括節(jié)點(diǎn)只包括節(jié)點(diǎn)n；2/21/202210與與/或圖搜索或圖搜索2. 若若n有一個(gè)從有一個(gè)從n出發(fā)的連接符出發(fā)的連接符k指向后繼

8、節(jié)點(diǎn)集合指向后繼節(jié)點(diǎn)集合n1，nk，而每一個(gè)而每一個(gè)ni都有從都有從ni出發(fā)的解出發(fā)的解圖，則圖，則G由節(jié)點(diǎn)由節(jié)點(diǎn)n、連接符連接符k、n1，nk中的每一個(gè)節(jié)點(diǎn)到中的每一個(gè)節(jié)點(diǎn)到N的解圖所構(gòu)成；的解圖所構(gòu)成；3. 否則，否則，G沒(méi)有從沒(méi)有從n出發(fā)到出發(fā)到N的解圖的解圖2/21/202211n0n1n3n5n6n8n7an0n4n5n7n8bn0n4n5n7n8c2/21/202212與與/或圖搜索或圖搜索l加權(quán)與加權(quán)與/或圖：權(quán)加在連接符上?；驁D：權(quán)加在連接符上。 假定所有連接符的費(fèi)用均大于某一小的正數(shù)假定所有連接符的費(fèi)用均大于某一小的正數(shù)。使用連接符的費(fèi)用可以計(jì)算解圖的費(fèi)用使用連接符的費(fèi)用可以

9、計(jì)算解圖的費(fèi)用l設(shè)從節(jié)點(diǎn)設(shè)從節(jié)點(diǎn)n到終止節(jié)點(diǎn)集合到終止節(jié)點(diǎn)集合N的的解圖的費(fèi)用解圖的費(fèi)用用用 k(n, N)表示，則表示，則k(n, N)遞歸定義如下：遞歸定義如下： 1. 若若n是是N中的元素，則中的元素，則k(n, N) =0； 2/21/202213與與/或圖搜索或圖搜索2. 若有從若有從n出發(fā)的一個(gè)連接符指向它的解圖后繼出發(fā)的一個(gè)連接符指向它的解圖后繼節(jié)點(diǎn)節(jié)點(diǎn)n1，ni，設(shè)此連接符的費(fèi)用為設(shè)此連接符的費(fèi)用為Ci，則則: k(n, N)= Ci+ k(n1, N)+k(ni, N)l最佳解圖最佳解圖：具有最低費(fèi)用的解圖：具有最低費(fèi)用的解圖2/21/202214設(shè)設(shè)k-連接符的費(fèi)用為連接符

10、的費(fèi)用為k，計(jì)算，計(jì)算k(n0, N) n0n1n3n5n6n8n7an0n4n5n7n8bn0n4n5n7n8c2/21/202215與與/或圖搜索或圖搜索l假定假定h*(n)是從是從n出發(fā)的最佳解圖的費(fèi)用，出發(fā)的最佳解圖的費(fèi)用， h(n)是是h*(n)的估計(jì)值。的估計(jì)值。利用利用h(n)指導(dǎo)對(duì)指導(dǎo)對(duì)AND/OR圖的啟發(fā)式搜索。圖的啟發(fā)式搜索。2/21/202216與與/或圖搜索或圖搜索l在在AND/OR圖中，對(duì)任意連接符的圖中，對(duì)任意連接符的單調(diào)限制單調(diào)限制是是 h(n)c+h(n1)+h(nk)其中，其中，n是任意節(jié)點(diǎn)，是任意節(jié)點(diǎn)，c是從是從n出發(fā)的連接符的費(fèi)出發(fā)的連接符的費(fèi)用，用， n

11、1，nk是是n的在此連接符下的后繼節(jié)點(diǎn)。的在此連接符下的后繼節(jié)點(diǎn)。Note: 若對(duì)于所有的終止節(jié)點(diǎn)，都有若對(duì)于所有的終止節(jié)點(diǎn)，都有h(n)0，則則單調(diào)限制還隱含著單調(diào)限制還隱含著h對(duì)所有的節(jié)點(diǎn)對(duì)所有的節(jié)點(diǎn)n，都有：都有：h(n) h*(n)。 2/21/202217 搜索過(guò)程還要標(biāo)記能解節(jié)點(diǎn)（搜索過(guò)程還要標(biāo)記能解節(jié)點(diǎn)（SOLVED），），為此為此給出如下定義：給出如下定義：能解節(jié)點(diǎn)（能解節(jié)點(diǎn)（SOLVED）終止節(jié)點(diǎn)是能解節(jié)點(diǎn)；終止節(jié)點(diǎn)是能解節(jié)點(diǎn)；若非終止節(jié)點(diǎn)有若非終止節(jié)點(diǎn)有“或或”子節(jié)點(diǎn)時(shí)，其子節(jié)點(diǎn)有一子節(jié)點(diǎn)時(shí)，其子節(jié)點(diǎn)有一能解，則該非終止節(jié)點(diǎn)是能解節(jié)點(diǎn)；能解，則該非終止節(jié)點(diǎn)是能解節(jié)點(diǎn)；若非終

12、止節(jié)點(diǎn)有若非終止節(jié)點(diǎn)有“與與”子節(jié)點(diǎn)時(shí)，若其子節(jié)點(diǎn)均子節(jié)點(diǎn)時(shí)，若其子節(jié)點(diǎn)均能解，則該非終止節(jié)點(diǎn)是能解節(jié)點(diǎn)能解，則該非終止節(jié)點(diǎn)是能解節(jié)點(diǎn)。2/21/2022184.2 與與/或圖的搜索算法或圖的搜索算法算法算法AO* lAO*算法解析：算法解析：l回憶： 普通圖搜索中的A算法：對(duì)當(dāng)前搜索圖的“前沿”（即在OPEN表中的節(jié)點(diǎn)）節(jié)點(diǎn)進(jìn)行評(píng)價(jià)，選取f值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。 回想一下，f是如何定義的？ f(n) = g(n) + h(n)，其中 g(n)：已經(jīng)求得的當(dāng)前搜索圖中從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)n的最優(yōu)路徑費(fèi)用。 h(n)：從n到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑費(fèi)用的估計(jì)值。結(jié)論：對(duì)節(jié)點(diǎn)n的評(píng)價(jià)，實(shí)際上是對(duì) 初始節(jié)

13、點(diǎn)-節(jié)點(diǎn)n-目標(biāo)節(jié)點(diǎn)這一條路徑的評(píng)價(jià)。2/21/202219AO*算法解析：算法解析：l 在與/或圖搜索中，由于“與”節(jié)點(diǎn)的存在，單純對(duì)一個(gè)節(jié)點(diǎn)的評(píng)價(jià)已經(jīng)不能反映解圖的全面情況。 與/或圖中的解圖相當(dāng)于普通圖中的解路徑。 從對(duì)節(jié)點(diǎn)n的評(píng)價(jià)，實(shí)際上是對(duì)初始節(jié)點(diǎn)-節(jié)點(diǎn)n-目標(biāo)節(jié)點(diǎn)這一條路徑的評(píng)價(jià)這一思路出發(fā)，可以很容易的想到，能否通過(guò)對(duì)局部解圖進(jìn)行評(píng)價(jià)，來(lái)達(dá)到類似于普通圖中A*搜索的目的。AO*算法，正是這樣的一種適用于與/或圖的搜索算法。2/21/202220AO*算法解析：算法解析：AO*算法可以劃分為兩個(gè)階段。第一階段：自頂向下的圖生成過(guò)程。（對(duì)于每一個(gè)已經(jīng)擴(kuò)展了的節(jié)點(diǎn)，算法都有一個(gè)指針，指

14、向該節(jié)點(diǎn)的后繼節(jié)點(diǎn)中費(fèi)用值小的那個(gè)連接符。） 從初始節(jié)點(diǎn)出發(fā)，先通過(guò)有指針標(biāo)記的連接符，向下搜索，一直到找到未擴(kuò)展的節(jié)點(diǎn)為止（找到目前為止費(fèi)用值最小的一個(gè)局部解圖）。然后對(duì)其中一個(gè)非終止節(jié)點(diǎn)進(jìn)行擴(kuò)展，并對(duì)其后繼節(jié)點(diǎn)賦費(fèi)用值和加能解標(biāo)記。2/21/202221AO*算法解析：算法解析：第二階段：費(fèi)用值計(jì)算過(guò)程。 完成自下向上的費(fèi)用值修正計(jì)算、指針的標(biāo)記以及節(jié)點(diǎn)的能解標(biāo)記。2/21/202222AO*算法解析：算法解析：l兩個(gè)圖 G：搜索圖 G：局部解圖（準(zhǔn)部分解圖）（可能變化的） l兩個(gè)函數(shù) h(n)：?jiǎn)l(fā)函數(shù)（靜態(tài)）對(duì)h*(n)的估計(jì) q(n)：費(fèi)用函數(shù)（動(dòng)態(tài)變化）l兩重循環(huán) 外層：從上向下擴(kuò)

15、展 內(nèi)層：從下向上修改費(fèi)用q值、標(biāo)記指針2/21/202223AO*算法解析：算法解析：l兩種標(biāo)記 SOLVED：標(biāo)記能解節(jié)點(diǎn) 表明此節(jié)點(diǎn)的解圖已找到 指針：標(biāo)記連接符，用于計(jì)算G2/21/2022241 與與/或圖搜索或圖搜索算法算法AO* Procedure AO* 1建立一個(gè)只由根節(jié)點(diǎn)構(gòu)成的搜索圖建立一個(gè)只由根節(jié)點(diǎn)構(gòu)成的搜索圖G s的費(fèi)用的費(fèi)用 q(s) := h(s), G:=G 如果如果s是目標(biāo)，標(biāo)記是目標(biāo)，標(biāo)記s為為SOLVED. 2Until s被標(biāo)記為被標(biāo)記為 SOLVED，do：2/21/202225 3begin 4 通過(guò)跟蹤從通過(guò)跟蹤從s出發(fā)的有標(biāo)記的連接符計(jì)算部分解圖出

16、發(fā)的有標(biāo)記的連接符計(jì)算部分解圖G（G的連接符將在以后的步驟中標(biāo)記）的連接符將在以后的步驟中標(biāo)記） 5在在G中選一個(gè)非終止的葉節(jié)點(diǎn)中選一個(gè)非終止的葉節(jié)點(diǎn)n. 6擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n產(chǎn)生產(chǎn)生n的所有后繼，并把它們連到圖的所有后繼，并把它們連到圖G上，上， 對(duì)于每一個(gè)不曾在對(duì)于每一個(gè)不曾在G中出現(xiàn)的后繼中出現(xiàn)的后繼nj，q(nj) :=h(nj)， 如果這些后繼中某些節(jié)點(diǎn)是終止節(jié)點(diǎn)，則用如果這些后繼中某些節(jié)點(diǎn)是終止節(jié)點(diǎn)，則用SOLVED標(biāo)標(biāo)記。記。與與/或圖搜索或圖搜索算法算法AO*2/21/202226 7S:n；建立一個(gè)只由；建立一個(gè)只由n構(gòu)成的單元素集合構(gòu)成的單元素集合S。 8Until S變空

17、，變空，do： 9begin 10從從 S中刪除節(jié)點(diǎn)中刪除節(jié)點(diǎn)m，滿足，滿足 m在在G中的后裔不中的后裔不 出現(xiàn)在出現(xiàn)在 S中中 與與/或圖搜索或圖搜索算法算法AO*2/21/20222711 按以下步驟修改按以下步驟修改m的費(fèi)用的費(fèi)用q(m)： 對(duì)于每一從對(duì)于每一從m出發(fā)的指向節(jié)點(diǎn)集合出發(fā)的指向節(jié)點(diǎn)集合n1i，nki的連接符，計(jì)算的連接符，計(jì)算qi(m)=ci+q(n1i)+q(nki)，q(m):min qi(m)。(1)將指針標(biāo)記加到實(shí)現(xiàn)此最小值的連接符上。將指針標(biāo)記加到實(shí)現(xiàn)此最小值的連接符上。(2)如果本次標(biāo)記與以前的不同，抹去先前的標(biāo)記。如果本次標(biāo)記與以前的不同，抹去先前的標(biāo)記。(3

18、)如果這個(gè)連接符指向的所有后繼節(jié)點(diǎn)都標(biāo)記了如果這個(gè)連接符指向的所有后繼節(jié)點(diǎn)都標(biāo)記了SOLVED，則把，則把m標(biāo)上標(biāo)上SOLVED與與/或圖搜索或圖搜索算法算法AO*2/21/20222812 如果如果m標(biāo)記了標(biāo)記了SOLVED 或者或者 如果如果m的修改費(fèi)用與以前的費(fèi)用不同，的修改費(fèi)用與以前的費(fèi)用不同，則把則把m的通過(guò)指針標(biāo)記的連接的所有父節(jié)點(diǎn)加的通過(guò)指針標(biāo)記的連接的所有父節(jié)點(diǎn)加到到S中中13 end14 end 與與/或圖搜索或圖搜索算法算法AO*2/21/2022292 AO*算法應(yīng)用舉例算法應(yīng)用舉例設(shè)某個(gè)問(wèn)題的狀態(tài)空間如圖所示。設(shè)某個(gè)問(wèn)題的狀態(tài)空間如圖所示。h (n0)0，h(n1)2，

19、h(n2)4，h(n3)4，h(n4)1，h(n5)1，h(n6)2，h(n7)h(n8)0（目標(biāo)節(jié)點(diǎn)）。目標(biāo)節(jié)點(diǎn)）。假設(shè)假設(shè)k-連接符的費(fèi)用值為連接符的費(fèi)用值為k。2/21/202230 圖4.3(a) 一次循環(huán)后2/21/202231圖4.3(b) 兩次循環(huán)后2/21/202232圖4.3(c) 三次循環(huán)后02/21/202233圖4.3(d) 四次循環(huán)后2/21/202234從n0開(kāi)始，沿指向連接符的指針找到的解圖即為搜索的結(jié)果。n0給出的修正費(fèi)用值q(n0)5就是解圖的費(fèi)用值。圖4.3(e) 搜索得到的解圖2/21/202235Note（1）在第6步擴(kuò)展節(jié)點(diǎn)n時(shí)，若不存在后繼節(jié)點(diǎn)（即陷

20、入死胡同），則可在第11步中對(duì)m（即n）賦一個(gè)高的q值，這個(gè)高的q值會(huì)依次傳遞到s，使得含有節(jié)點(diǎn)n的子圖具有高的q（s），從而排除了被當(dāng)作候選局部解圖的可能性。2/21/202236(2)如果一個(gè)與或 圖存在解圖，如果對(duì)于圖中所有的節(jié)點(diǎn)n都有h（n）h*（n），并且啟發(fā)函數(shù)h滿足單調(diào)限制，則AO*算法必然終止于找出最佳解圖。2/21/202237練習(xí)練習(xí)1： 假定我們有一個(gè)產(chǎn)生式系統(tǒng)，基于如下重寫(xiě)規(guī)則：R1：n0n1, n2 R5：n2n6, n7R2：n0n2, n3 R6：n3n5, n6R3：n1n2 R7：n4n2R4：n1n4 R8：n5n7（1）用與/或圖表示此產(chǎn)生式系統(tǒng)。（2）若

21、h(n0)=0, h(n1)=2, h(n2)=4,h(n3)=4, h(n4)=3,h(n5)=1,h(n6)=0,h(n7)=0, 為啟發(fā)函數(shù)，k-連接符的費(fèi)用為k，求n0到 n6, n7的最佳解圖。（要求：使用AO*算法，畫(huà)出各次循環(huán)圖，標(biāo)明各點(diǎn)費(fèi)用q(n)，畫(huà)出最后的最佳解圖，并指明最佳解圖的費(fèi)用） 2/21/202238練習(xí)練習(xí)2： 一個(gè)產(chǎn)生式系統(tǒng)使用下面一組重寫(xiě)規(guī)則，這些重寫(xiě)規(guī)則把左面的數(shù)字轉(zhuǎn)換成右邊的數(shù)字串。 63,3 43,1 64,2 32,1 42,2 21,1 使用這些規(guī)則把6轉(zhuǎn)換成由1組成的數(shù)字串。假設(shè)k-連接符的費(fèi)用是k，用數(shù)字1標(biāo)記的節(jié)點(diǎn)的h函數(shù)值是0，用數(shù)字n(n

22、1)標(biāo)記的節(jié)點(diǎn)的h函數(shù)值是n。請(qǐng)用AO*算法描述解題過(guò)程（要求：畫(huà)出各次循環(huán)圖，標(biāo)明各點(diǎn)費(fèi)用q(n)，畫(huà)出最后的最佳解圖，并指明最佳解圖的費(fèi)用）。2/21/2022394.4 博弈樹(shù)搜索博弈樹(shù)搜索博弈博弈l具有競(jìng)爭(zhēng)或?qū)剐再|(zhì)的行為稱為博弈行為。 比如日常生活中的下棋，打牌等。 在這類行為中，參加斗爭(zhēng)或競(jìng)爭(zhēng)的各方各自具有不同的目標(biāo)或利益。為了達(dá)到各自的目標(biāo)和利益，各方必須考慮對(duì)手的各種可能的行動(dòng)方案，并力圖選取對(duì)自己最為有利或最為合理的方案。l博弈論博弈論 Game Theory 博弈論就是研究博弈行為中斗爭(zhēng)各方是否存在著最合理的行為方案，以及如何找到這個(gè)合理的行為方案的數(shù)學(xué)理論和方法。 博弈論

23、亦名“對(duì)策論”、“賽局理論”，屬應(yīng)用數(shù)學(xué)的一個(gè)分支, 目前在生物學(xué)，經(jīng)濟(jì)學(xué)，國(guó)際關(guān)系，計(jì)算機(jī)科學(xué), 政治學(xué)，軍事戰(zhàn)略和其他很多學(xué)科都有廣泛的應(yīng)用。2/21/202240博弈論歷史博弈論歷史l博弈論思想古已有之，我國(guó)古代的孫子兵法就不僅是一部軍事著作，而且算是最早的一部博弈論專著。博弈論最初主要研究象棋、橋牌、賭博中的勝負(fù)問(wèn)題，人們對(duì)博弈局勢(shì)的把握只停留在經(jīng)驗(yàn)上，沒(méi)有向理論化發(fā)展。l近代對(duì)于博弈論的研究，開(kāi)始于策墨洛（Zermelo），波雷爾（Borel）及馮諾伊曼（von Neumann）。l1928年，馮諾依曼證明了博弈論的基本原理，從而宣告了博弈論的正式誕生。1944年，馮諾依曼和摩根斯坦

24、共著的劃時(shí)代巨著博弈論與經(jīng)濟(jì)行為將二人博弈推廣到n人博弈結(jié)構(gòu)并將博弈論系統(tǒng)的應(yīng)用于經(jīng)濟(jì)領(lǐng)域，從而奠定了這一學(xué)科的基礎(chǔ)和理論體系。l19501951年，約翰福布斯納什（John Forbes Nash Jr）利用不動(dòng)點(diǎn)定理證明了均衡點(diǎn)的存在，為博弈論的一般化奠定了堅(jiān)實(shí)的基礎(chǔ)。納什的開(kāi)創(chuàng)性論文n人博弈的均衡點(diǎn)（1950），非合作博弈（1951）等等，給出了納什均衡的概念和均衡存在定理。此外，塞爾頓、哈桑尼的研究也對(duì)博弈論發(fā)展起到推動(dòng)作用。今天博弈論已發(fā)展成一門較完善的學(xué)科。 2/21/202241博弈分類博弈分類-根據(jù)不同的基準(zhǔn)有不同的分類根據(jù)不同的基準(zhǔn)有不同的分類l合作博弈和非合作博弈。 它們的

25、區(qū)別在于相互發(fā)生作用的當(dāng)事人之間有沒(méi)有一個(gè)具有約束力的協(xié)議，如果有，就是合作博弈，如果沒(méi)有，就是非合作博弈。l從行為的時(shí)間序列性，分為靜態(tài)博弈和動(dòng)態(tài)博弈 靜態(tài)博弈是指在博弈中，參與人同時(shí)選擇或雖非同時(shí)選擇但后行動(dòng)者并不知道先行動(dòng)者采取了什么具體行動(dòng)； 動(dòng)態(tài)博弈是指在博弈中，參與人的行動(dòng)有先后順序，且后行動(dòng)者能夠觀察到先行動(dòng)者所選擇的行動(dòng)。 “囚徒困境”就是同時(shí)決策的，屬于靜態(tài)博弈；而棋牌類游戲等決策或行動(dòng)有先后次序的，屬于動(dòng)態(tài)博弈。l按照參與人對(duì)其他參與人的了解程度分為完全信息博弈和不完全信息博弈。 完全博弈是指在博弈過(guò)程中，每一位參與人對(duì)其他參與人的特征、策略空間及收益函數(shù)有準(zhǔn)確的信息。 如

26、果參與人對(duì)其他參與人的特征、策略空間及收益函數(shù)信息了解的不夠準(zhǔn)確、或者不是對(duì)所有參與人的特征、策略空間及收益函數(shù)都有準(zhǔn)確的準(zhǔn)確信息，在這種情況下進(jìn)行的博弈就是不完全信息博弈。2/21/202242囚徒困境囚徒困境警方逮捕甲、乙兩名嫌疑犯，但沒(méi)有足夠證據(jù)指控二人入罪。于是警方分開(kāi)囚禁嫌疑犯，分別和二人見(jiàn)面，并向雙方提供以下相同的選擇：l若一人認(rèn)罪并作證檢舉對(duì)方（稱“背叛”對(duì)方），而對(duì)方保持沉默，此人將即時(shí)獲釋，沉默者將判監(jiān)10年。l若二人都保持沉默（稱互相“合作”），則二人同樣判監(jiān)半年。l若二人都互相檢舉（互相“背叛”），則二人同樣判監(jiān)2年。假定：每個(gè)參與者（即“囚徒”）都是利己的，即都尋求最大

27、自身利益，而不關(guān)心另一參與者的利益。參與者某一策略所得利益，如果在任何情況下都比其他策略要低的話，此策略稱為“嚴(yán)格劣勢(shì)”，理性的參與者絕不會(huì)選擇。沒(méi)有任何其他力量干預(yù)個(gè)人決策，參與者可完全按照自己意愿選擇策略。2/21/202243試設(shè)想困境中兩名理性囚徒會(huì)如何作出選擇：l若對(duì)方沉默，背叛會(huì)讓我獲釋，所以會(huì)選擇背叛。l若對(duì)方背叛指控我，我也要指控對(duì)方才能得到較低的刑期，所以也是會(huì)選擇背叛。 二人面對(duì)的情況一樣，所以二人的理性思考都會(huì)得出相同的結(jié)論選擇背叛，結(jié)果二人同樣服刑2年。 這顯然不是顧及團(tuán)體利益的最優(yōu)解決方案。以全體利益而言，如果兩個(gè)參與者都合作保持沉默，兩人都只會(huì)被判刑半年，總體利益更

28、高，結(jié)果也比兩人背叛對(duì)方、判刑2年的情況較佳。但根據(jù)以上假設(shè)，二人均為理性的個(gè)人，且只追求自己個(gè)人利益。均衡狀況會(huì)是兩個(gè)囚徒都選擇背叛，結(jié)果二人判決均比合作為高，總體利益較合作為低。這就是“困境”所在。2/21/2022444.4 博弈樹(shù)搜索博弈樹(shù)搜索 對(duì)于單人博弈的一些問(wèn)題，可用一般的搜索技術(shù)進(jìn)行求解，本節(jié)著重討論雙人完備信息這一類博弈問(wèn)題的搜索策略。l雙人、具有完備信息博弈問(wèn)題的特點(diǎn)：（1）雙人對(duì)弈，對(duì)壘的雙方輪流走步。（2）信息完備，對(duì)壘雙方所得到的信息是一樣的， 不存在一方能看到，而另一方看不到的情況。（3）零和。即對(duì)一方有利的棋，對(duì)另一方肯定不利， 不存在對(duì)雙方均有利、或均無(wú)利的棋。

29、 對(duì)弈的結(jié)果是一方贏，另一方輸，或者雙方和棋。2/21/202245l零和博弈 （zero - sum game）： 是指博弈的參與者中,一方之所得是它方之所失,總量上看,支付水平不起變化或者為零。l非零和博弈是一種非合作下的博弈，博弈中各方的收益或損失的總和不是零值。在經(jīng)濟(jì)學(xué)研究中很有用。 在這種狀況時(shí)，自己的所得并不與他人的所失的大小相等，連自己的幸福也未必建立在他人的痛苦之上，即使傷害他人也可能“損人不利己”，所以博弈雙方存在“雙贏”的可能，進(jìn)而合作。 譬如，在戀愛(ài)中一方受傷的時(shí)候，對(duì)方并不是一定得到滿足。也有可能雙方一起能得到精神的滿足。也有可能雙方一起受傷。通常，彼此精神的損益不是零

30、和的。 比如目前的中美關(guān)系，就并非“非此即彼”，而是可以合作雙贏。2/21/202246無(wú)處不在的博弈無(wú)處不在的博弈 l日常生活中的一切，均可從博弈得到解釋，大到美日貿(mào)易戰(zhàn)，小到今天早上你突然生病。 l“自然”是研究單人博弈的重要假定。 農(nóng)夫種莊稼也是同自然進(jìn)行博弈的一個(gè)過(guò)程。 自然的策略可以是：天旱、多雨、風(fēng)調(diào)雨順。 農(nóng)夫?qū)?yīng)的策略分別是：防旱、防澇、放心地休息。當(dāng)然，“自然”究竟采用哪種策略并不確定，于是農(nóng)夫只有根據(jù)經(jīng)驗(yàn)判斷或氣象預(yù)報(bào)來(lái)確定自己的行動(dòng)。 如果估計(jì)今年的旱情較重，就可早做防旱準(zhǔn)備； 如果估計(jì)水情嚴(yán)重，就早做防澇準(zhǔn)備； 如果估計(jì)是風(fēng)調(diào)雨順，農(nóng)夫就可以悠哉悠哉了。 2/21/20

31、2247l雙人博弈：夫妻吵架 夫妻雙方都有兩種策略，強(qiáng)硬或軟弱。 博弈的可能結(jié)果有四種組合：夫強(qiáng)硬妻強(qiáng)硬、夫強(qiáng)硬妻軟弱、夫軟弱妻強(qiáng)硬、夫軟弱妻軟弱。商業(yè)界常見(jiàn)，如兩個(gè)空調(diào)廠家的價(jià)格戰(zhàn) 2/21/202248l智豬博弈智豬博弈（Pigspayoffs） 智豬博弈講的是：豬圈里有兩頭豬，一頭大豬，一頭小豬。豬圈的一邊有個(gè)踏板，每踩一下踏板，在遠(yuǎn)離踏板的豬圈的另一邊的投食口就會(huì)落下少量的食物。如果有一只豬去踩踏板，另一只豬就有機(jī)會(huì)搶先吃到另一邊落下的食物。當(dāng)小豬踩動(dòng)踏板時(shí)，大豬會(huì)在小豬跑到食槽之前剛好吃光所有的食物；若是大豬踩動(dòng)了踏板，則還有機(jī)會(huì)在小豬吃完落下的食物之前跑到食槽，爭(zhēng)吃到另一半殘羹。

32、2/21/202249l兩只豬各會(huì)采取什么策略？ 小豬將選擇“搭便車”策略，也就是舒舒服服地等在食槽邊；而大豬則為一點(diǎn)殘羹不知疲倦地奔忙于踏板和食槽之間。 l“小豬躺著大豬跑”的現(xiàn)象是由于故事中的游戲規(guī)則所導(dǎo)致的。規(guī)則的核心指標(biāo)是：每次落下的食物數(shù)量和踏板與投食口之間的距離。 2/21/202250l如果改變一下核心指標(biāo)，豬圈里還會(huì)出現(xiàn)同樣的“小豬躺著大豬跑”的景象嗎？試試看。 改變方案一：減量方案。投食僅原來(lái)的一半分量。 結(jié)果：是小豬大豬都不去踩踏板了。 如果目的是想讓豬們?nèi)ザ嗖忍ぐ?，這個(gè)游戲規(guī)則的設(shè)計(jì)顯然是失敗的。 2/21/202251 改變方案二：增量方案。投食為原來(lái)的一倍分量。 結(jié)果

33、：小豬、大豬都會(huì)去踩踏板。誰(shuí)想吃，誰(shuí)就會(huì)去踩踏板。反正對(duì)方不會(huì)一次把食物吃完。小豬和大豬相當(dāng)于生活在物質(zhì)相對(duì)豐富的“共產(chǎn)主義”社會(huì)，所以競(jìng)爭(zhēng)意識(shí)卻不會(huì)很強(qiáng)。 對(duì)于游戲規(guī)則的設(shè)計(jì)者來(lái)說(shuō)，這個(gè)規(guī)則的成本相當(dāng)高（每次提供雙份的食物）；而且因?yàn)楦?jìng)爭(zhēng)不強(qiáng)烈，想讓豬們?nèi)ザ嗖忍ぐ宓男Ч⒉缓谩?2/21/202252 改變方案三：減量加移位方案。投食僅原來(lái)的一半分量，但同時(shí)將投食口移到踏板附近。 結(jié)果：小豬和大豬都在拼命地?fù)屩忍ぐ?。等待者不得食，而多勞者多得。每次的收獲剛好消費(fèi)完。 對(duì)于游戲設(shè)計(jì)者，這是一個(gè)最好的方案。成本不高，但收獲最大。 2/21/202253l原版的“智豬博弈”故事給了競(jìng)爭(zhēng)中的弱者（

34、小豬）以等待為最佳策略的啟發(fā)。但是對(duì)于社會(huì)而言，因?yàn)樾∝i未能參與競(jìng)爭(zhēng)，小豬搭便車時(shí)的社會(huì)資源配置的并不是最佳狀態(tài)。為使資源最有效配置，規(guī)則的設(shè)計(jì)者是不愿看見(jiàn)有人搭便車的，政府如此，公司的老板也是如此。而能否完全杜絕“搭便車”現(xiàn)象，就要看游戲規(guī)則的核心指標(biāo)設(shè)置是否合適了。 l許多人并未讀過(guò)“智豬博弈”的故事，但是卻在自覺(jué)地使用小豬的策略。股市上等待莊家抬轎的散戶；等待產(chǎn)業(yè)市場(chǎng)中出現(xiàn)具有贏利能力新產(chǎn)品、繼而大舉仿制牟取暴利的游資；公司里不創(chuàng)造效益但分享成果的人，等等。因此，對(duì)于制訂各種經(jīng)濟(jì)管理的游戲規(guī)則的人，必須深諳“智豬博弈”指標(biāo)改變的個(gè)中道理。 2/21/2022544.4 博弈樹(shù)搜索博弈樹(shù)搜

35、索l雙人、具有完備信息博弈的實(shí)例有：一字棋、余一棋、西洋跳棋、國(guó)際象棋、中國(guó)象棋、圍棋等。l對(duì)于帶機(jī)遇性的任何博弈，因不具有完備信息，不屬這里討論范圍，但有些論述可推廣到某些機(jī)遇博弈中應(yīng)用。 2/21/202255一、一、博弈樹(shù)博弈樹(shù)l博弈問(wèn)題可以用產(chǎn)生式系統(tǒng)的形式來(lái)描述。 例如中國(guó)象棋， 狀態(tài)描述：棋盤上棋子各種位置布局 產(chǎn)生式規(guī)則：各類棋子的合法走步 目標(biāo)：將（帥）被吃掉 規(guī)則作用于初始狀態(tài)描述及其所有的后裔狀 態(tài)描述，就產(chǎn)生了博弈圖或博弈樹(shù)2/21/202256？ ？博弈問(wèn)題為什么可以用與？博弈問(wèn)題為什么可以用與/或圖表示或圖表示 可以這樣來(lái)看待這個(gè)問(wèn)題：當(dāng)輪到我方走棋時(shí)，只需從若干個(gè)可

36、以走的棋中，選擇一個(gè)棋走就可以了。從這個(gè)意義上說(shuō)，若干個(gè)可以走的棋是“或”的關(guān)系。而對(duì)于輪到對(duì)方走棋時(shí)，對(duì)于我方來(lái)說(shuō)，必須能夠應(yīng)付對(duì)手的每一種走棋。這就相當(dāng)于這些棋是“與的關(guān)系。因此，博弈問(wèn)題可以看成是一個(gè)與/或圖，但是與一般的與/或圖并不一樣，是一種特殊的與/或圖。2/21/202257Grundy博弈博弈lGrundy博弈是一個(gè)分錢幣的游戲。分錢幣問(wèn)題是一種簡(jiǎn)單的博弈問(wèn)題。l有一堆數(shù)目為N的錢幣，由兩位選手輪流進(jìn)行分堆，要求每個(gè)選手每次只把其中某一堆分成數(shù)目不等的兩小堆。例如選手甲把N分成兩堆后，輪到選手乙就可以挑其中一堆來(lái)分，如此進(jìn)行下去直到有一位選手先無(wú)法把錢幣再分成不相等的兩堆時(shí)就得

37、認(rèn)輸（直到桌子上的每堆硬幣都是一個(gè)或兩個(gè)為止，誰(shuí)先遇到這種情況誰(shuí)就算是輸了）。 以下用MIN代表對(duì)方，MAX代表我方。2/21/202258Grundy博弈狀態(tài)空間圖2/21/202259l 實(shí)現(xiàn)一種取勝的策略就是搜索一個(gè)解圖的問(wèn)題，解圖就代表一種完整的博弈策略。l 問(wèn)題：對(duì)于簡(jiǎn)單的游戲，采用與尋找 ANDOR圖解圖相類似的技術(shù)是可以解決的但是，對(duì)于復(fù)雜的游戲，這種方法是根本行不通的 中國(guó)象棋，每個(gè)勢(shì)態(tài)有40種不同的走法，如果一盤棋雙方平均走50步，則總節(jié)點(diǎn)數(shù)約為10161個(gè)。要考慮完整的搜索策略，就是用億次機(jī)來(lái)處理，花的時(shí)間也得比宇宙的年齡還長(zhǎng)。2/21/202260 對(duì)于西洋跳棋、國(guó)際象棋

38、大致也如此，博弈樹(shù)大約有1040個(gè)節(jié)點(diǎn)，象棋博弈樹(shù)大約有10120個(gè)節(jié)點(diǎn)假設(shè)每13毫微秒產(chǎn)生一個(gè)節(jié)點(diǎn)，產(chǎn)生整個(gè)跳棋的博弈樹(shù)也需要1021個(gè)世紀(jì)。 而圍棋更復(fù)雜了。 因此，對(duì)于實(shí)際的博弈問(wèn)題，無(wú)論是從空間，還是從時(shí)間上來(lái)說(shuō)，要想通過(guò)生成其所有狀態(tài)空間圖的方法來(lái)得到取勝策略，都是不可能的。2/21/202261 思考：對(duì)于一個(gè)優(yōu)秀的博弈者來(lái)說(shuō)，應(yīng)考慮的不只是對(duì)方一步的走法，而是若干步的走法。而且這一過(guò)程一般來(lái)說(shuō)是動(dòng)態(tài)進(jìn)行的，也就是說(shuō)，在考慮若干步走法以后，下了一步棋，而在對(duì)方走棋之后，還要再次考慮若干步走法，決定下一步的走法，而不是一勞永逸，搜索一次就決定了所有的走法。2/21/202262 二、

39、極小極大過(guò)程二、極小極大過(guò)程 極小極大過(guò)程模擬的就是人的一種思維過(guò)程。是考慮雙方對(duì)弈若干步之后，從可能的走步中選一步相對(duì)好棋的著法來(lái)走，即在有限的搜索深度范圍內(nèi)進(jìn)行求解。 下面的討論規(guī)定：頂節(jié)點(diǎn)深度d0，MAX代表程序方，MIN代表對(duì)手方，且MAX先走。2/21/202263l靜態(tài)估值函數(shù)e(p)：建立在該棋的各種知識(shí)和特征上。對(duì)在一定深度處的節(jié)點(diǎn)所代表的局面 進(jìn)行評(píng)價(jià)優(yōu)劣的估計(jì)值l靜態(tài)估值函數(shù)因游戲而異 如果對(duì)自己（MAX）有利，則取正值，越大，表示對(duì)我方越有利。等于正無(wú)窮大時(shí)，表示我方必勝。 如果對(duì)自己不利，則取負(fù)值越小，表示對(duì)我方越不利。等于負(fù)無(wú)窮大時(shí)，表示對(duì)方必勝。2/21/20226

40、4極小極大過(guò)程基本思想： 當(dāng)輪到我方走棋時(shí)，首先按照一定的搜索深度生成出給定深度以內(nèi)的所有狀態(tài)，計(jì)算所有葉節(jié)點(diǎn)的靜態(tài)估值函數(shù)值。然后逆向計(jì)算：對(duì)于我方要走的節(jié)點(diǎn)（MAX節(jié)點(diǎn)）取其子節(jié)點(diǎn)中的最大值為該節(jié)點(diǎn)的值（因?yàn)槲曳娇偸沁x擇對(duì)我方有利的棋）；對(duì)于對(duì)方要走的節(jié)點(diǎn)（MIN節(jié)點(diǎn)）取其子節(jié)點(diǎn)中的最小值為該節(jié)點(diǎn)的值（對(duì)方總是選擇對(duì)我方不利的棋）。一直到計(jì)算出根節(jié)點(diǎn)的值為止。獲得根節(jié)點(diǎn)取值的那一分枝，即為所選擇的最佳走步。2/21/202265l極小極大原則 MAX節(jié)點(diǎn)在其MIN子節(jié)點(diǎn)的倒推值中選max； MIN節(jié)點(diǎn)在其MAX子節(jié)點(diǎn)的倒推值中選minl倒推值 在極小極大過(guò)程中，第i層節(jié)點(diǎn)根據(jù)第i+1層節(jié)點(diǎn)

41、的值使用極小極大原則而獲得的值。l極小極大過(guò)程1.按寬度優(yōu)先生成0至L層所有節(jié)點(diǎn)。2.使用靜態(tài)估值函數(shù)計(jì)算第L層節(jié)點(diǎn)的函數(shù)值。3.按極小極大原則計(jì)算各層節(jié)點(diǎn)的倒推值，直到求出初始節(jié)點(diǎn)的倒推值為止。實(shí)現(xiàn)該倒推值的走步就是相對(duì)好的走步。2/21/202266例例2/21/202267MINIMAX過(guò)程T:（s，MAX），），OPEN:（s），），CLOSED:（ ）；）； 開(kāi)始時(shí)樹(shù)由初始節(jié)點(diǎn)構(gòu)成，開(kāi)始時(shí)樹(shù)由初始節(jié)點(diǎn)構(gòu)成，OPEN表只含有表只含有s。LOOP1:IF OPEN（ ），THEN GO LOOP2；n:FIRST（OPEN），），REMOVE（n，OPEN），）， ADD（n，CLOSE

42、D）；）；IF n可直接判定為贏、輸或平局可直接判定為贏、輸或平局 THEN e(n):0，GO LOOP1 ELSE EXPAND（n）ni，ADD（ni，T） IF d（ni）L, THEN ADD（ni，OPEN），），GO LOOP1 ELSE計(jì)算計(jì)算e(ni)，GO LOOP1；ni達(dá)到深度達(dá)到深度L，計(jì)算各端節(jié)點(diǎn)計(jì)算各端節(jié)點(diǎn)e值。值。2/21/202268LOOP2：IF CLOSEDNIL THEN GO LOOP3 ELSE np:FIRST（CLOSED）；）；IF n np pMAX，且對(duì)，且對(duì)n np p的任意子節(jié)點(diǎn)的任意子節(jié)點(diǎn)n ncici，e（n ncici）都有值）

43、都有值 THEN e（n np p）:maxe（n ncici），REMOVE（n np p，CLOSED）；）； 若若MAX所有子節(jié)點(diǎn)均有值，則該所有子節(jié)點(diǎn)均有值，則該MAX取其極大值。取其極大值。IF n np pMIN，且對(duì)，且對(duì)n np p的任意子節(jié)點(diǎn)的任意子節(jié)點(diǎn)n ncici，e（n ncici）都有值）都有值 THEN e（n np p）:mine（n ncici），REMOVE（n np p，CLOSED）；）； 若若MIN所有子節(jié)點(diǎn)均有值，則該所有子節(jié)點(diǎn)均有值，則該MIN取其極小值。取其極小值。GO LOOP2；LOOP3：IF e（s）有值有值, ,THEN EXIT（END

44、M（Move，T）；）；若若s有值，則結(jié)束或標(biāo)記走步。有值，則結(jié)束或標(biāo)記走步。2/21/202269在九宮格棋盤上，兩位選手輪流在棋盤上擺各自的棋子（每次一枚），誰(shuí)先取得三子一線的結(jié)果就取勝。設(shè)程序方MAX的棋子用（）表示 對(duì)手MIN的棋子用（）表示 MAX先走。靜態(tài)估計(jì)函數(shù)e(p)：(1)若p是MAX獲勝的格局，則e(p)；(2)若p是MIN獲勝的格局，則e(p)。(3)若p對(duì)任何一方來(lái)說(shuō)都不是獲勝的格局，則e(p)（所有空格都放上MAX的棋子之后，MAX的三子成線（行、列、對(duì)角線）的總數(shù)（所有空格都放上MIN的棋子之后，MIN的三子成線（行、列、對(duì)角線）的總數(shù)）一字棋游戲一字棋游戲2/21

45、/202270 例如，當(dāng)p的格局如上圖時(shí)，則可得e(p)642； 設(shè)考慮走兩步的搜索過(guò)程。利用棋盤對(duì)稱性的條件，則第一次調(diào)用算法產(chǎn)生的搜索樹(shù)如圖4.8所示.2/21/202271圖4.8一字棋第一階段搜索樹(shù) 2/21/202272圖4.9 一字棋第二階段搜索樹(shù) 2/21/202273圖4.10一字棋第三階段搜索樹(shù) 2/21/202274極小極大過(guò)程的問(wèn)題極小極大過(guò)程的問(wèn)題l把搜索的產(chǎn)生過(guò)程與尖端節(jié)點(diǎn)的靜態(tài)估值過(guò)程完全分開(kāi)在搜索樹(shù)完全產(chǎn)生之后，才開(kāi)始對(duì)尖端節(jié)點(diǎn)的估值這種分開(kāi)進(jìn)行的方式導(dǎo)致博弈樹(shù)搜索的低效率：節(jié)點(diǎn)數(shù)將隨著搜索深度的增加呈指數(shù)增長(zhǎng)。這極大地限制了極小極大搜索方法的使用。l解決方法：讓

46、搜索樹(shù)的產(chǎn)生過(guò)程與靜態(tài)估值與返回值的過(guò)程同時(shí)進(jìn)行，在搜索深度不變的情況下，利用已有的搜索信息減少生成的節(jié)點(diǎn)數(shù)，從而使搜索效率大為提高。 -過(guò)程 2/21/202275三、博弈搜索的三、博弈搜索的-過(guò)程過(guò)程 最早在1956年John McCarthy構(gòu)思了-搜索，但他并沒(méi)有發(fā)表。1958年Newell等人開(kāi)發(fā)的國(guó)際象棋程序NSS使用了一個(gè)簡(jiǎn)化版本的-搜索，它是第一個(gè)使用-搜索的國(guó)際象棋程序。根據(jù)Nilsson,1971所述， (Samuel,1959,1967)的西洋跳棋程序也使用了-搜索。描述-搜索的論文最早發(fā)表于20世紀(jì)60年代（Hart和Edwards,1961;Brudno,1963;S

47、lagle,1963b)。Slagle和Dixon于1969年在他們的玩Kalah游戲的程序中第一次實(shí)現(xiàn)了完整的-搜索。 -搜索也被用John McCarthy的一個(gè)學(xué)生寫(xiě)的Kotok國(guó)際象棋程序中。Knuth和Moore(1975)提供了-搜索的歷史，及其正確性證明與時(shí)間復(fù)雜性分析。1982年P(guān)earl證明了-搜索在所有固定深度的博弈樹(shù)搜索算法中是漸進(jìn)最優(yōu)的。IBM研制的“深藍(lán)”國(guó)際象棋程序采用的就是這種搜索算法，改程序戰(zhàn)勝了卡斯帕羅夫。2/21/202276某博弈問(wèn)題示意圖2/21/202277圖4.10一字棋第三階段搜索樹(shù) 2/21/202278圖 一字棋第一階段-剪枝方法 2/21/2

48、02279（1）剪枝：如果一個(gè)MIN節(jié)點(diǎn)的值小于或等于它的某一個(gè)MAX祖先節(jié)點(diǎn)的值，則剪枝發(fā)生在該MIN節(jié)點(diǎn)之下：中止這個(gè)MIN節(jié)點(diǎn)以下的搜索過(guò)程。這個(gè)MIN節(jié)點(diǎn)最終的倒推值就確定為這個(gè)值。（2）剪枝：如果一個(gè)MAX節(jié)點(diǎn)的值大于或者等于它的某一個(gè)MIN祖先節(jié)點(diǎn)的值，則剪枝發(fā)生在該MAX節(jié)點(diǎn)之下中止這個(gè)MAX節(jié)點(diǎn)以下的搜索過(guò)程。該MAX節(jié)點(diǎn)的最終返回值可以置成它的值剪枝規(guī)則2/21/202280圖4.11 -搜索過(guò)程的博弈樹(shù)2/21/202281（1）比較都是在極小節(jié)點(diǎn)和極大節(jié)點(diǎn)間進(jìn)行的，極大節(jié)點(diǎn)和極大節(jié)點(diǎn)的比較，或者極小節(jié)點(diǎn)和極小節(jié)點(diǎn)間的比較是無(wú)意義的。（2）在比較時(shí)注意是與“祖先層節(jié)點(diǎn)比較，

49、不只是與父輩節(jié)點(diǎn)比較。當(dāng)然，這里的祖先層節(jié)點(diǎn)，指的是那些已經(jīng)有了值的節(jié)點(diǎn)。（3）當(dāng)只有一個(gè)節(jié)點(diǎn)的固定以后，其值才能夠向其父節(jié)點(diǎn)傳遞。（4）-剪枝方法搜索得到的最佳走步與極小極大方法得到的結(jié)果是一致的，-剪枝并沒(méi)有因?yàn)樘岣咝?，而降低得到最佳走步的可能性。?）在實(shí)際搜索時(shí)，并不是先生成指定深度的搜索圖，再在搜索圖上進(jìn)行剪枝。如果這樣，就失去了-剪枝方法的意義。在實(shí)際程序?qū)崿F(xiàn)時(shí)，首先規(guī)定一個(gè)搜索深度，然后按照類似于深度優(yōu)先搜索的方式，生成節(jié)點(diǎn)。在節(jié)點(diǎn)的生成過(guò)程中，如果在某一個(gè)節(jié)點(diǎn)處發(fā)生了剪枝，則該節(jié)點(diǎn)其余未生成的節(jié)點(diǎn)就不再生成了。進(jìn)行-剪枝注意的問(wèn)題：2/21/202282若以最理想的情況進(jìn)行搜

50、索，即對(duì)MIN節(jié)點(diǎn)先擴(kuò)展最低估值的節(jié)點(diǎn)（若從左向右順序進(jìn)行，則設(shè)節(jié)點(diǎn)估計(jì)值從左向右遞增排序），MAX先擴(kuò)展最高估值的節(jié)點(diǎn)（設(shè)估計(jì)值從左向右遞減排序），則當(dāng)搜索樹(shù)深度為D，分枝因數(shù)為B時(shí)，若不使用-剪枝技術(shù)，搜索樹(shù)的端節(jié)點(diǎn)數(shù)BD；若使用-剪枝技術(shù)可以證明理想條件下生成的端節(jié)點(diǎn)數(shù)最少，有 ND=2BD/2-1（D為偶數(shù)） ND=B(D+1)/2+B(D-1)/2-1（D為奇數(shù)）比較后得出最佳-搜索技術(shù)所生成深度為D處的端節(jié)點(diǎn)數(shù)約等于不用-搜索技術(shù)所生成深度為D2處的端節(jié)點(diǎn)數(shù)。因此，在使用相同存儲(chǔ)空間的條件下，-過(guò)程能把搜索深度擴(kuò)大一倍-剪枝的效率剪枝的效率2/21/202283以上介紹的各種博弈搜索技術(shù)可用于求解所提到的一些雙人博弈問(wèn)題。但是這些方法還不能全面反映人們弈棋過(guò)程實(shí)際所使用的一切推理技術(shù)，也未涉及棋局的表示和啟發(fā)函數(shù)問(wèn)題。例如一些高明的棋手，對(duì)棋局的表示有獨(dú)特的模式，他們往往記住的是一個(gè)可識(shí)別的模式集合，而不是單獨(dú)棋子的具體位置。此外有些博弈過(guò)程，在一個(gè)短時(shí)期內(nèi)短兵相接，進(jìn)攻和防御的戰(zhàn)術(shù)變化劇烈，這些情況如何在搜索策略中加以考慮。還有基于極小極大過(guò)程的一些方法都設(shè)想對(duì)手總是走的最優(yōu)走步，即我方總應(yīng)考慮最壞的情況，實(shí)際上再好的選手也