Minimax search 與 Alpha-beta 剪枝

Minimax search 是一種狀態搜尋演算法，在遊戲對局 AI 設計中時常會用到。如果你有玩五子棋、象棋、西洋棋等等的經驗，你在下棋的過程中是不是常在腦內有這樣的小劇場呢：「如果我動了這步，他大概會有『甲行為』或『乙行為』，如果他做了甲行為的話，那輪到我的時候我可以這樣；如果他做了乙行為的話，那輪到我的時候我可以那樣…」，為了讓自己能做出最正確的選擇，要不斷地在對方的角度和自己的角度切換來切換去，試想看看當下的情況有哪些做法可選、最好的做法是什麼。這個「小劇場」的邏輯在遊戲對局 AI 的設計上也非常有用，而這個演算法的名字就叫做 minimax search。

這篇將會介紹 minimax search，一步一步演示 minimax search 過程的脈絡，以及介紹一個可以減短搜尋過程的技法 — alpha-beta 剪枝。

Minimax search 的適用情境

minimax search 適用的情況必須符合三個條件：

• 1.遊戲是零和遊戲，我愈賺，對方一定愈虧；我愈虧，對方一定愈賺
• 2.遊戲資訊完全公開透明，沒有可隱瞞的
• 3.雙方都以最佳的策略行動，所以沒有任何「隨機、賭賭看」的成分，完全可以正確預測出對方的行動

舉例來說，像是排七(接龍)就不適合，因為看不到對手的牌，而且某些舉動可以利人利己或害人害己；像是大富翁也不適合，因為包含了擲骰子的隨機成分，完全無法預測對方，連自己的行為也無法掌握。

像是雙人橋牌的打牌階段就很適合了，己方多吃一墩時，對方就少吃一墩，反之亦然，而且雙方都知道對方有哪些牌，也大致上都會照著最佳策略行動；許多棋類遊戲例如五子棋或是西洋棋、象棋也很適合，因為一旦自己露出破綻時，對方一定不會手下留情。不過棋類比較麻煩的地方是只有輸贏、沒有分數，但搜尋時卻又難以直接搜到輸贏結果，頂多搜到「吃掉、被吃掉」等等，因此還必須要另外設計把「吃掉、被吃掉」量化成「分數」的 heuristic，才能讓 minimax search 派上用場。

Minimax search 簡單的例子

兩層搜尋

夜市裡有個攤販老闆擺出了兩個盒子，每個盒子裡面有兩張紙條，每張紙條上面寫著一個金額。你可以任意選擇一個盒子，再讓老闆從你選的盒子中挑一張紙條，成為你能夠贏得的獎金。你想盡量拿到最多的獎金，老闆想盡量讓你拿到最少的獎金，互相制衡之下，你能夠拿多少獎金呢？

如果我們挑了甲盒子，老闆一定會選 80 的紙條；如果我們挑了乙盒子，老闆一定會選 50 的紙條。因此，我們要挑甲盒子，而 80 就是我們能拿到的獎金！儘管乙盒子裡面有一萬元獎金，我們也不能挑乙盒子，因為我們知道老闆一定不會選擇一萬元獎金紙條，我們看得到卻吃不到。

如上圖，綠色是老闆的選擇，紅色是我們的選擇。我們也可以將選擇的過程用樹狀圖來表示：

三層搜尋

現在我們更改一下遊戲規則：我們可以從 A、B 兩個袋子中挑一個，老闆從我們挑的袋子中選一個盒子，我們再從老闆選的盒子中挑一張紙條。雙方制衡之下，我們能拿到多少獎金呢？

我們可以先預想看看，每個盒子如果被老闆挑到，我們可以選哪張紙條，如下圖紅圈處。哇，丙盒子有兩萬元呢，如果老闆挑到丙盒子就太好了！

然而老闆早就看透了我們的心思，知道我們會選哪張紙條，因此在甲和乙中，老闆會選擇甲盒子、在丙和丁中，老闆會選擇丁盒子，如下圖綠圈處。儘管丙盒子裡面的 0 元紙條很吸引老闆，他也不敢選，因為他知道一旦選了丙盒子，我們會把兩萬元獎金拿走。

