一、極大極小搜索（Minimax Algorithm）

在零和博弈（有完整信息的，確定的、輪流行動的，兩個參與者收益之和為0的博弈）中，雙方都希望自己獲勝，因此每一步都選擇對自己最有利，對對方最不利的做法。

假設我們是參與博弈的一方。我們用靜態(tài)估計函數(shù)$f(p)$來估計博弈雙方的態(tài)勢：

• 有利于我方的態(tài)勢：$f(p)>0$
• 有利于敵方的態(tài)勢：$f(p)<0$
• 雙方均衡的態(tài)勢：$f(p)=0$

顯然，我方希望$f(p)$最大化，敵方希望$f(p)$最小化。因此稱我方為Max方，敵方為Min方。

在Max方的角度，因為是我們自己做決策，我們可以選擇任意一種方案，所以我們只需選擇收益最大的方案，也就是說每種方案之間是“或”的關系。
而對于Min方而言，因為是敵方做決策，我們無法控制敵方選擇哪種策略，假設敵方足夠聰明，我們應該假設敵方選擇對他最有利的方案，也就是對我們最不利的方案、使我們收益最小的方案，所以對他而言每種方案之間是“與”的關系。

假設我們在進行動態(tài)博弈——你一步，我一步，且一方做完決策之后另一方知曉他所做的決策，那么我們可以把雙方的行動展開成一棵樹——博弈樹。
在博弈樹中，每個節(jié)點代表一種格局，每條邊代表Max方或Min方的一步操作。那些下一步該Max方走的節(jié)點稱為Max節(jié)點，下一步該Min方走的節(jié)點稱為Min節(jié)點。

博弈樹的特點：
(1) 博弈的初始狀態(tài)是初始節(jié)點（假如Max方為先手，則初始節(jié)點為Max節(jié)點）；
(2) Max節(jié)點是“或”節(jié)點，Min節(jié)點是“與”節(jié)點，這兩種節(jié)點逐層交替出現(xiàn)；
(3) 整個博弈過程始終站在一方（一般為Max方）的立場上。

博弈樹上有以下幾種節(jié)點：

• 端節(jié)點（葉節(jié)點）
  • 可解節(jié)點
  • 非可解節(jié)點
• 與節(jié)點（Min節(jié)點）
• 或節(jié)點（Max節(jié)點）

其中，端節(jié)點可能是可解節(jié)點或非可解節(jié)點。使自己一方（Max方）獲勝的為可解節(jié)點，使對方（Min）方獲勝的為非可解節(jié)點。

對于當前的格局，我們的目標是找到一個最有利于自己獲勝的策略。將當前棋局作為根節(jié)點，假設現(xiàn)在該Max方走了，Max方需要枚舉根節(jié)點的所有子節(jié)點，來判斷哪個子節(jié)點所對應的格局的靜態(tài)估計函數(shù)的數(shù)值，那么這個節(jié)點對于Max方就最有利，Max方的下一步應該將格局轉(zhuǎn)變?yōu)檫@個子節(jié)點的格局。

設$f(u)$是節(jié)點$u$所對應的格局的靜態(tài)估計函數(shù)數(shù)值（也稱效用值）。$f(u)$越大，節(jié)點$u$的格局對Max方越有利，對Min方越不利。顯然，博弈樹每層的節(jié)點類型的交替的——與節(jié)點、或節(jié)點、與節(jié)點、或節(jié)點、……，因為博弈雙方是輪流采取行動的。

現(xiàn)在，要獲得節(jié)點$u$的$f(u)$值，就需要進行極小極大搜索（min-max search）。極小極大搜索是指：在有限的深度范圍內(nèi)，使用深度優(yōu)先搜索（DFS）算法，利用遞歸回溯從可能的走法中選擇對自己最有利的走法，即讓自己的收益最大、對手的收益最小。

• 或節(jié)點（Max方）：該節(jié)點的效用值為所有子節(jié)點效用值的最大值。即：若節(jié)點$u$為或節(jié)點且$u$的子節(jié)點為$v_1,v_2,?,v_k$，則$f(u)=\underset{1\le i\le k}{\max }f(v_i)$。
• 與節(jié)點（Min方）：該節(jié)點的效用值為所有子節(jié)點效用值的最小值。即：若節(jié)點$u$為與節(jié)點且$u$的子節(jié)點為$v_1,v_2,?,v_k$，則$f(u)=\underset{1\le i\le k}{\min }f(v_i)$。
• 端節(jié)點：這類節(jié)點的效用值取決于具體問題。

