人工智能知識表示與推理博弈樹搜索PPT課件

2020/5/17,.,1,人工智能ArtificialIntelligence(AI),2020/5/17,.,2,2.4博弈問題的搜索技術(shù)2.4.1博弈問題的表達2.4.2極大極小搜索過程2.4.3-剪枝法,2020/5/17,.,3,2.4.1博弈問題的表達,博弈是一類具有競爭性的智能活動雙人博弈：即兩位選手對壘，輪流依次走步，其中任何一方都完全知道對方過去已經(jīng)走過的棋步和今后可能的走步，其結(jié)果是一方贏(而另一方則輸)，或雙方和局,2020/5/17,.,4,博弈的例子：一字棋跳棋中國象棋圍棋五子棋,2020/5/17,.,5,雙方的智能活動，任何一方都不能單獨控制博弈過程，而是由雙方輪流實施其控制對策的過程,博弈的特點：,2020/5/17,.,6,如何根據(jù)當前的棋局，選擇對自己最有利的一步棋？！,人工智能中研究的博弈問題：,2020/5/17,.,7,用博弈樹來表示，它是一種特殊的與或圖。節(jié)點代表博弈的格局（即棋局），相當于狀態(tài)空間中的狀態(tài)，反映了博弈的信息。與節(jié)點、或節(jié)點隔層交替出現(xiàn),博弈問題的表示：,2020/5/17,.,8,假設(shè)博弈雙方為：MAX和MIN在博弈過程中，規(guī)則是雙方輪流走步。在博弈樹中，相當于博弈雙方輪流擴展其所屬節(jié)點,為什么與節(jié)點、或節(jié)點隔層交替出現(xiàn)？,2020/5/17,.,9,從MAX方的角度來看：所有MIN方節(jié)點都是與節(jié)點理由：因為MIN方必定選擇最不利于MAX方的方式來擴展節(jié)點，只要MIN方節(jié)點的子節(jié)點中有一個對MAX方不利，則該節(jié)點就對MAX方不利，故為“與節(jié)點”,2020/5/17,.,10,從MAX方的角度來看：所有屬于MAX方的節(jié)點都是“或節(jié)點”理由：因為擴展MAX方節(jié)點時，MAX方可選擇擴展最有利于自己的節(jié)點，只要可擴展的子節(jié)點中有一個對已有利，則該節(jié)點就對已有利,MAX,好招,2020/5/17,.,11,總之從MAX方來說，與節(jié)點、或節(jié)點交替出現(xiàn)；反之，從MIN方的角度來看，情況正好相反,2020/5/17,.,12,在博弈樹中，先行一方的初始狀態(tài)對應(yīng)著樹的根節(jié)點，而任何一方獲勝的最終格局為目標狀態(tài)，對應(yīng)于樹的終葉節(jié)點（可解節(jié)點或本原問題）,但是，從MAX的角度出發(fā)，所有使MAX獲勝的狀態(tài)格局都是本原問題，是可解節(jié)點，而使MIN獲勝的狀態(tài)格局是不可解節(jié)點,2020/5/17,.,13,例Grundy博弈：分配物品的問題如果有一堆數(shù)目為N的錢幣，由兩位選手輪流進行分配，要求每個選手每次把其中某一堆分成數(shù)目不等的兩小堆，直至有一選手不能將錢幣分成不等的兩堆為止，則判定這位選手為輸家,2020/5/17,.,14,用數(shù)字序列加上一個說明來表示一個狀態(tài)：(3,2,1,1,MAX)數(shù)字序列：表示不同堆中錢幣的個數(shù)說明：表示下一步由誰來分，即取MAX或MIN,2020/5/17,.,15,現(xiàn)在取N7的簡單情況，并由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),2020/5/17,.,16,對于比較復(fù)雜的博弈問題，只能模擬人的思維“向前看幾步”，然后作出決策，選擇最有利自己的一步。即只能給出幾層走法，然后按照一定的估算辦法，決定走一好招,2020/5/17,.,17,2.4.2極大極小過程,對于復(fù)雜的博弈問題，要規(guī)定搜索深度與時間，以便于博弈搜索能順利進行,假設(shè)由MAX來選擇走一步棋，問題是：MAX如何來選擇一步好棋？,2020/5/17,.,18,對于每一格局（棋局）給出（定義或者倒推）一個靜態(tài)估價函數(shù)值。值越大對MAX越有利，反之越不利,極大極小過程的基本思路：,2020/5/17,.,19,對于給定的格局，MAX給出可能的走法，然后MIN對應(yīng)地給出相應(yīng)的走法，這樣重復(fù)若干次，得到一組端節(jié)點（必須由MIN走后得到的，由MAX下的棋局）。這一過程相當于節(jié)點擴展注：博弈樹深度或?qū)訑?shù)一定是偶數(shù),2020/5/17,.,20,對于每一個端節(jié)點，計算出它們的靜態(tài)估價函數(shù)，然后自下而上地逐層計算倒推值，直到MAX開始的格局。在MIN下的格局中取估值的最小值，在MAX下格局中取估值的最大值取估值最大的格局作為MAX要走的一招棋,2020/5/17,.,21,例：向前看一步的兩層博弈樹,2020/5/17,.,22,定義靜態(tài)函數(shù)e(P)的一般原則：,2020/5/17,.,23,OPEN：存放待擴展的節(jié)點，此時為隊列，即以寬度優(yōu)先的策略擴展節(jié)點CLOSED：存放已擴展的節(jié)點，此時為堆棧，即后擴展的節(jié)點先計算靜態(tài)估價函數(shù)值,符號：,2020/5/17,.,24,1、將初始節(jié)點S放入OPEN表中，開始時搜索樹T由初始節(jié)點S構(gòu)成2、若OPEN表為空，則轉(zhuǎn)53、將OPEN表中第一個節(jié)點n移出放入CLOSED表的前端,極大極小搜索過程為：,2020/5/17,.,25,4、若n可直接判定為贏、輸、或平局，則令對應(yīng)的e(n)=，-或0，并轉(zhuǎn)2；否則擴展n，產(chǎn)生n的后繼節(jié)點集ni，將ni放入搜索樹T中,2020/5/17,.,26,此時，若搜索深度dni小于預(yù)先設(shè)定的深度k，則將ni放入OPEN表的末端，轉(zhuǎn)2；否則，ni達到深度k，計算e(ni)，并轉(zhuǎn)2,（續(xù)）,2020/5/17,.,27,5、若CLOSED表為空，則轉(zhuǎn)8；否則取出CLOSED表中的第一個節(jié)點，記為np,Open為空，即已經(jīng)擴展完節(jié)點,步2,2020/5/17,.,28,6、若np屬于MAX層，且對于它的屬于MIN層的子節(jié)點nci的e(nci)有值，則：e(np)=maxnci,某一個節(jié)點屬于MAX的含義是該節(jié)點等待MAX來擴展,2020/5/17,.,29,（續(xù)）若np屬于MIN層，且對于它的屬于MAX層的子節(jié)點nci的e(nci)有值，則：e(np)=minnci,2020/5/17,.,30,7、轉(zhuǎn)58、根據(jù)e(S)的值，標記走步或者結(jié)束（-，或0）,2020/5/17,.,31,第一階段為1、2、3、4步，用寬度優(yōu)先算法生成規(guī)定深度k的全部博弈樹，然后對其所有端節(jié)點計算e(P)第二階段為5、6、7、8步，是自下而上逐級求節(jié)點的倒推估價值，直至求出初始節(jié)點的e(S)為止，再由e(S)選得相對較好的走法，過程結(jié)束,算法分成兩個階段：,2020/5/17,.,32,等對手走出相應(yīng)的棋，再以當前的格局作為初始節(jié)點，重復(fù)此過程，選擇對自己有利的走法,2020/5/17,.,33,2020/5/17,.,34,例：一字棋的極大極小搜索過程,約定：每一方只向前看一步（擴展出二層）記MAX的棋子為“”，MIN的棋子為“O”規(guī)定MAX先手,2020/5/17,.,35,若格局P對任何一方都不能獲勝，則e(P)=（所有空格上都放上MAX的棋子后，MAX的三個棋子所組成的行、列及對角線的總數(shù)）-（所有空格上都放上MIN的棋子后，MIN的三個棋子所組成的行、列及對角線的總數(shù)）,靜態(tài)估計函數(shù)e(P)定義為：,2020/5/17,.,36,若P是MAX獲勝，則e(P)=+若P是MIN獲勝，則e(P)=,2020/5/17,.,37,例：計算下列棋局的靜態(tài)估價函數(shù)值,e(P)=6-4=2,棋局,行=2列=2對角=2,行=2列=2對角=0,2020/5/17,.,38,利用棋盤的對稱性，有些棋局是等價的,2020/5/17,.,39,1,0,1,0,-1,-1,0,-1,0,-2,1,2,1,-2,-1,1,MAX,MIN,MAX,MAX的走步,2020/5/17,.,40,第二步,2,1,3,2,1,1,1,0,2,0,1,1,0,2,2,3,1,2,2,1,1,1,0,0,1,3,MIN,2020/5/17,.,41,第三步,-,0,2,1,-,-,-,1,2,2,1,0,1,-,-,-,1,1,1,1,1,1,2,-,1,1,2020/5/17,.,42,MAX,MIN,2020/5/17,.,43,MAX,MIN,O,O,2020/5/17,.,44,上機實驗作業(yè)：用C/C+語言編寫“一字棋”的游戲程序，基本要求：必須實現(xiàn)極大極小過程能夠進行“人-機”對壘、“機-機”對壘簡單地顯示對壘過程實驗形式：兩人或者一人一組,2020/5/17,.,45,實驗報告格式：“一字棋”游戲的計算機程序?qū)W號：姓名：專業(yè)：摘要1一字棋游戲的文字描述2一字棋對壘過程的計算機描述和實現(xiàn)3實例（人機對壘的過程、機機對壘的過程）4體會5參考文獻附錄：程序使用的簡單說明,2020/5/17,.,46,提交的材料：1、文字報告；2、程序原代碼提交的方式：以學(xué)號姓名為壓縮文件名（發(fā)送到wgqu提交的時間：11月21日口頭報告：介紹報告的主要內(nèi)容和演示程序，特別是自己覺得有特色的地方。初步時間是12月初。,2020/5/17,.,47,2.4.3-剪枝法,極大極小搜索過程由兩個完全分離的兩個步驟組成：1、用寬度優(yōu)先算法生成一棵博弈搜索樹。2、估計值的倒推計算。缺點：這種分離使得搜索的效率比較低。,2020/5/17,.,48,改進：在博弈樹生成過程中同時計算端節(jié)點的估計值及倒推值，以減少搜索的次數(shù)，這就是-過程的思想，也稱為-剪枝法。其中，表示MAX節(jié)點的估值的下界（已經(jīng)搜索到的MAX節(jié)點的最小值）。表示MIN節(jié)點的估值的上界（已經(jīng)搜索到的MIN節(jié)點的最大值）。,2020/5/17,.,49,極大極小過程：采用寬度優(yōu)先的方式來擴展節(jié)點-剪枝法：改用深度優(yōu)先的策略來擴展節(jié),2020/5/17,.,50,一字棋的左邊部分,MAX,MIN,現(xiàn)擴展B得到C，其值為-1，則B的倒推值小于等于-1，即-1。再擴展B的子節(jié)點，B的值也不會大于-1。結(jié)果是B比A差，不用再擴展B的其他子節(jié)點了。此處，MIN節(jié)點B的值小于等于其先輩MAX節(jié)點S的值，停止擴展。,C,擴展S生成A,B,.。擴展A生成5個子節(jié)點，倒推得到A的值為-1?？梢缘玫絊的值大于等于-1，即-1。,2020/5/17,.,51,更一般的情況,MIN節(jié)點的不大于其先輩MAX節(jié)點的值，則可以中止擴展,MAX節(jié)點的不小于其先輩MIN節(jié)點的值，則可以中止擴展,2020/5/17,.,52,一般而言，當某一個節(jié)點的后繼節(jié)點倒推值已經(jīng)給定時，則倒推值的上下界可以被修正。注意：MAX節(jié)點的值非減，MIN節(jié)點的值非增。,2020/5/17,.,53,、值的計算方法：第一、一個MAX節(jié)點的值等于其后繼節(jié)點當前最大的最終倒推值。第二、一個MIN節(jié)點的值等于其后繼節(jié)點當前最小的最終倒推值。,2020/5/17,.,54,-剪枝的規(guī)則為：1、若任何MIN結(jié)點的值小于或等于任何它的先輩MAX結(jié)點的值，則可中止該MIN結(jié)點以下的搜索，此時這個MIN結(jié)點的最終倒推值就是已得到的值。該值與真正的極大極小的搜索結(jié)果的倒推值可能不相同，但是對起始結(jié)點而言，倒推值是相同的，使用它選擇的走步也是相同的。,2020/5/17,.,55,2、若任何MAX結(jié)點的值大于或等于它的MIN先輩結(jié)點的值，則可以中止該MAX結(jié)點以下的搜索，此時這個MAX結(jié)點處的倒推值就是已得到的值。,2020/5/17,.,56,當搜索用規(guī)則1終止時，我們稱進行了剪枝，而當搜索用規(guī)則2終止時，我們稱進行了剪枝。在搜索過程中，保存和值，如果出現(xiàn)滿足使用兩條規(guī)則的條件，我們就中止某一些搜索，這一過程稱為-(剪枝)過程。,2020/5/17,.,57,-過程的主要思想（步驟）:1、采用有界的深度優(yōu)先搜索算法。2、立即計算端節(jié)點的估值。3、剪枝4、剪枝5、當初始節(jié)點的所有后繼節(jié)點的最終倒推值全部給出后，搜索過程結(jié)束。,2020/5/17,.