Alpha-Beta 剪枝

此頁面將簡要介紹 minimax 算法和 \(\alpha-\beta\) 剪枝。

Minimax 算法

定義

Minimax 算法又叫極小化極大算法，是一種找出失敗的最大可能性中的最小值的算法。¹

在局面確定的雙人對弈裏，常進行對抗搜索，構建一棵每個節點都為一個確定狀態的搜索樹。奇數層為己方先手，偶數層為對方先手。搜索樹上每個葉子節點都會被賦予一個估值，估值越大代表我方贏面越大。我方追求更大的贏面，而對方會設法降低我方的贏面，體現在搜索樹上就是，奇數層節點（我方節點）總是會選擇贏面最大的子節點狀態，而偶數層（對方節點）總是會選擇我方贏面最小的的子節點狀態。

過程

Minimax 算法的整個過程，會從上到下遍歷搜索樹，回溯時利用子樹信息更新答案，最後得到根節點的值，意義就是我方在雙方都採取最優策略下能獲得的最大分數。

解釋

來看一個簡單的例子。

稱我方為 MAX，對方為 MIN，圖示如下：

例如，對於如下的局勢，假設從左往右搜索，根節點的數值為我方贏面：

我方應選擇中間的路線。因為，如果選擇左邊的路線，最差的贏面是 3；如果選擇中間的路線，最差的贏面是 15；如果選擇右邊的路線，最差的贏面是 1。雖然選擇右邊的路線可能有 22 的贏面，但對方也可能使我方只有 1 的贏面，假設對方會選擇使得我方贏面最小的方向走，那麼經過權衡，顯然選擇中間的路線更為穩妥。

實際上，在看右邊的路線時，當發現贏面可能為 1 就不必再去看贏面為 12、20、22 的分支了，因為已經可以確定右邊的路線不是最好的。

樸素的 Minimax 算法常常需要構建一棵龐大的搜索樹，時間和空間複雜度都將不能承受。而 \(\alpha-\beta\) 剪枝就是利用搜索樹每個節點取值的上下界來對 Minimax 進行剪枝優化的一種方法。

需要注意的是，對於不同的問題，搜索樹每個節點上的值有着不同的含義，它可以是估值、分數、贏的概率等等，為方便起見，我們下面統一用分數來稱呼。

alpha-beta 剪枝

過程

對於如下的局勢，假設從左往右搜索：

若已知某節點的所有子節點的分數，則可以算出該節點的分數：對於 MAX 節點，取最大分數；對於 MIN 節點，取最小分數。

若已知某節點的部分子節點的分數，雖然不能算出該節點的分數，但可以算出該節點的分數的取值範圍。同時，利用該節點的分數的取值範圍，在搜素其子節點時，如果已經確定沒有更好的走法，就不必再搜索剩餘的子節點了。

記 \(\mathit{v}\) 為節點的分數，且 \(\alpha \leq v \leq \beta\)，即 \(\alpha\) 為最大下界，\(\beta\) 為最小上界。當 \(\alpha \geq \beta\) 時，該節點剩餘的分支就不必繼續搜索了（也就是可以進行剪枝了）。注意，當 \(\alpha = \beta\) 時，也可以剪枝，這是因為不會有更好的結果了，但可能有更差的結果。

初始化時，令 \(\alpha = -\infty, \beta = +\infty\)，也就是 \(-\infty \leq v \leq +\infty\)。到節點 A 時，由於左子節點的分數為 3，而節點 A 是 MIN 節點，試圖找分數小的走法，於是將 \(\beta\) 值修改為 3，這是因為 3 小於當前的 \(\beta\) 值（\(\beta = +\infty\)）。然後節點 A 的右子節點的分數為 17，此時不修改節點 A 的 \(\beta\) 值，這是因為 17 大於當前的 \(\beta\) 值（\(\beta = 3\)）。之後，節點 A 的所有子節點搜索完畢，即可計算出節點 A 的分數為 3。

