IBM的深蓝降服国际象棋大师卡斯帕罗夫很大程度上要归功于α-β剪枝算法[2]，那么什么是α-β剪枝算法呢？我们从极小-极大过程开始讲起。

1. 极小-极大过程

我们先看看人是如何下棋的。
人不才棋时首先根据当前局势考虑多少总可能的走法，再对每种可能的走法考虑对方会如何走，再考虑自己会如何应对……高手会这样往前看很多步，根据末了的局势判断哪种走法是最优的。
换句话说，高手会选择那种纵然对方正确应对的情形下，己方依然霸占最大上风的走法，而不是把希望寄托在对方犯错上。
人类棋手的这种思考方法可以用一个“极小极大过程”来描述，个中“极小”是指由于对方的精确应对，使己方收益最小，而“极大”是指假设对方让自己收益最小的条件下，通过己方走棋使自己收益最大。

图1：极小-极大过程

如图1所示，个中方框表示轮到我方走棋，圆圈表示轮到对方走棋。
最上面的方框表示当前棋局状态。
从当前状态开始向下搜索4步，最下方的数字给出了四步之后的棋局得分，数字越大表示对我方越有利，数字越小表示对对方越有利（在深蓝系统中，这些得分来自于国际象棋大师总结的干系知识）。
有了这棵搜索树，就可以自底向上倒推每个节点的得分。
如何倒推呢？显然，在双方都不犯错的前题下，我方会选择得分更高的走法，对方会选择得分最低的走法。
基于这一原则，圆圈节点的分值是其所有子节点的最小分值，而方框节点是所有子节点的最大分值。
由此可自底向上得到所有节点的分值，如图1所示。

基于图1所示的各节点得分，可以看到在双方都没有涌现缺点的情形下，如果己方向左走将得到0分，而向右走的话，将得到1分。
显然我方该当选择向右走，如赤色箭头所示，这将担保无论对方如何应对，我方至少得到1分的上风，这便是极小-极大过程。
实质上，这一过程担保在最差情形下（对手完美走棋）选择对自己最有利的走法，因此可表现出稳定的棋力。
极小-极大过程由喷鼻香农于1949年提出[3]，是包括深蓝在内的浩瀚打算机奕棋机系统的根本。

2. α-β剪枝

当搜索深度增加，极小-极大过程将产生规模弘大的搜索树，涌现“组合爆炸”问题。
据深蓝开拓者估算，如果不做改进的话，即便每次走棋只往前考虑十步旁边，每步棋也须要“思考”17年。

如何办理这一问题呢？我们先看看人类棋手是如何处理的。
众所周知，有履历的棋手在思考可能的走法时，并不是对每种可能性都平权考虑，而是根据自己的履历选择几种可能的走法进行考试测验。
打算机可以借鉴这一思路，在搜索的过程中减掉一些不必要的路径分枝，以提高搜索的效率，这一方案称为剪枝。
利用极小-极大过程的特点（我方选择最大子节点，对方选择最小子节点），可以设计剪枝算法，在担保决策不变的条件下，去掉大量不必要的搜索路径。
α-β剪枝算法正是这样一种算法。

我们假定节点是按照深度优先的办法边搜索边产生的，如图2所示。
从根节点s开始，顺序产生a、b、c三个节点，达到了搜索深度后，打算c的两个子节点的得分。
由于c是极小节点，以是两个子节点中最小得分（0）即为c的得分。
由于b是极大节点，因此b的得分最小为0。
由b向下扩展天生节点d和e，e的得分为-3，而d又是极小节点，从而我们知道d的值最大为-3。
到此我们会创造，b的最小值为0，d的最大值为-3，因此节点f得分多少已经不主要了，以是f可以被剪掉，不须要天生。
这样由b得分为0，我们有a的最大值为0。
同样我们扩展a的另一个子节点，并向下延伸到k，得到k的分数为3。
由于h没有其他的子节点，我们推断极大节点g最小为3。
从前面我们知道极小节点a最大为0，它的子节点g是极大节点，最小为3，以是g的其他子节点得分是多少也不主要了，可以不须要天生。

图2：α-β剪枝示意图

上面的例子可以总结成如下剪枝规则：

1，子弟极小节点的值≤先人极大节点的值时， 发生剪枝，称为α剪枝。

2，子弟极大节点的值≥先人极小节点的值时， 发生剪枝，称为β剪枝。

请把稳，这里发生剪枝的条件都是子弟跟先人比较，不但是跟父节点比，只要有一个先人知足剪枝条件就发生剪枝。

上述剪枝方法被称为α-β剪枝算法，由人工智能创始人之一，图灵奖得到者约翰-麦卡锡提出（同期多位学者做过干系研究并独立提出了该算法）[1]。
α-β剪枝算法显著提高了搜索效率，许可在有限的韶光内做更深的搜索，从而得到更好的性能。
须要强调的是，α-β剪枝算法是一个“无损”算法，即剪枝只会提高搜索效率，不会影响走棋决策。