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

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