人工智能三搜索策略

2023/9/221啟發(fā)式搜索啟發(fā)式知識指導(dǎo)OPEN表排序的一般圖搜索：全局排序——對OPEN表中的所有節(jié)點排序，使最有希望的節(jié)點排在表首。A算法，A*算法（掌握?。┚植颗判颉獌H對新擴展出來的子節(jié)點排序，使這些新節(jié)點中最有希望者能優(yōu)先取出考察和擴展；爬山法（了解，對深度優(yōu)先法的改進）；2023/9/222

簡單的搜索策略：

g(n)≡0,f(n)=h(n),

局部排序——只排序新擴展出來的子節(jié)點，即局部排序

簡單易行，適用于不要求最優(yōu)解答的問題求解任務(wù)。1）爬山法——實現(xiàn)啟發(fā)式搜索的最簡單方法。

類似于人爬山——只要好爬，總是選取最陡處，以求快速登頂。

求函數(shù)極大值問題——非數(shù)值解法，依賴于啟發(fā)式知識，試探性地逐步向頂峰逼近

適用于能逐步求精的問題。

爬山法特點：

只能向上，不準后退，從而簡化了搜索算法；體現(xiàn)在：*從當前狀態(tài)節(jié)點擴展出的子節(jié)點（相當于找到上爬的路徑）中，將h(n)最小的子節(jié)點（對應(yīng)于到頂峰最近的上爬路徑）作為下一次考察和擴展的節(jié)點，其余子節(jié)點全部丟棄。

不需設(shè)置OPEN和CLOSE表，因為沒有必要保存任何待擴展節(jié)點；

爬山法對于單一極值問題（登單一山峰）十分有效而又簡便,對于具有多極值的問題無能為力——會錯登上次高峰而失?。翰荒艿竭_最高峰?；厮莶呗院团郎椒?/p>

2023/9/223

2）回溯策略

可以有效地克服爬山法面臨的困難——保存了每次擴展出的子節(jié)點，并按h(n)值從小到大排列。

相當于爬山的過程中記住了途經(jīng)的岔路口——路徑搜索失敗時回溯（后退），向另一路徑方向搜索回溯策略和爬山法

2023/9/224

2）回溯策略

遞歸過程——實現(xiàn)回溯策略的有效方式

算法就取名為BACKTRACK(n),參數(shù)n為當前被擴展的節(jié)點，

初次調(diào)用時n即為初始狀態(tài)節(jié)點s；

分二個部分：*判斷當前節(jié)點n的狀態(tài)，*作搜索工作——擴展節(jié)點n，遞歸調(diào)用該算法，處理返回結(jié)果?；厮莶呗院团郎椒?/p>

2023/9/225令PATH、SNL、n、n'為局部變量：

·PATH--節(jié)點列表，指示解答路徑；

·SNL--當前節(jié)點擴展出的子節(jié)點列表；

·MOVE-FIRST(SNL)--把SNL表首的節(jié)點移出，作為下一次要加以擴展的節(jié)點；

·n、n‘--分別指示當前考察和下一次考察的節(jié)點。該遞歸過程的算法就取名為BACKTRACK(n),參數(shù)n為當前被擴展的節(jié)點，算法的初次調(diào)用式是BACKTRACK(s),s即為初始狀態(tài)節(jié)點。算法的步驟如下：（1）若n是目標狀態(tài)節(jié)點，則算法的本次調(diào)用成功結(jié)束，返回空表；（2）若n是失敗狀態(tài)，則算法的本次調(diào)用失敗結(jié)束，返回'FAIL'；（3）擴展節(jié)點n，將生成的子節(jié)點置于列表SNL，并按評價函數(shù)f(k)=h(k)的值從小到大排序（k指示子節(jié)點）；（4）若SNL為空，則算法的本次調(diào)用失敗結(jié)束，返回'FAIL'；（5）n'=MOVE-FIRST(SNL)；（6）PATH=BACKTRACK(n')；（7）若PATH='FAIL',返回到語句（4）；（8）將n'加到PATH表首，算法的本次調(diào)用成功結(jié)束，返回PATH。2023/9/226

2）回溯策略

三種失敗狀態(tài)：

不合法狀態(tài)（如傳教士和野人問題中所述的那樣）

