人工智能之與或圖搜索問題

第二章與或圖搜索問題目標目標初始節(jié)點sabc1人工智能之與或圖搜索問題第1頁2.1基本概念與或圖是一個超圖，節(jié)點間經(jīng)過連接符連接。K-連接符：…...K個2人工智能之與或圖搜索問題第2頁耗散值計算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N為終節(jié)點集

Cn為連接符耗散值…...i個nn1n2ni3人工智能之與或圖搜索問題第3頁目標目標初始節(jié)點解圖：4人工智能之與或圖搜索問題第4頁能解節(jié)點終節(jié)點是能解節(jié)點若非終節(jié)點有“或”子節(jié)點時，當且僅當其子節(jié)點最少有一能解時，該非終節(jié)點才能解。若非終節(jié)點有“與”子節(jié)點時，當且僅當其子節(jié)點均能解時，該非終節(jié)點才能解。5人工智能之與或圖搜索問題第5頁不能解節(jié)點沒有后代非終節(jié)點是不能解節(jié)點。若非終節(jié)點有“或”子節(jié)點，當且僅當全部子節(jié)點均不能解時，該非終節(jié)點才不能解。若非終節(jié)點有“與”子節(jié)點時，當最少有一個子節(jié)點不能解時，該非終節(jié)點才不能解。6人工智能之與或圖搜索問題第6頁普通圖搜索情況 f(n)=g(n)+h(n) 對n評價實際是對從s到n這條路徑評價ns7人工智能之與或圖搜索問題第7頁與或圖:對局部圖評價目標目標初始節(jié)點abc8人工智能之與或圖搜索問題第8頁兩個過程圖生成過程，即擴展節(jié)點從最優(yōu)局部途中選擇一個節(jié)點擴展計算耗散值過程對當前局部圖從新計算耗散值9人工智能之與或圖搜索問題第9頁AO*算法舉例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0設(shè)：K連接符耗散值為K目標目標初始節(jié)點n0n1n2n3n4n5n6n7n810人工智能之與或圖搜索問題第10頁目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8初始節(jié)點n0n1(2)n4(1)n5(1)紅色：4黃色：311人工智能之與或圖搜索問題第11頁初始節(jié)點n0n4(1)n5(1)紅色：4黃色：6n1n2(4)n3(4)5目標目標初始節(jié)點n0n1n2n3n4n5n6n7n812人工智能之與或圖搜索問題第12頁紅色：5黃色：6初始節(jié)點n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目標目標初始節(jié)點n0n1n2n3n4n5n6n7n813人工智能之與或圖搜索問題第13頁紅色：5黃色：621初始節(jié)點n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)目標目標初始節(jié)點n0n1n2n3n4n5n6n7n814人工智能之與或圖搜索問題第14頁博弈是一類含有競爭性智能活動雙人博弈：即兩位選手對壘，輪番依次走步，其中任何一方都完全知道對方過去已經(jīng)走過棋步和今后可能走步，其結(jié)果是一方贏(而另一方則輸)，或雙方和局2.3博弈樹搜索15人工智能之與或圖搜索問題第15頁博弈例子：一字棋跳棋中國象棋圍棋五子棋16人工智能之與或圖搜索問題第16頁2.3博弈樹搜索博弈問題雙人對弈，對壘雙方輪番走步；信息完備，對壘雙方所得到信息是一樣，不存在一方能看到，而另外一方看不到情況；零和，即對一方有利棋，對另一方必定是不利，不存在對雙方都有利或均無利棋，對弈結(jié)果是一方贏，而另一方輸，或者雙方和棋。17人工智能之與或圖搜索問題第17頁雙方智能活動，任何一方都不能單獨控制博弈過程，而是由雙方輪番實施其控制對策過程。博弈特點：18人工智能之與或圖搜索問題第18頁怎樣依據(jù)當前棋局，選擇對自己最有利一步棋？人工智能中研究博弈問題：中國象棋19人工智能之與或圖搜索問題第19頁用博弈樹來表示，它是一個特殊與或樹。節(jié)點代表博弈格局（即棋局），相當于狀態(tài)空間中狀態(tài)，反應(yīng)了博弈信息，而且與節(jié)點、或節(jié)點隔層交替出現(xiàn)。博弈問題（求解過程）表示：20人工智能之與或圖搜索問題第20頁假設(shè)博弈雙方為：MAX和MIN在博弈過程中，規(guī)則是雙方輪番走步。在博弈樹中，相當于博弈雙方輪番擴展其所屬節(jié)點。為何與節(jié)點、或節(jié)點隔層交替出現(xiàn)？21人工智能之與或圖搜索問題第21頁從MAX方角度來看：全部MIN方節(jié)點都是與節(jié)點理由：因為MIN方必定選擇最不利于MAX方方式來擴展節(jié)點，只要MIN方節(jié)點子節(jié)點（下出棋局）中有一個對MAX方不利，則該節(jié)點就對MAX方不利，故為“與節(jié)點”。MIN好招22人工智能之與或圖搜索問題第22頁從MAX方角度來看：

