可分解產生式系統(tǒng)的搜索策略

1、3/17/2024,1,第四章 可分解產生式系統(tǒng)的搜索策略,學習目標：了解一般的與/或圖搜索問題，掌握與/或圖的啟發(fā)式搜索算法AO*。 了解博弈樹搜索問題，掌握博弈樹搜索中的極小極大方法和α-β剪枝搜索方法。重點：　　AO*算法，α-β剪枝算法。,3/17/2024,2,第二章可分解產生式系統(tǒng)中提到的與/或樹表示，其中加到每一個節(jié)點上AND或OR的標記是取決于該節(jié)點對其父節(jié)點的關系。如復合狀態(tài)分解后擁有一組“與”關系的后繼

2、節(jié)點；而分量狀態(tài)經可應用規(guī)則作用后，生成一組“或”關系的后繼節(jié)點。與/或樹是本章介紹的與/或圖的特例。在一般與/或圖中，一個節(jié)點可能是復合狀態(tài)的組成部分，而同時又是一個規(guī)則應用的結果，很難說明它是與后繼還是或后繼．因此，不再區(qū)別AND節(jié)點或OR節(jié)點．但在稱謂上沿用習慣，仍把這種結構稱作與/或圖。,4.1 與/或圖搜索,3/17/2024,3,,,,例. 一個與/或圖,3/17/2024,4,與/或圖搜索,定義： 與/或圖是一種超圖

3、．在超圖中父親節(jié)點和一組后繼節(jié)點用超弧連接． 超弧又叫 k-連接符． k-連接符: 一個父節(jié)點指向一組k個有與關系的后繼節(jié)點， 這樣一組弧線稱為一個k-連接符． k>1時，用一圓弧標記此連接符。Note:若所有的連接符都是1-連接符， 則得到的就是與/或圖的特例--普通有向圖。,3/17/2024,5,與/或圖搜索,與/或樹: 每一個節(jié)點最多

4、只有一個父親的與/或圖．根節(jié)點: 在AND/OR樹或AND / OR圖中沒有父節(jié)點的節(jié)點.葉節(jié)點: 在AND/OR樹或AND / OR圖中沒有后繼的節(jié)點．終止節(jié)點: 滿足終止條件的節(jié)點．,3/17/2024,6,與/或圖搜索,一個可分解的產生式系統(tǒng)定義一個隱含的與/或圖．圖的根節(jié)點表示產生式系統(tǒng)的初始狀態(tài)描述，連接符表示對一狀態(tài)描述應用產生式規(guī)則或把這一狀態(tài)描述分解成若干組成部分．可分解產生式系統(tǒng)的任務:從隱含的與/或圖出發(fā)找出

5、一個從根節(jié)點出發(fā)到終止節(jié)點集的解圖。,3/17/2024,7,例,重寫規(guī)則：n0→ n1n0→ n5，n4n1→ n2,n1→ n3n2→ n3n2→ n5，n4 n3→ n5，n6,n4→ n5n4→ n8,n5→ n7, n8n5→ n6 n6→ n7, n8,,3/17/2024,8,練習1：,假定我們有一個產生式系統(tǒng)，基于如下重寫規(guī)則：R1：n0→n1, n2 R5：n2→n6

6、, n7 R2：n0→n2, n3 R6：n3→n5, n6 R3：n1→n2 R7：n4→n2 R4：n1→n4 R8：n5→n7 請用與/或圖表示此產生式系統(tǒng)。,3/17/2024,9,練習2：,一個產生式系統(tǒng)使用下面一組重寫規(guī)則，這些重寫規(guī)則把左面的數字轉換成右邊的數字串。6→3,

7、3 4→3,16→4,2 3→2,14→2,2 2→1,1使用這些規(guī)則把6轉換成由1組成的數字串。請用與/或圖表示此產生式系統(tǒng)。,3/17/2024,10,與/或圖搜索,定義 設N是與/或圖G的終止節(jié)點集合，圖G中無回路，從節(jié)點n出發(fā)到 N的一個解圖是與/或圖G的一個子圖，用G’表示，遞歸定義如下： 1. 若n是N中的一個元素，則G’只包括節(jié)點n；,3/17/202

8、4,11,與/或圖搜索,2. 若n有一個從n出發(fā)的連接符k指向后繼節(jié)點集合｛n1，…，nk｝，而每一個ni都有從ni出發(fā)的解圖，則G’由節(jié)點n、連接符k、｛n1，…，nk｝中的每一個節(jié)點到N的解圖所構成；3. 否則，G沒有從n出發(fā)到N的解圖．,3/17/2024,12,,,,,,,,,,,,,,,,,,,,n0,n1,n3,n5,n6,n8,n7,a,n0,n4,,,,,,,,,,,,,n0,n4,n5,n7,n8,c,,3/17/2