舊狀態(tài)重現(xiàn)（如八數(shù)碼游戲中某一棋盤布局的重現(xiàn)，會導(dǎo)致搜索算法死循環(huán)），

狀態(tài)節(jié)點深度超過預(yù)定限度（例如八數(shù)碼游戲中，指示解答路徑不超過6步）。

回溯條件

失敗狀態(tài)，由算法第（2）句指示；

搜索進入“死胡同”，由該算法的第(4)句定義。回溯策略和爬山法

2023/9/227

2）回溯策略

解答路徑的生成——從相應(yīng)于目標狀態(tài)節(jié)點的空表開始，遞歸返回PATH。

影響回溯算法效率的關(guān)鍵因素——回溯次數(shù)。

回溯——搜索到失敗狀態(tài)時的一種彌補行為，

準確選擇下一步搜索考察的節(jié)點——大幅度減少甚至避免回溯。

設(shè)計好的啟發(fā)式函數(shù)h(n)是至關(guān)重要的?；厮莶呗院团郎椒?/p>

2023/9/228課堂練習(xí):提高題在應(yīng)用遞歸回溯算法解決四皇后的問題中，若按行的序號從小到大試探性放置各列的皇后，請畫出搜索圖，并指出分別從算法第2步和第4步回溯的次數(shù)。

2023/9/229定義L，為表示清晰起見,L表中只記載皇后所在列,皇后所在行可由在L表中的先后位置指示,例如L=(13)指示兩個皇后位置分別為第1行第1列和第2行第3列。

搜索圖(樹)如右圖所示:共回溯22次,其中算法第2步的回溯18次,算法第4次的回溯4次。2023/9/22103.4問題歸約和與或圖啟發(fā)式搜索問題歸約是人求解問題常用的策略：把復(fù)雜的問題變換為若干需要同時處理的較為簡單的子問題后再加以分別求解只有子問題全部解決時，問題才算解決；問題的解答由子問題的解答聯(lián)合構(gòu)成。本節(jié)主要內(nèi)容：問題歸約的描述（理解）與或圖搜索的基本過程（理解）與或圖的啟發(fā)式搜索（掌握）2023/9/2211問題歸約法

（ProblemReductionRepresentation）子問題1子問題n原始問題子問題集本原問題2023/9/2212問題歸約可以用三元組表示：（S0，O，P），其中S0是初始問題，即要求解的問題；P是本原問題集，其中的每一個問題是不用證明的，自然成立的，如公理、已知事實等，或已證明過的問題；O是操作算子集，它是一組變換規(guī)則，通過一個操作算子把一個問題化成若干個子問題。2023/9/2213問題歸約表示方法就是由初始問題出發(fā)，運用操作算子產(chǎn)生一些子問題，對子問題再運用操作算子產(chǎn)生子問題的子問題，這樣一直進行到產(chǎn)生的問題均為本原問題，則問題得解。2023/9/2214看如下符號積分問題： 初始問題——∫f(x)dx

變換規(guī)則——積分規(guī)則 本原問題——可直接求原函數(shù)和積分，如∫sin(x)dx，∫cos

(x)dx等。 所有問題歸約的最終目的是產(chǎn)生本原問題。2023/9/2215

符號積分問題

∫（sin3x+x4/(x2+1)）dx

=∫sin3xdx+∫(x4/(x2+1))dx

=∫-(1-cos2x)dcosx+∫(x2-1+1/(1+x2))dx

