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

1、目標目標目標目標初始節(jié)點初始節(jié)點sabc1.K個個2.i個個nn1n2ni3目標目標目標目標初始節(jié)點初始節(jié)點 解圖：解圖：456ns7目標目標目標目標初始節(jié)點初始節(jié)點abc89其中：其中： h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0設：設：K連接符連接符的耗散值為的耗散值為K目標目標目標目標初始節(jié)點初始節(jié)點n0n1n2n3n4n5n6n7n810目標目標目標目標初始節(jié)點初始節(jié)點n0n1n2n3n4n5n6n7n8初始節(jié)點初始節(jié)點n0n1(2)n4(1)n5(1)紅色：紅色：4黃色：黃色：311初

2、始節(jié)點初始節(jié)點n0n4(1)n5(1)紅色：紅色：4黃色：黃色：6n1n2(4)n3(4)5目標目標目標目標初始節(jié)點初始節(jié)點n0n1n2n3n4n5n6n7n812紅色：紅色：5黃色：黃色：6初始節(jié)點初始節(jié)點n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目標目標目標目標初始節(jié)點初始節(jié)點n0n1n2n3n4n5n6n7n813紅色：紅色：5黃色：黃色：621初始節(jié)點初始節(jié)點n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)目標目標目標目標初始節(jié)點初始節(jié)點n0n1n2n3n4n5n6n7n814博弈博弈 是一類具有競爭性的智能活動是

3、一類具有競爭性的智能活動雙人博弈雙人博弈：即兩位選手對壘，輪流依次走步，：即兩位選手對壘，輪流依次走步，其中任何一方都完全知道對方過去已經(jīng)走過的其中任何一方都完全知道對方過去已經(jīng)走過的棋步和今后可能的走步，其結果是一方贏棋步和今后可能的走步，其結果是一方贏(而另而另一方則輸一方則輸)，或雙方和局，或雙方和局15博弈的例子博弈的例子： 一字棋一字棋 跳棋跳棋 中國象棋中國象棋 圍棋圍棋 五子棋五子棋1617雙方的智能活動，任何一方都不能單獨控制雙方的智能活動，任何一方都不能單獨控制博弈過程，而是由雙方輪流實施其控制對策博弈過程，而是由雙方輪流實施其控制對策的過程。的過程。博弈的特點：博弈的特點：

4、18如何根據(jù)當前的棋局，選擇對自己最有利的如何根據(jù)當前的棋局，選擇對自己最有利的一步棋一步棋 ？人工智能中研究的博弈問題人工智能中研究的博弈問題：中國象棋中國象棋19用博弈樹來表示，它是一種特殊的用博弈樹來表示，它是一種特殊的與或樹與或樹。節(jié)點。節(jié)點代表博弈的格局（即棋局），相當于狀態(tài)空間中代表博弈的格局（即棋局），相當于狀態(tài)空間中的狀態(tài)，反映了博弈的信息，的狀態(tài)，反映了博弈的信息， 并且與節(jié)點、或并且與節(jié)點、或節(jié)點隔層交替出現(xiàn)。節(jié)點隔層交替出現(xiàn)。博弈問題（求解過程）的表示博弈問題（求解過程）的表示：20假設博弈雙方為：假設博弈雙方為：MAX和和MIN在博弈過程中，規(guī)則是雙方輪流走步。在博弈在

5、博弈過程中，規(guī)則是雙方輪流走步。在博弈樹中，相當于博弈雙方輪流擴展其所屬節(jié)點。樹中，相當于博弈雙方輪流擴展其所屬節(jié)點。為什么與節(jié)點、或節(jié)點隔層交替出現(xiàn)為什么與節(jié)點、或節(jié)點隔層交替出現(xiàn)？21從從MAX方的角度來看方的角度來看： 所有所有MIN方節(jié)點都是方節(jié)點都是與節(jié)點與節(jié)點理由理由：因為因為MIN方必定選擇最不利于方必定選擇最不利于MAX方的方式來方的方式來擴展節(jié)點，只要擴展節(jié)點，只要MIN方節(jié)點的子節(jié)點（下出棋方節(jié)點的子節(jié)點（下出棋局）中有一個對局）中有一個對MAX方不利，則該節(jié)點就對方不利，則該節(jié)點就對MAX方不利，故為方不利，故為“與節(jié)點與節(jié)點”。MIN好招好招22從從MAX方的角度來看方