全部屬于MAX方節(jié)點都是或節(jié)點理由：因為擴展MAX方節(jié)點時，MAX方可選擇擴展最有利于自己節(jié)點，只要可擴展子節(jié)點中有一個對已經(jīng)有利，

則該節(jié)點就對已經(jīng)有利。MAX好招23人工智能之與或圖搜索問題第23頁總之：從MAX方來說，與節(jié)點、或節(jié)點交替出現(xiàn)；反之，從MIN方角度來看，情況恰好相反。24人工智能之與或圖搜索問題第24頁在博弈樹中，先行一方初始狀態(tài)對應(yīng)著樹根節(jié)點，而任何一方獲勝最終格局為目標狀態(tài)，對應(yīng)于樹終葉節(jié)點（可解節(jié)點或本原問題）。不過，從MAX角度出發(fā)，全部使MAX獲勝狀態(tài)格局都是本原問題，是可解節(jié)點，而使MIN獲勝狀態(tài)格局是不可解節(jié)點。25人工智能之與或圖搜索問題第25頁博弈樹特點(1)博弈初始狀態(tài)是初始節(jié)點；(2)博弈樹“與”節(jié)點和“或”節(jié)點是逐層交替出現(xiàn)；(3)整個博弈過程一直站在某一方立場上，所以能使自己一方獲勝終局都是本原問題，對應(yīng)節(jié)點也是可解節(jié)點，全部使對方獲勝節(jié)點都是不可解節(jié)點。26人工智能之與或圖搜索問題第26頁例

Grundy博弈：分配物品問題假如有一堆數(shù)目為N錢幣，由兩位選手輪番進行分配，要求每個選手每次把其中某一堆分成數(shù)目不等兩小堆，直至有一選手不能將錢幣分成不等兩堆為止，則判定這位選手為輸家。27人工智能之與或圖搜索問題第27頁用數(shù)字序列加上一個說明來表示一個狀態(tài)：(3,2,1,1,MAX)數(shù)字序列：表示不一樣堆中錢幣個數(shù)說明：表示下一步由誰來分，即取MAX或MIN28人工智能之與或圖搜索問題第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人工智能之與或圖搜索問題第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人工智能之與或圖搜索問題第30頁對于比較復(fù)雜博弈問題，只能模擬人思維“向前看幾步”，然后作出決議，選擇最有利自己一步。即只能給出幾層走法，然后按照一定估算方法，決定走一好招。31人工智能之與或圖搜索問題第31頁中國象棋一盤棋平均走50步，總狀態(tài)數(shù)約為10161次方。假設(shè)1毫微秒走一步，約需10145次方年。結(jié)論：不可能窮舉。32人工智能之與或圖搜索問題第32頁在人工智能中能夠采取搜索方法來求解博弈問題，下面就來討論博弈中兩中最基本搜索方法。