9、024,13,與/或圖搜索,加權與/或圖：權加在連接符上。 假定所有連接符的費用均大于某一小的正數ε。使用連接符的費用可以計算解圖的費用．設從節(jié)點n到終止節(jié)點集合N的解圖的費用用 k(n, N)表示，則k(n, N)遞歸定義如下： 1. 若n是N中的元素，則k(n, N) =0；,3/17/2024,14,與/或圖搜索,2. 若有從n出發(fā)的一個連接符指向它的解圖后繼節(jié)點｛n1，…，ni｝，設此連接符的費

10、用為Ci，則: k(n, N)= Ci+ k(n1, N)+…+k(ni, N)最佳解圖：具有最低費用的解圖,3/17/2024,15,設k-連接符的費用為k，計算k(n0, N),,3/17/2024,16,與/或圖搜索,假定h*(n)是從n出發(fā)的最佳解圖的費用， h(n)是h*(n)的估計值。利用h(n)指導對AND/OR圖的啟發(fā)式搜索。,3/17/2024,17,與/或圖搜索,在A

11、ND/OR圖中，對任意連接符的單調限制是 h(n)≤c+h(n1)+…+h(nk)其中，n是任意節(jié)點，c是從n出發(fā)的連接符的費用， n1，…，nk是n的在此連接符下的后繼節(jié)點。Note: 若對于所有的終止節(jié)點，都有h(n)＝0，則單調限制還隱含著h對所有的節(jié)點n，都有：h(n) ≤h*(n)。,3/17/2024,18,,搜索過程還要標記能解節(jié)點（SOLVED），為此給出如下定義：能解節(jié)點（S

12、OLVED）①終止節(jié)點是能解節(jié)點；②若非終止節(jié)點有“或”子節(jié)點時，其子節(jié)點有一能解，則該非終止節(jié)點是能解節(jié)點；③若非終止節(jié)點有“與”子節(jié)點時，若其子節(jié)點均能解，則該非終止節(jié)點是能解節(jié)點。,3/17/2024,19,4.2 與/或圖的搜索算法……算法AO*,AO*算法解析：回憶： 普通圖搜索中的A算法：對當前搜索圖的“前沿”（即在OPEN表中的節(jié)點）節(jié)點進行評價，選取f值最小的節(jié)點進行擴展。 回想一下，f是如何定義

13、的？,,f(n) = g(n) + h(n)，其中 g(n)：已經求得的當前搜索圖中從初始節(jié)點到當前節(jié)點n的最優(yōu)路徑費用。 h(n)：從n到目標節(jié)點的最優(yōu)路徑費用的估計值。,結論：對節(jié)點n的評價，實際上是對 "初始節(jié)點--節(jié)點n--目標節(jié)點"這一條路徑的評價。,3/17/2024,20,AO*算法解析：,在與/或圖搜索中，由于“與”節(jié)點的存在，單純對一個節(jié)點的評價已經不能反映解圖的

14、全面情況。 與/或圖中的解圖相當于普通圖中的解路徑。 從"對節(jié)點n的評價，實際上是對'初始節(jié)點--節(jié)點n--目標節(jié)點'這一條路徑的評價"這一思路出發(fā)，可以很容易的想到，能否通過對局部解圖進行評價，來達到類似于普通圖中A*搜索的目的。AO*算法，正是這樣的一種適用于與/或圖的搜索算法。,3/17/2024,21,AO*算法解析：,AO*算法可以劃分為兩個階段。第一階段：自頂向下的圖生成

15、過程。（對于每一個已經擴展了的節(jié)點，算法都有一個指針，指向該節(jié)點的后繼節(jié)點中費用值小的那個連接符。） 從初始節(jié)點出發(fā)，先通過有指針標記的連接符，向下搜索，一直到找到未擴展的節(jié)點為止（找到目前為止費用值最小的一個局部解圖）。然后對其中一個非終止節(jié)點進行擴展，并對其后繼節(jié)點賦費用值和加能解標記。,3/17/2024,22,AO*算法解析：,第二階段：費用值計算過程。 完成自下向上的費用值修正計算、指針的標記以及節(jié)點的能解標記

16、。,3/17/2024,23,AO*算法解析：,兩個圖 G：搜索圖 G’：局部解圖（準部分解圖）（可能變化的） 兩個函數 h(n)：啟發(fā)函數（靜態(tài)）對h*(n)的估計 q(n)：費用函數（動態(tài)變化）兩重循環(huán) 外層：從上向下擴展 內層：從下向上修改費用q值、標記指針,3/17/2024,24,AO*算法解析：,兩種標記

17、 SOLVED：標記能解節(jié)點 —表明此節(jié)點的解圖已找到 指針：標記連接符，用于計算G’,3/17/2024,25,1 與/或圖搜索……算法AO*,Procedure AO* 1．建立一個只由根節(jié)點構成的搜索圖G． s的費用 q(s) := h(s), G’:=G． 如果s是目標，標記s為SOLVED. 2

18、．Until s被標記為 SOLVED，do：,3/17/2024,26,3．begin 4． 通過跟蹤從s出發(fā)的有標記的連接符計算部分解圖G’（G的連接符將在以后的步驟中標記） 5．在G’中選一個非終止的葉節(jié)點n. 6．擴展節(jié)點n產生n的所有后繼，并把它們連到圖G上， 對于每一個不曾在G中出現的后繼nj，q(nj) :=h(nj)， 如果這些后繼中某些節(jié)點是終止節(jié)點，則用SOLVED標記。,與/或