=(∫-dcosx+cos2xdcosx)+(∫x2dx-∫dx+∫(1/(1+x2))dx）

=-cosx+cos3x/3+x3/3-x+arctgx

2023/9/2216分子結(jié)構(gòu)識別問題

如何區(qū)分分子式相同但分子結(jié)構(gòu)不同的有機化合物成為重要而又困難的問題。著名的專家系統(tǒng)

DENDRAL能用于有效地識別分子結(jié)構(gòu)，該系統(tǒng)建立了一套重寫規(guī)則去把分子式重寫為原子數(shù)較少的分子式和原子間結(jié)合關(guān)系的混合結(jié)構(gòu)

2023/9/2217問題歸約的實質(zhì)：★從目標(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。2023/9/2218應(yīng)用問題歸約策略得到的狀態(tài)空間圖，也稱為“與或圖”邏輯“與”關(guān)系——用圓弧將幾條節(jié)點間關(guān)聯(lián)弧連接在一起表示問題分解為子問題；子問題的狀態(tài)聯(lián)合起來構(gòu)成問題狀態(tài)。子問題全部解決才會導(dǎo)致問題的解決；邏輯“或”關(guān)系：①問題可以有多種分解方式；②問題（子問題）可能激活多個狀態(tài)變遷操作；只要一種分解方式或狀態(tài)變遷操作能導(dǎo)致最終的解答成功即可；導(dǎo)致多個可能的解答。與或圖2023/9/2219用AND-OR圖把問題歸約為子問題替換集合。如，假設(shè)問題A既可通過問題C1與C2，也可通過問題C3、C4和C5，或者由單獨求解問題C6來解決，如下圖所示。圖中各節(jié)點表示要求解的問題或子問題。與或圖2023/9/2220梵塔問題問題描述：初始狀態(tài)下三個盤按A、B、C順序堆放在1號柱子上；目標狀態(tài)下三個盤以同樣次序順序堆放在3號柱子上；盤子的搬移規(guī)則：每次只能搬一個盤子；較大盤不能壓放在較小盤之上；CAB初始狀態(tài)(111)目標狀態(tài)(333)CAB132132與或圖2023/9/2221梵塔問題——狀態(tài)空間圖(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(2,2,1)132CAB(2,2,3)123ABC目標狀態(tài)(333)CAB1322023/9/2222梵塔問題——狀態(tài)空間圖(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)2023/9/2223梵塔問題(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)123456789子問題間有交互作用，問題分解注意正確的順序2023/9/2224與或圖搜索與或圖視為對一般圖(或圖)的擴展；★引入K-連接父子節(jié)點間可以存在“與”關(guān)系結(jié)果——解圖。解答路徑往往不復(fù)存在，代之以廣義的解路徑——解圖。問題歸約求解問題的過程表示為與或圖搜索2023/9/2225與或圖搜索1)與或圖搜索的基本概念1、K-連接★從父節(jié)點到K個子節(jié)點的連接，子節(jié)點間有“與”關(guān)系；以圓弧指示這些子節(jié)點間的“與”關(guān)系；一個父節(jié)點可以有多個K-連接K-連接間——”或”關(guān)系當所有的K都等于1時，與或圖蛻化為一般圖（或圖）。3個子節(jié)點2個子節(jié)點2023/9/2226與或圖搜索1)與或圖搜索的基本概念2、根、葉、終節(jié)點★根節(jié)點——無父節(jié)點的節(jié)點用于指示問題初始狀態(tài)（和一般圖一樣）葉節(jié)點——無子節(jié)點的節(jié)點終節(jié)點——能用于聯(lián)合表示目標狀態(tài)的節(jié)點終節(jié)點必定是葉節(jié)點，反之不然；目標狀態(tài)——終結(jié)點的集合。2023/9/2227一些關(guān)于與或圖的術(shù)語HMBCDEFGAN父節(jié)點與節(jié)點弧線或節(jié)點子節(jié)點終節(jié)點2023/9/2228與或圖搜索1)與或圖搜索的基本概念3、解圖的生成★解圖純粹是一種“與”圖解圖中，節(jié)點或節(jié)點組間不存在“或”關(guān)系；所有葉節(jié)點都是終節(jié)點2023/9/2229與或圖搜索1)與或圖搜索的基本概念3、解圖的生成★自根節(jié)點開始選K-連接;從該K-連接指向的每個子節(jié)點出發(fā)，再選一K-連接;如此反復(fù)進行，直到所有K-連接都指向終節(jié)點為止.2023/9/22302023/9/2231與或圖搜索1)與或圖搜索的基本概念3、解圖的生成★解圖純粹是一種“與”圖解圖中，節(jié)點或節(jié)點組間不存在“或”關(guān)系；所有葉節(jié)點都是終節(jié)點與或圖中存在“或”關(guān)系，搜索到多個解圖；2023/9/2232與或圖搜索2)解圖、解圖代價、能解節(jié)點和不能解節(jié)點的定義

