人工智能-博弈樹的搜索

?●○

?●○

?●○

?●○●

?○●

?○●

?○●

?○2.3博弈樹搜索人工智能-博弈樹的搜索第1頁20世紀(jì)60年代，研制出西洋跳棋和國際象棋博弈程序到達(dá)了大師級水平。1958約翰?麥卡錫提出博弈樹搜索算法1997年，IBM企業(yè)研制“深藍(lán)”國際象棋程序，采取博弈樹搜索算法，該程序戰(zhàn)勝了國際象棋世界冠軍卡斯帕羅夫。1.概述人工智能-博弈樹的搜索第2頁正在與深藍(lán)下棋卡斯帕羅夫人工智能-博弈樹的搜索第3頁博弈問題特點(diǎn)：雙人對弈，輪番走步。信息完備，雙方所得到信息是一樣。零和，即對一方有利棋，對另一方必定是不利，不存在對雙方都有利或無利棋。1.概述人工智能-博弈樹的搜索第4頁博弈特征兩個(gè)棋手交替地走棋；比賽最終止果，是贏、輸和平局中一個(gè)；可用圖搜索技術(shù)進(jìn)行，但效率很低；博弈過程，是尋找置對手于必?cái)B(tài)過程；雙方都無法干預(yù)對方選擇。1.概述人工智能-博弈樹的搜索第5頁2.Grundy博弈下棋雙方是對立，命名博弈雙方，一方為“正方”，這類節(jié)點(diǎn)稱為“MAX”節(jié)點(diǎn)；另一方為“反方”，這類節(jié)點(diǎn)稱為“MIN”節(jié)點(diǎn)。正方和反方是交替走步，所以MAX節(jié)點(diǎn)和MIN節(jié)點(diǎn)會(huì)交替出現(xiàn)。人工智能-博弈樹的搜索第6頁2.Grundy博弈Grundy博弈是一個(gè)分錢幣游戲。有一堆數(shù)目為N錢幣，由兩位選手輪番進(jìn)行分堆，要求每個(gè)選手每次只把其中某一堆分成數(shù)目不等兩小堆。比如，選手甲把N分成兩堆后，輪到選手乙就能夠挑其中一堆來分，如此進(jìn)行下去，直到有一位選手先無法把錢幣再分成不相等兩堆時(shí)就得認(rèn)輸。人工智能-博弈樹的搜索第7頁2.Grundy博弈設(shè)初始狀態(tài)為(7，MIN)，建立問題狀態(tài)空間圖，圖中全部終止點(diǎn)均表示該選手必輸情況，取勝方目標(biāo)是設(shè)法使棋局發(fā)展為結(jié)束在對方走步時(shí)終止點(diǎn)上。人工智能-博弈樹的搜索第8頁MIN先走M(jìn)AX必勝2.Grundy博弈人工智能-博弈樹的搜索第9頁結(jié)點(diǎn)A是MAX搜索目標(biāo)，而結(jié)點(diǎn)B，C則為MIN搜索目標(biāo)。2.Grundy博弈人工智能-博弈樹的搜索第10頁搜索策略要考慮問題是：對MIN走步后每一個(gè)MAX結(jié)點(diǎn)，必須證實(shí)MAX對MIN可能走每一個(gè)棋局對弈后能獲勝，即MAX必須考慮應(yīng)付MIN全部招法，這是一個(gè)與含意，所以含有MAX符號結(jié)點(diǎn)可看成與結(jié)點(diǎn)。