由此我們可以歸納出極小極大搜索算法（Minimax Algorithm）的一般步驟：
(1) 利用廣度優(yōu)先搜索算法生成Max方當前狀態(tài)下可猜測的$k$步博弈樹；
(2) 定義靜態(tài)估計函數(shù)，計算端節(jié)點的效用值；
(3) 回溯評估：利用極大極小運算自下而上逐層推出各節(jié)點的效用值，其中在Max節(jié)點取最大值，在Min節(jié)點取最小值；
(4) 根據(jù)當前狀態(tài)子節(jié)點的效用值做出最優(yōu)決策，狀態(tài)轉(zhuǎn)移到子節(jié)點的狀態(tài)，對方變?yōu)镸ax方，回到(1)開始新的搜索。

P.S. 注意畫博弈數(shù)的時候，Max節(jié)點用方框表示，Min節(jié)點用圓表示，且Min節(jié)點的下方要畫一條弧線！

例 （井字棋）給定一個$3\times 3$的棋盤，Max方和Min方輪流走棋，每次僅能在空格擺一個自己的棋，自己的棋子三個連成一線即為獲勝。
規(guī)定估計函數(shù)$f(p)$為：

• 若格局$p$是Max方獲勝，則$f(p)=+\infty$；
• 若格局$p$是Min方獲勝，則$f(p)=?\infty$；
• 若雙方均未獲勝，則$f(p)=f_{\max }(p)?f_{\min }(p)$，其中
  • $f_{\max }(p)$表示所有空格全放上Max方的棋子后三子一線的總數(shù)，
  • $f_{\min }(p)$表示所有空格全放上Min方的棋子后三子一線的總數(shù)。
    
    那么，先手做出第一步?jīng)Q策的過程是這樣的：

搜索過程中將很多對稱的情況合并為一個情況，給出了$k=2$步博弈樹，并確定最優(yōu)策略為走中間。

極大極小搜索過程比較簡單，但當考慮的步數(shù)過多后就會導致博弈樹太大、搜索效率變低，需要進行優(yōu)化。

二、α-β剪枝（Alpha-Beta Pruning）

α-β剪枝是一種優(yōu)化方法，在博弈樹生成的過程中同時計算各節(jié)點的估計值及倒推值，通過對估值的上下限進行估計，減去沒有用的分支，減少搜索范圍，提高效率。

α-β剪枝的基本思想：

• “或”節(jié)點（Max方）：取當前子節(jié)點中效用值的極大值為該節(jié)點效用值的下界，稱為α（α≥該極大值），只有當下一個節(jié)點的值大于α才會被選擇
• “與”節(jié)點（Min方）：取當前子節(jié)點中效用值的極小值為該節(jié)點效用值的上界，稱為β（β≤該極小值），只有當下一個節(jié)點的值小于α才會被選擇

α：目前Max方可以搜索到的最好值，初始值為$?\infty$
β：目前Min方可以接受的最壞值，初始值為$+\infty$

注意：
設節(jié)點$u$為或節(jié)點，$u$的效用值為$f(u)$，$f(u)\ge \alpha$不一定成立。
同理，設$v$為與節(jié)點，$v$的效用值為$f(v)$，$f(v)\le \beta$也不一定成立。
α，β是中間量，它們的作用是排除對結(jié)果沒有影響的分支，不能決定最終節(jié)點的效用值。

或節(jié)點（Max方）α剪枝規(guī)則：
設當前節(jié)點為$u$，$u$是或節(jié)點，則$u$的子節(jié)點都是與節(jié)點或端節(jié)點，設為$v_1,v_2,?,v_k$。我們在掃描$v_1,v_2,?,v_k$的過程中，若發(fā)現(xiàn)$v_i$的β值小于等于其任何祖先節(jié)點的α值時，則對該節(jié)點以下的分支停止搜索，且$v_i$的最終倒推值就是其β值（可能與未加優(yōu)化的極大極小搜索的結(jié)果不同）。

與節(jié)點（Min方）β剪枝規(guī)則：
設當前節(jié)點為$v$，$v$是與節(jié)點，則$v$的子節(jié)點都是或節(jié)點或端節(jié)點，設為$u_1,u_2,?,u_k$。我們在掃描$u_1,u_2,?,u_k$的過程中，若發(fā)現(xiàn)$u_i$的α值大于等于其任何祖先節(jié)點的β值時，則對該節(jié)點以下的分支停止搜索，且$u_i$的最終倒推值就是其α值（可能與未加優(yōu)化的極大極小搜索的結(jié)果不同）。

