1、2.3 博弈樹搜索博弈樹搜索n20世紀60年代，研制出的西洋跳棋和國際象棋的博弈程序達到了大師級的水平。n1958約翰麥卡錫提出博弈樹搜索算法n1997年，IBM公司研制的“深藍”國際象棋 程序，采用博弈樹搜索算法，該程序戰勝了國際象棋世界冠軍卡斯帕羅夫。1.1.概述概述正在與深藍下棋的卡斯帕羅夫n博弈問題特點：博弈問題特點：n雙人對弈，輪流走步。雙人對弈，輪流走步。n信息完備，雙方所得到的信息是一樣的。信息完備，雙方所得到的信息是一樣的。n零和，即對一方有利的棋，對另一方肯定零和，即對一方有利的棋，對另一方肯定是不利的，不存在對雙方均有利或無利的是不利的，不存在對雙方均有利或無利的棋。棋。1

2、.1.概述概述n博弈的特性博弈的特性兩個棋手交替地走棋兩個棋手交替地走棋 ；比賽的最終結果，是贏、輸和平局中的比賽的最終結果，是贏、輸和平局中的一種；一種；可用圖搜索技術進行，但效率很低；可用圖搜索技術進行，但效率很低；博弈的過程，是尋找置對手于必敗態的博弈的過程，是尋找置對手于必敗態的過程；過程；雙方都無法干預對方的選擇。雙方都無法干預對方的選擇。1.1.概述概述2.Grundy 2.Grundy 博弈博弈n下棋的雙方是對立的，命名博弈的雙方，一方為下棋的雙方是對立的，命名博弈的雙方，一方為“正方正方”，這類節點稱為，這類節點稱為“MAX”節點；另一方為節點；另一方為“反方反方”，這類節點稱

3、為，這類節點稱為“MIN”節點。正方和反節點。正方和反方是交替走步的，因此方是交替走步的，因此MAX節點和節點和MIN節點會交替節點會交替出現。出現。2.Grundy 2.Grundy 博弈博弈nGrundy博弈是一個分錢幣的游戲。有博弈是一個分錢幣的游戲。有 一堆數目為一堆數目為N的錢幣，由兩位選手輪流的錢幣，由兩位選手輪流進行分堆，要求每個選手每次只把其中進行分堆，要求每個選手每次只把其中某一堆分成數目不等的兩小堆。例如，某一堆分成數目不等的兩小堆。例如，選手甲把選手甲把N分成兩堆后，輪到選手乙就分成兩堆后，輪到選手乙就可以挑其中一堆來分，如此進行下去，可以挑其中一堆來分，如此進行下去，直

4、到有一位選手先無法把錢幣再分成不直到有一位選手先無法把錢幣再分成不相等的兩堆時就得認輸。相等的兩堆時就得認輸。2.Grundy 2.Grundy 博弈博弈n設初始狀態為設初始狀態為(7，MIN)，建立問題的狀，建立問題的狀態空間圖，圖中所有終結點均表示該選態空間圖，圖中所有終結點均表示該選手必輸的情況，取勝方的目標是設法使手必輸的情況，取勝方的目標是設法使棋局發展為結束在對方走步時的終結點棋局發展為結束在對方走步時的終結點上。上。MIN先走先走MAX必勝必勝2.Grundy 2.Grundy 博弈博弈n結點結點A是是MAX的搜索目標，而結點的搜索目標，而結點B，C則為則為MIN的搜索目標。的搜

5、索目標。2.Grundy 2.Grundy 博弈博弈搜索策略要考慮的問題是：搜索策略要考慮的問題是：n對對MIN走步后的每一個走步后的每一個MAX結點，必須證結點，必須證明明MAX對對MIN可能走的每一個棋局對弈后可能走的每一個棋局對弈后能獲勝，即能獲勝，即MAX必須考慮應付必須考慮應付MIN的所有的所有招法，這是一個與的含意，因此含有招法，這是一個與的含意，因此含有MAX符號的結點可看成與結點。符號的結點可看成與結點。 2.Grundy 2.Grundy 博弈博弈n對對MAX走步后的每一個走步后的每一個MIN結點，只須證結點，只須證明明MAX有一步能走贏就可以，即有一步能走贏就可以，即MAX

6、只要只要考慮能走出一步棋使考慮能走出一步棋使MIN無法招架就成，無法招架就成，因此含有因此含有MIN符號的結點可看成或結點。符號的結點可看成或結點。2.Grundy 2.Grundy 博弈博弈n對弈過程的搜索圖呈現出與或圖表示的形式。對弈過程的搜索圖呈現出與或圖表示的形式。n實現一種取勝的策略就是搜索一個解圖的問題，實現一種取勝的策略就是搜索一個解圖的問題，解圖就代表一種完整的博弈策略。解圖就代表一種完整的博弈策略。 2.Grundy 2.Grundy 博弈博弈中國象棋中國象棋n一盤棋平均走50步，總狀態數約為10的161次方。n假設1毫微秒走一步，約需10的145次方年。n結論：不可能窮舉。

