博弈樹的搜索雙人完備信息兩位選手對壘，輪流走步。這時每一方不僅知道對方過去已經走過的棋步，而且還能估計出對方未來可能的走步。對弈的結果是一方贏（另一方則輸），或者雙方和局。博弈問題可以用產生式系統的形式來描述。產生式系統構造知識型系統和建立認知模型時常用的知識表示的形式系統。一個產生式系統由下列3部分組成：一個總數據庫(globaldatabase)，它含有與具體任務有關的信息。一套規則，它對數據庫進行操作運算。每條規則由左右兩部分組成，左部鑒別規則的適用性或先決條件，右部描述規則應用時所完成的動作。應用規則來改變數據庫。一個控制策略，它確定應該采用哪一條適用規則，而且當數據庫的終止條件滿足時，就停止計算。例如中國象棋，綜合數據庫可規定為棋盤上棋子各種位置布局的一種描述，產生式規則是各類棋子合法走步的描述，目標則可規定為將（帥）被吃掉，規則作用于數據庫的結果便生成出博弈圖或博弈樹。Grundy博弈問題：有一堆數目為N的錢幣，由兩位選手輪流進行分堆，要求每個選手每次只把其中某一堆分成數目不等的兩小堆。例如選手甲把N分成兩堆后，輪到選手乙就可以挑其中一堆來分，如此進行下去直到有一位選手先無法把錢幣再分成不相等的兩堆時就得認輸。當初始錢幣數為7時的狀態空間圖，如下：MIN代表對方走，MAX代表我方走。對于簡單問題可以這樣找到取勝策略，但對于復雜問題就不可能了。下面討論：如何根據有限的狀態，得到較好走步的搜索方法。極小極大搜索方法極小極大搜索方法是博弈樹搜索的基本方法。首先假定，有一個評價函數可以對所有的棋局進行評估。當評價函數值大于0時，表示棋局對我方有利，對對方不利。當評價函數小于0時，表示棋局對我方不利，對對方有利。方法：當輪到我方走棋時，首先按照一定的搜索深度生成出給定深度d以內的所有狀態，計算所有葉節點的評價函數值。然后從d-1層節點開始逆向計算：對于我方要走的節點（用MAX標記，稱為極大節點）取其子節點中的最大值為該節點的值（因為我方總是選擇對我方有利的棋）。對于對方要走的節點（用MIN標記，稱為極小節點）取其子節點中的最小值為該節點的值（對方總是選擇對我方不利的棋）。一直到計算出根節點的值為止。獲得根節點取值的那一分枝，即為所選擇的最佳走步。因此，極小極大過程是一種假定對手每次回應都正確的情況下，如何從中找出對我方最有利的走步的搜索方法。值得注意的是，不管設定的搜索深度是多少層，經過一次搜索以后，只決定了我方一步棋的走法。等到對方回應一步棋之后，需要在新的棋局下重新進行搜索，來決定下一步棋如何走。靜態估計函數f(x)

一般規定有利于MAX的勢態，f(p)取正值，有利于MIN的勢態，f(p)取負值，勢均力敵的勢態，f(p)取0值。若f(p)＝＋∞，則表示MAX贏，若f(p)＝－∞，則表示MIN贏。下面的討論規定：頂節點深度d＝0，MAX代表程序方，MIN代表對手方，MAX先走。當用端節點的靜態估計函數f（p）求倒推值時，兩位選手應采取不同的策略，從下往上逐層交替使用極小和極大的選值方法，故稱極小極大過程。3×3棋盤的一字棋為例問題：在九宮格棋盤上，兩位選手輪流在棋盤上擺各自的棋子（每次一枚），誰先取得三子一線的結果就取勝。設程序方MAX的棋子用（×）表示，對手MIN的棋子用（○）表示，MAX先走。靜態估計函數f（p）規定如下：若p對任何一方來說都不是獲勝的格局，則f(p)＝（所有空格都放上MAX的棋子之后，MAX的三子成線（行、列、對角）的總數）

－（所有空格都放上MIN的棋子之后，MIN的三子成線（行、列、對角）的總數）若p是MAX獲勝的格局，則f(p)＝∞；若p是MIN獲勝的格局，則f(p)＝－∞。一字棋第一階段搜索樹

一字棋第二階段搜索樹

一字棋第三階段搜索樹

α-β搜索過程能否在搜索深度不變的情況下，利用已有的搜索信息減少生成的節點數呢？

MIN-MAX過程是把搜索樹的生成和格局估值這兩個過程分開來進行，即先生成全部搜索樹，然后再進行端節點靜態估值和倒推值計算，這顯然會導致低效率。實際上把生成和倒推估值結合起來進行，再根據一定的條件判定，有可能盡早修剪掉一些無用的分枝，同樣可獲得類似的效果，這就是α-β過程的基本思想。用一字棋的例子來說明α-β剪枝方法為了使生成和估值過程緊密結合，采用有界深度優先策略進行搜索，這樣當生成達到規定深度的節點時，就立即計算其靜態估值函數，而一旦某個非端節點有條件確定其倒推值時就立即計算賦值。一字棋第一階段α-β剪枝方法

（1）α剪枝：若任一極小值層節點的β值小于或等于它任一先輩極大值居節點的α值，即α（先輩層）≥β（后繼層），則可中止該極小值層中這個MIN節點以下的搜索過程。這個MIN節點最終的倒推值就確定為這個β值（2）β剪枝：若任一極大值層節點的α值大于或等于它任一先輩極小值層節點的β值，即α（后繼層）≥β（先輩層），則可以中止該極大值層中這個MAX節點以下的搜索過程。這個MAX節點的最終倒推值就確定為這個α值。通過對下圖的搜索，來說明α-β剪枝搜索過程

根據這些剪枝規則，很容易給出α-β算法描述，顯然剪枝后選得的最好優先走步，其結果與不剪枝的MINIMAX方法所得完全相同，因而α-β過程具有較高的效率。在一般條件下使用α-β搜索技術，在同樣的資源限制下，可以向前考慮更多的走步數，這樣選取當前的最好優先走步，將帶來更大的取勝優勢。其他改進方法（1）不嚴格限制搜索的深度，當到達深度限制時，如出現博弈格局有可能發生較大變化時（如出現兌子格局），則應多搜索幾層，使格局進入較穩定狀態后再中止，這樣可使倒推值計算的結果比較合理，避免考慮不充分產生的影響，這是等候狀態平穩后中止搜索的方法。

（2）當算法給出所選的走步后，不馬上停止搜索，而是在原先估計可能的路徑上再往前搜索幾步，再次檢驗會不會出現意外，這是一種增添輔助搜索的方法。（3）對某些博弈的開局階段和殘局階段，往往總結有一些固定的對弈模式，因此可以利用這些知識編好走步表，以便在開局和結局時使用查表法。只是在進入中盤階段后，再調用其他有效的搜索算法，來選擇最優的走步。需要