2.Grundy博弈人工智能-博弈樹的搜索第11頁對MAX走步后每一個(gè)MIN結(jié)點(diǎn)，只須證實(shí)MAX有一步能走贏就能夠，即MAX只要考慮能走出一步棋使MIN無法招架就成，所以含有MIN符號結(jié)點(diǎn)可看成或結(jié)點(diǎn)。2.Grundy博弈人工智能-博弈樹的搜索第12頁對弈過程搜索圖展現(xiàn)出與或圖表示形式。實(shí)現(xiàn)一個(gè)取勝策略就是搜索一個(gè)解圖問題，解圖就代表一個(gè)完整博弈策略。2.Grundy博弈人工智能-博弈樹的搜索第13頁中國象棋一盤棋平均走50步，總狀態(tài)數(shù)約為10161次方。假設(shè)1毫微秒走一步，約需10145次方年。結(jié)論：不可能窮舉。3.極小極大搜索過程人工智能-博弈樹的搜索第14頁對各個(gè)局面進(jìn)行評定評定目標(biāo)：對后面狀態(tài)提前進(jìn)行考慮，而且以各種狀態(tài)評定值為基礎(chǔ)作出最好走棋選擇。評定方法：用評價(jià)函數(shù)對棋局進(jìn)行評定。贏評定值設(shè)為+∞，輸評定值設(shè)為-∞，平局評定值設(shè)為0。評定標(biāo)準(zhǔn)：因?yàn)橄缕咫p方是對立，只能選擇其中一方為評定標(biāo)準(zhǔn)方。3.極小極大搜索過程人工智能-博弈樹的搜索第15頁MAX節(jié)點(diǎn)和MIN節(jié)點(diǎn)命名博弈雙方，一方為“正方”，對每個(gè)狀態(tài)評定都是對應(yīng)于該方輸贏。比如，贏2個(gè)，輸1個(gè)等，都是指正方。正方每走一步，都在選擇使自己贏得更多節(jié)點(diǎn)，所以這類節(jié)點(diǎn)稱為“MAX”節(jié)點(diǎn)；3.極小極大搜索過程人工智能-博弈樹的搜索第16頁另一方為“反方”，對每個(gè)狀態(tài)評定都是對應(yīng)于對手輸贏。比如，贏2個(gè)，輸一個(gè)，其實(shí)是指自己輸2個(gè)，贏1個(gè)。反方每走一步，都在選擇使對手輸?shù)酶喙?jié)點(diǎn)，所以這類節(jié)點(diǎn)稱為“MIN”節(jié)點(diǎn)。3.極小極大搜索過程人工智能-博弈樹的搜索第17頁因?yàn)檎胶头捶绞墙惶孀卟剑訫AX節(jié)點(diǎn)和MIN節(jié)點(diǎn)會(huì)交替出現(xiàn)。3.極小極大搜索過程人工智能-博弈樹的搜索第18頁正方（MAX節(jié)點(diǎn)）從全部子節(jié)點(diǎn)中，選取含有最大評定值節(jié)點(diǎn)。反方（MIN節(jié)點(diǎn)）從其全部子節(jié)點(diǎn)中，選取含有最小評定值節(jié)點(diǎn)。重復(fù)進(jìn)行這種選取，就能夠得到雙方各個(gè)節(jié)點(diǎn)評定值。這種確定棋步方法，稱為極小極大搜索法。

3.極小極大搜索過程人工智能-博弈樹的搜索第19頁3.極小極大搜索過程人工智能-博弈樹的搜索第20頁5-333-3022-30-23541-30689-3MINMAX0MAXMIN3.極小極大搜索過程人工智能-博弈樹的搜索第21頁015-333-3022-30-23541-30689-30-33-3-3-21-36-3031601MAXMINMAXMIN3.極小極大搜索過程人工智能-博弈樹的搜索第22頁

在九宮格棋盤上，兩位選手輪番在棋盤上擺各自棋子(每次一枚)，誰先取得三線結(jié)果就取勝。設(shè)程序方MAX棋子用(×)表示，MAX先走。對手MIN棋子用(o)表示。比如：3.極小極大搜索過程MIN取勝人工智能-博弈樹的搜索第23頁

預(yù)計(jì)函數(shù)f(p)=(全部空格都放上MAX棋子之后，MAX三子成線數(shù))－(全部空格都放上MIN棋子之后，MIN三子成線總數(shù))

若P是MAX獲勝格局，則f(p)=+∞；若P是MIN獲勝格局，則f(p)＝-∞。3.極小極大搜索過程人工智能-博弈樹的搜索第24頁3.極小極大搜索過程預(yù)計(jì)函數(shù)值f(p)=6-4=2預(yù)計(jì)函數(shù)f(p)=(全部空格都放上MAX棋子之后，MAX三子成線(行、列、對角)數(shù))－(全部空格都放上MIN棋子之后，MIN三子成線(行、列、對角)總數(shù))當(dāng)前棋局f(p)=2人工智能-博弈樹的搜索第25頁3.極小極大搜索過程一字棋第一階段搜索樹人工智能-博弈樹的搜索第26頁3.極小極大搜索過程一字棋第二階段搜索樹人工智能-博弈樹的搜索第27頁3.極小極大搜索過程一字棋第三階段搜索樹人工智能-博弈樹的搜索第28頁

設(shè)有一個(gè)擺放三個(gè)子棋盤殘局，以下列圖所表示，〇和╳在結(jié)束前有三步棋能夠走，而且設(shè)走第一步是╳。這時(shí)存在著三個(gè)空格A，B，C，用博弈樹搜索算法判斷應(yīng)該把棋子放到哪一格內(nèi)。

AB╳╳╳〇〇C〇棋盤殘局舉例：3.極小極大搜索過程人工智能-博弈樹的搜索第29頁AB╳╳╳〇〇C〇╳B╳╳╳〇〇C〇╳〇╳╳╳〇〇C〇╳B╳╳╳〇〇〇〇0A╳╳╳╳〇〇C〇〇╳╳╳╳〇〇C〇A╳╳╳╳〇〇〇〇AB╳╳╳〇〇╳〇〇B╳╳╳〇〇╳〇A〇╳╳╳〇〇╳〇-1-

0-

10-

-

0MAX節(jié)點(diǎn)MIN節(jié)點(diǎn)終端節(jié)點(diǎn)3.極小極大搜索過程人工智能-博弈樹的搜索第30頁

對于棋盤殘局中╳來說，最好選擇，是將╳放在C位置上，這時(shí)能夠造成平局局面。