(1)解圖——與或圖（記為G）任一節(jié)點（記為n）到終節(jié)點集合的解圖（記為G‘）是G的子圖。(1)若n是終節(jié)點，則G‘就由單一節(jié)點n構(gòu)成；(2)若n有一K-連接指向子節(jié)點n1，n2，…nk,且每個子節(jié)點都有到終節(jié)點集合的解圖，則G‘由該k-連接和所有這些相應(yīng)于子節(jié)點的解圖構(gòu)成;(3)否則不存在n到終節(jié)點集合的解圖。2023/9/2233與或圖搜索2)解圖、解圖代價、能解節(jié)點和不能解節(jié)點的定義

(2)解圖代價★

——以C(n)指示節(jié)點n到終節(jié)點集合解圖的代價，并令K-連接的代價就為K,則

(1)若n是終節(jié)點，則C(n)=0；(2)若n有一K-連接指向子節(jié)點n1，n2，…nk,且這些子節(jié)點每個都有到終節(jié)點集合的解圖,則

C(n)=K+C(n1)+C(n2)+…+C(nk)352023/9/2234與或圖搜索2)解圖、解圖代價、能解節(jié)點和不能解節(jié)點的定義

(3)能解節(jié)點

★(1)終節(jié)點是能解節(jié)點；(2)若節(jié)點n有一K-連接指向子節(jié)點n1，n2，…nk,且這些子節(jié)點都是能解節(jié)點，則n是能解節(jié)點；能解節(jié)點能解節(jié)點能解節(jié)點能解節(jié)點2023/9/2235與或圖搜索2)解圖、解圖代價、能解節(jié)點和不能解節(jié)點的定義

(4)不能解節(jié)點★(1)非終節(jié)點的葉節(jié)點是不能解節(jié)點；(2)若節(jié)點n的每一個K-連接都至少指向一個不能解節(jié)點，則n是不能解節(jié)點。能解節(jié)點不能解節(jié)點能解節(jié)點不能解節(jié)點不能解節(jié)點2023/9/2236與或圖的啟發(fā)式搜索與或圖中搜索的是解圖，不是解答路徑；評價函數(shù)f(n)=h(n)h(n)是對n到終節(jié)點集合解圖最小解圖代價的估計；與或圖中存在“或”關(guān)系，會有多個候選的局部解圖；選擇局部解圖中可能代價最小的用于下一步搜索。1)（局部）解圖代價——f(n0)★n0——初始狀態(tài)節(jié)點遞歸地計算出f(n0),比直接用h(n0)估算更為準確。父節(jié)點n的K-連接指向的子節(jié)點：n1，n2，…nkf(n)=K+h(n1)+h(n2)+…+h(nk)，代替h(n)2023/9/2237與或圖的啟發(fā)式搜索2)

AO*算法★符號說明：G-搜索圖；G’-被選中的待擴展局部解圖；LGS-待擴展局部解圖集；n0-根節(jié)點，即初始狀態(tài)節(jié)點；n-被選中的待擴展節(jié)點；fi(n0)-第i個待擴展局部解圖的可能代價。2023/9/2238與或圖的啟發(fā)式搜索2)AO*算法★算法劃分二個階段：1、初始化

建立只包含初始狀態(tài)節(jié)點n0的搜索圖G:={n0}；待擴展局部解圖集LGS:={}；2、搜索循環(huán)選擇和擴展LGS中的局部解圖；精化新局部解圖代價的估計；傳遞節(jié)點的能解性。2023/9/2239與或圖的啟發(fā)式搜索2、搜索循環(huán)選擇和擴展LGS中的局部解圖；④選擇LGS中fi(n0)最小的待擴展解圖G’；⑤隨機選擇G’中一個非終節(jié)點的葉節(jié)點作為n；⑥擴展n建立K-連接，子節(jié)點ni并加入G；計算子節(jié)點ni的f(ni)=h(ni)⑦若n存在j個K-連接LGS中刪除G’將j個新的局部解圖加入LGS;2023/9/2240與或圖的啟發(fā)式搜索2、搜索循環(huán)選擇和擴展LGS中的局部解圖；⑧精化新局部解圖代價的估計用公式f(n)=K+h(n1)+h(n2)+…+h(nk)取代原先的f(n);遞歸地作用到初始節(jié)點n0；⑨傳遞新局部解圖中節(jié)點的能解性標記作為終節(jié)點的子節(jié)點為能解節(jié)點；遞歸地傳遞節(jié)點的能解性到初始節(jié)點n0

