文档介绍：α-β 搜索过程
在极小极大搜索方法中，由于要先生成指定深度以内的所有节点，其节点数将随着搜索深度的
增加承指数增长。这极大地限制了极小极大搜索方法的使用。能否在搜索深度不变的情况下，利用
已有的搜索信息减少生成的节点数呢？
小值层的 β 值，很容易发现若 α≥β 时，节点 7 的其他子节点不必再生成，这不影响高一层极
大值的选取，因 s 的极大值不可能比这个 β 值还小，再生成无疑是多余的，因此可以进行剪枝。这
样一来，只要在搜索过程记住倒推值的上下界并进行比较，就可以实现修剪操作，称这种操作为 α
剪枝。类似的还有 β 剪枝，统称为 α-β 剪枝技术。在实际修剪过程中，α、β 还可以随时修正，但
极大值层的倒推值下界 α 永不下降，实际的倒推值取其后继节点最终确定的倒推值中最大的一个
倒推值。而极小值层的倒推值上界 β 永不上升，其倒推值则取后继节点最终确定的倒推值中最小的
一个倒推值。
归纳一下以上讨论，可将 α-β 过程的剪枝规则描述如下：
在进行 α-β 剪枝时，应注意以下几个问题：
（1）比较都是在极小节点和极大节点间进行的，极大节点和极大节点的比较，或者极小节点
和极小节点间的比较是无意义的。
（2）在比较时注意是与"先辈层"节点比较，不只是与父辈节点比较。当然，这里的"先辈层"
节点，指的是那些已经有了值的节点。
（3）当只有一个节点的"固定"以后，其值才能够向其父节点传递。
（4）α-β 剪枝方法搜索得到的最佳走步与极小极大方法得到的结果是一致的，α-β 剪枝并没有
因为提高效率，而降低得到最佳走步的可能性。
（5）在实际搜索时，并不是先生成指定深度的搜索图，再在搜索图上进行剪枝。
如果这样，就失去了 α-β 剪枝方法的意义。在实际程序实现时，首先规定一个搜索深度，然后按照
类似于深度优先搜索的方式，生成节点。在节点的生成过程中，如果在某一个节点处发生了剪枝，
则该节点其余未生成的节点就不再生成了。
（1）α 剪枝：若任一极小值层节点的 β 值小于或等于它任一先辈极大值居节点的 α 值，即 α（先
辈层）≥β（后继层），则可中止该极小值层中这个 MIN 节点以下的搜索过程。这个 MIN 节点最终
的倒推值就确定为这个 β 值
（2）β 剪枝：若任一极大值层节点的 α 值大于或等于它任一先辈极小值层节点的 β 值，即 α（后
继层）≥β（先辈层），则可以中止该极大值层中这个 MAX 节点以下的搜索过程。这个 MAX 节点
的最终倒推值就确定为这个 α 值。