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