最後，看透老闆心思的我們，知道若選擇了 A 袋子最終會拿到 100 元、若選擇了 B 袋子最終會拿到 70 元，因此當然是選擇 A 袋子囉！儘管 B 袋子裡面有吸引人的兩萬元獎項，我們也不可選，因為我們知道老闆不會選擇丙盒子。最終這個 100 元就是雙方都以最佳策略互相制衡後，我們能夠拿到的獎金。

Minimax search 實作

在剛才的範例中，我們計算搜尋樹上每個節點的數值時，順序是先從 leaf 開始，計算出所有 leaf 的爸爸們，再計算出爺爺們，最後才算 root 阿祖。不過這個順序只有在人腦手算時方便易懂，若要寫程式讓電腦搜尋的話，從 root 開始往下遞迴會更簡潔，而且如此才能有機會使用 alpha-beta 剪枝來減少搜尋的數量。

先來看看，從夜市老闆的角度，遞迴的程式長什麼樣子。對夜市老闆來說，他希望挑一個讓你拿到最少獎金的選項。首先，如果這個節點是 leaf，代表它是「一張紙條」，那根本沒什麼可選的，只得給出紙條上的金額；如果是個可做選擇的節點，那麼老闆要「每個都選給顧客看看」，看顧客能拿多少錢，並從中選擇金額最少的。

function vendor_get_min(node)
    
    // 如果是 leaf，直接回傳該節點的值
    if node is leaf then  
        return node's value
    
    // 每個都選給顧客看看，選出金額最少的
    minimum = ∞
    for each child of node do
        money = customer_get_max(child) // 遞迴呼叫客人的 function
        minimum = min(minimum, money)
    return minimum
    
end function

再來看看，從客人的角度，遞迴的程式長什麼樣子。對客人來說，我們希望挑一個能拿到最多獎金的選項。首先，如果這個節點是 leaf，代表它是「一張紙條」，那根本沒什麼可選的，只得接受紙條上的金額；如果是個可做選擇的節點，那麼我們要「每個都選給老闆看看」，看老闆能壓低成多少錢，並從中選擇金額最多的。

function customer_get_max(node)
    
    // 如果是 leaf，直接回傳該節點的值
    if node is leaf then  
        return node's value
    
    // 每個都選給老闆看看，選出金額最多的
    maximum = -∞
    for each child of node do
        money = vendor_get_min(child) // 遞迴呼叫老闆的 function
        maximum = max(maximum, money)
    return maximum
    
end function

只要讓兩個函數互相呼叫對方，一個選最大值，一個選最小值，並且設定好遞迴終止條件，就能成為正確的 minimax search 了！

還是要記得，這個演算法的複雜度是指數級的，假設搜尋總共有 $h$ 層，每次都有 $k$ 個分支，那麼複雜度就是 $O(k^h)$，代表總共有 $k^h$ 個 leaf 都要被拜訪到。不過，由於我們只想知道「最小」、「最大」值為何，導致在搜尋的過程中，某些節點的值變得完全不重要，反正不會被選到，這種情況就可以省下計算該節點的時間！雖然複雜度仍然是 $O(k^h)$，但實務上卻能省下不少運算資源。這個技法就是 alpha-beta search！

Alpha-beta 剪枝 - 簡單的例子

我們來實際演示一次，在 minimax 搜尋的過程中，每個節點的值是如何被計算出來，以及何時有機會「省下」搜尋。

根據我們的 DFS 遞迴式，我們計算樹上每個節點值的順序其實就是「post order traversal」，也就是對每個節點來說，當所有小孩的值都確定後，才能確定自己的值。

我們用類似剛才的例子來示範：

首先，最先能確定的是顧客在甲盒子中挑的值 100，是兩張紙條 (100, 80) 之中較大的那張。

這時來看看 A 節點。對於在「A袋子」裡挑「甲盒或乙盒」的老闆來說，他已知道「如果挑了甲盒子就要給顧客 100 元」，那麼這時他只在乎一件事：「選乙盒子可以比 100 元少嗎？」如果不能，他就直接選甲了。

