【正文】 索 。 ? 描述 αβ搜索 的論文最早發(fā)表于 20世紀 60年代（ Hart和Edwards,1961。Brudno,1963。Slagle,1963b)。 ? Slagle和 Dixon于 1969年在他們的玩 Kalah游戲的程序中第一次實現(xiàn)了完整的 αβ搜索 。 ? αβ搜索 也被用 John McCarthy的一個學生寫的 Kotok國際象棋程序中。 ? Knuth和 Moore(1975)提供了 αβ搜索 的歷史，及其正確性證明與時間復雜性分析。 ? 1982年 Pearl證明了 αβ搜索 在所有固定深度的博弈樹搜索算法中是漸進最優(yōu)的。 ? IBM研制的 “深藍 ”國際象棋程序采用的就是這種搜索算法，改程序戰(zhàn)勝了卡斯帕羅夫。 3/11/2023 76 某博弈問題示意圖 3/11/2023 77 圖 3/11/2023 78 圖 一字棋第一階段 α β 剪枝方法 3/11/2023 79 （ 1） α剪枝： 如果一個 MIN節(jié)點的 β值小于或等于它的某一個 MAX祖先節(jié)點的 α值，則剪枝發(fā)生在該 MIN節(jié)點之下： 中止這個 MIN節(jié)點以下的搜索過程。這個 MIN節(jié)點最終的倒推值就確定為這個 β值。 （ 2） β剪枝： 如果一個 MAX節(jié)點的 α值大于或者等于它的某一個 MIN祖先節(jié)點的 β值，則剪枝發(fā)生在該 MAX節(jié)點之下． 中止這個 MAX節(jié)點以下的搜索過程。 該 MAX節(jié)點的最終返回值可以置成它的 α值． 剪枝規(guī)則 3/11/2023 80 圖 αβ搜索過程的博弈樹 3/11/2023 81 （ 1）比較都是在極小節(jié)點和極大節(jié)點間進行的，極大節(jié)點和極大節(jié)點的比較，或者極小節(jié)點和極小節(jié)點間的比較是無意義的。 （ 2）在比較時注意是與 “祖先層 節(jié)點比較，不只是與父輩節(jié)點比較。當然，這里的 祖先層 節(jié)點，指的是那些已經(jīng)有了值的節(jié)點。 （ 3）當只有一個節(jié)點的 固定 以后，其值才能夠向其父節(jié)點傳遞。 （ 4） αβ剪枝方法搜索得到的最佳走步與極小極大方法得到的結(jié)果是一致的， αβ剪枝并沒有因為提高效率，而降低得到最佳走步的可能性。 （ 5）在實際搜索時，并不是先生成指定深度的搜索圖，再在搜索圖上進行剪枝。如果這樣，就失去了 αβ剪枝方法的意義。在實際程序?qū)崿F(xiàn)時，首先規(guī)定一個搜索深度，然后按照類似于深度優(yōu)先搜索的方式，生成節(jié)點。在節(jié)點的生成過程中，如果在某一個節(jié)點處發(fā)生了剪枝，則該節(jié)點其余未生成的節(jié)點就不再生成了。 進行 αβ剪枝注意的問題： 3/11/2023 82 若以最理想的情況進行搜索，即對 MIN節(jié)點先擴展最低估值的節(jié)點（若從左向右順序進行，則設節(jié)點估計值從左向右遞增排序）， MAX先擴展最高估值的節(jié)點（設估計值從左向右遞減排序），則當搜索樹深度為 D，分枝因數(shù)為B時，若不使用 αβ剪枝技術(shù)，搜索樹的端節(jié)點數(shù) BD；若使用 αβ剪枝技術(shù)．可以證明理想條件下生成的端節(jié)點數(shù)最少，有 ND=2BD/21（ D為偶數(shù)） ND=B(D+1)/2+B(D1)/21（ D為奇數(shù)） 比較后得出最佳 αβ搜索技術(shù)所生成深度為 D處的端節(jié)點數(shù)約等于不用 αβ搜索技術(shù)所生成深度為 D／ 2處的端節(jié)點數(shù)。 因此，在使用相同存儲空間的條件下， αβ過程能把搜索深度擴大一倍． αβ剪枝的效率 3/11/2023 83 以上介紹的各種博弈搜索技術(shù)可用于求解所提到的一些雙人博弈問題。但是這些方法還不能全面反映人們弈棋過程實際所使用的一切推理技術(shù)，也未涉及棋局的表示和啟發(fā)函數(shù)問題。例如一些高明的棋手，對棋局的表示有獨特的模式，他們往往記住的是一個可識別的模式集合，而不是單獨棋子的具體位置。此外有些博弈過程，在一個短時期內(nèi)短兵相接，進攻和防御的戰(zhàn)術(shù)變化劇烈，這些情況如何在搜索策略中加以考慮。還有基于極小極大過程的一些方法都設想對手總是走的最優(yōu)走步，即我方總應考慮最壞的情況，實際上再好的選手也會有失誤，如何利用失誤加強攻勢，也值得考慮。再一點就是選手的棋風問題?？傊嬲鉀Q具體的博弈搜索技術(shù)，有許多更深入的問題需要作進一步的研究和探討。 3/11/2023 84 1．用可分解產(chǎn)生式系統(tǒng)求解問題時，求解過程可歸結(jié)為對一個隱含的與 /或圖進行搜索。初始狀態(tài)對應于與或圖的根節(jié)點，規(guī)則對應于 k連接符，結(jié)束條件的數(shù)據(jù)庫對應于一組終止節(jié)點集合，搜索策略的任務就是找到從初始節(jié)點 s到一組終止節(jié)點集 N的一個解圖。解圖及其費用值可由遞歸定義給出。 2．若 s→N 集存在解圖，當 h（ n） ≤h*（ n）且 h（ n）滿足單調(diào)限制條件時， AO*算法一定能找到最佳解圖，即在這種情況下， AO*具有可采納性。 小結(jié) 3/11/2023 85 3．博弈問題可用產(chǎn)生式系統(tǒng)來描述，求解過程也是一個對與 /或圖進行搜索的問題。 針對雙人完備信息的博弈問題，通?？尚械膶嵱貌呗允撬阉鞅幌拗圃谝欢ǖ姆秶?，搜索的目標是確定一步好棋，等對手回手后，再繼續(xù)搜索。 MINIMAX就是按這種思想建立的過程，而 αβ過程是 MINIMAX過程的改進，并可提高效率。 3/11/2023 86 多人游戲中的最優(yōu)決策 許多流行的游戲允許多于兩個的參加者。讓我們來看看如何把極小極大思想推廣到多人游戲中。這在技術(shù)上看比較直接。 首先我們需要把每一個上的單一值替換成一個向量值。例如在一個三人 A,B,C的游戲中，每個節(jié)點都與一個向量 (vA,vB,vC)相關(guān)聯(lián)。對于終止狀態(tài)，這個向量給出了從每個人角度出發(fā)得到的狀態(tài)效用值（在二人零和游戲中，由于效用值總是正好相反，所以二維向量可以簡化為一個單一值）。簡單的實現(xiàn)這個方法是讓評估函數(shù)返回一個效用向量值。 3/11/2023 87 考慮在中的博弈樹上標為 X的節(jié)點。在這個狀態(tài)，輪到游戲者 C選擇做什么。兩種選擇導致的終止狀態(tài)的效用值向量分別為(vA=1,vB=2,vC=6)和 (vA=4,vB=2,vC=3)。由于 6大于 3，所以 C應該選擇第一種走法。 1， 2， 6 1， 2， 6 1， 2， 6 1， 5， 2 6， 1， 2 1， 5， 2 5， 4， 5 1， 2， 6 6， 1， 2 4， 2， 3 7， 4， 1 5， 1， 1 1， 5， 2 5， 4， 5 7， 7， 1 行棋方 A B C A 圖 有三個游戲者 (A,B,C)的博弈樹中的前三層，節(jié)點標有從每個游戲者出發(fā)的值。根節(jié)點標示了最佳步驟 3/11/2023 88 任何玩過諸如 Diplomacy（外交游戲）這樣的多人游戲的人很快會意識到這比雙人游戲要復雜得多。多人游戲通常會涉及在游戲者之間出現(xiàn)正式的聯(lián)盟的情況。隨著游戲的進行，聯(lián)盟也建立或者解散。我們?nèi)绾稳ダ斫膺@種行為呢？是否在多人游戲中對每一個游戲者來說聯(lián)盟是最優(yōu)策略的一個自然結(jié)果？看起來可能是這樣的。例如 A和B相對比較弱，而 C很強。那么對于 A和 B而言，他們一起進攻 C比等C逐個消滅它們要好，這樣通常是最優(yōu)的。如此，合作從純自私的行為中涌現(xiàn)出來。當然一旦 C在聯(lián)合攻擊下被削弱，聯(lián)盟就失去了價值，于是 A或 B就會破壞協(xié)議。某些情況下，外在的聯(lián)盟僅僅是把將要發(fā)生的具體化。在另一些情況下，違反盟約會損害社會聲譽，所以游戲者要在毀約得到直接利益和被認為不可信任而帶來的長期弊端之間進行權(quán)衡。 3/11/2023 89 如果游戲是非零和的，那么合作也可能發(fā)生在兩人游戲中。例如，假設有一個終止狀態(tài)的效用值向量是（ vA=1000,vB=1000)，并且 1000對于兩個游戲者都是最高的可能效用值。那么雙方的最優(yōu)策略就是做一切可能的招數(shù)來達到這個狀態(tài) —也就是說，雙方會自動合作來達到共同渴望的目標。 3/11/2023 90 產(chǎn)生式系統(tǒng)表示及其搜索方法基本內(nèi)容 ? 產(chǎn)生式系統(tǒng)概念 基本工作過程（ Procedure PRODUCTION） ? 產(chǎn)生式系統(tǒng)工作方式：正向、反向、雙向 ? 產(chǎn)生式系統(tǒng)控制策略 不可撤回式：爬山函數(shù) 試探式： 回溯： BACKTRACK、 BACKTRACK1 圖搜索： GRAPHSEARCH、 A算法、 A*算法 ? 特殊產(chǎn)生式系統(tǒng) 可交換、可分解 (Procedure SPLIT) ? 可分解產(chǎn)生式系統(tǒng)的搜索策略： 與或圖的啟發(fā)式搜索算法 AO* 博弈樹搜索 MINIMAX過程、 αβ過程 3/11/2023 91 演講完畢，謝謝觀看！