19、圖搜索……算法AO*,3/17/2024,27,7．S:＝{n}；建立一個只由n構成的單元素集合S。 8．Until S變空，do： 9．begin 10．從 S中刪除節(jié)點m，滿足 m在G中的后裔不 出現在 S中,與/或圖搜索……算法AO*,3/17/2024,28,11． 按以下步驟修改m的費用q(m)： 對于每一從m出發(fā)的指向節(jié)點集合{n1i，…，nki}的連接符，計算qi(m)=ci+q(n

20、1i)+…+q(nki)，q(m):＝min {qi(m)}。(1)將指針標記加到實現此最小值的連接符上。(2)如果本次標記與以前的不同，抹去先前的標記。(3)如果這個連接符指向的所有后繼節(jié)點都標記了SOLVED，則把m標上SOLVED．,與/或圖搜索……算法AO*,3/17/2024,29,12． 如果m標記了SOLVED 或者 如果m的修改費用與以前的費用不同，則把m的通過指針標記的連接的所有父節(jié)點加

21、到S中．13． end14． end,與/或圖搜索……算法AO*,3/17/2024,30,2 AO*算法應用舉例,設某個問題的狀態(tài)空間如圖所示。　　h (n0)＝0，h(n1)＝2，h(n2)＝4，h(n3)＝4，h(n4)＝1，h(n5)＝1，h(n6)＝2，h(n7)＝h(n8)＝0（目標節(jié)點）。假設k-連接符的費用值為k。,,,3/17/2024,31,,圖4.3(a) 一次循環(huán)后,,3/17/2024,3

22、2,,圖4.3(b) 兩次循環(huán)后,3/17/2024,33,,圖4.3(c) 三次循環(huán)后,0,3/17/2024,34,,圖4.3(d) 四次循環(huán)后,3/17/2024,35,從n0開始，沿指向連接符的指針找到的解圖即為搜索的結果。n0給出的修正費用值q(n0)＝5就是解圖的費用值。,,圖4.3(e) 搜索得到的解圖,3/17/2024,36,Note,（1）在第6步擴展節(jié)點n時，若不存在后繼節(jié)點（即陷入死胡同），則可在第11步

23、中對m（即n）賦一個高的q值，這個高的q值會依次傳遞到s，使得含有節(jié)點n的子圖具有高的q（s），從而排除了被當作候選局部解圖的可能性。,3/17/2024,37,,(2)如果一個與／或 圖存在解圖，如果對于圖中所有的節(jié)點n都有h（n）≤h*（n），并且啟發(fā)函數h滿足單調限制，則AO*算法必然終止于找出最佳解圖。,3/17/2024,38,練習1’：,假定我們有一個產生式系統(tǒng)，基于如下重寫規(guī)則：R1：n0→n1, n2

24、 R5：n2→n6, n7R2：n0→n2, n3 R6：n3→n5, n6R3：n1→n2 R7：n4→n2R4：n1→n4 R8：n5→n7（1）用與/或圖表示此產生式系統(tǒng)。（2）若h(n0)=0, h(n1)=2, h(n2)=4,h(n3)=4, h(n4)=3

25、,h(n5)=1,h(n6)=0,h(n7)=0, 為啟發(fā)函數，k-連接符的費用為k，求n0到{ n6, n7}的最佳解圖。（要求：使用AO*算法，畫出各次循環(huán)圖，標明各點費用q(n)，畫出最后的最佳解圖，并指明最佳解圖的費用）,3/17/2024,39,練習2’：,一個產生式系統(tǒng)使用下面一組重寫規(guī)則，這些重寫規(guī)則把左面的數字轉換成右邊的數字串。 6→3,3 4→3,1 6→4,2

26、 3→2,1 4→2,2 2→1,1 使用這些規(guī)則把6轉換成由1組成的數字串。假設k-連接符的費用是k，用數字1標記的節(jié)點的h函數值是0，用數字n(n≠1)標記的節(jié)點的h函數值是n。請用AO*算法描述解題過程（要求：畫出各次循環(huán)圖，標明各點費用q(n)，畫出最后的最佳解圖，并指明最佳解圖的費用）。,3/17/2024,40,4.4 博弈樹搜索博弈,具有競爭或對抗性質的行為稱為博弈行為。

27、 比如日常生活中的下棋，打牌等。 在這類行為中，參加斗爭或競爭的各方各自具有不同的目標或利益。為了達到各自的目標和利益，各方必須考慮對手的各種可能的行動方案，并力圖選取對自己最為有利或最為合理的方案。博弈論 Game Theory 博弈論就是研究博弈行為中斗爭各方是否存在著最合理的行為方案，以及如何找到這個合理的行為方案的數學理論和方法。 博弈論亦名“對策論”、“賽局理論”，屬應用數學的一個分支, 目