用一個實際的例子來說明：如果你和一個人在下棋，現(xiàn)在輪到你走。現(xiàn)在你有兩種選擇：走“A”或者走“B”。如果走“A”，那么你的局勢會變好。走“B”也比較好，但是如果你走“B”的話，對方可以在兩步之內(nèi)獲勝，這對你是非常不利的。也就是說，你考慮到了走“B”的最壞結(jié)果，那么其他可能的結(jié)果就可以不考慮了（因為對手不傻，肯定會想方設法使你敗北），那么你相當于在博弈樹中剪掉了“B”的其他情況。最終，因為“A”至少不會讓你在兩步以內(nèi)輸棋，所以你選擇走“A”。（摘自維基百科）

核心思想是：如果存在一個比某一分支更好的走法，那么就不考察這一分支。

α-β剪枝的一個Python實現(xiàn)：

# encoding: GB2312

tree = [ # 博弈樹的結(jié)構(gòu)
    [
        [
            [4, 8, 6],
            [1, 9]
        ],
        [
            [5, 8],
            [-1, 2]
        ]
    ],
    [
        [
            [0, 3],
            [-6, 6]
        ],
        [
            [1],
            [0, 9, -7]
        ]
    ]
]

def is_terminal(node): # 判斷是否為端節(jié)點
    return isinstance(node, int)

infinity = int(1e10) # 無窮大

def alpha_beta(node, alpha, beta, ismax):
    # node: 當前節(jié)點
    # ismax: 若為True則當前節(jié)點是Max節(jié)點，否則為Min節(jié)點
    # 當node為Max節(jié)點時，alpha為當前節(jié)點的α，beta為父節(jié)點的β
    # 當node為Min節(jié)點時，alpha為父節(jié)點的α，beta為當前節(jié)點的β
    if is_terminal(node):
        return node # 若當前節(jié)點為端節(jié)點，直接返回其效用值
    if ismax:
        value = -infinity # 當前節(jié)點的效用值
        for child in node:
            value = max(value,
                alpha_beta(child, alpha, beta, False))
                # 當前節(jié)點的效用值是子節(jié)點效用值的最大值
            alpha = max(alpha, value)
            if value >= beta:
                # 這個子節(jié)點的效用值不小于beta，不可能被選擇
                break # 進行β剪枝
        return value
    else:
        value = +infinity
        for child in node:
            value = min(value,
                alpha_beta(child, alpha, beta, True))
            beta = min(beta, value)
            if value <= alpha:
                # 這個子節(jié)點的效用值不大于alpha，不可能被選擇
                break # alpha剪枝
        return value

print(alpha_beta(tree, -infinity, +infinity, True))

三、解題技巧

對于我們的期末考試而言，給你一棵樹，請問需要在哪里剪枝。其實我們并不需要搞那些α，β什么的，只需要簡單的邏輯就能算出來。

考慮下面的樹：

首先我們假設路線是$Q\to P\to J\to A\to R$?，F(xiàn)在考慮節(jié)點$A$。Min方不選擇去$R$而是選擇去其他端節(jié)點的條件是什么呢？是其他端節(jié)點的效用值小于$f(R)=4$。但是$f(S)=8$和$f(T)=6$都大于$4$，所以Min方還是選擇去$R$。所以 f ( A ) = min ? { 4 , 8 , 6 } = 4 f(A)=\min\{4,8,6\}=4 f(A)=min{4,8,6}=4。

現(xiàn)在考慮節(jié)點$J$。Max方選擇去$B$而不是去$A$的條件是什么呢？就是$f(B)>f(A)=4$。而 f ( B ) = min ? { f ( U ) , f ( V ) } f(B)=\min\{f(U),f(V)\} f(B)=min{f(U),f(V)}，所以轉(zhuǎn)化為 min ? { f ( U ) , f ( V ) } > 4 \min\{f(U),f(V)\}>4 min{f(U),f(V)}>4，即$$[f(U)>4]\wedge [f(V)>4]$$這是一個且的關系?，F(xiàn)在$f(U)=1$，$f(U)>4$已經(jīng)不滿足了，所以這個且的關系肯定不成立，不論$f(V)$是多少都不可能成立，所以Max方不會去$B$。因此要把$V$剪掉，$f(J)=f(A)=4$。