。f(n)=h(n)2023/9/22412023/9/2242與或圖的啟發(fā)式搜索2)AO*算法AO*算法應(yīng)用例搜索過程中，啟發(fā)式函數(shù)h(ni)的估算如下：h(n0)=3h(n1)=2h(n2)=1h(n3)=1h(n4)=4h(n5)=2h(n6)=2h(n7)=1h(n8)=1h(n13)=3012354678910111213141516171819202023/9/2243初始化候選的待擴展局部解圖集LGS:0302023/9/2244012354循環(huán)1候選的待擴展局部解圖集LGS:32114202023/9/2245012354循環(huán)1候選的待擴展局部解圖集LGS:321142031201235432114202023/9/2246012354循環(huán)1候選的待擴展局部解圖集LGS:10211420512f(n)=K+h(n1)+h(n2)+…+h(nk)取代原先的f(n);f1(n0)=2+h(n1)+h(n2)=5f2(n0)=3+h(n3)+h(n4)+h(n5)=102023/9/2247012354循環(huán)2候選的待擴展局部解圖集LGS:102114205678211122023/9/2248012354循環(huán)2候選的待擴展局部解圖集LGS:1021142057811012215623422023/9/2249012354循環(huán)2候選的待擴展局部解圖集LGS:10411420778110123166234225252023/9/2250012354候選的待擴展局部解圖集LGS:104114207781101231662342131430循環(huán)32023/9/2251012354候選的待擴展局部解圖集LGS:104114207781101261965342131430循環(huán)33622023/9/2252012354循環(huán)4候選的待擴展局部解圖集LGS:1041142077811012619653421314301402023/9/2253012354循環(huán)5候選的待擴展局部解圖集LGS:1041142077811012619653421314301401502023/9/2254012354循環(huán)5候選的待擴展局部解圖集LGS:1051142087812012619653421314301401504712023/9/2255012354循環(huán)6候選的待擴展局部解圖集LGS:105114208781201261965342131430140150902023/9/2256012354搜索成功！候選的待擴展局部解圖集LGS:105114208781201261965342131430140150902023/9/2257與或圖的啟發(fā)式搜索4）算法應(yīng)用的若干問題1、從局部解圖G’中選擇加以擴展的節(jié)點n與或圖搜索的是解圖而非解路徑；選擇f(n)=h(n)的值最小的節(jié)點n加以擴展并不一定會加速搜索過程；應(yīng)選擇導(dǎo)致解圖代價發(fā)生較大變化的節(jié)點n優(yōu)先加以擴展；使搜索的注意力快速地聚焦到實際代價較小的候選解圖上；簡單情況下，可隨機選擇加以擴展的節(jié)點。2023/9/2258與或圖的啟發(fā)式搜索4）算法應(yīng)用的若干問題2、算法AO*與A*的比較★解圖——解答路徑，估計代價最小的局部解圖加以優(yōu)先擴展——OPEN表中f(n)最小的節(jié)點；只考慮評價函數(shù)f(n)=h(n)——同時計算分量g(n)和h(n)，應(yīng)用LGS存放待擴展局部解圖，并依據(jù)fi(n0)值排序——應(yīng)用OPEN表和CLOSE表分別存放待擴展節(jié)點和已擴展節(jié)點，并依據(jù)f(n)值排序OPEN表。2023/9/2259與或圖的啟發(fā)式搜索4）算法應(yīng)用的若干問題3、解圖代價的重復(fù)計算某些子節(jié)點可能會有多個父節(jié)點；這種子節(jié)點到終節(jié)點集合的解圖代價在計算自根節(jié)點n0出發(fā)的解圖時被重復(fù)累計。1781781415125178142216241182023/9/2260博弈

博弈提供了一個可構(gòu)造的任務(wù)領(lǐng)域，在這個領(lǐng)域中，具有明確的勝利和失??；博弈問題對人工智能研究提出了嚴峻的挑戰(zhàn)。例如，如何表示博弈問題的狀態(tài)、博弈過程和博弈知識等。這里講的博弈是二人博弈，二人零和、全信息、非偶然博弈，博弈雙方的利益是完全對立的。