28、前在生物學，經濟學，國際關系，計算機科學, 政治學，軍事戰(zhàn)略和其他很多學科都有廣泛的應用。,3/17/2024,41,博弈論歷史,博弈論思想古已有之，我國古代的《孫子兵法》就不僅是一部軍事著作，而且算是最早的一部博弈論專著。博弈論最初主要研究象棋、橋牌、賭博中的勝負問題，人們對博弈局勢的把握只停留在經驗上，沒有向理論化發(fā)展。近代對于博弈論的研究，開始于策墨洛（Zermelo），波雷爾（Borel）及馮·諾伊曼（von Neu

29、mann）。1928年，馮·諾依曼證明了博弈論的基本原理，從而宣告了博弈論的正式誕生。1944年，馮·諾依曼和摩根斯坦共著的劃時代巨著《博弈論與經濟行為》將雙人博弈推廣到n人博弈結構并將博弈論系統(tǒng)地應用于經濟領域，從而奠定了這一學科的基礎和理論體系。1950～1951年，約翰·福布斯·納什（John Forbes Nash Jr）利用不動點定理證明了均衡點的存在，為博弈論的一般化奠定了堅實的

30、基礎。納什的開創(chuàng)性論文《n人博弈的均衡點》（1950），《非合作博弈》（1951）等等，給出了納什均衡的概念和均衡存在定理。此外，塞爾頓、哈桑尼的研究也對博弈論發(fā)展起到推動作用。今天博弈論已發(fā)展成一門較完善的學科。,3/17/2024,42,博弈分類-根據不同的基準有不同的分類,合作博弈和非合作博弈。 它們的區(qū)別在于相互發(fā)生作用的當事人之間有沒有一個具有約束力的協(xié)議，如果有，就是合作博弈，如果沒有，就是非合作博弈。從行為的

31、時間序列性，分為靜態(tài)博弈和動態(tài)博弈 靜態(tài)博弈是指在博弈中，參與人同時選擇或雖非同時選擇但后行動者并不知道先行動者采取了什么具體行動； 動態(tài)博弈是指在博弈中，參與人的行動有先后順序，且后行動者能夠觀察到先行動者所選擇的行動。 “囚徒困境”就是同時決策的，屬于靜態(tài)博弈；而棋牌類游戲等決策或行動有先后次序的，屬于動態(tài)博弈。按照參與人對其他參與人的了解程度分為完全信息博弈和不完全信息博弈。 完

32、全博弈是指在博弈過程中，每一位參與人對其他參與人的特征、策略空間及收益函數有準確的信息。 如果參與人對其他參與人的特征、策略空間及收益函數信息了解的不夠準確、或者不是對所有參與人的特征、策略空間及收益函數都有準確的信息，在這種情況下進行的博弈就是不完全信息博弈。,3/17/2024,43,囚徒困境,警方逮捕甲、乙兩名嫌疑犯，但沒有足夠證據指控二人入罪。于是警方分開囚禁嫌疑犯，分別和二人見面，并向雙方提供以下相同的選擇：

33、若一人認罪并作證檢舉對方（稱“背叛”對方），而對方保持沉默，此人將即時獲釋，沉默者將判監(jiān)10年。若二人都保持沉默（稱互相“合作”），則二人同樣判監(jiān)半年。若二人都互相檢舉（互相“背叛”），則二人同樣判監(jiān)2年。假定：每個參與者（即“囚徒”）都是利己的，即都尋求最大自身利益，而不關心另一參與者的利益。參與者某一策略所得利益，如果在任何情況下都比其他策略要低的話，此策略稱為“嚴格劣勢”，理性的參與者絕不會選擇。沒有任何其它力量干預個人

34、決策，參與者可完全按照自己意愿選擇策略。,3/17/2024,44,,試設想困境中兩名理性囚徒會如何作出選擇：若對方沉默，背叛會讓我獲釋，所以會選擇背叛。若對方背叛指控我，我也要指控對方才能得到較低的刑期，所以也是會選擇背叛。 二人面對的情況一樣，所以二人的理性思考都會得出相同的結論——選擇背叛，結果二人同樣服刑2年。 這顯然不是顧及團體利益的最優(yōu)解決方案。以全體利益而言，如果兩個參與者都合作保持沉默，兩人都只會

35、被判刑半年，總體利益更高，結果也比兩人背叛對方、判刑2年的情況較佳。但根據以上假設，二人均為理性的個人，且只追求自己個人利益。均衡狀況會是兩個囚徒都選擇背叛，結果二人判決均比合作為高，總體利益較合作為低。這就是“困境”所在。,3/17/2024,45,4.4 博弈樹搜索,對于單人博弈的一些問題，可用一般的搜索技術進行求解，本節(jié)著重討論雙人完備信息這一類博弈問題的搜索策略。雙人、具有完備信息博弈問題的特點：（1）雙人對弈，對壘的雙方輪