因此我們從顧客的角度看看乙盒子可以拿多少錢。我們首先翻開 10000 元的紙條，又起了貪念，想知道另一張紙條會有比 10000 元還要高額的紙條嗎？但這時我們恢復理智，知道既然甲盒子是 100 元，那麼如果在乙盒子中選擇了高於 100 元的獎項，老闆就只會挑甲盒子。因此，另一張紙條是多少獎金一點也不重要了，低於 10000 的話顧客不會選，高於 100 的話老闆不會選。直接當成乙盒子是 10000 元就好，就算乙盒子裡有更大的值也沒關係！

這樣一來就能夠確定，若老闆拿到 A 袋子，他會選擇甲盒子的 100 元了。

而要從 A 袋子和 B 袋子中擇一的我們顧客，只在乎一件事：「選 B 袋子可以比 100 元多嗎？」如果不能，我們就直接選 A 了。

因此我們從老闆的角度看看 B 袋子可以拿多少錢。首先試試看丙盒子，老闆得知我方會在 50 元和 70 元之間選擇 70 元。

貪心的老闆想知道，如果選擇丁盒子，能不能出現比 70 元還要低的獎項？但這時他恢復理智，知道既然 A 袋子是 100 元，那麼如果在 B 袋子中選擇了低於 100 元的獎項，顧客就只會挑 A 袋子。因此，選擇丁盒子究竟會出現什麼獎項一點也不重要了，高於 70 的話老闆不願選，低於 100 的話顧客不會選。直接當成 B 袋子是 70 元就好！

這樣一來搜尋就完成了！顧客會在 A 袋子 100 元和 B 袋子 70 元之間選擇 100 元，這是和「腳踏實地把整棵樹搜完」一樣的結果，但是透過 alpha-beta 剪枝，搜尋的過程「捨棄」了 4 個節點！雖然不能降低時間複雜度，但實際省下來的運算時間還是很可觀的。

Alpha-beta 剪枝 - 規則整理

我們來統整一下，那些被「判定不重要」、「跳過」的節點，是依據什麼規則被跳過的？

上圖中藍色框處的節點 (15000 葉子) 是剛才被跳過的節點之一，他被跳過的原因是：

• 他的爺爺節點 (A 節點) 的大兒子 (甲節點) 是 100，而爺爺要取最小值，所以他要比 100 還要小，才會被爺爺選中
• 他的爸爸節點 (乙節點) 的大兒子 (10000 葉子) 是 10000，而爸爸要取最大值，所以他要比 10000 還要大，才會被爸爸選中
• 以上兩者的範圍是空集合，所以他絕對不可能「又被爸爸選上又被爺爺選上」

再看剛才的另一個例子：

上圖藍色框處的丁節點被跳過的原因是：

• 他的爺爺節點 (root) 的大兒子 (A節點) 是 100，而爺爺要取最大值，所以他要比 100 還要大，才會被爺爺選中
• 他的爸爸節點 (B節點) 的大兒子 (丙節點) 是 70，而爸爸要取最小值，所以他要比 70 還要小，才會被爸爸選中
• 以上兩者的範圍是空集合，所以他絕對不可能「又被爸爸選上又被爺爺選上」

如此可以發現，對每個節點來說，他的值若要有意義，就必須大於「該節點的每個『取最大值的祖先』的大兒子」，也必須小於「該節點的每個『取最小值的祖先』的大兒子」。就像上面的例子：「若爸爸想取最小值，那我必須比我的哥哥還要小；若爺爺想取最大值，那我必須比我的大伯還要大」。而一旦這個範圍成為空集合，我的值是什麼就完全不重要了，可以直接在我節點的頭上「剪枝」，捨棄我和我的所有子孫。

如上圖所示，對於藍色框的 $me$ 節點來說，它的值必須大於 $x, y, z$，才有可能被紅色祖先們選中，這個搜尋時的「下界」就稱為 alpha $\alpha$，亦即 $\alpha = max(x, y, z)$；另一方面，藍色框節點 $me$ 的值也必須小於 $w, v$，才有可能被綠色祖先們選中，這個搜尋時的「上界」就稱為 beta $\beta$，亦即 $\beta = min(w, v)$。至於樹上的其他節點，在此時計算上下界 $\alpha, \beta$ 時則不需用到。一旦出現 $\alpha \geq \beta$，我們就可以確定 $me$ 節點絕對不會被祖先選上，因此可以直接剪去 $me$ 節點以及他的所有子孫。