2023/9/2261所謂“二人零和”，是指在博弈中只有“敵、我”二方。且雙方的利益完全對立，其贏得函數(shù)之和為零，即

φ1+φ2=0

式中，φ1為我方贏得(利益)；φ2為敵方贏得(利益)。即：博弈的雙方有三種結(jié)局：

(1)我勝：φ1>0；敵負：φ2=-φ1<0。

(2)我負：φ1=-φ2<0；敵勝：φ2>0。

(3)平局：φ1=0，φ2=0。博弈問題對人工智能研究提出了嚴峻的挑戰(zhàn)。例如，如何表示博弈問題的狀態(tài)、博弈過程和博弈知識等。2023/9/2262所謂“全信息”，是指博弈雙方都了解當前的格局及過去的歷史。所謂“非偶然"，是指博弈雙方都可根據(jù)得失大小進行分析，選取我方贏得最大，敵方贏得最小的對策，而不是偶然的隨機對策。2023/9/2263（1）對壘的雙方MAX和MIN輪流采取行動，博弈的結(jié)果只能有3種情況：MAX勝、MIN?。籑AX敗，MIN勝；和局。（2）在對壘過程中，任何一方都了解當前的格局和過去的歷史。（3）任何一方在采取行動前都要根據(jù)當前的實際情況，進行得失分析，選擇對自己最為有利而對對方最不利的對策，在不存在“碰運氣”的偶然因素，即雙方都很理智地決定自己的行動。這類博弈如一字棋、象棋、圍棋等。博弈的特點

2023/9/2264另外一種博弈是機遇性博弈，是指不可預(yù)測性的博弈，如擲硬幣游戲等。2023/9/2265例：假設(shè)有七枚錢幣，任一選手只能將已分好的一堆錢幣分成兩堆個數(shù)不等的錢幣，兩位選手輪流進行，直到每一堆都只有一個或兩個錢幣，不能再分為止，哪個選手遇到不能再分的情況，則為輸。2023/9/2266用數(shù)字序列加上一個說明表示一個狀態(tài)，其中數(shù)字表示不同堆中錢幣的個數(shù)，說明表示下一步由誰來分，如（7，MIN）表示只有一個由七枚錢幣組成的堆，由MIN走，MIN有3種可供選擇的分法，即（6，1，MAX），（5，2，MAX），（4，3，MAX），其中MAX表示另一選手，不論哪一種方法，MAX在它的基礎(chǔ)上再作符合要求的劃分。2023/9/2267下圖已將雙方可能的方案完全表示出來了，無論MIN開始時怎么走法，MAX總可以獲勝，取勝的策略用雙線箭頭表示。2023/9/2268實際的情況沒有這么簡單，任何一種棋都不可能將所有情況列盡，因此，只能模擬人“向前看幾步”，然后做出決策，決定自己走哪一步最有利。只能給出幾層走法，然后按照一定的估算方法，決定走哪一步棋。在雙人完備信息博弈過程中，雙方都希望自己能夠獲勝。因此當一方走步時，都是選擇對自己最有利，而對對方最不利的走法。2023/9/2269假設(shè)博弈雙方為MAX和MIN。在博弈的每一步，可供他們選擇的方案都有很多種。從MAX的觀點看，可供自己選擇的方案之間是“或”的關(guān)系，原因是主動權(quán)在自己手里，選擇哪個方案完全由自己決定，可供自己選擇的方案之間是“或”的關(guān)系，而對那些可供MIN選擇的方案之間是“與”的關(guān)系，這是因為主動權(quán)在MIN手中，任何一個方案都可能被MIN選中，MAX必須防止那種對自己最不利的情況出現(xiàn)。2023/9/2270下圖是把雙人博弈過程用圖的形式表示出來，這樣就可以得到一棵AND-OR樹，這種AND-OR樹稱為博弈樹。在博弈樹中，那些下一步該MAX走的節(jié)點稱為MAX節(jié)點，而下一步該MIN走的節(jié)點稱為MIN節(jié)點。2023/9/2271下圖所示是向前看兩步，共四層的博弈樹，用□表示MAX，用○表示MIN，端節(jié)點上的數(shù)字表示它對應(yīng)的估價函數(shù)的值。在MIN處用圓弧連接，用0表示其子節(jié)點取估值最小的格局。圖中節(jié)點處的數(shù)字，在端節(jié)點是估價函數(shù)的值，稱它為靜態(tài)值，在MIN處取最小值，在MAX處取最大值，最后MAX選擇箭頭方向的走步。2023/9/2272博弈樹特點：★(1)博弈的初始狀態(tài)是初始節(jié)點；(2)博弈樹的“與”節(jié)點和“或”節(jié)點是逐層交替出現(xiàn)的；(3)整個博弈過程始終站在某一方的立場上，所以能使自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點也是可解節(jié)點，所有使對方獲勝的節(jié)點都是不可解節(jié)點。2023/9/2273在人工智能中可以采用搜索方法來求解博弈問題，下面就來討論博弈中兩中最基本的搜索方法。