7、3.極小極大搜索過程極小極大搜索過程n對各個局面進行評估對各個局面進行評估n評估的目的：對后面的狀態提前進行考慮，并評估的目的：對后面的狀態提前進行考慮，并且以各種狀態的評估值為基礎作出最好的走棋且以各種狀態的評估值為基礎作出最好的走棋選擇。選擇。 n評估的方法：用評價函數對棋局進行評估。贏評估的方法：用評價函數對棋局進行評估。贏的評估值設為的評估值設為+，輸的評估值設為，輸的評估值設為-，平局，平局的評估值設為的評估值設為0。 n評估的標準：由于下棋的雙方是對立的，只能評估的標準：由于下棋的雙方是對立的，只能選擇其中一方為評估的標準方。選擇其中一方為評估的標準方。3.3.極小極大搜索過程極小

8、極大搜索過程MAX節點和節點和MIN節點節點n命名博弈的雙方，一方為命名博弈的雙方，一方為“正方正方”，對每，對每個狀態的評估都是對應于該方的輸贏的。個狀態的評估都是對應于該方的輸贏的。例如，贏例如，贏2個，輸個，輸1個等，都是指正方的。個等，都是指正方的。正方每走一步，都在選擇使自己贏得更多正方每走一步，都在選擇使自己贏得更多的節點，因此這類節點稱為的節點，因此這類節點稱為“MAX”節點；節點；3.極小極大搜索過程極小極大搜索過程n另一方為另一方為“反方反方”，對每個狀態的評估，對每個狀態的評估都是對應于對手的輸贏的。例如，贏都是對應于對手的輸贏的。例如，贏2個，個，輸一個，其實是指自己輸輸

9、一個，其實是指自己輸2個，贏個，贏1個的。個的。反方每走一步，都在選擇使對手輸得更反方每走一步，都在選擇使對手輸得更多的節點，因此這類節點稱為多的節點，因此這類節點稱為“MIN”節節點。點。3.3.極小極大搜索過程極小極大搜索過程n由于正方和反方是交替走步的，因此由于正方和反方是交替走步的，因此MAX節點和節點和MIN節點會交替出現。節點會交替出現。3.極小極大搜索過程極小極大搜索過程n正方（正方（MAX節點）從所有子節點中，選節點）從所有子節點中，選取具有最大評估值的節點。取具有最大評估值的節點。n反方（反方（MIN節點）從其所有子節點中，節點）從其所有子節點中，選取具有最小評估值的節點。選

10、取具有最小評估值的節點。n反復進行這種選取，就可以得到雙方各反復進行這種選取，就可以得到雙方各個節點的評估值。這種確定棋步的方法，個節點的評估值。這種確定棋步的方法，稱為稱為極小極大搜索法極小極大搜索法。 3.極小極大搜索過程極小極大搜索過程3.極小極大搜索過程極小極大搜索過程5-333-3022-30-235 41-30 68 9-3MINMAX0MAXMIN3.極小極大搜索過程極小極大搜索過程015-333-3022-30-235 41-30 68 9-30-33-3-3-21-36-3031601MAXMINMAXMIN3.極小極大搜索過程極小極大搜索過程n 在九宮格棋盤上，兩位選手輪流

11、在棋盤上擺各自的在九宮格棋盤上，兩位選手輪流在棋盤上擺各自的 棋子棋子( (每次一枚每次一枚) )，誰先取得三線的結果就取勝。，誰先取得三線的結果就取勝。 設程序方設程序方MAXMAX的棋子用的棋子用( () )表示，表示， MAXMAX先走。先走。 對手對手MINMIN的棋子用的棋子用( (o o) )表示。表示。 例如：例如：3.極小極大搜索過程極小極大搜索過程MIN取勝取勝 估計函數估計函數 f(p)=(f(p)=(所有空格都放上所有空格都放上MAXMAX的的棋子之后，棋子之后，MAXMAX的三子成線數的三子成線數) )( (所有空所有空格都放上格都放上MINMIN的棋子之后，的棋子之后

12、，MINMIN的三子成的三子成線的總數線的總數) ) 若若P P是是MAXMAX獲勝的格局，則獲勝的格局，則f(p)=+ f(p)=+ ； 若若P P是是MINMIN獲勝的格局，則獲勝的格局，則f(p)f(p)- - 。3.極小極大搜索過程極小極大搜索過程3.極小極大搜索過程極小極大搜索過程估計函數值估計函數值 f(p)=6-4=2估計函數估計函數 f(p)=(f(p)=(所有空格都放上所有空格都放上MAXMAX的棋子之后，的棋子之后，MAXMAX的三子的三子成線成線( (行、列、對角行、列、對角) )數數) )( (所有空格都放上所有空格都放上MINMIN的棋子之后，的棋子之后，MINMIN

13、的三子成線的三子成線( (行、列、對角行、列、對角) )的總數的總數) )當前棋局當前棋局f(p)=23.極小極大搜索過程極小極大搜索過程一字棋第一階段搜索樹一字棋第一階段搜索樹3.極小極大搜索過程極小極大搜索過程一字棋第二階段搜索樹一字棋第二階段搜索樹3.極小極大搜索過程極小極大搜索過程一字棋第三階段搜索樹一字棋第三階段搜索樹 設有一個擺放三個子的設有一個擺放三個子的棋盤棋盤殘局，如下圖所示，殘局，如下圖所示，和和在結束前有三步棋可以走，而且設走第一步在結束前有三步棋可以走，而且設走第一步的是的是 。這時存在著三個空格。這時存在著三個空格A，B，C，用博弈樹，用博弈樹搜索算法判斷應該把棋子放