33人工智能之與或圖搜索問題第33頁對于復(fù)雜博弈問題，要要求搜索深度與時間，方便于博弈搜索能順利進行。假設(shè)由MAX來選擇走一步棋，問題是：MAX怎樣來選擇一步好棋？

極大極小過程34人工智能之與或圖搜索問題第34頁極大極小過程

極大極小過程是考慮雙方對弈若干步之后，從可能走法中選一步相對好走法來走，即在有限搜索深度范圍內(nèi)進行求解。需要定義一個靜態(tài)估價函數(shù)e,方便對棋局態(tài)勢做出評定。35人工智能之與或圖搜索問題第35頁①

對于每一格局（棋局）給出（定義或者倒推）一個靜態(tài)估價函數(shù)值。值越大對MAX越有利，反之越不利；極大極小過程基本思緒：36人工智能之與或圖搜索問題第36頁②

對于給定格局，MAX給出可能走法，然后MIN對應(yīng)地給出對應(yīng)走法，這么重復(fù)若干次，得到一組端節(jié)點（必須由MIN走后得到，等候MAX下棋局）。這一過程相當于節(jié)點擴展；注：博弈樹深度或?qū)訑?shù)一定是偶數(shù)。37人工智能之與或圖搜索問題第37頁③對于每一個端節(jié)點，計算出它們靜態(tài)估價函數(shù)，然后自下而上地逐層計算倒推值，直到MAX開始格局。在MIN下格局中取估值最小值，在MAX下格局中取估值最大值；④取估值最大格局作為MAX要走一招棋。38人工智能之與或圖搜索問題第38頁例：向前看一步兩層博弈樹

39人工智能之與或圖搜索問題第39頁定義靜態(tài)函數(shù)e(P)普通標準：40人工智能之與或圖搜索問題第40頁OPEN：存放待擴展節(jié)點，此時為隊列，即以寬度優(yōu)先策略擴展節(jié)點。CLOSED：存放已擴展節(jié)點，此時為堆棧，即后擴展節(jié)點先計算。

符號：41人工智能之與或圖搜索問題第41頁極大極小過程基本思想：(1)當輪到MIN走步節(jié)點時，MAX應(yīng)考慮最壞情況（即f(p)取極小值）；(2)當輪到MAX走步節(jié)點時，MAX應(yīng)考慮最好情況（即f(p)取極大值）；(3)評價往回倒推時，對應(yīng)于兩位棋手反抗策略，交替使用（1）和（2）兩種方法傳遞倒推值。42人工智能之與或圖搜索問題第42頁1、將初始節(jié)點

S放入

OPEN表中，開始時搜索樹

T由初始節(jié)點

S組成；2、若OPEN表為空（節(jié)點擴展結(jié)束），則轉(zhuǎn)5；3、將OPEN

表中第一個節(jié)點

n移出放入CLOSED表前端；極大極小搜索過程為：43人工智能之與或圖搜索問題第43頁4、若n可直接判定為贏、輸、或平局，則令對應(yīng)e(n)=∞，-∞或0，并轉(zhuǎn)2；不然擴展n，產(chǎn)生n后繼節(jié)點集{ni}，將{ni

}放入搜索樹T中。此時，若搜索深度d{ni}小于預(yù)先設(shè)定深度k，則將{ni}放入OPEN表末端，轉(zhuǎn)2；不然，ni到達深度k，計算e(ni)，并轉(zhuǎn)2；44人工智能之與或圖搜索問題第44頁5、若CLOSED表為空，則轉(zhuǎn)8；不然取出CLOSED表中第一個節(jié)點，記為

np；Open為空，即已經(jīng)擴展完節(jié)點步245人工智能之與或圖搜索問題第45頁6、若

np

屬于MAX層，且對于它屬于MIN層子節(jié)點

nci

e

(

nci

)有值，則：

e

(

np

)=max{

nci

}46人工智能之與或圖搜索問題第46頁（續(xù)）若np屬于MIN層，且對于它屬于MAX層子節(jié)點

nci