6、的角度來看： 所有屬于所有屬于MAX方的節(jié)點都是方的節(jié)點都是或節(jié)點或節(jié)點理由理由：因為擴展因為擴展MAX方節(jié)點時，方節(jié)點時，MAX方可選擇擴展最方可選擇擴展最有利于自己的節(jié)點，只要可擴展的子節(jié)點中有有利于自己的節(jié)點，只要可擴展的子節(jié)點中有一個對已有利，一個對已有利， 則該節(jié)點就對已有利。則該節(jié)點就對已有利。MAX好招好招23總之：總之：從從MAX方來說，與節(jié)點、或節(jié)點交替出現(xiàn)；反之，方來說，與節(jié)點、或節(jié)點交替出現(xiàn)；反之，從從MIN方的角度來看，情況正好相反。方的角度來看，情況正好相反。24在博弈樹中，先行一方的初始狀態(tài)對應著樹的在博弈樹中，先行一方的初始狀態(tài)對應著樹的根根節(jié)點節(jié)點，而任何一方獲

7、勝的最終格局為目標狀態(tài)，而任何一方獲勝的最終格局為目標狀態(tài)，對應于樹的對應于樹的終葉節(jié)點終葉節(jié)點（可解節(jié)點或本原問題）。（可解節(jié)點或本原問題）。但是，從但是，從MAX的角度出發(fā)，所有使的角度出發(fā)，所有使MAX獲勝的獲勝的狀態(tài)格局都是本原問題，是狀態(tài)格局都是本原問題，是可解節(jié)點可解節(jié)點，而使，而使MIN獲勝的狀態(tài)格局是獲勝的狀態(tài)格局是不可解節(jié)點不可解節(jié)點。2526例例 Grundy博弈：分配物品的問題博弈：分配物品的問題如果有一堆數(shù)目為如果有一堆數(shù)目為N的錢幣，由兩位選手輪流進的錢幣，由兩位選手輪流進行分配，要求每個選手每次把其中某一堆分成數(shù)行分配，要求每個選手每次把其中某一堆分成數(shù)目目不等不等

