人工智能第二章與或圖搜索問題

第二章與或圖搜索問題目的目的初始節(jié)點sabc12.1根本概念與或圖是一個超圖，節(jié)點間經(jīng)過銜接符銜接。K-銜接符：…...K個2耗散值的計算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N為終節(jié)點集Cn為銜接符的耗散值…...i個nn1n2ni3目的目的初始節(jié)點解圖：4能解節(jié)點終節(jié)點是能解節(jié)點假設(shè)非終節(jié)點有“或〞子節(jié)點時，當(dāng)且僅當(dāng)其子節(jié)點至少有一能解時，該非終節(jié)點才干解。假設(shè)非終節(jié)點有“與〞子節(jié)點時，當(dāng)且僅當(dāng)其子節(jié)點均能解時，該非終節(jié)點才干解。5不能解節(jié)點沒有后裔的非終節(jié)點是不能解節(jié)點。假設(shè)非終節(jié)點有“或〞子節(jié)點，當(dāng)且僅當(dāng)一切子節(jié)點均不能解時，該非終節(jié)點才不能解。假設(shè)非終節(jié)點有“與〞子節(jié)點時，當(dāng)至少有一個子節(jié)點不能解時，該非終節(jié)點才不能解。6普通圖搜索的情況 f(n)=g(n)+h(n) 對n的評價實踐是對從s到n這條途徑的評價ns7與或圖:對部分圖的評價目的目的初始節(jié)點abc8兩個過程圖生成過程，即擴(kuò)展節(jié)點從最優(yōu)的部分途中選擇一個節(jié)點擴(kuò)展計算耗散值的過程對當(dāng)前的部分圖重新計算耗散值9AO*算法舉例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0設(shè)：K銜接符的耗散值為K目的目的初始節(jié)點n0n1n2n3n4n5n6n7n810目的目的初始節(jié)點n0n1n2n3n4n5n6n7n8初始節(jié)點n0n1(2)n4(1)n5(1)紅色：4黃色：311初始節(jié)點n0n4(1)n5(1)紅色：4黃色：6n1n2(4)n3(4)5目的目的初始節(jié)點n0n1n2n3n4n5n6n7n812紅色：5黃色：6初始節(jié)點n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目的目的初始節(jié)點n0n1n2n3n4n5n6n7n813紅色：5黃色：621初始節(jié)點n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)目的目的初始節(jié)點n0n1n2n3n4n5n6n7n814博弈是一類具有競爭性的智能活動雙人博弈：即兩位選手對壘，輪番依次走步，其中任何一方都完全知道對方過去曾經(jīng)走過的棋步和今后能夠的走步，其結(jié)果是一方贏(而另一方那么輸)，或雙方和局2.3博弈樹搜索15博弈的例子：一字棋跳棋中國象棋圍棋五子棋162.3博弈樹搜索博弈問題雙人對弈，對壘的雙方輪番走步；信息完備，對壘雙方所得到的信息是一樣的，不存在一方能看到，而另外一方看不到的情況；零和，即對一方有利的棋，對另一方一定是不利的，不存在對雙方均有利或均無利的棋，對弈的結(jié)果是一方贏，而另一方輸，或者雙方和棋。17雙方的智能活動，任何一方都不能單獨控制博弈過程，而是由雙方輪番實施其控制對策的過程。博弈的特點：18如何根據(jù)當(dāng)前的棋局，選擇對本人最有利的一步棋？人工智能中研討的博弈問題：中國象棋19用博弈樹來表示，它是一種特殊的與或樹。節(jié)點代表博弈的格局〔即棋局〕，相當(dāng)于形狀空間中的形狀，反映了博弈的信息，并且與節(jié)點、或節(jié)點隔層交替出現(xiàn)。博弈問題〔求解過程〕的表示：20假設(shè)博弈雙方為：MAX和MIN在博弈過程中，規(guī)那么是雙方輪番走步。在博弈樹中，相當(dāng)于博弈雙方輪番擴(kuò)展其所屬節(jié)點。為什么與節(jié)點、或節(jié)點隔層交替出現(xiàn)？21從MAX方的角度來看：一切MIN方節(jié)點都是與節(jié)點理由：由于MIN方必定選擇最不利于MAX方的方式來擴(kuò)展節(jié)點，只需MIN方節(jié)點的子節(jié)點〔下出棋局〕中有一個對MAX方不利，那么該節(jié)點就對MAX方不利，故為“與節(jié)點〞。MIN好招22從MAX方的角度來看：一切屬于MAX方的節(jié)點都是或節(jié)點理由：由于擴(kuò)展MAX方節(jié)點時，MAX方可選擇擴(kuò)展最有利于本人的節(jié)點，只需可擴(kuò)展的子節(jié)點中有一個對已有利，那么該節(jié)點就對已有利。MAX好招23總之：從MAX方來說，與節(jié)點、或節(jié)點交替出現(xiàn)；反之，從MIN方的角度來看，情況正好相反。24在博弈樹中，先行一方的初始形狀對應(yīng)著樹的根節(jié)點，而任何一方獲勝的最終格局為目的形狀，對應(yīng)于樹的終葉節(jié)點〔可解節(jié)點或本原問題〕。但是，從MAX的角度出發(fā)，一切使MAX獲勝的形狀格局都是本原問題，是可解節(jié)點，而使MIN獲勝的形狀格局是不可解節(jié)點。25博弈樹特點(1)博弈的初始形狀是初始節(jié)點；(2)博弈樹的“與〞節(jié)點和“或〞節(jié)點是逐層交替出現(xiàn)的；(3)整個博弈過程一直站在某一方的立場上，所以能使本人一方獲勝的結(jié)局都是本原問題，相應(yīng)的節(jié)點也是可解節(jié)點，一切使對方獲勝的節(jié)點都是不可解節(jié)點。26例Grundy博弈：分配物品的問題假設(shè)有一堆數(shù)目為N的錢幣，由兩位選手輪番進(jìn)展分配，要求每個選手每次把其中某一堆分成數(shù)目不等的兩小堆，直至有一選手不能將錢幣分成不等的兩堆為止，那么斷定這位選手為輸家。27用數(shù)字序列加上一個闡明來表示一個形狀：(3,2,1,1,MAX)數(shù)字序列：表示不同堆中錢幣的個數(shù)闡明：表示下一步由誰來分，即取MAX或MIN28如今取N＝7的簡單情況，并由MIN先分注：假設(shè)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分錢幣問題〔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對于比較復(fù)雜的博弈問題，只能模擬人的思想“向前看幾步〞，然后作出決策，選擇最有利本人的一步。即只能給出幾層走法，然后按照一定的估算方法，決議走一好招。31中國象棋一盤棋平均走50步，總形狀數(shù)約為10的161次方。假設(shè)1毫微秒走一步，約需10的145次方年。結(jié)論：不能夠窮舉。32在人工智能中可以采用搜索方法來求解博弈問題，下面就來討論博弈中兩中最根本的搜索方法。

