字母排序树剪枝法

Alpha-beta剪枝是一种搜索算法，用于减少极大极小搜索树中的节点数量。这是一个对抗性搜索算法，主要应用于两个可以玩那种游戏(如井字游戏、国际象棋和围棋)的机器上。当算法评估出一个策略的后续走法比前一个策略更差时，就会停止计算该策略的后续发展。该算法的结论与极小极大算法相同，但不影响最终决策的分支被砍掉。

阿尔法-贝塔算法原理:

α-β剪枝算法是基于极大极小搜索算法的。极大极小搜索策略是在考虑双方博弈的几个步骤后，从可能的步骤中选择一个相对较好的方式，在有限的搜索范围内求解，可以理解为指定一个有限的搜索深度。

所以要定义一个静态的估计函数F来估计棋势的优劣，可以根据棋势的优劣特点来定义。这里规定MAX代表程序员，MIN代表对手，p代表一盘棋(也就是一种状态)。有利于MAX的情况，f(p)为正，有利于MIN的情况，f(p)为负，情况平衡，f(p)为零。

最大层的下界定义为α，最小层的上界为β。alpha-beta的修剪规则描述如下:

(1)alpha修剪。如果任一最小层节点的beta值不大于其任一前任最大层节点的alpha值，即alpha(前驱层)>；=β(后继层)，可以终止最小层中这个MIN节点以下的搜索过程。该最小节点的最终反向计算值被确定为该β值。

(2)贝塔剪枝。如果任一最大层节点的alpha值不小于任一先前最小层节点的beta值，即alpha(后继层)>；= beta(前驱层)，可以终止最大层中这个max节点以下的搜索过程，将这个MAX节点的最终后向值确定为这个alpha值。