2023/9/2274極大極小過程★

極大極小過程是考慮雙方對弈若干步之后，從可能的走法中選一步相對好的走法來走，即在有限的搜索深度范圍內(nèi)進行求解。需要定義一個靜態(tài)估價函數(shù)f,以便對棋局的態(tài)勢做出評估。2023/9/2275這個函數(shù)可以根據(jù)棋局的態(tài)勢特征進行定義。假定對弈雙方分別為MAX和MIN，規(guī)定：有利于MAX方的態(tài)勢：f(p)取正值有利于MIN方的態(tài)勢：f(p)取負值態(tài)勢均衡的時候：f(p)取零其中p代表棋局。2023/9/2276MINMAX基本思想：(1)當輪到MIN走步的節(jié)點時（取與時），MAX應(yīng)考慮最壞的情況（即f(p)取極小值）。(2)當輪到MAX走步的節(jié)點時（取或時），MAX應(yīng)考慮最好的情況（即f(p)取極大值）。(3)評價往回倒推時，相應(yīng)于兩位棋手的對抗策略，交替使用（1）和（2）兩種方法傳遞倒推值。所以這種方法稱為極大極小過程。

2023/9/2277用一字棋說明極大極小過程，設(shè)只進行兩層，即每方只走一步。一字棋游戲規(guī)則如下：設(shè)有一個三行三列的棋盤，如圖所示，兩個棋手輪流走步，每個棋手走步時往空格上擺一個自己的棋子，誰先使自己的棋子成三子一線為贏。設(shè)MAX方的棋子用×標記，MIN方的棋子用○標記，并規(guī)定MAX方先走步。2023/9/2278

為了不致于生成太大的博弈樹，假設(shè)每次僅擴展兩層。估價函數(shù)定義如下：設(shè)棋局為P，估價函數(shù)為e(P)。(1)若格局p對任何一方都不是獲勝的，則

e(p)=(所有空格都放上MAX的棋子之后三子成一線的總數(shù))–（所有空格都放上MIN的棋子后三子成一線的總數(shù)）(2)若p是MAX獲勝，則

e(p)=+∞（3）若p是MIN獲勝，則

e(p)=-∞

2023/9/2279若p為下圖所示，且e(P)=e(+P)-e(-P)=5-4=12023/9/2280假設(shè)由MAX先走棋，且我們站在MAX立場上。下圖給出了MAX的第一著走棋生成的博弈樹。圖中節(jié)點旁的數(shù)字分別表示相應(yīng)節(jié)點的靜態(tài)估值或倒推值。由圖可以看出，對于MAX來說最好的一著棋是S3，因為S3比S1和S2有較大的估值。2023/9/2281下圖所示是向前看兩步，共四層的博弈樹，用□表示MAX，用○表示MIN，端節(jié)點上的數(shù)字表示它對應(yīng)的估價函數(shù)的值。在MIN處用圓弧連接，用0表示其子節(jié)點取估值最小的格局。圖中節(jié)點處的數(shù)字，在端節(jié)點是估價函數(shù)的值，稱它為靜態(tài)值，在MIN處取最小值，在MAX處取最大值，最后MAX選擇箭頭方向的走步。2023/9/2282α-β過程上面討論的極大極小過程先生成一棵博弈搜索樹，而且會生成規(guī)定深度內(nèi)的所有節(jié)點，然后再進行估值的倒推計算，這樣使得生成博弈樹和估計值的倒推計算兩個過程完全分離，因此搜索效率較低。如果能邊生成博弈樹，邊進行估值的計算，則可能不必生成規(guī)定深度內(nèi)的所有節(jié)點，以減少搜索的次數(shù)，這就是下面要討論的α-β過程。2023/9/2283考慮：如果邊生成博弈樹，邊進行估值的計算會帶來什么好處。2023/9/2284α-β過程就是把生成后繼和倒推值估計結(jié)合起來，及時剪掉一些無用分支，以此來提高算法的效率。下面仍然用一字棋進行說明?，F(xiàn)將原圖左邊所示的一部分重畫在中。2023/9/2285前面的過程實際上類似于寬度優(yōu)先搜索，將每層格局均生成，現(xiàn)在用深度優(yōu)先搜索來處理。比如在節(jié)點A處，若已生成5個子節(jié)點，并且A處的倒推值等于-1，我們將此下界叫做MAX節(jié)點的α值，即α≥-1。