就算樹不是二元樹，也適用於這個規則。如下圖所示，我們可知對 $me$ 節點來說，下界 $\alpha = max(a, b, c, d, e)$ 以及上界 $\beta = min(p, q, r)$

至於那些空心黑圈的「祖先的弟弟」們值為何，則不會影響此時的上下界，因為它們屬於的分支本來就要在此分支搜尋結束後才會探索到 (想想 DFS 的探索順序)，幸運的話也許還能藉由此分支算出的值，來把將來要被搜尋的弟弟叔叔們「剪枝」掉。

也是因為這樣，搜尋過程中如何排序孩子們被搜索的順序就變得非常重要：對「要取最大值」的節點來說，應該要優先搜尋可能擁有較大值的子節點；對「要取最小值」的節點來說，也應該要優先搜尋可能擁有較小值的子節點。如此就會更有機會快速地讓上下界相併，把大部分還沒被搜尋的小兒子們剪枝掉，進而節省運算資源、加速搜尋時間。

不過，都還沒有搜尋，要怎麼知道哪個子節點「可能擁有較大值」、哪個子節點「可能擁有較小值」呢？在使用這個 minimax 搜尋演算法時，我們通常會再設計一個 heuristic 函數來「粗估」每個節點可能會擁有的值，或是「粗略」排序每個節點的孩子們誰先誰後。當這個 heuristic 函數愈可靠，就愈有機會因為早日合併上下界而大量剪枝減少搜尋時間。這個 heuristic 函數有千百種，取決於 AI 的作者怎麼設計，有時甚至只是人類常識。以西洋棋為例，假設當前的盤面我方有兩種選擇：「吃掉對方的皇后」、「吃掉對方的士兵」，根據常識，我們應該先搜尋「吃掉皇后」的選項，因為一旦搜完後發現它的值大到(或小到)能把上下界相併，就可以省去搜尋「吃掉士兵」的選項了。

Alpha-beta 剪枝 - 在 DFS 的過程維護 $\alpha$ 和 $\beta$

根據以上的結論，判斷樹上的某一個節點是否要被剪枝，可以藉由它的每個祖先的哥哥們來取得上界和下界，再判斷上下界是否圍成空集合並剪枝。在實作上，要取得「每個祖先的每個哥哥」的資訊看似很麻煩，實際上則可以在遞迴的過程中維護和傳遞。

我們來單獨看一個節點 $(P)$ 與它的孩子們 $(a, b, c, d)$ ，細究上下界維護的過程：

• 首先，父節點 $P$ 的下界為 alpha_P，上界為 beta_P。這是 $P$ 節點的所有祖先的所有哥哥造成的。
• 再來看 $P$ 的第一個兒子 $a$ 節點，它的所有的祖先哥哥都和爸爸的所有祖先哥哥相同，因此它的上下界也和爸爸的上下界相同，是 alpha_P, beta_P
• 再來看 $P$ 的第二個兒子 $b$ 節點，它的所有的祖先哥哥只比爸爸多一個 $a$ 節點，而因為它的爸爸要取最大值，因此 $b$ 節點的下界改為 max($a$, alpha_P)，上界不變
• $c$ 節點和 $d$ 節點也以此類推，如上圖所示。

由此可以發現，每個節點的上下界，都可以從前一個被拜訪的節點得知，因此，我們不需要真的對每一個節點都重新去找回所有祖先哥哥的資訊，而是可以在遞迴的過程中傳遞更新，就能讓每個節點都有正確的上下界。

我們來用剛才的夜市攤販挑獎金的例子來演示一次每個節點的上下界：

首先，從 root 開始，上下界分別為 $\infty$ 和 $-\infty$，隨著函數呼叫，拜訪 A 節點、甲節點和甲的大兒子時都是同樣這組上下界 $(-\infty, \infty)$。由於此範圍不為空集合，因此攤開甲的大兒子看看，發現值為 100。

再來，由於甲節點要取最大值，因此在得知大兒子的值是 100 後，就將下界更新為 100，再拜訪小兒子。由於 $(100, \infty)$ 範圍不為空，因此攤開小兒子看看，發現值為 80。