8、的兩小堆，直至有一選手不能將錢幣分成的兩小堆，直至有一選手不能將錢幣分成不等的兩堆為止，則判定這位選手為輸家。不等的兩堆為止，則判定這位選手為輸家。27用數(shù)字序列加上一個說明來表示一個狀態(tài)：用數(shù)字序列加上一個說明來表示一個狀態(tài)： ( (3, 2, 1, 1, MAX) )數(shù)字序列數(shù)字序列：表示不同堆中錢幣的個數(shù)：表示不同堆中錢幣的個數(shù)說明說明：表示下一步由誰來分，即?。罕硎鞠乱徊接烧l來分，即取MAX或或MIN28現(xiàn)在取現(xiàn)在取 N7 的簡單情況的簡單情況，并由，并由MIN先分先分 注注：如果如果MAX走紅箭頭的分法，必定獲勝。走紅箭頭的分法，必定獲勝。所有可能的分法所有可能的分法(7,MIN)(

9、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對于比較復雜的博弈問題，只能模擬

10、人的思維對于比較復雜的博弈問題，只能模擬人的思維“向前看幾步向前看幾步”，然后作出決策，選擇最有利自，然后作出決策，選擇最有利自己的一步。即己的一步。即只能給出幾層走法，然后按照一定只能給出幾層走法，然后按照一定的估算辦法，的估算辦法，決定走一好招。決定走一好招。313233對于復雜的博弈問題，要規(guī)定搜索深度與時間，對于復雜的博弈問題，要規(guī)定搜索深度與時間，以便于博弈搜索能順利進行。以便于博弈搜索能順利進行。假設由假設由MAX來選擇走一步棋，問題是：來選擇走一步棋，問題是：MAX如何來選擇一步好棋如何來選擇一步好棋？ 3435 對于每一格局（棋局）給出（定義或者倒推）對于每一格局（棋局）給出（

11、定義或者倒推）一個靜態(tài)估價函數(shù)值。值越大對一個靜態(tài)估價函數(shù)值。值越大對MAX越有利，反越有利，反之越不利；之越不利；極大極小過程的基本思路極大極小過程的基本思路：36 對于給定的格局，對于給定的格局，MAX給出可能的走法，然后給出可能的走法，然后MIN對應地給出相應的走法，這樣重復若干次，對應地給出相應的走法，這樣重復若干次，得到一組端節(jié)點（必須由得到一組端節(jié)點（必須由MIN走后得到的，等待走后得到的，等待MAX下的棋局）。這一過程相當于節(jié)點擴展；下的棋局）。這一過程相當于節(jié)點擴展；注注：博弈樹深度或層數(shù)一定是偶數(shù)。：博弈樹深度或層數(shù)一定是偶數(shù)。37 對于每一個端節(jié)點，計算出它們的靜態(tài)估價函對

12、于每一個端節(jié)點，計算出它們的靜態(tài)估價函數(shù)，然后自下而上地逐層計算倒推值，直到數(shù)，然后自下而上地逐層計算倒推值，直到MAX開始的格局。在開始的格局。在MIN下的格局中取估值的最小值，下的格局中取估值的最小值，在在MAX下格局中取估值的最大值；下格局中取估值的最大值； 取估值最大的格局作為取估值最大的格局作為MAX要走的一招棋。要走的一招棋。38例例：向前看一步的兩層博弈樹向前看一步的兩層博弈樹 39定義靜態(tài)函數(shù)定義靜態(tài)函數(shù)e(P)的一般原則的一般原則：0MAXMIN( )0 0MAX MINe P 占優(yōu)，不利勢均力敵不利，占優(yōu)40OPEN：存放待擴展的節(jié)點，此時為隊列，即以存放待擴展的節(jié)點，此時

13、為隊列，即以寬度優(yōu)先的策略擴展節(jié)點。寬度優(yōu)先的策略擴展節(jié)點。CLOSED：存放已擴展的節(jié)點，此時為堆棧，存放已擴展的節(jié)點，此時為堆棧，即后擴展的節(jié)點先計算。即后擴展的節(jié)點先計算。 符號符號：41421、將初始節(jié)點、將初始節(jié)點 S 放入放入 OPEN 表中，開始時搜索表中，開始時搜索樹樹 T 由初始節(jié)點由初始節(jié)點 S 構成；構成；2、若、若 OPEN 表為空（表為空（節(jié)點擴展結束節(jié)點擴展結束），則轉），則轉5；3、將、將 OPEN 表中第一個節(jié)點表中第一個節(jié)點 n 移出放移出放入入CLOSED 表的前端；表的前端；極大極小搜索過程極大極小搜索過程為為：434、若、若 n 可直接判定為贏、輸、或平

14、局，則令對應的可直接判定為贏、輸、或平局，則令對應的 e(n)=，-或或 0，并轉，并轉2；否則擴展；否則擴展 n，產(chǎn)生產(chǎn)生 n 的的后繼節(jié)點集后繼節(jié)點集 ni ，將將 ni 放入搜索樹放入搜索樹 T 中。此時，中。此時，若搜索深度若搜索深度d ni 小于預先設定的深度小于預先設定的深度 k，則將則將 ni 放入放入OPEN表的末端，轉表的末端，轉2；否則，；否則，ni 達到深達到深度度k，計算計算e ( ni )，并轉并轉2；445、若、若CLOSED表為空，則轉表為空，則轉8；否則取出；否則取出CLOSED表中的第一個節(jié)點，記為表中的第一個節(jié)點，記為 np；Open為空，即已經(jīng)擴展完節(jié)點為

15、空，即已經(jīng)擴展完節(jié)點步步2456、若若 np 屬于屬于MAX層，且對于它的屬于層，且對于它的屬于MIN層層的子節(jié)點的子節(jié)點 nci 的的 e ( nci )有值，則：有值，則： e ( np ) =max nci 46（續(xù)）（續(xù)）若若 np 屬于屬于MIN層，且對于它的屬于層，且對于它的屬于MAX層的子層的子節(jié)點節(jié)點 nci 的的 e ( nci )有值，則：有值，則： e ( np )=min nci 477、轉、轉5；8、根據(jù)、根據(jù) e (S) 的值，標記走步或者結束（的值，標記走步或者結束（-，或或 0）。）。48第一階段第一階段為為1、2、3、4步，用寬度優(yōu)先算法生成步，用寬度優(yōu)先算法

16、生成規(guī)定深度規(guī)定深度 k 的全部博弈樹，然后對其所有端節(jié)點的全部博弈樹，然后對其所有端節(jié)點計算計算 e(P)；第二階段第二階段為為5、6、7、8步，是自下而上逐級求節(jié)步，是自下而上逐級求節(jié)點的倒推估價值，直至求出初始節(jié)點的點的倒推估價值，直至求出初始節(jié)點的 e(S) 為止，為止，再由再由 e(S) 選得相對較好的走法，過程結束。選得相對較好的走法，過程結束。算法分成兩個階段算法分成兩個階段：49等對手走出相應的棋，再以當前的格局等對手走出相應的棋，再以當前的格局作為初始節(jié)點，重復此過程，選擇對自作為初始節(jié)點，重復此過程，選擇對自己有利的走法。己有利的走法。50極大極小過程極大極小過程51例例：

17、 一字棋的極大極小搜索過程一字棋的極大極小搜索過程 約定約定： 每一方只向前看一步每一方只向前看一步 （擴展出二層）（擴展出二層） 記記MAX的棋子為的棋子為“”，MIN的棋子為的棋子為“O” 規(guī)定規(guī)定MAX先手先手52 若格局若格局 P 對任何一方都不能獲勝，則對任何一方都不能獲勝，則e(P) =（所有空格上都放上所有空格上都放上MAX的棋子后，的棋子后，MAX的三個棋子所組成的行、列及對角線的總數(shù)的三個棋子所組成的行、列及對角線的總數(shù)）-（所有空格上都放上所有空格上都放上MIN的棋子后，的棋子后，MIN的三個的三個棋子所組成的行、列及對角線的總數(shù)棋子所組成的行、列及對角線的總數(shù)）靜態(tài)估計函

18、數(shù)靜態(tài)估計函數(shù)e(P)定義為定義為：53 若若 P 是是MAX獲勝，則獲勝，則 e(P)=+ 若若 P 是是MIN獲勝，則獲勝，則 e(P)=54例：例：計算下列棋局的靜態(tài)估價函數(shù)值計算下列棋局的靜態(tài)估價函數(shù)值 e(P)=6-4=2 棋局棋局行行=2列列=2對角對角=2行行=2列列=2對角對角=055利用棋盤的對稱性，有些棋局是等價的利用棋盤的對稱性，有些棋局是等價的 561010-1-10-10-2121-2-11MAXMIN MAXMAX的走步的走步57第二步第二步213211102011022312211100158第三步第三步- 021- - - 122101- - - 1111112

19、- 1159MAXMIN60MAXMINOO61極大極小搜索過程由兩個完全分離的兩個步驟極大極小搜索過程由兩個完全分離的兩個步驟組成：組成：第一第一、用寬度優(yōu)先算法生成一棵博弈搜索樹、用寬度優(yōu)先算法生成一棵博弈搜索樹第二第二、估計值的倒推計算、估計值的倒推計算缺點缺點：這種分離使得搜索的效率比較低：這種分離使得搜索的效率比較低6205-333-3022-30-23541-30689-30-33-3-3-21-360316011極大極大極小極小ab注：用表示注：用表示MAXMAX，用表示，用表示MINMIN，端節(jié)點上的數(shù)字表示它對應，端節(jié)點上的數(shù)字表示它對應的估價函數(shù)的值。的估價函數(shù)的值。極大極

20、大極小極小63極大極小過程是先生成與極大極小過程是先生成與/或樹，然后再計算各節(jié)或樹，然后再計算各節(jié)點的估值，這種生成節(jié)點和計算估值相分離的搜點的估值，這種生成節(jié)點和計算估值相分離的搜索方式，需要生成規(guī)定深度內的所有節(jié)點，因此索方式，需要生成規(guī)定深度內的所有節(jié)點，因此搜索效率較低。搜索效率較低。改進改進：在博弈樹生成過程中同時計算端節(jié)點的估在博弈樹生成過程中同時計算端節(jié)點的估計值及倒推值，以減少搜索的次數(shù)，這就是計值及倒推值，以減少搜索的次數(shù)，這就是-過過程的思想，也稱為程的思想，也稱為-剪枝法。剪枝法。剪枝的概念剪枝的概念 : 如果能邊生成節(jié)點邊對節(jié)點估值，并剪去一些沒如果能邊生成節(jié)點邊對節(jié)點估值，并剪去一些沒用的分枝，這種技術被稱為用的分枝，這種技術被稱為-剪枝。剪枝。6465 一個一個-剪枝的具體例子，如下圖所示。其中最下面一層端節(jié)剪枝的具體例子，如下圖所示。其中最下面一層端節(jié)點旁邊的數(shù)字是假設的估值。點旁邊的數(shù)字是假設的估值。 在該圖中，在該圖中，L、M、N的估值推出節(jié)點的估值推出節(jié)點F的倒推值為的倒推值為4，即，即F的的值為值為4，由此可推出節(jié)點，由此可推出節(jié)點C的倒推值的倒推值4。 記記C的倒推值的下