人工智能-博弈樹的搜索課件

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

2.Grundy博弈11人工智能-博弈樹的搜索對MAX走步后的每一個MIN結點，只須證明MAX有一步能走贏就可以，即MAX只要考慮能走出一步棋使MIN無法招架就成，因此含有MIN符號的結點可看成或結點。2.Grundy博弈12人工智能-博弈樹的搜索對弈過程的搜索圖呈現(xiàn)出與或圖表示的形式。實現(xiàn)一種取勝的策略就是搜索一個解圖的問題，解圖就代表一種完整的博弈策略。2.Grundy博弈13人工智能-博弈樹的搜索中國象棋一盤棋平均走50步，總狀態(tài)數(shù)約為10的161次方。假設1毫微秒走一步，約需10的145次方年。結論：不可能窮舉。3.極小極大搜索過程14人工智能-博弈樹的搜索對各個局面進行評估評估的目的：對后面的狀態(tài)提前進行考慮，并且以各種狀態(tài)的評估值為基礎作出最好的走棋選擇。評估的方法：用評價函數(shù)對棋局進行評估。贏的評估值設為+∞，輸?shù)脑u估值設為-∞，平局的評估值設為0。評估的標準：由于下棋的雙方是對立的，只能選擇其中一方為評估的標準方。3.極小極大搜索過程15人工智能-博弈樹的搜索MAX節(jié)點和MIN節(jié)點命名博弈的雙方，一方為“正方”，對每個狀態(tài)的評估都是對應于該方的輸贏的。例如，贏2個，輸1個等，都是指正方的。正方每走一步，都在選擇使自己贏得更多的節(jié)點，因此這類節(jié)點稱為“MAX”節(jié)點；3.極小極大搜索過程16人工智能-博弈樹的搜索另一方為“反方”，對每個狀態(tài)的評估都是對應于對手的輸贏的。例如，贏2個，輸一個，其實是指自己輸2個，贏1個的。反方每走一步，都在選擇使對手輸?shù)酶嗟墓?jié)點，因此這類節(jié)點稱為“MIN”節(jié)點。3.極小極大搜索過程17人工智能-博弈樹的搜索由于正方和反方是交替走步的，因此MAX節(jié)點和MIN節(jié)點會交替出現(xiàn)。3.極小極大搜索過程18人工智能-博弈樹的搜索正方（MAX節(jié)點）從所有子節(jié)點中，選取具有最大評估值的節(jié)點。反方（MIN節(jié)點）從其所有子節(jié)點中，選取具有最小評估值的節(jié)點。反復進行這種選取，就可以得到雙方各個節(jié)點的評估值。這種確定棋步的方法，稱為極小極大搜索法。

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人工智能-博弈樹的搜索

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

估計函數(shù)f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成線數(shù))－(所有空格都放上MIN的棋子之后，MIN的三子成線的總數(shù))

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

設有一個擺放三個子的棋盤殘局，如下圖所示，〇和╳在結束前有三步棋可以走，而且設走第一步的是╳。這時存在著三個空格A，B，C，用博弈樹搜索算法判斷應該把棋子放到哪一格內。

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

0-

10-

-

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

對于棋盤殘局中的╳來說，最好的選擇，是將╳放在C的位置上，這時可以導致平局局面。

3.極小極大搜索過程31人工智能-博弈樹的搜索-剪支法的引入在極小極大法中，必須求出所有終端節(jié)點的評估值，當預先考慮的棋步比較多時，計算量會大大增加。為了提高搜索的效率，引入了通過對評估值的上下限進行估計，從而減少需進行評估的節(jié)點范圍的

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

作為正方出現(xiàn)的MAX節(jié)點，假設它的MIN子節(jié)點有N個，那么當它的第一個MIN子節(jié)點的評估值為時，則對于其它的子節(jié)點，如果有高過的，就取那最高的值作為該MAX節(jié)點的評估值；如果沒有，則該MAX節(jié)點的評估值為。總之，該MAX節(jié)點的評估值不會低于，這個就稱為該MAX節(jié)點的評估下限值。4.-搜索過程

MAX節(jié)點的評估下限值

33人工智能-博弈樹的搜索MIN節(jié)點的評估上限值

作為反方出現(xiàn)的MIN節(jié)點，假設它的MAX子節(jié)點有N個，那么當它的第一個MAX子節(jié)點的評估值為時，則對于其它子節(jié)點，如果有低于的，就取那個低于的值作為該MIN節(jié)點的評估值；如果沒有，則該MIN節(jié)點的評估值取?？傊?，該MIN節(jié)點的評估值不會高過，這個就稱為該MIN節(jié)點的評估上限值。4.-搜索過程34人工智能-博弈樹的搜索

剪支法

MAX節(jié)點

MIN節(jié)點=

剪支ABCD4.-搜索過程

設MAX節(jié)點的下限為，則其所有的MIN子節(jié)點中，其評估值的上限小于等于的節(jié)點，其以下部分的搜索都可以停止了，即對這部分節(jié)點進行了剪支。35人工智能-博弈樹的搜索

設MIN節(jié)點的上限為，則其所有的MAX子節(jié)點中，其評估值的下限大于等于的節(jié)點，其以下部分的搜索都可以停止了，即對這部分節(jié)點進行了剪支。MAX節(jié)點

MIN節(jié)點=

剪支ABCD4.-搜索過程

剪支法

36人工智能-博弈樹的搜索ABCDEFGHIJKLNOM4.-搜索過程MAX節(jié)點MAX節(jié)點MIN節(jié)點終端節(jié)點3565216437人工智能-博弈樹的搜索MAX節(jié)點(5,

)35652164(6,

)(2,

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

)MIN節(jié)點終端節(jié)點

剪支

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

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

使用

-剪支技術，當不滿足剪支條件(即

)時或

值比

值大不了多少或極相近時，這時也可以進行剪支，以便有條件把搜索集中到會帶來更大效果的其他路徑上，這就是中止對效益不大的一些子樹的搜索，以提高搜索效率。

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

不嚴格限制搜索的深度。當?shù)竭_深度限制時，如出現(xiàn)博弈格局有可能發(fā)生較大變化時，則應多搜索幾層，使格局進入較穩(wěn)定狀態(tài)后再中止，這樣可使倒推值計算的結果比較合理，避免考慮不充分產生的影響，這是等