对于电脑下棋领域，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
