對於電腦下棋領域，Minimax 搜尋方式與 Alpha-beta pruning 的修剪策略組合，可以說是最有效的下棋算法。西元2000年，IBM 的深藍對世界西洋棋王 Kasparov 的一戰，電腦首度打敗世界西洋棋王。從此之後，Minimax 與 Alpha-beta pruning 一直是電腦下棋的主流演算法。而電腦下棋領域，成為少數被 AI 技術攻陷的領域之一。
一、遊戲樹 (Game Tree)
用來表達一個賽局中各種後續可能性的樹。一個完整的遊戲樹有一個起始節點，代表賽局中某一個情形，接著下一層的子節點是原來父節點賽局下一步的各種可能性，依照這規則擴展直到賽局結束。遊戲樹中形成的葉節點代表各種遊戲結束的可能情形，例如井字遊戲會有26,830個葉節點。
二、MiniMax 對局搜尋演算法
MiniMax算法常用於棋類等由兩方較量的遊戲和程序。該算法是一個零總和算法，即一方要在可選的選項中選擇將其優勢最大化的選擇，另一方則選擇令對手優勢最小化的方法。而開始的時候總和為0。很多棋類遊戲可以採取此算法，例如圈圈叉叉。
- Quality of the result
- Completeness : Yes (if tree is finite, you will see the entire game tree)
- Optimality : Yes (against an optimal opponent)
- Time : $O(b^m)$
- Space : $O(b \times m)$ (depth-first exploration)
三、Chess Background
- 1950’s first chess programs (Shannon, Turing, Bernstein)
- Tournament play = 40 moves in 2 hours/player.
- Branching factor $b$ : $b ≈ 35$.
- Depth $m$ : Often 50 moves per player ($m ≈ 100$ plies)
- State $S$ : $35^{100} ≈ 10^{150}$ nodes in search tree $ ≈ 10^{40} $ different legal board positions.
- Problem : In real games, we can’t go all the way down to the terminal states.
- For chess, b ≈35, m ≈100 for "reasonable" games. Exact solution completely infeasible.
四、Alpha-Beta 剪枝法 (α - β pruning)
Alpha-Beta 剪枝是 Minimax 對局搜尋法的一個修改版，主要是在 Minimax 當中加入了 α 與 β 兩個紀錄值，用來做為是否要修剪的參考標準。兩個參數以交錯的方式傳遞給下層的子樹。
- 在最大層取最大值的時候，若發現了一個大於等於β 的值，就不用再對其它分枝進行搜尋，這就是所謂的 β 剪枝。
- 在最小層取最小值的時候，發現了一個小於等於α 的值，也不用再對其它分枝進行搜尋，這就是所謂的α 剪枝。
1. Alpha-Beta 剪枝核心思想
在搜尋的過程中，若發現無論如何都無法改變對方目前的最佳分數時，就可以提早放棄，不必浪費時間搜尋其它的著法。
也就是說，Max方從自己的利益出發，努力尋找盡可能好的棋步，但是一旦他的棋步好過頭了，極有可能同一層的選擇中有極壞的棋步，因此Min方不可能那樣選擇，因此當前局面的搜索工作就瞬間變成是多餘的。
2. Alpha-Beta 剪枝結論
- α-β剪枝真正關注的是(α, β)區間內的估值。對於區間之外的估值，則會引發剪枝
- Alpha-beta剪枝不會影響Minimax搜尋法的結果
- 修剪法並不保證能將對局樹修剪得非常小，而且樹的大小會與拜訪的順序有關，但通常應用上我們可以做到接近最佳情況($O(b^{m/2})$)。
3. Alpha-Beta 剪枝例題
下面是一個非常詳細易懂的Alpha-Beta 剪枝的例題網站，裡面有很好的解說!
CS 161 Recitation Notes - Minimax with Alpha Beta Pruning
Reference
Stanford CS221 - Deep Blue
wiki - 遊戲樹
電腦下棋的關鍵： Min-Max 對局搜尋與 Alpha-Beta 修剪算法
陳鍾誠的網站 - 人工智慧的歷史
發表文章