3.極小極大搜索過程人工智能-博弈樹的搜索第31頁-剪支法引入在極小極大法中，必須求出全部終端節(jié)點(diǎn)評定值，當(dāng)預(yù)先考慮棋步比較多時(shí)，計(jì)算量會(huì)大大增加。為了提升搜索效率，引入了經(jīng)過對評定值上下限進(jìn)行預(yù)計(jì)，從而降低需進(jìn)行評定節(jié)點(diǎn)范圍

-剪支法。4.-搜索過程人工智能-博弈樹的搜索第32頁

作為正方出現(xiàn)MAX節(jié)點(diǎn)，假設(shè)它MIN子節(jié)點(diǎn)有N個(gè)，那么當(dāng)它第一個(gè)MIN子節(jié)點(diǎn)評定值為時(shí)，則對于其它子節(jié)點(diǎn)，假如有高過，就取那最高值作為該MAX節(jié)點(diǎn)評定值；假如沒有，則該MAX節(jié)點(diǎn)評定值為?？傊?，該MAX節(jié)點(diǎn)評定值不會(huì)低于，這個(gè)就稱為該MAX節(jié)點(diǎn)評定下限值。4.-搜索過程

MAX節(jié)點(diǎn)評定下限值

人工智能-博弈樹的搜索第33頁MIN節(jié)點(diǎn)評定上限值

作為反方出現(xiàn)MIN節(jié)點(diǎn)，假設(shè)它MAX子節(jié)點(diǎn)有N個(gè)，那么當(dāng)它第一個(gè)MAX子節(jié)點(diǎn)評定值為時(shí)，則對于其它子節(jié)點(diǎn)，假如有低于，就取那個(gè)低于值作為該MIN節(jié)點(diǎn)評定值；假如沒有，則該MIN節(jié)點(diǎn)評定值取。總之，該MIN節(jié)點(diǎn)評定值不會(huì)高過，這個(gè)就稱為該MIN節(jié)點(diǎn)評定上限值。4.-搜索過程人工智能-博弈樹的搜索第34頁

剪支法

MAX節(jié)點(diǎn)

MIN節(jié)點(diǎn)=

剪支ABCD4.-搜索過程

設(shè)MAX節(jié)點(diǎn)下限為，則其全部MIN子節(jié)點(diǎn)中，其評定值上限小于等于節(jié)點(diǎn)，其以下部分搜索都能夠停頓了，即對這部分節(jié)點(diǎn)進(jìn)行了剪支。人工智能-博弈樹的搜索第35頁

設(shè)MIN節(jié)點(diǎn)上限為，則其全部MAX子節(jié)點(diǎn)中，其評定值下限大于等于節(jié)點(diǎn)，其以下部分搜索都能夠停頓了，即對這部分節(jié)點(diǎn)進(jìn)行了剪支。MAX節(jié)點(diǎn)

MIN節(jié)點(diǎn)=

剪支ABCD4.-搜索過程

剪支法

人工智能-博弈樹的搜索第36頁ABCDEFGHIJKLNOM4.-搜索過程MAX節(jié)點(diǎn)MAX節(jié)點(diǎn)MIN節(jié)點(diǎn)終端節(jié)點(diǎn)35652164人工智能-博弈樹的搜索第37頁MAX節(jié)點(diǎn)(5,

)35652164(6,

)(2,

)(-,5)(-,2)(5,

)MIN節(jié)點(diǎn)終端節(jié)點(diǎn)

剪支

剪支ABCDEFGHIJKLNOMMAX節(jié)點(diǎn)4.-搜索過程人工智能-博弈樹的搜索第38頁一字棋第一階段

-剪支方法4.-搜索過程人工智能-博弈樹的搜索第39頁4.-搜索過程極大節(jié)點(diǎn)下界為。極小節(jié)點(diǎn)上界為。剪支條件：后輩節(jié)點(diǎn)值≤祖先節(jié)點(diǎn)值時(shí)，剪支后輩節(jié)點(diǎn)值≥祖先節(jié)點(diǎn)值時(shí)，剪支簡記為：極小≤極大，剪支極大≥極小，剪支人工智能-博弈樹的搜索第40頁4.-搜索過程86-31453-3503-3022-30-2309-300-303305411-31661abcdefghijkmnMAXMINMAXMIN人工智能-博弈樹的搜索第41頁改進(jìn)方法

使用

-剪支技術(shù)，當(dāng)不滿足剪支條件(即

)時(shí)或

值比

值大不了多少或極相近時(shí)，這時(shí)也能夠進(jìn)行剪支，方便有條件把搜索集中到會(huì)帶來更大效果其它路徑上，這就是中止對效益不大一些子樹搜索，以提升搜索效率。

4.-搜索過程人工智能-博弈樹的搜索第42頁

不嚴(yán)格限制搜索深度。當(dāng)?shù)诌_(dá)深度限制時(shí)，如出現(xiàn)博弈格局有可能發(fā)生較大改變時(shí)，則應(yīng)多搜索幾層，使格局進(jìn)入較穩(wěn)定狀態(tài)后再中止，這么可使倒推值計(jì)算結(jié)果比較合理，防止考慮不充分產(chǎn)生影響，