算出甲的所有子節點後，就可以知道甲的值為 100 了。再來，由於 A 節點要取最小值，因此在得知大兒子的值是 100 後，就將上界更新為 100，再拜訪小兒子。由於 $(-\infty, 100)$ 範圍不為空，因此要搜尋乙節點看看；而乙的大兒子也是同樣的上下界 $(-\infty, 100)$ 不為空，所以攤開大兒子看看，發現值為 10000。

由於乙節點要取最大值，因此在得知大兒子的值是 10000 後，就將下界更新為 10000，再拜訪小兒子。然而 $(10000, 100)$ 是空集合，因此小兒子是什麼值都無所謂，要在這裡「剪枝」小兒子。

這樣一來就搜尋完整個 A 子樹了，並且得知 A 節點的值為 100。再來，由於 root 要取最大值，因此在得知大兒子的值是 100 後，就將下界更新為 100，再拜訪小兒子。由於 $(100, \infty)$ 範圍不為空，因此要搜尋 B 節點看看；而 B 的大兒子丙和丙的大兒子也是同樣的上下界 $(100, \infty)$ 不為空，所以攤開大兒子看看，發現值為 50。

由於丙節點要取最大值，因此在得知大兒子的值是 50 後應該要更新下界，但原本的下界就是 100 了，$max(100, 50)=100$，所以搜尋小兒子時維持原本的範圍 $(100, \infty)$。範圍不為空，所以攤開小兒子看看，發現值為 70。

算出丙的所有子節點後，就可以知道丙的值為 70 了。再來，由於 B 節點要取最小值，因此在得知大兒子丙節點的值是 70 後，就將上界更新為 70，再拜訪小兒子丁節點。然而 $(100, 70)$ 是空集合，因此丁節點是什麼值都無所謂，要把丁節點「剪枝」掉。

如此一來就完成搜尋了，root 的值是 100。

Alpha-beta 剪枝 - 實作

了解了 alpha-beta 剪枝的原理後，來為 minimax search 加上 alpha-beta 剪枝吧！

這是「取最小值」的節點對應的函數，在呼叫函數時，我們多傳遞兩個參數 alpha 和 beta，並且在每次取得子節點的值時更新 beta：

function vendor_get_min(node, alpha, beta)
    
    // 如果是 leaf，直接回傳該節點的值
    if node is leaf then  
        return node's value
    
    // 每個都選給顧客看看，選出金額最少的
    minimum = ∞
    for each child of node do
        money = customer_get_max(child, alpha, beta) // 遞迴呼叫客人的 function
        minimum = min(minimum, money)
        beta = min(beta, money) // 用子節點的值更新上界 beta
        if alpha >= beta then // 如果範圍已是空集合，則不須再檢查剩下的小兒子們
            break
    return minimum
    
end function

「取最大值」的節點對應的函數也是同樣的道理，要在每次取得子節點的值時更新下界 alpha：

function customer_get_max(node, alpha, beta)
    
    // 如果是 leaf，直接回傳該節點的值
    if node is leaf then  
        return node's value
    
    // 每個都選給老闆看看，選出金額最多的
    maximum = -∞
    for each child of node do
        money = vendor_get_min(child, alpha, beta) // 遞迴呼叫老闆的 function
        maximum = max(maximum, money)
        alpha = max(alpha, money) // 用子節點的值更新下界 alpha
        if alpha >= beta then // 如果範圍已是空集合，則不須再檢查剩下的小兒子們
            break
    return maximum
    
end function

附錄：比較其他情境

最後，來比較一下 minimax search 以及其他常見的 game theory 情境以及適用的演算法。此篇介紹的 minimax search 是指數級的演算法，因為適用於 minimax search 的遊戲狀態種類的組合數量就是指數級，而搜尋的過程必須把所有可能都列舉出來，因此複雜度絕對逃不了指數級。也就是因為複雜度這麼要命，才會需要 alpha-beta 剪枝這個技法。