e(nci

)有值，則：

e(np

)=min{

nci

}47人工智能之與或圖搜索問題第47頁7、轉(zhuǎn)5；8、依據(jù)

e(S)

值，標識走步或者結(jié)束（-∞，∞或0）。48人工智能之與或圖搜索問題第48頁第一階段為1、2、3、4步，用寬度優(yōu)先算法生成要求深度k全部博弈樹，然后對其全部端節(jié)點計算e(P)；第二階段為5、6、7、8步，是自下而上逐層求節(jié)點倒推估價值，直至求出初始節(jié)點e(S)為止，再由e(S)選得相對很好走法，過程結(jié)束。算法分成兩個階段：49人工智能之與或圖搜索問題第49頁等對手走出對應(yīng)棋，再以當前格局作為初始節(jié)點，重復(fù)此過程，選擇對自己有利走法。50人工智能之與或圖搜索問題第50頁極大極小過程51人工智能之與或圖搜索問題第51頁例：

一字棋極大極小搜索過程

約定：每一方只向前看一步（擴展出二層）記MAX棋子為“×”，MIN棋子為“O”要求MAX先手52人工智能之與或圖搜索問題第52頁①

若格局P對任何一方都不能獲勝，則e(P)=（全部空格上都放上MAX棋子后，MAX三個棋子所組成行、列及對角線總數(shù)）-（全部空格上都放上MIN棋子后，MIN三個棋子所組成行、列及對角線總數(shù)）靜態(tài)預(yù)計函數(shù)e(P)定義為：53人工智能之與或圖搜索問題第53頁②

若P是MAX獲勝，則e(P)=+∞③

若P是MIN獲勝，則e(P)=－∞54人工智能之與或圖搜索問題第54頁例：計算以下棋局靜態(tài)估價函數(shù)值

e(P)=6-4=2

棋局O××O×××××××OOOO×OOOO行=2列=2對角=2行=2列=2對角=055人工智能之與或圖搜索問題第55頁利用棋盤對稱性，有些棋局是等價

O××OO××O56人工智能之與或圖搜索問題第56頁××××O×O×O×O×OO×O×O×O×O××O×O1010-1-10-10-2121-2-11MAXMINMAXMAX走步57人工智能之與或圖搜索問題第57頁第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX1100158人工智能之與或圖搜索問題第58頁第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021---122101---1111112-1159人工智能之與或圖搜索問題第59頁×OO××MAXMIN60人工智能之與或圖搜索問題第60頁MAXMIN×O××O61人工智能之與或圖搜索問題第61頁極大極小搜索過程由兩個完全分離兩個步驟組成：第一、用寬度優(yōu)先算法生成一棵博弈搜索樹第二、預(yù)計值倒推計算缺點：這種分離使得搜索效率比較低62人工智能之與或圖搜索問題第62頁極小極大過程05-333-3022-30-23541-30689-30-33-3-3-21-360316011極大極小ab注：用□表示MAX，用○表示MIN，端節(jié)點上數(shù)字表示它對應(yīng)估價函數(shù)值。極大極小63人工智能之與或圖搜索問題第63頁極大極小過程是先生成與/或樹，然后再計算各節(jié)點估值，這種生成節(jié)點和計算估值相分離搜索方式，需要生成要求深度內(nèi)全部節(jié)點，所以搜索效率較低。改進：在博弈樹生成過程中同時計算端節(jié)點預(yù)計值及倒推值，以降低搜索次數(shù)，這就是α-β過程思想，也稱為α-β剪枝法。剪枝概念:假如能邊生成節(jié)點邊對節(jié)點估值，并剪去一些沒用分枝，這種技術(shù)被稱為α-β剪枝。64人工智能之與或圖搜索問題第64頁-剪枝極大節(jié)點下界為。極小節(jié)點上界為。剪枝條件：后輩節(jié)點值≤祖先節(jié)點值時，剪枝后輩節(jié)點值≥祖先節(jié)點值時，剪枝簡記為：