36、流走步。（2）信息完備，對壘雙方所得到的信息是一樣的， 不存在一方能看到，而另一方看不到的情況。（3）零和。即對一方有利的棋，對另一方肯定不利， 不存在對雙方均有利、或均無利的棋。 對弈的結果是一方贏，另一方輸，或者雙方和棋。,3/17/2024,46,,零和博弈 （zero - sum game）： 是指博弈的參與者中,一方之所得是它方之所失,總量上看,支付水平不起變化或者為

37、零。非零和博弈是一種非合作下的博弈，博弈中各方的收益或損失的總和不是零值。在經濟學研究中很有用。 在這種狀況時，自己的所得并不與他人的所失的大小相等，連自己的幸福也未必建立在他人的痛苦之上，即使傷害他人也可能“損人不利己”，所以博弈雙方存在“雙贏”的可能，進而合作。 譬如，在戀愛中一方受傷的時候，對方并不是一定得到滿足。也有可能雙方一起能得到精神的滿足。也有可能雙方一起受傷。通常，彼此精神的損益不是零和的。

38、比如目前的中美關系，就并非“非此即彼”，而是可以合作雙贏。,3/17/2024,47,無處不在的博弈,日常生活中的一切，均可從博弈得到解釋，大到美日貿易戰(zhàn)，小到今天早上你突然生病。 “自然”是研究單人博弈的重要假定。 農夫種莊稼也是同自然進行博弈的一個過程。 自然的策略可以是：天旱、多雨、風調雨順。 農夫對應的策略分別是：防旱、防澇、放心地休息。當然，“自然”究竟采用哪種策略并不確定，于是農夫只有根據經驗判斷或

39、氣象預報來確定自己的行動。 如果估計今年的旱情較重，就可早做防旱準備； 如果估計水情嚴重，就早做防澇準備； 如果估計是風調雨順，農夫就可以悠哉悠哉了。,3/17/2024,48,,雙人博弈：夫妻吵架 夫妻雙方都有兩種策略，強硬或軟弱。 博弈的可能結果有四種組合：夫強硬妻強硬、夫強硬妻軟弱、夫軟弱妻強硬、夫軟弱妻軟弱。商業(yè)界常見，如兩個空調廠家的價格戰(zhàn),3/17/2024,49,,智豬博弈（P

40、igs’payoffs） 智豬博弈講的是：豬圈里有兩頭豬，一頭大豬，一頭小豬。豬圈的一邊有個踏板，每踩一下踏板，在遠離踏板的豬圈的另一邊的投食口就會落下少量的食物。如果有一只豬去踩踏板，另一只豬就有機會搶先吃到另一邊落下的食物。當小豬踩動踏板時，大豬會在小豬跑到食槽之前剛好吃光所有的食物；若是大豬踩動了踏板，則還有機會在小豬吃完落下的食物之前跑到食槽，爭吃到另一半殘羹。,3/17/2024,50,,兩只豬各會采取什么策略？

41、 小豬將選擇“搭便車”策略，也就是舒舒服服地等在食槽邊；而大豬則為一點殘羹不知疲倦地奔忙于踏板和食槽之間。 “小豬躺著大豬跑”的現象是由于故事中的游戲規(guī)則所導致的。規(guī)則的核心指標是：每次落下的食物數量和踏板與投食口之間的距離。,3/17/2024,51,,如果改變一下核心指標，豬圈里還會出現同樣的“小豬躺著大豬跑”的景象嗎？試試看。 改變方案一：減量方案。投食僅原來的一半分量。 結果：是小豬大豬都不去踩踏板了。

42、如果目的是想讓豬們去多踩踏板，這個游戲規(guī)則的設計顯然是失敗的。,3/17/2024,52,,改變方案二：增量方案。投食為原來的2倍分量。 結果：小豬、大豬都會去踩踏板。誰想吃，誰就會去踩踏板。反正對方不會一次把食物吃完。小豬和大豬相當于生活在物質相對豐富的“共產主義”社會，所以競爭意識卻不會很強。 對于游戲規(guī)則的設計者來說，這個規(guī)則的成本相當高（每次提供雙份的食物）；而且因為競爭不強烈，想讓豬們去多踩踏板的效果并不好

43、。,3/17/2024,53,,改變方案三：減量加移位方案。投食僅原來的一半分量，但同時將投食口移到踏板附近。 結果：小豬和大豬都在拼命地搶著踩踏板。等待者不得食，而多勞者多得。每次的收獲剛好消費完。 對于游戲設計者，這是一個最好的方案。成本不高，但收獲最大。,3/17/2024,54,,原版的“智豬博弈”故事給了競爭中的弱者（小豬）以等待為最佳策略的啟發(fā)。但是對于社會而言，因為小豬未能參與競爭，小豬搭便車時的社會資源配

44、置的并不是最佳狀態(tài)。為使資源最有效配置，規(guī)則的設計者是不愿看見有人搭便車的，政府如此，公司的老板也是如此。而能否完全杜絕“搭便車”現象，就要看游戲規(guī)則的核心指標設置是否合適了。 許多人并未讀過“智豬博弈”的故事，但是卻在自覺地使用小豬的策略。股市上等待莊家抬轎的散戶；等待產業(yè)市場中出現具有贏利能力新產品、繼而大舉仿制牟取暴利的游資；公司里不創(chuàng)造效益但分享成果的人，等等。因此，對于制訂各種經濟管理的游戲規(guī)則的人，必須深諳“智豬博弈”指標