看看這個西洋棋盤，總共 $64$ 格，每一格有 $6+6+1$ 種可能，因此盤面總共約有 $13^{64}$ 種。或也可以算成總共有 $32$ 個棋子，每一個棋子的位置有 $64+1$ 種可能，因此盤面共約有 $65^{32}$。無論哪一種，都是令人頭痛的指數級。

不過，一想到「零和遊戲、雙方都最佳策略」這些關鍵字，你會不會聯想到經典問題「Nim game」以及 leetcode 經典 DP 題目「Stone game」系列呢？他們究竟有什麼特質，可以不用指數級的 minimax search，而是可以被 Polynomial time 的演算法解決呢？

先來討論較為直觀的 stone game 系列。

Stone game 系列之 VII：有 N 疊石頭，Alice 和 Bob 輪流除去最左或最右的整疊石頭，並得到值為「剩下所有石頭數量加總」的分數。目標是最大化「己方總分減對方總分」

雖然雙方每次都有兩種動作可以選，遊戲狀態組合看似會以 $2^N$ 增長，但實際上狀態們都會不斷重複出現，以 stone game VII 為例，「剩餘石頭堆的起始位置和結束位置」只會有 $N^2$ 種可能，因此只要利用 DP 把每一種對應的答案用表格存起來，就能把複雜度控制在 $N^2$。再看看適用 minimax search 的遊戲，儘管我們也能使出 DP 大法，把每個狀態對應的答案用表格存起來，但因為狀態的數量是指數級，表格的大小也會是指數級，所以還是避免不了指數級時間複雜度。

再來討論較為玄學的 Nim game 系列。

Nim game：有 N 疊石頭，Alice 和 Bob 輪流選取某一疊，並除去那一疊中任意數量的石頭，拿走最後一顆石頭的人獲勝

Nim game 的遊戲狀態數量其實是指數級的：每一疊石頭最多有 $k$ 個，總共有 $N$ 疊石頭的話，遊戲狀態就有 $(k+1)^N$ 種。

這種遊戲的特質為：只有輸贏沒有分數、而且不管輪到誰能做的動作都一樣、不會出現循環的盤面。因此盤面之間有這樣的遞迴規則：

• 1.不能動的盤面，為「必敗」盤面 (輪到誰誰輸)
• 2.可以動一步就成為必敗盤面的盤面，為「必勝」盤面 (輪到誰誰贏)
• 3.任何動一步都只能成為必勝盤面的盤面，為「必敗」盤面 (輪到誰誰輸)

不過經由神奇的數學研究，解 Nim game 不需要真的把所有狀態列出來搜尋，而是只要把每一疊石頭的數量 XOR 起來，若是 0 就是必敗盤面 (輪到誰誰輸)，否則就是必勝盤面 (輪到誰誰贏)！舉例來說，如果總共有三疊石頭，分別是「6顆、5顆、3顆」，那麼這時輪到誰，誰就輸定了，因為 $6⊕5⊕3=0$；如果總共有兩疊石頭，分別是「4顆、2顆」，那麼這時輪到誰，誰就贏定了，因為 $4⊕2 =6\neq0$！

你可以簡單驗證看看：

• 1.不能動的局面，亦即沒有任何石頭的局面，XOR 值為0
• 2.任何 XOR 不為 0 的局面，都可以藉由減少某一疊的石頭數，變成 XOR 為 0 的局面
• 3.任何 XOR 為 0 的局面，減少任何一疊的石頭數，都只能成為 XOR 不為 0 的局面

不只是 Nim game 本身，所有有上述特質的遊戲，都能轉換成等價的「N 疊石頭」，並用 XOR 算出必勝或必敗。這個神奇理論稱為「SG 定理」，而「轉換」的動作稱為「SG 函數」，如果有興趣的話，可以搜尋「SG 定理」相關的資料，也可以參考看看 我的 combinatorial game theory 投影片，裡面有簡單的 SG 定理證明以及一些範例。簡而言之，這類型的遊戲如果能在 polynomial time 的時間算出 SG 值，總體的時間複雜度就也會是 polynomial time，不須用指數級的時間搜尋。再看看適用於本篇演算法的遊戲，由於雙方能對盤面做的動作集合不相同 (例如只能動白子或只能動黑子、只能選袋子或只能選紙條)，所以無法用這個方法解決。