極大極小演算法有些不明白 ?

01-02

為什麼是回溯進行相加？怎麼取最優演算法？

先來說極小極大演算法主要應用於什麼樣的遊戲：

1. 零和遊戲（Zero-sum Game）：意思就是你死我活，一方的勝利代表另一方的失敗，比如，象棋，五子棋等。

2. 完全信息（Perfect Information）：玩家知道之前所有的步驟。象棋就是完全信息，因為玩家是交替著落子，且之前的步驟都能在棋盤上體現，但是石頭剪子布就不是。

這樣的遊戲通常可以把他們看作一個樹狀圖，把每一種可能性列出來。比如下面這個井字棋遊戲，Max代表你自己，Min代表你的對手。

這個時候我們需要給每一種結果一個分數，就是這裡的Utility。這個分數是站在我自己（也就是Max）的角度評估的，比如上圖中我贏了就是＋1，輸了是－1，平局時0。所以，我希望最大化這個分數，而我的對手希望最小化這個分數。（在遊戲中，這個分數被稱為static value。）這裡要說一下，井字棋是個比較簡單的遊戲，所以可以列出所有可能的結果。但是，大部分遊戲是不太可能把所有結果都列出來的。根據計算機運算量，我們可能只能往前推7，8步，所以這個時候分數就不只－1，1，0這麼簡單了，會有專門的演算法來根據當前結果給不同的分數。

假設我們有如下圖的遊戲，我是先手，我應該如何利用Minmax演算法來選出第一步怎麼走呢？

這個時候我們就要從結果看起，也就是第4步。圖中標註第四步是我的對手下的，所以他要做的是最小化這個分數，於是對手根據結果可以反推出如下選擇

繼續從後往前看到第3步，當我們知道了對手的選擇以後，我們可以根據對手的結果反推出自己的選擇，我們要做的是最大化這個分數，如圖

重複這個步驟，我們最終可以發現第一步的最優選擇，如圖

以上就是極小極大演算法（Minimax）。當然對於一個複雜的遊戲來說，比如象棋，肯定是需要非常多步才能完成的。這就導致結果的數量是成幾何增長的，也就是說，如果這個遊戲每一步都有n個選擇，那麼在x步以後，將會有n^x個選擇。這個時候，我們就需要採取剪枝演算法（Alpha-Beta）來減少運算量。從剪枝演算法這個名字我們就能看出，這個演算法能讓我們剪掉樹狀圖中的一些分支，從而減少運算量。在這裡也說一下剪枝演算法，因為這並不是個不同於極小極大的演算法，而是極小極大演算法的升級版。

我們將遊戲簡化成如下圖，使用Minimax演算法，我們可以得出這樣的結果

但是，最後一步的分數其實也需要計算機來算（static evaluation），所以我們並不會一開始就有所有的數據，其實我們一開始是這樣的

然後，計算機給出了第一個分數

當給出了這個分數的時候，我們站在步驟1看，無論另一分支的數字是多少，步驟1左邊方框的數字不會超過2。因為第2步是我的對手下的，他希望分數儘可能的小，也就是這樣的

這個時候，電腦再計算另一分支的分數，也就是7。知道另一分數是7以後，也就知道步驟1的左邊方框分數為2。這時，我們往前看一步（步驟0）。步驟0的分數是大於等於2，因為我要最大化分數。如圖

現在，再來計算右邊分支的分數，得到了1。同理，我們站在步驟1來看，右邊方框中的數不會超過1，如圖

在這個情況下，即使我不算最後一個數字，我也能知道在步驟0的結果為2，因為已知步驟1中的右邊方框，數值不會超過1。所以我們就能直接知道結果，也就是

我們可以看到，加上剪枝演算法，我們不僅得到了相同的結果，而且減少了計算量。在實際應用中，加上剪枝演算法，計算機大約需要算2*n^(x/2)個結果，如果n為分支數，x為步數。相比於之前僅用極小極大演算法的n^x，效率提高了很多。這也就意味著，如果在象棋比賽中，假設使用極小極大的演算法，計算機能往前評估7步，加上剪枝演算法，計算機能往前評估14步。極小極大和剪枝演算法曾在IBM開發的國際象棋超級電腦，深藍（Deep Blue）中被應用，並且兩次打敗當時的世界國際象棋冠軍。

首先他是個深度優先的搜索，和對手一人一步，你走的時候選會選擇使局面最好的（對於一個局面你沒辦法靠搜索得到他對應的勝率，所以這邊就要憑機器學習得到的知識，加上人的經驗，設計一個速度很快的評估函數，能夠對任意局面打分），對方走的時候選讓你的局面最差的（同樣是用自己的評估函數去快速評價局面）。

所以每一層輪流從子節點選擇最大值－最小值－最大值－最小值...

這個時候也可以用alpha-beta pruning來剪枝，如圖：

圖(d)，在C節點的時候，因為知道了兄弟節點B的最小值是3，C的孩子發現了有2以後，C這個結點無論怎麼繼續搜索，因為這一層要選擇極小值，所以最優的方案也不會讓評估函數超過2，那麼就C結點可以直接放棄。

這個是我用Python寫的極大極小和alpha beta剪枝，是個類似於五子棋的東西。

https://github.com/jieaozhu/Machine_Learning/blob/master/minimax_alpha_beta_pruning/basicplayer.py#L48

極小極大演算法（Minimax）和α-β剪枝（Alpha-Beta Pruning）都是game playing領域的經典演算法（可參考 AIAM（Artificial Intelligence - A Modern Approach）的第五章），極小極大實際上使用了DFS來遍歷當前局勢以後所有可能的結果，通過『最大化』自己和『最小化』對手的方法獲取下一步的動作。α-β剪枝也是類似的思想，只不過效率更高，因為它刪減了一些不需要遍歷的結點。

下圖是一個極小極大演算法的例子，MAX層代表自己，總是選取下面三個結點中的最大值，MIN層代表對手，總是選取下面一層結點中的最小值。在此例子中，MAX下一步會選擇a1。

Minimax的偽代碼如下(遞歸實現)：

01 function minimax(node, depth, maximizingPlayer) 02 if depth = 0 or node is a terminal node 03 return the heuristic value of node


04     if maximizingPlayer

05         bestValue := ?∞

06         for each child of node

07             v := minimax(child, depth ? 1, FALSE)

08             bestValue := max(bestValue, v)

09         return bestValue

10 else (minimizing player) 11 bestValue := +∞ 12 for each child of node 13 v := minimax(child, depth ? 1, TRUE) 14 bestValue := min(bestValue, v) 15 return bestValue

開始時調用 :

minimax(root, depth, TRUE)

函數返回的是Max下一步的最大值，所以需要稍加修改偽代碼才能返回Max下一步的移動動作。

可以使用Java裡面的ArrayList&來產生並且保存child of node。

在極大極小偽代碼的基礎上增加兩行就變成了α-β剪枝。

也可以參考Cornell University OOAD這門課的講義(http://www.cs.cornell.edu/courses/cs2110/2014sp/L16-GameTree_and_MiniMax_and_GenericTypes/L16cs2110sp14.pdf)