節點 A 是節點 B 的子節點，計算出節點 A 的分數後，可以更新節點 B 的分數範圍。由於節點 B 是 MAX 節點，試圖找分數大的走法，於是將 \(\alpha\) 值修改為 3，這是因為 3 大於當前的 \(\alpha\) 值（\(\alpha = -\infty\)）。之後搜索節點 B 的右子節點 C，並將節點 B 的 \(\alpha\) 和 \(\beta\) 值傳遞給節點 C。

對於節點 C，由於左子節點的分數為 2，而節點 C 是 MIN 節點，於是將 \(\beta\) 值修改為 2。此時 \(\alpha \geq \beta\)，故節點 C 的剩餘子節點就不必搜索了，因為可以確定，通過節點 C 並沒有更好的走法。然後，節點 C 是 MIN 節點，將節點 C 的分數設為 \(\beta\)，也就是 2。由於節點 B 的所有子節點搜索完畢，即可計算出節點 B 的分數為 3。

計算出節點 B 的分數後，節點 B 是節點 D 的一個子節點，故可以更新節點 D 的分數範圍。由於節點 D 是 MIN 節點，於是將 \(\beta\) 值修改為 3。然後節點 D 將 \(\alpha\) 和 \(\beta\) 值傳遞給節點 E，節點 E 又傳遞給節點 F。對於節點 F，它只有一個分數為 15 的子節點，由於 15 大於當前的 \(\beta\) 值，而節點 F 為 MIN 節點，所以不更新其 \(\beta\) 值，然後可以計算出節點 F 的分數為 15。

計算出節點 F 的分數後，節點 F 是節點 E 的一個子節點，故可以更新節點 E 的分數範圍。節點 E 是 MAX 節點，更新 \(\alpha\)，此時 \(\alpha \geq \beta\)，故可以剪去節點 E 的餘下分支。然後，節點 E 是 MAX 節點，將節點 E 的分數設為 \(\alpha\)，也就是 15。此時，節點 D 的所有子節點搜索完畢，即可計算出節點 D 的分數為 3。

計算出節點 D 的分數後，節點 D 是節點 H 的一個子節點，故可以更新節點 H 的分數範圍。節點 H 是 MAX 節點，更新 \(\alpha\)。然後，按搜索順序，將節點 H 的 \(\alpha\) 和 \(\beta\) 值依次傳遞給節點 I、J、K。對於節點 K，其左子節點的分數為 2，而節點 K 是 MIN 節點，更新 \(\beta\)，此時 \(\alpha \geq \beta\)，故可以剪去節點 K 的餘下分支。然後，將節點 K 的分數設為 2。

計算出節點 K 的分數後，節點 K 是節點 J 的一個子節點，故可以更新節點 J 的分數範圍。節點 J 是 MAX 節點，更新 \(\alpha\)，但是，由於節點 K 的分數小於 \(\alpha\)，所以節點 J 的 \(\alpha\) 值維持 3 保持不變。然後，將節點 J 的 \(\alpha\) 和 \(\beta\) 值傳遞給節點 L。由於節點 L 是 MIN 節點，更新 \(\beta = 3\)，此時 \(\alpha \geq \beta\)，故可以剪去節點 L 的餘下分支，由於節點 L 沒有餘下分支，所以此處並沒有實際剪枝。然後，將節點 L 的分數設為 3。

實現

參考代碼

int alpha_beta(int u, int alph, int beta, bool is_max) {
  if (!son_num[u]) return val[u];
  if (is_max) {
    for (int i = 0; i < son_num[u]; ++i) {
      int d = son[u][i];
      alph = max(alph, alpha_beta(d, alph, beta, is_max ^ 1));
      if (alph >= beta) break;
    }
    return alph;
  } else {
    for (int i = 0; i < son_num[u]; ++i) {
      int d = son[u][i];
      beta = min(beta, alpha_beta(d, alph, beta, is_max ^ 1));
      if (alph >= beta) break;
    }
    return beta;
  }
}

參考資料與註釋

本文部分引用自博文詳解 Minimax 算法與α-β剪枝_文劍木然，遵循 CC 4.0 BY-SA 版權協議。

極小化極大算法 - 維基百科，自由的百科全書 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用