45、改變的個中道理。,3/17/2024,55,4.4 博弈樹搜索,雙人、具有完備信息博弈的實例有：一字棋、余一棋、西洋跳棋、國際象棋、中國象棋、圍棋等。對于帶機遇性的任何博弈，因不具有完備信息，不屬這里討論范圍，但有些論述可推廣到某些機遇博弈中應用。,3/17/2024,56,一、博弈樹,博弈問題可以用產生式系統(tǒng)的形式來描述。 例如中國象棋， 狀態(tài)描述：棋盤上棋子各種位置布局 產生式規(guī)則：各類棋子的合法走步

46、 目標：將（帥）被吃掉 規(guī)則作用于初始狀態(tài)描述及其所有的后裔狀 態(tài)描述，就產生了博弈圖或博弈樹．,3/17/2024,57,？ ？博弈問題為什么可以用與/或圖表示,可以這樣來看待這個問題：當輪到我方走棋時，只需從若干個可以走的棋中，選擇一個棋走就可以了。從這個意義上說，若干個可以走的棋是“或”的關系。而對于輪到對方走棋時，對于我方來說，必須能夠應付對手的每一種走棋。這就相當于這些棋是“與"的關系。因此，博弈問

47、題可以看成是一個與/或圖，但是與一般的與/或圖并不一樣，是一種特殊的與/或圖。,3/17/2024,58,Grundy博弈,Grundy博弈是一個分錢幣的游戲。分錢幣問題是一種簡單的博弈問題。有一堆數目為N的錢幣，由兩位選手輪流進行分堆，要求每個選手每次只把其中某一堆分成數目不等的兩小堆。例如選手甲把N分成兩堆后，輪到選手乙就可以挑其中一堆來分，如此進行下去直到有一位選手先無法把錢幣再分成不相等的兩堆時就得認輸（直到桌子上的每堆硬幣都

48、是一個或兩個為止，誰先遇到這種情況誰就算是輸了）。 以下用MIN代表對方，MAX代表我方。,3/17/2024,59,,,,Grundy博弈狀態(tài)空間圖,3/17/2024,60,,實現一種取勝的策略就是搜索一個解圖的問題，解圖就代表一種完整的博弈策略。問題：對于簡單的游戲，采用與尋找 AND／OR圖解圖相類似的技術是可以解決的．但是，對于復雜的游戲，這種方法是根本行不通的． 中國象棋，每個勢態(tài)有40種不同的走法，如果一

49、盤棋雙方平均走50步，則總節(jié)點數約為10161個。要考慮完整的搜索策略，就是用億次機來處理，花的時間也得比宇宙的年齡還長。,3/17/2024,61,,對于西洋跳棋、國際象棋大致也如此，博弈樹大約有1040個節(jié)點，象棋博弈樹大約有10120個節(jié)點．假設每1／3毫微秒產生一個節(jié)點，產生整個跳棋的博弈樹也需要1021個世紀。 而圍棋更復雜了。 因此，對于實際的博弈問題，無論是從空間，還是從時間上來說，要想通過生成其所有狀態(tài)

50、空間圖的方法來得到取勝策略，都是不可能的。,3/17/2024,62,,思考：對于一個優(yōu)秀的博弈者來說，應考慮的不只是對方一步的走法，而是若干步的走法。而且這一過程一般來說是動態(tài)進行的，也就是說，在考慮若干步走法以后，下了一步棋，而在對方走棋之后，還要再次考慮若干步走法，決定下一步的走法，而不是一勞永逸，搜索一次就決定了所有的走法。,3/17/2024,63,二、極小極大過程,極小極大過程模擬的就是人的一種思維過程。是考慮雙方對弈若干步

51、之后，從可能的走步中選一步相對好棋的著法來走，即在有限的搜索深度范圍內進行求解。 下面的討論規(guī)定：頂節(jié)點深度d＝0，MAX代表程序方，MIN代表對手方，且MAX先走。,3/17/2024,64,,靜態(tài)估值函數e(p)：建立在該棋的各種知識和特征上。對在一定深度處的節(jié)點所代表的局面 進行評價優(yōu)劣的估計值．靜態(tài)估值函數因游戲而異． 如果對自己（MAX）有利，則取正值，越大，表示對我方越有利。等于正無窮大時，表示我方必勝。

52、 如果對自己不利，則取負值．越小，表示對我方越不利。等于負無窮大時，表示對方必勝。,3/17/2024,65,,極小極大過程基本思想： 當輪到我方走棋時，首先按照一定的搜索深度生成出給定深度以內的所有狀態(tài)，計算所有葉節(jié)點的靜態(tài)估值函數值。然后逆向計算：對于我方要走的節(jié)點（MAX節(jié)點）取其子節(jié)點中的最大值為該節(jié)點的值（因為我方總是選擇對我方有利的棋）；對于對方要走的節(jié)點（MIN節(jié)點）取其子節(jié)點中的最小值為該節(jié)點的值（對方總是選擇

