第5部分對抗搜索

第5部分對抗搜索本章內容5.1博弈5.2博弈中的優(yōu)化決策5.3-剪枝5.4不完美的實時決策5.5隨機博弈5.6部分可觀察的博弈5.7博弈程序發(fā)展現狀5.8其他途徑5.1博弈概述Grundy博弈概述在博弈問題中——比如說象棋——搜索是在博弈者雙方之間進行的。任何一方在搜索時，都必須要考慮對方可能要采用的走步。對于一個優(yōu)秀的博弈者來說，應考慮的不只是對方一步的走法，而是若干步的走法。這一過程一般來說是動態(tài)進行的。在考慮若干步走法以后，下了一步棋；而在對方走棋之后，還要再次考慮若干步走法，決定下一步的走法，而不是一勞永逸，搜索一次就決定了所有的走法。概述本章所講的博弈：主要指的是類似于象棋這樣的游戲問題。這類問題有以下一些特點：雙人對弈，對壘的雙方輪流走步。信息完備，對壘雙方所得到的信息是一樣的，不存在一方能看到，而另一方看不到的情況。零和。即對一方有利的棋，對另一方肯定是不利的，不存在對雙方均有利、或均無利的棋。對弈的結果是一方贏，而另一方輸，或者雙方和棋。概述雙人完備信息博弈：指兩位選手對壘，輪流走步，這時每一方不僅都知道對方過去已經走過的棋步，而且還能估計出對方未來可能的走步。對弈的結果是一方贏（另一方則輸），或者雙方和局。這類博弈的實例有：一字棋、余一棋、西洋跳棋、國際象棋、中國象棋、圍棋等。機遇性博弈：存在不可預測性的博弈，例如擲幣等。例如：西洋雙陸棋。Grundy博弈Grundy博弈是一個分錢幣的游戲。有一堆數目為N的錢幣，由兩位選手輪流進行分堆，要求每個選手每次只把其中某一堆分成數目不等的兩小堆。例如，選手甲把N分成兩堆后，輪到選手乙就可以挑其中一堆來分。如此進行下去，直到有一位選手先無法把錢幣再分成不相等的兩堆時就得認輸。對于這樣的簡單博弈問題，可以生成出它的狀態(tài)空間圖。這樣就有可能從狀態(tài)空間圖中找出取勝的策略。Grundy博弈當初始錢幣數為7時的狀態(tài)空間圖MIN代表對方走MAX代表我方走MAX存在完全取勝的策略Grundy博弈搜索策略要考慮的問題：對MIN走步后的每一個MAX節(jié)點，必須證明MAX對MIN可能走的每一個棋局對弈后能獲勝，即MAX必須考慮應付MIN的所有招法，這是一個與的含意。因此含有MAX符號的節(jié)點可看成與節(jié)點。對MAX走步后的每一個MIN節(jié)點，只須證明MAX有一步能走贏就可以，即MAX只要考慮能走出一步棋使MIN無法招架就成。因此含有MIN符號的節(jié)點可看成或節(jié)點。因此，對弈過程的搜索圖就呈現出與或圖表示的形式。Grundy博弈尋找MAX的取勝策略和求與或圖的解圖相對應。MAX要取勝，必須對所有與節(jié)點取勝，但只需對一個或節(jié)點取勝，這就是一個解圖。因此，尋找一種取勝的策略就是搜索一個解圖的問題，解圖就代表一種完整的博弈策略。對于Grundy這種較簡單的博弈，或者復雜博弈的殘局，可以用類似于與或圖的搜索技術求出解圖，解圖代表了從開局到終局任何階段上的弈法。顯然這對許多博弈問題是不可能實現的。例如，中國象棋，國際象棋和圍棋等。Grundy博弈對于復雜的博弈問題，因此即使用了強有力的啟發(fā)式搜索技術，也不可能使分枝壓到很少。因此，這種完全取勝策略（或和局）必須丟棄。應當把目標確定為尋找一步好棋，等對手回敬后再考慮尋找另一步好棋這種實際可行的實用策略。這種情況下每一步的結束條件可根據時間限制、存儲空間限制或深度限制等因素加以確定。搜索策略可采用寬度、深度或啟發(fā)式方法。一個階段搜索結束后，要從搜索樹中提取一個優(yōu)先考慮的"最好的"走步，這就是實用策略的基本點。本章內容5.1博弈5.2博弈中的優(yōu)化決策5.3-剪枝5.4不完美的實時決策5.5隨機博弈5.6部分可觀察的博弈5.7博弈程序發(fā)展現狀5.8其他途徑5.2博弈中的優(yōu)化決策極小極大值法多人游戲中的最優(yōu)決策極小極大搜索過程人類下棋的方法：實際上采用的是一種試探性的方法。首先假定走了一步棋，看對方會有那些應法，然后再根據對方的每一種應法，看我方是否有好的回應......這一過程一直進行下去，直到若干步以后，找到了一個滿意的走法為止。初學者可能只能看一、兩個回合，而高手則可以看幾個，甚至十幾個回合。極小極大搜索方法：模擬的就是人的這樣一種思維過程。極小極大搜索過程極小極大搜索策略是考慮雙方對弈若干步之后，從可能的走步中選一步相對好棋的著法來走，即在有限的搜索深度范圍內進行求解。定義一個靜態(tài)估計函數f，以便對棋局的勢態(tài)（節(jié)點）作出優(yōu)劣估值。這個函數可根據勢態(tài)優(yōu)劣特征來定義（主要用于對端節(jié)點的“價值”進行度量）。一般規(guī)定：有利于MAX的勢態(tài)，f（p）取正值；有利于MIN的勢態(tài)，f（p）取負值；勢均力敵的勢態(tài)，f（p）取0值。若f（p）＝＋∞，則表示MAX贏，若f（p）＝－∞，則表示MIN贏。極小極大搜索過程注意：不管設定的搜索深度是多少層，經過一次搜索以后，只決定了我方一步棋的走法。等到對方回應一步棋之后，需要在新的棋局下重新進行搜索，來決定下一步棋如何走。極小極大過程是一種假定對手每次回應都正確的情況下，如何從中找出對我方最有利的走步的搜索方法。極小極大搜索過程規(guī)定：頂節(jié)點深度d＝0，MAX代表程序方，MIN代表對手方。MAX先走。例：一個考慮2步棋的例子。極小極大搜索過程規(guī)定：頂節(jié)點深度d＝0，MAX代表程序方，MIN代表對手方。MAX先走。例：一個考慮2步棋的例子。端節(jié)點給出的數字是用靜態(tài)估計函數f（p）計算得到。過程MINIMAX①T:＝（s，MAX），OPEN:＝（s），CLOSED:＝（）；開始時樹由初始節(jié)點構成，OPEN表只含有s。②LOOP1:IFOPEN＝（）THENGOLOOP2；③n:＝FIRST(OPEN)，REMOVE(n，OPEN)，ADD(n，CLOSED)；④IFn可直接判定為贏、輸或平局

