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

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

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

全部屬于MAX方節(jié)點(diǎn)都是或節(jié)點(diǎn)理由：因?yàn)閿U(kuò)展MAX方節(jié)點(diǎn)時(shí)，MAX方可選擇擴(kuò)展最有利于自己節(jié)點(diǎn)，只要可擴(kuò)展子節(jié)點(diǎn)中有一個(gè)對(duì)已經(jīng)有利，

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

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

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

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

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

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

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

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

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

S放入

OPEN表中，開始時(shí)搜索樹

T由初始節(jié)點(diǎn)

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

表中第一個(gè)節(jié)點(diǎn)

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

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

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

np

屬于MAX層，且對(duì)于它屬于MIN層子節(jié)點(diǎn)

nci

e

(

nci

)有值，則：

e

(

np

)=max{

nci

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

nci

e(nci

)有值，則：

e(np

)=min{

nci

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

e(S)

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

一字棋極大極小搜索過程

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

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

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

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

e(P)=6-4=2

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

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