14、到哪一格內。搜索算法判斷應該把棋子放到哪一格內。 A AB BC C棋盤殘局舉例：棋盤殘局舉例：3.極小極大搜索過程極小極大搜索過程A AB BC CB BC CC CB B0A AC CC CA AA A B BB BA A-1- - 0- - 10- - - - 0MAX節點節點MIN節點節點終端節點終端節點3.極小極大搜索過程極小極大搜索過程 對于棋盤殘局中的對于棋盤殘局中的來說，最好的選擇，是將來說，最好的選擇，是將放放在在C C的位置上，這時可以導致平局局面。的位置上，這時可以導致平局局面。 3.極小極大搜索過程極小極大搜索過程n - - 剪支法的剪支法的引入引入 在極小極大法中，必

15、須求出所有終端節點在極小極大法中，必須求出所有終端節點的評估值，當預先考慮的棋步比較多時，計的評估值，當預先考慮的棋步比較多時，計算量會大大增加。為了提高搜索的效率，引算量會大大增加。為了提高搜索的效率，引入了通過對評估值的上下限進行估計，從而入了通過對評估值的上下限進行估計，從而減少需進行評估的節點范圍的減少需進行評估的節點范圍的 - 剪支法。剪支法。4. 4. - - 搜索過程搜索過程 作為正方出現的作為正方出現的MAX節點，假設它的節點，假設它的MIN子子節點有節點有N個，那么當它的第一個個，那么當它的第一個MIN子節點的評估子節點的評估值為值為 時，則對于其它的子節點，如果有高過時，則

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

17、則對于其它子節點，如果有低于時，則對于其它子節點，如果有低于 的，的，就取那個低于就取那個低于 的值作為該的值作為該MIN節點的評估值；節點的評估值；如果沒有，則該如果沒有，則該MIN節點的評估值取節點的評估值取 。 總之，該總之，該MIN節點的評估值不會高過節點的評估值不會高過 ，這，這個個 就稱為該就稱為該MIN節點的評估上限值。節點的評估上限值。4. - 搜索過程搜索過程n 剪支法剪支法 MAX節點節點MIN節點節點 = 剪支剪支ABCD4. - 搜索過程搜索過程 設設MAX節點的下限為節點的下限為 ，則其，則其所有的所有的MIN子節點子節點中，其評估值的中，其評估值的 上限小于等于上限

18、小于等于 的節點，其以下部分的節點，其以下部分的搜索都可以停止了，即對這部分節點進行了的搜索都可以停止了，即對這部分節點進行了 剪支。剪支。 設設MIN節點的上限為節點的上限為 ，則其，則其所有的所有的MAX子節點子節點中，其評估值的中，其評估值的 下限大于等于下限大于等于 的節點，其以下部分的節點，其以下部分的搜索都可以停止了，即對這部分節點進行了的搜索都可以停止了，即對這部分節點進行了 剪支。剪支。MAX節點節點MIN節點節點 = 剪支剪支ABCD4. - 搜索過程搜索過程n 剪支法剪支法 A B CDEFG H I J K L N O M4. - 搜索過程搜索過程MAX節點節點MAX節點

19、節點MIN節點節點終端節點終端節點35652164MAX節點節點(5, )35652164(6, )(2, )(- ,5,5)(- ,2,2)(5, )MIN節點節點終端節點終端節點 剪支剪支 剪支剪支A B CDEFG H I J K L N O MMAX節點節點4. - 搜索過程搜索過程一字棋第一階段一字棋第一階段 - 剪支方法剪支方法4. - 搜索過程搜索過程4. - 搜索過程搜索過程n極大節點的下界為極大節點的下界為 。n極小節點的上界為極小節點的上界為 。n剪支的條件：剪支的條件：n后輩節點的后輩節點的 值值祖先節點的祖先節點的 值時，值時， 剪支剪支n后輩節點的后輩節點的 值值祖先節點的祖先節點的 值時，值時， 剪支剪支n簡記為：簡記為：n極小極小極大，極大， 剪支剪支n極大極大極小，極小， 剪支剪支4. - 搜索過程搜索過程86-31453-3503-3022-30-2309-300-303305411-31661abcdefghijkmnMAXMINMAXMIN改進方法改進方法n 使用使用 - - 剪支技術，當不滿足剪支條件剪支技術，當不滿足剪支條件( (即即) )時或時或 值比值比 值大不了多少或極相值大不了多少或極相近時，這時也可以進行剪支，以便有條件近時，這時也可以進行剪支，以便有條件把搜索集中到會帶來更大效果的其他路徑把搜索集中到會帶來更大效果