2023/9/2286現(xiàn)在輪到節(jié)點B，產(chǎn)生它的第一后繼節(jié)點C，C的靜態(tài)值為-1，可知B處的倒推值≤-1，此為上界MIN節(jié)點的β值，即B處β≤-1，這樣B節(jié)點最終的倒推值可能小于-1，但絕不可能大于-1，因此，B節(jié)點的其他后繼節(jié)點的靜態(tài)值不必計算，自然不必再生成，反正B決不會比A好，所以通過倒推值的比較，就可以減少搜索的工作量2023/9/2287上圖表示了β值小于等于父節(jié)點的α值時的情況，實際上當某個MIN節(jié)點的β值不大于它的先輩的MAX節(jié)點（不一定是父節(jié)點）的α值時，則MIN節(jié)點就可以終止向下搜索。同樣，當某個節(jié)點的α值大于等于它的先輩MIN節(jié)點的β值時，則該MAX節(jié)點就可以終止向下搜索。2023/9/2288

再看一個例子，如下圖所示。其中最下面一層端節(jié)點旁邊的數(shù)字是假設(shè)的估值。

2023/9/2289通過上面的討論可以看出，α-β過程首先使搜索樹的某一部分達到最大深度，這時計算出某些MAX節(jié)點的α值，或者是某些MIN節(jié)點的β值。隨著搜索的繼續(xù)，不斷修改個別節(jié)點的α或β值。對任一節(jié)點，當其某一后繼節(jié)點的最終值給定時，就可以確定該節(jié)點的α或β值。2023/9/2290當該節(jié)點的其他后繼節(jié)點的最終值給定時，就可以對該節(jié)點的α或β值進行修正。注意α、β值修改有如下規(guī)律：(1)MAX節(jié)點的α值永不下降；(2)MIN節(jié)點的β值永不增加。2023/9/2291

因此可以利用上述規(guī)律進行剪枝，一般可以停止對某個節(jié)點搜索，即剪枝的規(guī)則表述如下：

(1)若任何MIN節(jié)點的β值小于或等于任何它的先輩MAX節(jié)點的α值，則可停止該MIN節(jié)點以下的搜索，然后這個MIN節(jié)點的最終倒推值即為它已得到的β值。該值與真正的極大極小值的搜索結(jié)果的倒推值可能不相同，但是對開始節(jié)點而言，倒推值是相同的，使用它選擇的走步也是相同的。(2)若任何MAX節(jié)點的α值大于或等于它的MIN先輩節(jié)點的β值，則可以停止該MAX節(jié)點以下的搜索，然后這個MAX節(jié)點處的倒推值即為它已得到的α值。2023/9/2292當滿足規(guī)則1而減少了搜索時，進行了α剪枝；而當滿足規(guī)則2而減少了搜索時，進行了β剪枝。保存α和β值，并且一旦可能就進行剪枝的整個過程通常稱為α-β過程，當初始節(jié)點的全體后繼節(jié)點的最終倒推值全部給出時，上述過程便結(jié)束。在搜索深度相同的條件下，采用這個過程所獲得的走步總跟簡單的極大極小過程的結(jié)果是相同的，區(qū)別只在于α-β過程通常只用少得多的搜索便可以找到一個理想的走步。2023/9/2293約束滿足搜索約束滿足問題（CSP）就是為一組