THENf（n）:＝∞∨－∞∨0，GOLOOP1

ELSEEXPAND（n）→{ni}，ADD（{ni}，T）

IFd（ni）＜kTHENADD（{ni}，OPEN），GOLOOP1

ELSE計算f（ni

），GOLOOP1；ni達到深度k，計算各端節(jié)點f值。⑤LOOP2：IFCLOSED＝NILTHENGOLOOP3

ELSEnp:＝FIRST（CLOSED）；⑥IF（np∈MAX）∧（f（nci∈MIN）有值）

THENf（np

）:＝max{f（nci）}，REMOVE(np，CLOSED)；若MAX所有子節(jié)點均有值，則該MAX取其極大值。

IF（np∈MIN）∧（f（nci∈MAX）有值）

THENf（np

）:＝min{f（nci）}，REMOVE(np

，CLOSED)；若MIN所有子節(jié)點均有值，則該MIN取其極小值。⑦GOLOOP2；⑧LOOP3：IFf（s）≠NILTHENEXIT(END∨M(Move，T))；s有值，則結束或標記走步。過程MINIMAX該算法分兩個階段進行:第一階段②～④：用寬度優(yōu)先法生成規(guī)定深度的全部博弈樹，然后對其所有端節(jié)點計算其靜態(tài)估計函數值。第二階段⑥～⑧：從底向上逐級求非端節(jié)點的倒推估計值，直到求出初始節(jié)點s的倒推值f（s）為止，此時等對手響應走步后，再以當前的狀態(tài)作為起始狀態(tài)s，重復調用該過程。例：3×3棋盤的一字棋3×3棋盤的一字棋：九宮格棋盤上，兩位選手輪流在棋盤上擺各自的棋子（每次一枚），誰先取得三子一線的結果就取勝。假設：程序方MAX的棋子用（×）表示；對手MIN的棋子用（○）表示；MAX先走。例：3×3棋盤的一字棋靜態(tài)估計函數f（p）規(guī)定如下：若p是MAX獲勝的格局，則f（p）＝∞；若p是MIN獲勝的格局，則f（p）＝－∞；若p對任何一方來說都不是獲勝的格局，則f（p）＝（所有空格都放上MAX的棋子之后，MAX的三子成線（行、列、對角）的總數－（所有空格都放上MIN的棋子之后，MIN的三子成線（行、列、對角）的總數）。例、當p的格局如下時，則可得f（p）＝6－4＝2。在搜索過程中，具有對稱性的棋局認為是同一棋局，可以大大減少搜索空間。

