Alpha-Beta Pruning (Fail-Hard/Soft) & AB-DUAL* & AB-SSS*
Minimax
進行雙人回合制完美資訊的零和遊戲時，Minimax 是一種相當直覺的搜尋方法。假設雙方都是理性的，我方會選擇對我方最有利的策略，對方則會選擇對我方來說最差的策略。
以下圖為例，圖上的數字都是對我方來說的報酬。正方形為我們的決策階段，我方會選利益最大化的策略，以下稱為 MAX node；圓形是對方的決策階段，對方會選擇讓我們利益最小化的策略（以下稱為 MIN node），因為這是零和遊戲，我方好對方就不好，我方虧對方就賺。
我們可以用反向回推法(backward induction)，從最下面往上推，結果是我方第一回合會選 A 策略，對方第二回合會選 C 策略，最後我方的報酬是 5。
缺點
假設一個遊戲每回合的可能策略數為 b (branching factor)，總共能下到 d (depth)個回合。那麼這顆樹需要長到 $O(b^d)$ 這麼大。對一些較複雜的遊戲，例如圍棋，較長完整顆樹以現有硬體設備幾乎是不可能，所以我們需要改善這個方法。
Alpha-Beta Pruning
簡單來說，Alpha/Beta Cut-off 就是利用邏輯推理的方式，把不可能的分支直接跳過，讓樹要長的地方變少。以下直接用例子來看。
Alpha Cut-off
Beta Cut-off
Deep Cut-off
前面的 Alpha/Beta Cut-off 舉的都是比較淺層的狀況，但它其實也能用在深層的地方。
Alpha-Beta 與上下界
可以簡單把 alpha-beta 想成搜尋過程中的上下界，把不可能落在上下界的分支直接剪掉。
Fail-Hard vs Fail-Soft
Fail-hard 的回傳值會限制在 alpha-beta 區間，而 fail-soft 則不會；此外，每個 parent 在 iterate 它的 children 時，fail-hard 會把動態值初始為 beta/alpha，而 fail-soft 會把動態值初始為 ∞/-∞。
比較
比較上面兩張圖紅字處，可以發現 fail-soft 的回傳值相較於 fail-hard 的回傳值較於貼近該狀態實際 minimax 的值。
假設 F1 為暴力解 Minimax 的結果，F2 為上上圖 fail-hard alpha-beta pruning 的結果，F3 為上圖 fail-soft alpha-beta pruning 的結果。
上上圖中紅字處表示：F2 < alpha → F1 < alpha。
上上圖和上圖中紅字處表示：F3 < alpha → F1 < F3 < alpha → F1 有更貼近的 bound。
如果使用 fail-hard 我們只能得知選 B 到達的那個 node 實際值 < alpha；fail-soft 則帶給我們更多的資訊，我們能知道實際值 < F3 < alpha。可以搭配 transposition table，把這些 state 的值上下界記起來供下次使用。
Null Window Search
Null window，也就是一個沒有空間的窗口（假設值只會是整數，中間沒有空隙），例如設 alpha 和 beta 分別為 998 和 999。如果用 fail-soft 的方式，null window 能拿來搜尋嗎？可以的！接下來的 AB-SSS 和 AB-DUAL 就是基於這樣的概念，並搭配 transposition table。接下來的內容用 AB-SSS* paper 裡的偽代碼和範例來說明。
A. Plaat, J. Schaeffer, W. Pijls, en A. de Bruin, “SSS = Alpha-Beta + TT”, arXiv [cs.AI]*, 05-Apr-2014. (https://arxiv.org/abs/1404.1517)
下圖為搭配 transposition table 的 alpha-beta search。變數名稱有疑惑的可以看原論文。也可以直接跳到下面看範例。
AB-SSS*
一開始設定 null window 為 (alpha, beta) = (∞-1,∞)。重覆從根節點做 alpha-beta search，每次會得到新的回傳值，用回傳值當新的 null window。例如回傳 100，window 就會變成 (99,100)，以此類推，直到 null window 重複即停止，此時這個值就是最後結果。
範例
原本的樹：
搜完第一次：
改用 (40,41) 當 window，搜完第二次：
改用 (35,36) 當 window，搜完第三次：
改用 (34,35) 當 window，搜完第四次：
又是 (34,35)，所以最終搜尋結果為 35。
AB-DUAL*
和 AB-SSS* 幾乎一樣，只是倒過來。一開始設負無限大，再逐漸變大。