53、對我方不利的棋）。一直到計算出根節(jié)點的值為止。獲得根節(jié)點取值的那一分枝，即為所選擇的最佳走步。,3/17/2024,66,,極小極大原則 MAX節(jié)點在其MIN子節(jié)點的倒推值中選max； MIN節(jié)點在其MAX子節(jié)點的倒推值中選min倒推值 在極小極大過程中，第i層節(jié)點根據第i+1層節(jié)點的值使用極小極大原則而獲得的值。極小極大過程1.按寬度優(yōu)先生成0至L層所有節(jié)點。2.使用靜態(tài)估值函數計算第L層節(jié)點的函數值。

54、3.按極小極大原則計算各層節(jié)點的倒推值，直到求出初始節(jié)點的倒推值為止。實現該倒推值的走步就是相對好的走步。,3/17/2024,67,例,3/17/2024,68,MINIMAX過程,①T:＝（s，MAX），OPEN:＝（s），CLOSED:＝（ ）； 開始時樹由初始節(jié)點構成，OPEN表只含有s。②LOOP1:IF OPEN＝（ ），THEN GO LOOP2；③n:＝FIRST（OPEN），REMOVE（n，OP

55、EN）， ADD（n，CLOSED）；④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計算e(ni)，GO LOOP1；ni達到深度L，計算各端節(jié)點e值。,3/17/2024,69,,⑤LOOP2：IF CL

56、OSED＝NIL THEN GO LOOP3 ELSE np:＝FIRST（CLOSED）；⑥IF np∈MAX，且對np的任意子節(jié)點nci，e（nci）都有值 THEN e（np）:＝max{e（nci）}，REMOVE（np，CLOSED）； 若MAX所有子節(jié)點均有值，則該MAX取其極大值。IF np∈MIN，且對np的任意子節(jié)點nci，e（nci）都有值 THEN

57、 e（np）:＝min{e（nci）}，REMOVE（np，CLOSED）； 若MIN所有子節(jié)點均有值，則該MIN取其極小值。⑦GO LOOP2；⑧LOOP3：IF e（s）有值,THEN EXIT（END∨M（Move，T））；若s有值，則結束或標記走步。,3/17/2024,70,在九宮格棋盤上，兩位選手輪流在棋盤上擺各自的棋子（每次一枚），誰先取得三子一線的結果就取勝。設程序方MAX的棋子用（×）表示

58、 對手MIN的棋子用（○）表示 MAX先走。靜態(tài)估計函數e(p)：(1)若p是MAX獲勝的格局，則e(p)＝∞；(2)若p是MIN獲勝的格局，則e(p)＝－∞。(3)若p對任何一方來說都不是獲勝的格局，則e(p)＝（所有空格都放上MAX的棋子之后，MAX的三子成線（行、列、對角線）的總數－（所有空格都放上MIN的棋子之后，MIN的三子成線（行、列、對角線）的總數）,一字棋游戲,3/17/2024,71,,例如，當

59、p的格局如上圖時，則可得e(p)＝6－4＝2； 設考慮走兩步的搜索過程。利用棋盤對稱性的條件，則第一次調用算法產生的搜索樹如圖4.8所示.,3/17/2024,72,圖4.8一字棋第一階段搜索樹,3/17/2024,73,圖4.9 一字棋第二階段搜索樹,3/17/2024,74,圖4.10一字棋第三階段搜索樹,3/17/2024,75,極小極大過程的問題,把搜索的產生過程與尖端節(jié)點的靜態(tài)估值過程完全分開．在搜索樹完全產生之后，才開始

60、對尖端節(jié)點的估值．這種分開進行的方式導致博弈樹搜索的低效率：節(jié)點數將隨著搜索深度的增加呈指數增長。這極大地限制了極小極大搜索方法的使用。解決方法：讓搜索樹的產生過程與靜態(tài)估值與返回值的過程同時進行，在搜索深度不變的情況下，利用已有的搜索信息減少生成的節(jié)點數，從而使搜索效率大為提高。 ----α-β過程,3/17/2024,76,三、博弈搜索的α-β過程,最早在1956年John McCarthy構思了α-β搜索，但他并沒有發(fā)表。19

61、58年Newell等人開發(fā)的國際象棋程序NSS使用了一個簡化版本的α-β搜索，它是第一個使用α-β搜索的國際象棋程序。根據Nilsson,1971所述， (Samuel,1959,1967)的西洋跳棋程序也使用了α-β搜索。描述α-β搜索的論文最早發(fā)表于20世紀60年代（Hart和Edwards,1961;Brudno,1963;Slagle,1963b)。Slagle和Dixon于1969年在他們的玩Kalah游戲的程序中第一次

