【導(dǎo)讀】地摸索求解，這種問題求解過程就是搜索。估的代價計算在內(nèi)?；驍?shù)組或數(shù)據(jù)庫。路徑是解題過程中應(yīng)用的操作序列。稱為狀態(tài)空間搜索。問題空間搜索時，若子問題間互相無約束關(guān)系，棄已解決的子問題，走回頭路，尋找新的解法。數(shù)據(jù)驅(qū)動是向前搜索，目標(biāo)驅(qū)動是向后搜索。搜索，反之，稱為啟發(fā)式搜索。較優(yōu)解的方法是啟發(fā)式方法。標(biāo)拉開，則稱為有對手搜索，通常稱為博弈搜索。b)是部分展開還是全部展開？c)使用哪個規(guī)則(算子)？e)怎樣決定舍棄還是保留一棵子樹？g)如何定義啟發(fā)函數(shù)？哪一個狀態(tài)開始繼續(xù)前進(jìn)?，F(xiàn)最佳優(yōu)先搜索。的估計值的大小與初始狀態(tài)到該路徑有關(guān)。不是改進(jìn)型的)，則將此第一個狀態(tài)從SS中除去，功，算法運行結(jié)束(若該狀態(tài)形如S(path,f(path))，可歸結(jié)為已知的搜索，如令f為狀態(tài)節(jié)點的深度，定能找到解，甚至一定能找到最優(yōu)解。

　　

【正文】 ? ? ?obtain info. from pbest obtain info. from lbest 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 一、博弈樹 若參加搜索的不只有一個主體，而是對抗性的敵我雙方，則搜索的進(jìn)程不僅取決于一方，而且取決于對方應(yīng)付的策略，由此產(chǎn)生的搜索樹，稱為博弈樹。 注：博弈樹很象與或樹 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 二、博弈樹評價原則 假定對手不會犯錯誤 對手總是選擇對他最有利的步子走 自己不采取任何冒險行動 在最壞的可能中選擇最好的 注：博弈樹評價原則也稱為極小極大原則，即在極小中取極大，因此，博弈樹也稱為極小極大樹 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 三、極小極大算法 以甲為博弈樹的樹根和或節(jié)點，并把甲送入待展開節(jié)點庫 TB 若 TB為空，則對博弈樹處理如下： 1)若某個或節(jié)點的所有子與節(jié)點的值均為已知，則此或節(jié)點的值定義為所有子與結(jié)點的值中之最大者（注：贏最大、平次之、輸最?。? 2)若某個與節(jié)點的所有子或節(jié)點的值均為已知，則此與節(jié)點的值定義為所有子或結(jié)點的值中之最小者 3)反復(fù)執(zhí)行步驟 1）、 2），直至根節(jié)點被賦值，算法運行結(jié)束 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 三、極小極大算法 若 TB不為空，則從 TB任取節(jié)點 n，刪去 n，并 1)若 n已直接表現(xiàn)出甲之贏、輸或平，則對博弈樹的 n節(jié)點賦以相應(yīng)的值 (贏、輸或平 )，轉(zhuǎn) 2。 2)否則，若 n為或節(jié)點，則生成 n的所有子與節(jié)點，長在博弈樹上，也送入 TB之中，轉(zhuǎn) 2； 3)否則，若 n為與節(jié)點，則生成 n的所有子或節(jié)點，長在博弈樹上，也送入 TB之中，轉(zhuǎn) 2； 算法完 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 三、極小極大算法 注： 1)博弈的結(jié)局可能不是簡單的輸贏，而是有幾種可能的得分，但原理一樣 2)該算法并不保證一定結(jié)束，事實上，若想窮盡博弈的所有可能性，則在許多情況下不會結(jié)束 3)博弈樹中的每一分叉，必須有意義，該意義是根據(jù)具體領(lǐng)域情況而定 4)博弈樹體積可能會達(dá)到計算機根本無法處理地步，窮舉戰(zhàn)術(shù)行不通 5)對博弈樹的窮舉搜索到一定深度就不再向下走 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 三、極小極大算法 注： 6)不根據(jù)最后實際計算出的輸贏來評分，而是根據(jù)在一定深度處的節(jié)點的估計值來評分，即用估計值代替實際的搜索 7)計算這種估計值的函數(shù)，稱為靜態(tài)估值函數(shù) f，它相當(dāng)于 A*算法中的函數(shù) h 8)對于表示輸、贏、平的葉結(jié)點，其估計值可定義為： f(贏 )=+?、 f(輸 )=?、 f(平 )=0 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 三、極小極大算法 注： 9)一般情況下， f可定義為一個多項式，甚至線性函數(shù)，但若要取得較好的效果，則 f往往定義為非線性的，此時，計算復(fù)雜性就增加了。 10)除了確定靜態(tài)估值函數(shù)外，還應(yīng)盡量避免生成無用處的后代 消除冗余 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 三、博弈樹優(yōu)化 優(yōu)化方法 通過剪枝去除冗余現(xiàn)象 冗余情形 a)極大值冗余 1 2 3 4 5 6 max min min max f(4)=17 f(2)=19 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 三、博弈樹優(yōu)化 冗余情形 b)極小值冗余 1 2 3 4 5 6 min max max min f(4)=25 f(2)=10 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 三、博弈樹優(yōu)化 剪枝方法 a)?剪枝 將極大值冗余子樹剪去的方法 b)?剪枝 將極小值冗余子樹剪去的方法 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 四、帶剪枝的博弈樹搜索算法 使用靜態(tài)估值函數(shù)以及 ?剪枝和 ?剪枝，形成 帶剪枝的博弈樹搜索算法 建立一個空的棋局棧 PS[i,j], 其中，對每個 i： PS[i,1]是棋局內(nèi)容， PS[i,2]是“與”或“或” PS[i,3]是搜索深度， PS[i,4]是估計值 PS[i,5]是生成子節(jié)點數(shù) 確定正整數(shù) depth為最大推理深度 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 四、帶剪枝的博弈樹搜索算法 建立已知結(jié)果的棋局庫 PB,PB的元素與 PS的元素形式相同，并且每個元素的第一、第二和第四分量都已有確定的值； 建立根節(jié)點： PS[1,1]=初始棋局 PS[1,2]=“或” PS[1,3]=0 PS[1,4]=? PS[1,5]=0 t=1 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 四、帶剪枝的博弈樹搜索算法 若 PS[t,1]=X[1],PS[t,2]=X[2],且 X?PB,則 (1)PS[t,4]=X[4] (2)轉(zhuǎn) 10 若 PS[t,3]=depth，則 (1)PS[t,4]=f(PS[t,1]) (f是估值函數(shù) ) (2)轉(zhuǎn) 10 若 PS[t,1]不能生成新的后代，則 (1)若 PS[t,5]=0，則 PS[t,4]=f(PS[t,1]) (2)轉(zhuǎn) 10 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 四、帶剪枝的博弈樹搜索算法 生成 PS[t,1]的一個新后代： (1)PS[t,5]=PS[t,5]+1 (后代計數(shù) ) (2)t=t+1 (3)PS[t,1]=新棋局 (4)PS[t,2]=if PS[t1,2]=“或” then “與” else “或” (5)PS[t,3]=PS[t1,3]+1 (6)PS[t,4]=if PS[t,2]=“或” then ? else +? (7)PS[t,5]=0 (8)轉(zhuǎn) 6 若 t=1則算法運行結(jié)束，最后的估計值已算出 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 四、帶剪枝的博弈樹搜索算法 1 t=t1 1若 PS[t,2]=“或”，則 (1)若 PS[t+1,4]PS[t,4],則 PS[t,4]=PS[t+1,4] (取極大值 )，否則轉(zhuǎn) 8 (2)若 t=1，則轉(zhuǎn) 8 (3)若 PS[t,4]PS[t1,4],則 t=t1 (?剪枝 ) (4)轉(zhuǎn) 8 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 四、帶剪枝的博弈樹搜索算法 1若 PS[t,2]=“與”，則 (1)若 PS[t+1,4]PS[t,4],則 PS[t,4]=PS[t+1,4] (取極小值 )，否則轉(zhuǎn) 8 (2)若 t=1，則轉(zhuǎn) 8 (3)若 PS[t,4]PS[t1,4],則 t=t1 (?剪枝 ) (4)轉(zhuǎn) 8 算法完 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 四、帶剪枝的博弈樹搜索算法 注： 1)該算法是從開局先行者的立場出發(fā)的，計算所得根節(jié)點的值是對先行者前途的預(yù)測 2)該算法只給出對先行者前途的估計值，以及第一步應(yīng)該怎么走，而沒有給出全局棋每一步的走法 3)該算法的缺陷就是需說明是從某人的立場出發(fā)，若換一個立場，則要做一個對稱的改變 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 五、帶剪枝的博弈樹搜索算法的改進(jìn) 采用負(fù)極大值原理 兼顧雙方立場，消除與或節(jié)點差別，以統(tǒng)一方式處理，形式上只取極大值。若一節(jié)點的估計值代表一方的前途預(yù)測，則其負(fù)值代表另一方的前途預(yù)測。 對無后代的節(jié)點和搜索層次達(dá)到極限的節(jié)點，仍用靜態(tài)估計函數(shù)來計算它們的估計值，對于其它節(jié)點，均令父結(jié)點的估計值為各子節(jié)點的估計值的負(fù)數(shù)的極大值，即 PS[i,4]=max(PS[i+1,4]) (i+1遍及 i的所有子節(jié)點） 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 五、帶剪枝的博弈樹搜索算法的改進(jìn) B*算法 (1)盡早查出不合用的壞分枝，并把它剪掉 (改進(jìn) ??剪枝 ) (2)合理地確定搜索的深度限制 (3)每個節(jié)點設(shè)立兩個估計值：樂觀估計和悲觀估計，且兩個估計值可動態(tài)可變。 思考題 ? 如何認(rèn)識啟發(fā)式搜索的基本思想？ ? H*和 A*算法如何體現(xiàn)啟發(fā)式搜索的基本思想？ ? 如何認(rèn)識隨機搜索算法？ ? 帶剪枝的博弈樹搜索如何體現(xiàn)啟發(fā)式搜索的基本思想？