alpha-beta.md

**Alpha-Beta剪枝算法\(Alpha Beta Pruning\)**

\[说明\] 本文基于[<<CS 161 Recitation Notes - Minimax with Alpha Beta Pruning>>](http://cs.ucla.edu/~rosen/161/notes/alphabeta.html)，文中的图片均来源于此笔记。

Alpha-Beta剪枝用于裁剪搜索树中没有意义的不需要搜索的树枝，以提高运算速度。

假设α为下界，β为上界，对于α ≤ N ≤ β:

若 α ≤ β  则N有解。

若 α > β 则N无解。

下面通过一个例子来说明Alpha-Beta剪枝算法。

![](http://img.my.csdn.net/uploads/201404/04/1396586704_8178.gif)

上图为整颗搜索树。这里使用极小极大算法配合Alpha-Beta剪枝算法，正方形为自己（A），圆为对手（B）。

初始设置α为负无穷大，β为正无穷大。

![](http://img.my.csdn.net/uploads/201404/04/1396588299_8653.gif)

对于B\(第四层\)而已，尽量使得A获利最小，因此当遇到使得A获利更小的情况，则需要修改β。这里3小于正无穷大，所以β修改为3。

![](http://img.my.csdn.net/uploads/201404/04/1396587190_1464.gif)

\(第四层\)这里17大于3，不用修改β。

![](http://img.my.csdn.net/uploads/201404/04/1396588823_7249.gif)

对于A\(第三层\)而言，自己获利越大越好，因此遇到利益值大于α的时候，需要α进行修改，这里3大于负无穷大，所以α修改为3

![](http://img.my.csdn.net/uploads/201404/04/1396589203_8461.gif)

B\(第四层\)拥有一个方案使得A获利只有2，α=3,  β=2, α > β, 说明A\(第三层\)只要选择第二个方案, 则B必然可以使得A的获利少于A\(第三层\)的第一个方案,这样就不再需要考虑B\(第四层\)的其他候选方案了,因为A\(第三层\)根本不会选取第二个方案,多考虑也是浪费.

![](http://img.my.csdn.net/uploads/201404/04/1396590059_1975.gif)

B\(第二层\)要使得A利益最小,则B\(第二层\)的第二个方案不能使得A的获利大于β, 也就是3. 但是若B\(第二层\)选择第二个方案, A\(第三层\)可以选择第一个方案使得A获利为15, α=15,  β=3, α > β, 故不需要再考虑A\(第三层\)的第二个方案, 因为B\(第二层\)不会选择第二个方案.

![](http://img.my.csdn.net/uploads/201404/04/1396590632_4111.gif)

A\(第一层\)使自己利益最大,也就是A\(第一层\)的第二个方案不能差于第一个方案, 但是A\(第三层\)的一个方案会导致利益为2, 小于3, 所以A\(第三层\)不会选择第一个方案, 因此B\(第四层\)也不用考虑第二个方案.

![](http://img.my.csdn.net/uploads/201404/04/1396591056_5166.gif)

当A\(第三层\)考虑第二个方案时,发现获得利益为3,和A\(第一层\)使用第一个方案利益一样.如果根据上面的分析A\(第一层\)优先选择了第一个方案,那么B不再需要考虑第二种方案,如果A\(第一层\)还想进一步评估两个方案的优劣的话, B\(第二层\)则还需要考虑第二个方案,若B\(第二层\)的第二个方案使得A获利小于3,则A\(第一层\)只能选择第一个方案,若B\(第二层\)的第二个方案使得A获利大于3,则A\(第一层\)还需要根据其他因素来考虑最终选取哪种方案.  




一种基于剪枝（ α-βcut-off）的深度优先搜索（depth-first search）。  
•将走棋方定为MAX方，因为它选择着法时总是对其子节点的评估值取极大值，即选择对自己最为有利的着法；  
•将应对方定为MIN方，因为它走棋时需要对其子节点的评估值取极小值，即选择对走棋方最为不利的、最有钳制作用的着法。

•在对博弈树采取深度优先的搜索策略时，从左路分枝的叶节点倒推得到某一层MAX节点的值，可表示到此为止得以“落实”的着法最佳值，记为α。  
•显然此值可作为MAX方着法指标的下界。  
•在搜索此MAX节点的其它子节点，即探讨另一着法时，如果发现一个回合（2步棋）之后评估值变差，即孙节点评估值低于下界α值，则便可以剪掉此枝（以该子节点为根的子树），即不再考虑此“软着”的延伸。  
•此类剪枝称为α剪枝。  
![](http://img.blog.csdn.net/20160319115003997 "这里写图片描述")

![](http://img.blog.csdn.net/20160319115018184 "这里写图片描述")

•同理，由左路分枝的叶节点倒推得到某一层MIN节点的值，可表示到此为止对方着法的钳制值，记为β。  
•显然此β值可作为MAX方无法实现着法指标的上界。  
•在搜索该MIN节点的其它子节点，即探讨另外着法时，如果发现一个回合之后钳制局面减弱，即孙节点评估值高于上界β值，则便可以剪掉此枝，即不再考虑此“软着”的延伸。  
•此类剪枝称为β剪枝。  
![](http://img.blog.csdn.net/20160319115045434 "这里写图片描述")、  
![](http://img.blog.csdn.net/20160319115055857 "这里写图片描述")  
•α-β剪枝是根据极大-极小搜索规则的进行的，虽然它没有遍历某些子树的大量节点，但它仍不失为穷尽搜索的本性。

•α-β剪枝原理中得知：  
α值可作为MAX方可实现着法指标的下界  
β值可作为MAX方无法实现着法指标的上界  
于是由α和β可以形成一个MAX方候选着法的窗口  
也便出现了各种各样的α-β窗口搜索算法。