對稱棋局的例子例：3×3棋盤的一字棋例：3×3棋盤的一字棋假定考慮走兩步的搜索過程，利用棋盤對稱性的條件，則第一次調用算法產生的搜索樹為：例：3×3棋盤的一字棋假設MAX走完第一步后，MAX的對手是在×之上的格子下棋子，這時MAX在新格局下調用算法，第二次產生的搜索樹為：例：3×3棋盤的一字棋類似地，第三次的搜索樹為：至此MAX走完最好的走步后，不論MIN怎么走，都無法挽回敗局，因此只好認輸了。博弈中的優(yōu)化決策極小極大值法多人游戲中的最優(yōu)決策多人游戲中的最優(yōu)決策許多流行的游戲允許多于兩個的參加者。如何把極小極大思想推廣到多人游戲中？在兩人的零和游戲中，由于效用值正好相反，所以二維向量可以簡化為一個單一值。每個節(jié)點上的單一評估值要替換成一個向量。例、一個有三個人A,B和C的游戲中，每個節(jié)點都與一個向量<vA,vB,vC>相關聯。對于終止狀態(tài)，該向量給出了從每個人的角度出發(fā)得到的狀態(tài)效用值。多人游戲中的最優(yōu)決策一般來講，節(jié)點n的回傳值是該游戲者在節(jié)點n選擇的效用值最高的后繼者的效用值向量。多人游戲中的最優(yōu)決策多人游戲通常會涉及在游戲者之間出現正式或者非正式聯盟的情況。隨著游戲的進行，聯盟會建立或解散。在多人游戲中，對每個游戲者來說，聯盟是否是最優(yōu)策略的一個自然結果？違反盟約會損害社會聲譽。游戲者要在毀約得到的直接利益和被認為不可信任帶來的長期弊端之間尋求平衡。本章內容5.1博弈5.2博弈中的優(yōu)化決策5.3-剪枝5.4不完美的實時決策5.5隨機博弈5.6部分可觀察的博弈5.7博弈程序發(fā)展現狀5.8其他途徑-剪枝的基本思想在極小極大搜索方法中，由于要生成指定深度以內的所有節(jié)點，其節(jié)點數將隨著搜索深度的增加成指數增長。這極大地限制了極小極大搜索方法的使用。能否在搜索深度不變的情況下，利用已有的搜索信息減少生成的節(jié)點數呢？-剪枝的基本思想設某博弈問題如下圖所示：-剪枝的基本思想α-β搜索過程的基本思想：把博弈樹生成和倒推估值結合起來進行，再根據一定的條件判定，有可能盡早修剪掉一些無用的分枝。為了使生成和估值過程緊密結合，采用有界深度優(yōu)先策略進行搜索。當生成達到規(guī)定深度的節(jié)點時，就立即計算其靜態(tài)估值函數，而一旦某個非端節(jié)點有條件確定其倒推值時就立即計算賦值。-剪枝的基本思想極大值層的下界值稱為α極小值層的上界值稱為βα-β搜索過程的剪枝規(guī)則α剪枝：若任一極小值層節(jié)點的β值小于或等于它任一先輩極大值層節(jié)點的α值，即α（先輩層）≥β（后繼層），則可中止該極小值層中這個MIN節(jié)點以下的搜索過程。這個MIN節(jié)點最終的倒推值就確定為這個β值。β剪枝：若任一極大值層節(jié)點的α值大于或等于它任一先輩極小值層節(jié)點的β值，即α（后繼層）≥β（先輩層），則可以中止該極大值層中這個MAX節(jié)點以下的搜索過程。這個MAX節(jié)點的最終倒推值就確定為這個α值。根據這些剪枝規(guī)則，很容易給出α-β算法描述，顯然剪枝后選得的最好優(yōu)先走步，其結果與不剪枝的MINIMAX方法所得完全相同，因而α-β過程具有較高的效率。α-β搜索過程的博弈樹α-β剪枝舉例約定：在搜索過程中，節(jié)點的生成次序是從上到下，從左到右進行的。圖中帶圈的數字，表示節(jié)點的計算次序。在敘述時，為了表達上的方便，該序號也同時表示節(jié)點。當一個節(jié)點有兩個以上的序號時，不同的序號，表示的是同一個節(jié)點在不同次序下計算的結果。α-β搜索過程的博弈樹α-β剪枝舉例-搜索過程在進行α-β剪枝時，應注意以下幾個問題：比較都是在極小節(jié)點和極大節(jié)點間進行的；極大節(jié)點和極大節(jié)點的比較，或者極小節(jié)點和極小節(jié)點間的比較是無意義的。在比較時注意是與“先輩層”節(jié)點比較，不只是與父輩節(jié)點比較。當然，這里的“先輩層”節(jié)點，指的是那些已經有了值的節(jié)點。只有一個節(jié)點的值“固定”以后，其值才能夠向其父節(jié)點傳遞。-搜索過程在進行α-β剪枝時，應注意以下幾個問題：α-β剪枝方法搜索得到的最佳走步與極小極大方法得到的結果是一致的，α-β剪枝并沒有因為提高效率，而降低得到最佳走步的可能性。在實際搜索時，并不是先生成指定深度的搜索圖，再在搜索圖上進行剪枝。如果這樣，就失去了α-β剪枝方法的意義。在實際程序實現時，首先規(guī)定一個搜索深度，然后按照類似于深度優(yōu)先搜索的方式，生成節(jié)點。在節(jié)點的生成過程中，如果在某一個節(jié)點處發(fā)生了剪枝，則該節(jié)點其余未生成的節(jié)點就不再生成了。剪枝的效率問題若以最理想的情況進行搜索，即對MIN節(jié)點先擴展最低估值的節(jié)點（若從左向右順序進行，則設節(jié)點估計值從左向右遞增排序），MAX先擴展最高估值的節(jié)點（設估計值從左向右遞減排序），則當搜索樹深度為D，分枝因數為B時，若不使用α-β剪枝技術，搜索樹的端節(jié)點數為：若使用α-β剪枝技術，可以證明理想條件下生成的端節(jié)點數最少，有剪枝的效率問題比較后得出最佳α-β搜索技術所生成深度為D處的端節(jié)點數約等于不用α-β搜索技術所生成深度為D／2處的端節(jié)點數。這就是說，在一般條件下使用α-β搜索技術，在同樣的資源限制下，可以向前考慮更多的走步數，這樣選取當前的最好優(yōu)先走步，將帶來更大的取勝優(yōu)勢。其他改進方法使用α-β剪枝技術，當不滿足剪枝條件（即α不大于等于β）時，若β值比α值大不了多少或極相近，這時也可以進行剪枝。以便有條件把搜索集中到會帶來更大效果的其他路徑上，這就是中止對效益不大的一些子樹的搜索，以提高搜索效率。不嚴格限制搜索的深度，當到達深度限制時，如出現博弈格局有可能發(fā)生較大變化時（如出現兌子格局），則應多搜索幾層，使格局進入較穩(wěn)定狀態(tài)后再中止，這樣可使倒推值計算的結果比較合理，避免考慮不充分產生的影響，這是等候狀態(tài)平穩(wěn)后中止搜索的方法。其他改進方法當算法給出所選的走步后，不馬上停止搜索，而是在原先估計可能的路徑上再往前搜索幾步，再次檢驗會不會出現意外，這是一種增添輔助搜索的方法。對某些博弈的開局階段和殘局階段，往往總結有一些固定的對弈模式。因此，可以利用這些知識編好走步表，以便在開局和結局時使用查表法。只是在進入中盤階段后，再調用其他有效的搜索算法，來選擇最優(yōu)的走步。其他改進方法以上這些方法還不能全面反映人們弈棋過程實際所使用的一切推理技術，也未涉及棋局的表示和啟發(fā)函數問題。高明的棋手對棋局的表示有獨特的模式。博弈過程中，若在一個短時期內短兵相接，進攻和防御的戰(zhàn)術變化劇烈，這些情況如何在搜索策略中加以考慮？基于極小極大過程的一些方法都設想對手走的總是最優(yōu)走步，即我方總應考慮最壞的情況。實際上，再好的選手也會有失誤，如何利用失誤加強攻勢，也值得考慮。總之要真正解決具體的博弈搜索技術，有許多更深入的問題需要作進一步的研究和探討。本章內容5.1博弈5.2博弈中的優(yōu)化決策5.3-剪枝5.4不完美的實時決策5.5隨機博弈5.6部分可觀察的博弈5.7博弈程序發(fā)展現狀5.8其他途徑不完整的實時決策MINIMAX或–剪枝算法理想情況：算法一直搜索，直到至少一部分空間到達終止狀態(tài)，從而對端節(jié)點做出準確評價。這樣的搜索不現實。實用方法：用可以估計棋局效用的啟發(fā)式評價函數評價非終止節(jié)點。用可以決策什么時候運用評價函數的截斷測試取代終止測試。評價函數評價函數的設計：應該以和真正的效用函數同樣的方式對終止狀態(tài)進行排序。效用函數（又稱目標函數或者收益函數）：對終止狀態(tài)給出一個數值。例如，在國際象棋中，結果是贏、輸或平局，分別賦予＋1，－1或0。評價函數的計算不能花費太多的時間！對于非終止狀態(tài)，評價函數應該和取勝的實際機