62、實現了完整的α-β搜索。 α-β搜索也被用于John McCarthy的一個學生寫的Kotok國際象棋程序中。Knuth和Moore(1975)提供了α-β搜索的歷史，及其正確性證明與時間復雜性分析。1982年Pearl證明了α-β搜索在所有固定深度的博弈樹搜索算法中是漸進最優(yōu)的。IBM研制的“深藍”國際象棋程序采用的就是這種搜索算法，該程序戰(zhàn)勝了卡斯帕羅夫。,3/17/2024,77,某博弈問題示意圖,3/17/2024,78

63、,圖4.10一字棋第三階段搜索樹,,,3/17/2024,79,圖 一字棋第一階段α-β剪枝方法,3/17/2024,80,（1）α剪枝：如果一個MIN節(jié)點的β值小于或等于它的某一個MAX祖先節(jié)點的α值，則剪枝發(fā)生在該MIN節(jié)點之下：終止這個MIN節(jié)點以下的搜索過程。這個MIN節(jié)點最終的倒推值就確定為這個β值。（2）β剪枝：如果一個MAX節(jié)點的α值大于或者等于它的某一個MIN祖先節(jié)點的β值，則剪枝發(fā)生在該MAX節(jié)點之下．終止這個M

64、AX節(jié)點以下的搜索過程。該MAX節(jié)點的最終返回值可以置成它的α值．,剪枝規(guī)則,3/17/2024,81,圖4.11 α-β搜索過程的博弈樹,3/17/2024,82,（1）比較都是在極小節(jié)點和極大節(jié)點間進行的，極大節(jié)點和極大節(jié)點的比較，或者極小節(jié)點和極小節(jié)點間的比較是無意義的。（2）在比較時注意是與“祖先層"節(jié)點比較，不只是與父輩節(jié)點比較。當然，這里的"祖先層"節(jié)點，指的是那些已經有了值的節(jié)點。（3）當

65、只有一個節(jié)點的"固定"以后，其值才能夠向其父節(jié)點傳遞。（4）α-β剪枝方法搜索得到的最佳走步與極小極大方法得到的結果是一致的，α-β剪枝并沒有因為提高效率，而降低得到最佳走步的可能性。（5）在實際搜索時，并不是先生成指定深度的搜索圖，再在搜索圖上進行剪枝。如果這樣，就失去了α-β剪枝方法的意義。在實際程序實現時，首先規(guī)定一個搜索深度，然后按照類似于深度優(yōu)先搜索的方式，生成節(jié)點。在節(jié)點的生成過程中，如果在某一個節(jié)點

66、處發(fā)生了剪枝，則該節(jié)點其余未生成的節(jié)點就不再生成了。,進行α-β剪枝注意的問題：,3/17/2024,83,若以最理想的情況進行搜索，即對MIN節(jié)點先擴展最低估值的節(jié)點（若從左向右順序進行，則設節(jié)點估計值從左向右遞增排序），MAX先擴展最高估值的節(jié)點（設估計值從左向右遞減排序），則當搜索樹深度為D，分枝因數為B時，若不使用α-β剪枝技術，搜索樹的端節(jié)點數BD；若使用α-β剪枝技術．可以證明理想條件下生成的端節(jié)點數最少，有 ND=2BD/

67、2-1（D為偶數） ND=B(D+1)/2+B(D-1)/2-1（D為奇數）比較后得出最佳α-β搜索技術所生成深度為D處的端節(jié)點數約等于不用α-β搜索技術所生成深度為D／2處的端節(jié)點數。因此，在使用相同存儲空間的條件下，α-β過程能把搜索深度擴大一倍．,α-β剪枝的效率,3/17/2024,84,以上介紹的各種博弈搜索技術可用于求解所提到的一些雙人博弈問題。但是這些方法還不能全面反映人們弈棋過程實

68、際所使用的一切推理技術，也未涉及棋局的表示和啟發(fā)函數問題。例如一些高明的棋手，對棋局的表示有獨特的模式，他們往往記住的是一個可識別的模式集合，而不是單獨棋子的具體位置。此外有些博弈過程，在一個短時期內短兵相接，進攻和防御的戰(zhàn)術變化劇烈，這些情況如何在搜索策略中加以考慮。還有基于極小極大過程的一些方法都設想對手總是走的最優(yōu)走步，即我方總應考慮最壞的情況，實際上再好的選手也會有失誤，如何利用失誤加強攻勢，也值得考慮。再一點就是選手的棋風問題

69、。總之要真正解決具體的博弈搜索技術，有許多更深入的問題需要作進一步的研究和探討。,3/17/2024,85,1．用可分解產生式系統(tǒng)求解問題時，求解過程可歸結為對一個隱含的與/或圖進行搜索。初始狀態(tài)對應于與或圖的根節(jié)點，規(guī)則對應于k-連接符，結束條件的數據庫對應于一組終止節(jié)點集合，搜索策略的任務就是找到從初始節(jié)點s到一組終止節(jié)點集N的一個解圖。解圖及其費用值可由遞歸定義給出。2．若s→N集存在解圖，當h（n）≤h*（n）且h（n）滿足