在极小极大搜索中，会检查根本不需要去检查的节点。如图3.23所示，当搜索完a、b、c、d、e时，可以得到MIN层的b值为3，即知道其上一层MAX层父节点a一定大于或等于3，将3设置为α。继续搜索，当搜索到g时，就可以确定f将获得的值一定小于或等于2，将MIN层这个2设置为β，β≤α，表示f的值不会再向上传递了，因此此时可以停止搜索f的分支，也就是说在f的孩子节点只要发现一个比α还小的，那么f的其余分支就可以剪去，完全不用搜索了。
图3.23 极小极大搜索中的极大值冗余
在后面继续搜索到i值为12时，得到h不会超过12，即β此时为12；搜索到j，则更新h节点的β为5，表示上限为5，继续搜索到k，β更新为2，此时β≤α，如果还有其他分支，则可以停止搜索。如果假设图中没有k节点，h节点的β就更新为5，那么回溯到a节点时，则更新a节点的α为5。
也就是在这个剪枝算法中，以深度优先搜索方式推进，搜索过程中产生α和β两个值，α只在MAX层更新，更新时只取最大值，即不会减小，β则只在MIN层更新，更新时只取最小值，即不会增大。如果节点值为n，α为下限，β为上限，则α≤n≤β。
在任一个MIN节点下，如果发现了β更新时出现小于或等于它的任一个MAX祖先的α，则可以终止对该节点的搜索，将β作为该节点的值向上传递。类似地，如果在任一个MAX节点下，发现了一个α大于或等于它的任一个MIN祖先的β值，就可以终止对该节点的搜索，将α作为该节点的值向上传递。综上，在回溯过程中，出现α≥β时，进行剪枝操作。(www.xing528.com)
下面再看一个例子。状态空间转换图如图3.24所示，采用α-β剪枝，初始将α设为-∞，将β设为+∞，进行搜索和回溯标注，未标数字的状态不会被估算，其后继分支都可以剪去。
图3.24 α-β剪枝过程
可以看出，向上回传时，如果出现MAX层的节点值比之前的大，则肯定不会被上一层的MIN祖先选中，所以可以剪枝，比如f≥5，剪去h分支并将f值设为5。类似地，出现在MIN层的节点只会被上一层选最大的回传，所以在MIN层，没出现比之前的值更大的值，就可以剪枝。图3.24中的i和o节点分别不会超过0和2，都比之前在b节点出现的3小，所以进行剪枝，并将0和2分别作为i和o的值用于回传。
关于α-β剪枝的应用，可以在本章实验参考部分的第三个实验的扩展部分五子棋游戏设计中增加剪枝过程试试。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