33對于復(fù)雜的博弈問題，要規(guī)定搜索深度與時間，以便于博弈搜索能順利進(jìn)展。假設(shè)由MAX來選擇走一步棋，問題是：MAX如何來選擇一步好棋？極大極小過程34極大極小過程極大極小過程是思索雙方對弈假設(shè)干步之后，從能夠的走法中選一步相對好的走法來走，即在有限的搜索深度范圍內(nèi)進(jìn)展求解。需求定義一個靜態(tài)估價函數(shù)e,以便對棋局的態(tài)勢做出評價。35①對于每一格局〔棋局〕給出〔定義或者倒推〕一個靜態(tài)估價函數(shù)值。值越大對MAX越有利，反之越不利；極大極小過程的根本思緒：36②對于給定的格局，MAX給出能夠的走法，然后MIN對應(yīng)地給出相應(yīng)的走法，這樣反復(fù)假設(shè)干次，得到一組端節(jié)點〔必需由MIN走后得到的，等待MAX下的棋局〕。這一過程相當(dāng)于節(jié)點擴(kuò)展；注：博弈樹深度或?qū)訑?shù)一定是偶數(shù)。37③對于每一個端節(jié)點，計算出它們的靜態(tài)估價函數(shù)，然后自下而上地逐層計算倒推值，直到MAX開場的格局。在MIN下的格局中取估值的最小值，在MAX下格局中取估值的最大值；④取估值最大的格局作為MAX要走的一招棋。38例：向前看一步的兩層博弈樹39定義靜態(tài)函數(shù)e(P)的普通原那么：40OPEN：存放待擴(kuò)展的節(jié)點，此時為隊列，即以寬度優(yōu)先的戰(zhàn)略擴(kuò)展節(jié)點。CLOSED：存放已擴(kuò)展的節(jié)點，此時為堆棧，即后擴(kuò)展的節(jié)點先計算。符號：41極大極小過程的根本思想：(1)當(dāng)輪到MIN走步的節(jié)點時，MAX應(yīng)思索最壞的情況〔即f(p)取極小值〕；(2)當(dāng)輪到MAX走步的節(jié)點時，MAX應(yīng)思索最好的情況〔即f(p)取極大值〕；(3)評價往回倒推時，相應(yīng)于兩位棋手的對抗戰(zhàn)略，交替運用〔1〕和〔2〕兩種方法傳送倒推值。421、將初始節(jié)點S放入OPEN表中，開場時搜索樹T由初始節(jié)點S構(gòu)成；2、假設(shè)OPEN表為空〔節(jié)點擴(kuò)展終了〕，那么轉(zhuǎn)5；3、將OPEN表中第一個節(jié)點n移出放入CLOSED表的前端；極大極小搜索過程為：434、假設(shè)n可直接斷定為贏、輸、或平局，那么令對應(yīng)的e(n)=∞，-∞或0，并轉(zhuǎn)2；否那么擴(kuò)展n，產(chǎn)生n的后繼節(jié)點集{ni}，將{ni}放入搜索樹T中。此時，假設(shè)搜索深度d{ni}小于預(yù)先設(shè)定的深度k，那么將{ni}放入OPEN表的末端，轉(zhuǎn)2；否那么，ni到達(dá)深度k，計算e(ni)，并轉(zhuǎn)2；445、假設(shè)CLOSED表為空，那么轉(zhuǎn)8；否那么取出CLOSED表中的第一個節(jié)點，記為np；Open為空，即曾經(jīng)擴(kuò)展完節(jié)點步2456、假設(shè)np屬于MAX層，且對于它的屬于MIN層的子節(jié)點nci的e(nci)有值，那么：e(np)=max{nci}46〔續(xù)〕假設(shè)np屬于MIN層，且對于它的屬于MAX層的子節(jié)點nci的e(nci)有值，那么：e(np)=min{nci}477、轉(zhuǎn)5；8、根據(jù)e(S)的值，標(biāo)志走步或者終了〔-∞，∞或0〕。48第一階段為1、2、3、4步，用寬度優(yōu)先算法生成規(guī)定深度k的全部博弈樹，然后對其一切端節(jié)點計算e(P)；第二階段為5、6、7、8步，是自下而上逐級求節(jié)點的倒推估價值，直至求出初始節(jié)點的e(S)為止，再由e(S)選得相對較好的走法，過程終了。算法分成兩個階段：49等對手走出相應(yīng)的棋，再以當(dāng)前的格局作為初始節(jié)點，反復(fù)此過程，選擇對本人有利的走法。50極大極小過程51例：一字棋的極大極小搜索過程商定：每一方只向前看一步〔擴(kuò)展出二層〕記MAX的棋子為“×〞，MIN的棋子為“O〞規(guī)定MAX先手52①假設(shè)格局P對任何一方都不能獲勝，那么e(P)=〔一切空格上都放上MAX的棋子后，MAX的三個棋子所組成的行、列及對角線的總數(shù)〕-〔一切空格上都放上MIN的棋子后，MIN的三個棋子所組成的行、列及對角線的總數(shù)〕靜態(tài)估計函數(shù)e(P)定義為：53②假設(shè)P是MAX獲勝，那么e(P)=+∞③假設(shè)P是MIN獲勝，那么e(P)=－∞54例：計算以下棋局的靜態(tài)估價函數(shù)值e(P)=6-4=2棋局O××O×××××××OOOO×OOOO行=2列=2對角=2行=2列=2對角=055利用棋盤的對稱性，有些棋局是等價的O××OO××O56××××O×O×O×O×OO×O×O×O×O××O×O1010-1-10-10-2121-2-11MAXMINMAXMAX的走步57第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX1100158第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021---122101---1111112-1159×OO××MAXMIN60MAXMIN×O××O61極大極小搜索過程由兩個完全分別的兩個步驟組成：第一、用寬度優(yōu)先算法生成一棵博弈搜索樹第二、估計值的倒推計算缺陷：這種分別使得搜索的效率比較低62極小極大過程05-333-3022-30-23541-30689-30-33-3-3-21-360316011極大極小ab注：用□表示MAX，用○表示MIN，端節(jié)點上的數(shù)字表示它對應(yīng)的估價函數(shù)的值。極大極小63極大極小過程是先生成與/或樹，然后再計算各節(jié)點的估值，這種生成節(jié)點和計算估值相分別的搜索方式，需求生成規(guī)定深度內(nèi)的一切節(jié)點，因此搜索效率較低。改良：在博弈樹生成過程中同時計算端節(jié)點的估計值及倒推值，以減少搜索的次數(shù)，這就是α-β過程的思想，也稱為α-β剪枝法。剪枝的概念:假設(shè)能邊生成節(jié)點邊對節(jié)點估值，并剪去一些沒用的分枝，這種技術(shù)被稱為α-β剪枝。64-剪枝極大節(jié)點的下界為。極小節(jié)點的上界為。剪枝的條件：后輩節(jié)點的值≤祖先節(jié)點的值時，剪枝后輩節(jié)點的值≥祖先節(jié)點的值時，剪枝簡記為：極小≤極大，剪枝極大≥極小，剪枝65一個α-β剪枝的詳細(xì)例子，如以下圖所示。其中最下面一層端節(jié)點旁邊的數(shù)字是假設(shè)的估值。在該圖中，L、M、N的估值推出節(jié)點F