Minimax 算法

定義

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

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

過程

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

解釋

來看一個簡單的例子。

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

例如，對于如下的局勢，假設從左往右搜索，根節(jié)點的數(shù)值為我方贏面：

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

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

樸素的 Minimax 算法常常需要構建一棵龐大的搜索樹，時間和空間復雜度都將不能承受。而α ? β?

剪枝就是利用搜索樹每個節(jié)點取值的上下界來對 Minimax 進行剪枝優(yōu)化的一種方法。

需要注意的是，對于不同的問題，搜索樹每個節(jié)點上的值有著不同的含義，它可以是估值、分數(shù)、贏的概率等等，為方便起見，我們下面統(tǒng)一用分數(shù)來稱呼。

alpha-beta 剪枝

過程

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

若已知某節(jié)點的所有子節(jié)點的分數(shù)，則可以算出該節(jié)點的分數(shù)：對于 MAX 節(jié)點，取最大分數(shù)；對于 MIN 節(jié)點，取最小分數(shù)。

若已知某節(jié)點的部分子節(jié)點的分數(shù)，雖然不能算出該節(jié)點的分數(shù)，但可以算出該節(jié)點的分數(shù)的取值范圍。同時，利用該節(jié)點的分數(shù)的取值范圍，在搜素其子節(jié)點時，如果已經(jīng)確定沒有更好的走法，就不必再搜索剩余的子節(jié)點了。

記 v 為節(jié)點的分數(shù)，且 α ≤ v ≤ β，即 α 為最大下界，β 為最小上界。當 α ≥ β 時，該節(jié)點剩余的分支就不必繼續(xù)搜索了（也就是可以進行剪枝了）。注意，當 α = β 時，也可以剪枝，這是因為不會有更好的結果了，但可能有更差的結果。

初始化時，令 α = ?∞, β = +∞，也就是 ?∞ ≤ v ≤ +∞。到節(jié)點 A 時，由于左 子節(jié)點的分數(shù)為 3，而節(jié)點 A 是 MIN 節(jié)點，試圖找分數(shù)小的走法，于是將 β 值修 改為 3，這是因為 3 小于當前的 β 值（β = +∞）。然后節(jié)點 A 的右子節(jié)點的分數(shù) 為 17，此時不修改節(jié)點 A 的 β 值，這是因為 17 大于當前的 β 值（β = 3）。之 后，節(jié)點 A 的所有子節(jié)點搜索完畢，即可計算出節(jié)點 A 的分數(shù)為 3。

節(jié)點 A 是節(jié)點 B 的子節(jié)點，計算出節(jié)點 A 的分數(shù)后，可以更新節(jié)點 B 的分數(shù)范 圍。由于節(jié)點 B 是 MAX 節(jié)點，試圖找分數(shù)大的走法，于是將 α 值修改為 3，這是 因為 3 大于當前的 α 值（α = ?∞）。之后搜索節(jié)點 B 的右子節(jié)點 C，并將節(jié)點 B 的 α 和 β 值傳遞給節(jié)點 C。

對于節(jié)點 C，由于左子節(jié)點的分數(shù)為 2，而節(jié)點 C 是 MIN 節(jié)點，于是將 β 值修改 為 2。此時 α ≥ β，故節(jié)點 C 的剩余子節(jié)點就不必搜索了，因為可以確定，通過節(jié) 點 C 并沒有更好的走法。然后，節(jié)點 C 是 MIN 節(jié)點，將節(jié)點 C 的分數(shù)設為 β，也 就是 2。由于節(jié)點 B 的所有子節(jié)點搜索完畢，即可計算出節(jié)點 B 的分數(shù)為 3。

計算出節(jié)點 B 的分數(shù)后，節(jié)點 B 是節(jié)點 D 的一個子節(jié)點，故可以更新節(jié)點 D 的分 數(shù)范圍。由于節(jié)點 D 是 MIN 節(jié)點，于是將 β 值修改為 3。然后節(jié)點 D 將 α 和 β 值 傳遞給節(jié)點 E，節(jié)點 E 又傳遞給節(jié)點 F。對于節(jié)點 F，它只有一個分數(shù)為 15 的子 節(jié)點，由于 15 大于當前的 β 值，而節(jié)點 F 為 MIN 節(jié)點，所以不更新其 β 值，然 后可以計算出節(jié)點 F 的分數(shù)為 15。?

?計算出節(jié)點 F 的分數(shù)后，節(jié)點 F 是節(jié)點 E 的一個子節(jié)點，故可以更新節(jié)點 E 的分 數(shù)范圍。節(jié)點 E 是 MAX 節(jié)點，更新 α，此時 α ≥ β，故可以剪去節(jié)點 E 的余下分 支。然后，節(jié)點 E 是 MAX 節(jié)點，將節(jié)點 E 的分數(shù)設為 α，也就是 3。此時，節(jié)點 D 的所有子節(jié)點搜索完畢，即可計算出節(jié)點 D 的分數(shù)為 3。

計算出節(jié)點 D 的分數(shù)后，節(jié)點 D 是節(jié)點 H 的一個子節(jié)點，故可以更新節(jié)點 H 的分 數(shù)范圍。節(jié)點 H 是 MAX 節(jié)點，更新 α。然后，按搜索順序，將節(jié)點 H 的 α 和 β 值依次傳遞給節(jié)點 I、J、K。對于節(jié)點 K，其左子節(jié)點的分數(shù)為 2，而節(jié)點 K 是 MIN 節(jié)點，更新 β，此時 α ≥ β，故可以剪去節(jié)點 K 的余下分支。然后，將節(jié)點 K 的分數(shù)設為 2。

計算出節(jié)點 K 的分數(shù)后，節(jié)點 K 是節(jié)點 J 的一個子節(jié)點，故可以更新節(jié)點 J 的分 數(shù)范圍。節(jié)點 J 是 MAX 節(jié)點，更新 α，但是，由于節(jié)點 K 的分數(shù)小于 α，所以節(jié) 點 J 的 α 值維持 3 保持不變。然后，將節(jié)點 J 的 α 和 β 值傳遞給節(jié)點 L。由于節(jié) 點 L 是 MIN 節(jié)點，更新 β = 3，此時 α ≥ β，故可以剪去節(jié)點 L 的余下分支，由于 節(jié)點 L 沒有余下分支，所以此處并沒有實際剪枝。然后，將節(jié)點 L 的分數(shù)設為 3。

?實現(xiàn)

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;
  }
}

新手上路，請多多指教文章來源地址http://www.zghlxwxcb.cn/news/detail-764158.html

到了這里，關于Alpha-Beta 剪枝的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！