再考慮節(jié)點$P$。Min方去$K$而不是去$J$的條件是什么呢？就是$f(K)<f(J)=4$。而 f ( K ) = max ? { f ( C ) , f ( D ) } f(K)=\max\{f(C),f(D)\} f(K)=max{f(C),f(D)}，故轉(zhuǎn)化為$$[f(C)<4]\wedge [f(D)<4]$$又 f ( C ) = min ? { f ( W ) , f ( X ) } f(C)=\min\{f(W),f(X)\} f(C)=min{f(W),f(X)}， f ( D ) = min ? { f ( Y ) , f ( Z ) } f(D)=\min\{f(Y),f(Z)\} f(D)=min{f(Y),f(Z)}，又轉(zhuǎn)化為$$\{[f(W)<4]\vee [f(X)<4]\}\wedge \{[f(Y)<4]\vee [f(Z)<4]\}$$其中$f(W)=5$、$f(X)=8$，都不小于$4$，所以$[f(W)<4]\vee [f(X)<4]$不成立，那么$f(K)<4$也不可能成立，所以就沒必要考察$D$了，把$D$剪掉，并令$f(P)=4$。

再考慮節(jié)點$Q$。Max方不去$P$而是去$N$的節(jié)點是什么呢？是$f(N)>f(P)=4$。而 f ( N ) = min ? { f ( L ) , f ( M ) } f(N)=\min\{f(L),f(M)\} f(N)=min{f(L),f(M)}，故轉(zhuǎn)化為$$[f(L)>4]\wedge [f(M)>4]$$而 f ( L ) = max ? { f ( E ) , f ( F ) } f(L)=\max\{f(E),f(F)\} f(L)=max{f(E),f(F)}， f ( M ) = max ? { f ( G ) , f ( H ) } f(M)=\max\{f(G),f(H)\} f(M)=max{f(G),f(H)}，故轉(zhuǎn)化為$$\{[f(E)>4]\vee [f(F)>4]\}\wedge \{[f(G)>4]\vee [f(H)>4]\}$$又 f ( E ) = min ? { f ( Δ ) , f ( Ω ) } f(E)=\min\{f(\Delta),f(\Omega)\} f(E)=min{f(Δ),f(Ω)}， f ( F ) = min ? { f ( Ψ ) , f ( Σ ) } f(F)=\min\{f(\Psi),f(\Sigma)\} f(F)=min{f(Ψ),f(Σ)}，$f(G)=f(\Pi )$， f ( H ) = min ? { f ( Φ ) , f ( Γ ) , f ( Ξ ) } f(H)=\min\{f(\Phi),f(\Gamma),f(\Xi)\} f(H)=min{f(Φ),f(Γ),f(Ξ)}，故轉(zhuǎn)化為$$\{[f(\Delta )>4\wedge f(\Omega )>4]\vee [f(\Psi )>4\wedge f(\Sigma )>4]\}\wedge \{[f(\Pi )>4\vee f(\Phi )>4]\wedge [f(\Gamma )>4\vee f(\Xi )>4]\}$$觀察這個式子。這個式子成立，需要$\{[f(\Delta )>4\wedge f(\Omega )>4]\vee [f(\Psi )>4\wedge f(\Sigma )>4]\}$和$\{[f(\Pi )>4]\vee [f(\Phi )>4\wedge f(\Gamma )>4\wedge f(\Xi )>4]\}$都成立。而前者成立，只需使$[f(\Delta )>4\wedge f(\Omega )>4]$或$[f(\Psi )>4\wedge f(\Sigma )>4]$成立。
現(xiàn)在$f(\Delta )=0$不大于$4$，故$[f(\Delta )>4\wedge f(\Omega )>4]$不成立，不論$f(\Omega )$為何值，因此剪掉$\Omega$。而$f(\Psi )=?6$也不大與4，故$[f(\Psi )>4\wedge f(\Sigma )>4]$不成立，不論$f(\Sigma )$為和值，因此剪掉$\Sigma$。這意味著，$\{[f(\Delta )>4\wedge f(\Omega )>4]\vee [f(\Psi )>4\wedge f(\Sigma )>4]\}$不成立。那么$f(N)>f(P)$的條件就已經(jīng)不能滿足了，$N$這邊徹底沒戲了，所以把剩下沒去過的的都剪掉——也就是把$M$剪掉。最后，$f(Q)=f(P)=4$，也就是說在$Q$狀態(tài)下Max方選擇去$P$。

綜上，要剪掉的節(jié)點是$V,D,\Omega ,\Sigma ,M$。如下圖所示：
文章來源地址http://www.zghlxwxcb.cn/news/detail-415419.html

到了這里，關于【博弈論】極小極大搜索（Minimax Algorithm）與α-β剪枝（Alpha-Beta Pruning）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！