S e(s)=2 A e(a)=2 B e(b)?1 C e(c)=2
D e(d)=7 E e(e)=1 e(B)≤min[e(E),e(F)]≤1
继而有：
e(S)=min[e(A),e(B)]?2
者表示不论e (F)知如何，S结点倒退值的下限为2，也就是说，不必求取下结点及其估值。由此得出：若能边生成结点，边计算估值，则有些结点就不必产生，可以从博弈树中把这一枝剪去。
若把或结点候选倒退值的下限称为α值，与结点候选倒退值的上限称为β值，则删除或结点以下的分支称为α剪枝，删除与结点以下的分支称为β剪枝。 α-β值的定义：
①或结点x的α值，等于其当前子结点中的最大倒推估值（max），它是b（x）的下届；
②与结点y的β值，等于其当前子结点中的最小倒推估值（min），它是b（x）的上届；
b(x)≥α
倒推估值
b(y)≤β
最优“α-β”剪枝法：
“α-β”剪枝法的搜索效率与结点排列次序有关，若子结点的生成次序满足条件：
① 或结点中，估值最高的子结点最先生成； ② 与结点中，估值最低的子结点最先生成；
这样，所剪除的节点数目最多，生成的端节点数目最少，称“α-β”
最优。
五．通用问题求解：——GPS（General Problem Solver）
在人工智能发展的历史上GPS是最著称的一个程序，它由Newell Shaw和 Simon在1959年首次提出，1965年再次发表，1961年对它进行了一次论证性的描述，1969年由Eranet 和Newell完成了这个程序的详细的描述，并构成了程序。
1、 GPS的基本原理
GPS中应用了两个基本思想：中间—结局分析和递归问题求解。在讨论搜索的时候，我们研究了系统根据当前环境提供的启发式信息进行搜索，这可以看成环境提供启发式信息影响着系统的注意力。因此，启发式搜索的过程就是系统不断改变注意力的过程。Simon观察了布满砾石的海滩上的蚂蚁说：蚂蚁要回家，就要反复试探，曲折迂回地爬行，但这并不是高级的智能的行为。细致的分析与研究看出，其决策机构非常简单，Simon认为：蚂蚁的行为是由海滩决定的，也就是说环境控制着行为，行为就是操作的序列，或称过程。要理解行为的控制，就须弄明白过程之间的相互关系，而且行为控制机理可以按照下面三个要求来分类：
①按过程的控制方法分类 ②按激活过程的方法分类 ③按激活过程提供的结论分类
中间—结局分析法是GPS中所使用的关键方法，是一个按过程控制的方法。此方法把一定范围的问题抽象成一个世界，这个世界的理论模型就是知识的层次结构模型。这个世界是一个变化的世界，每一个时刻这一世界有其特征，特征的信息综合称为形势。那么如何使得当前的形势转化为所需要的形势呢？GPS的思想是根据这两种形势的差异来决定我们的动作的。如果把这种思想用到状态空间搜索法中，那就是把当前的状态和目标状态的差异作为启发信息的来源，由它控制搜索。
如何定义差异，怎样选择差异是一个十分复杂的问题，也是GPS所遇到的困难所在。在许多情况下，它不是单因素的，而是多因素的，而且还要考虑到多因素之间的主次问题。在多因素的简单情况下，可用差异操作表来决定动作。
2．规划—划分技术
我们曾把问题求解过程描述成状态空间的搜索。搜索是从初始状态开始，然后执行一系列允许的操作，直到达到目标为止，规划就是寻找达到目标状态的操作序列，从这个意义上说，规划问题本质上就是一个问题求解过程。
规划是人工智能中极其重要的一类问题，规划被定义为达到某一目的计划的动作的集合。动作的执行次序满足某种半序关系，如果此半序关系退化为线性的，则结果是一个动作的序列。规划的重要性还在于它可以显著地减缓组合爆炸的速度。原因是：
一个问题的搜索空间取决于分枝因素和搜索长度，因此搜索空间的大小可以形象地用一个三角形表示，如下图表示。其中问题So—Sg的搜索空间Ｂ，引入规划之后，S0→Sg问题就变为一系列问题，S0→S1搜索空间为B0，S1 →S2的搜索空间为B1??，SN→Sg的搜索空间为Bn，则有：
一般有：
S0 B0 S1
S3 B2 B1 S2
B3 Bn 这也就是说，由于采用了规划，使得总的搜索空间变小了，也可能对求解S0→Sg这个总目标，不存在高效率的搜索方法，然而对求解某个子问题Si→Sj 来说，有可能存在高效率的搜索方法，甚至存在现成的求解方法，特别是对于某些子问题，可能是解决整个问题的关键（例如，过河的桥）。由于它们的引入，使得求解问题的过程大大简化。
任何较复杂的专家系统或求解系统均首先为解题制定一个大致的解题规划：规划求解系统往往是一个复杂的求解系统，它有两个显著的特点：
①框架问题十分突出：对于一个复杂问题，由于状态内容很多，一次要求描述整个状态是很困难，也是不必要的。例如机器人世界的某一个动作只能改变整个世界的很小部分，与其写一个规划，不如写一些规划只描述状态中那些变化的部分。
②近似可分解问题：解决一个难题往往要求将问题分解成一些有希望更加容易解决的几个子问题。对一些简单的问题，分解为完全独立的子问题是可能的，此时，A*算法提供了一种实现方法。但是对于一个复杂问题，往往只是近似可分解的，即把一个较难得问题分解成相互影响较小的问题。例如，将家具搬出房间，原则上可以分解成一件件家具搬出，如果书柜在沙发之后，则需要搬出沙发之后搬书柜。
总之，规划主要研究如何将问题分解成适当的子问题或记录，处理在问题求解过程中发现的子问题间的相互关系。人工智能界已经研制出一大批规划系统，如STRIPS、 ABSTRIPS、NOAH等，其中STRIPS是一个早期的规划系统，它是一种线性规划系统，也是最基本的规划系统。
3．多层规划：
多次利用分解技术，将复杂问题逐级分解为简单子问题及子子问题，所构成求解问题的多级步骤，称为“多级规划”（Hicral chical）或多层规划。如图所示：
S0 P Sg S1 S0 P′ P′ Sg S11 S1 S12 S0 P′′ P′′ P′′ P′′ Sg
ABSTRIPS 是STRIPS的系统的改进型，它采用了分层规划的方法，在每一层逐层进行规划，高层的结果作为低层规划的基础，低层规划由高层规划的结果制约。分层对于规划来说是一种好方法，它可以提高解路径的径直性。但高层规划的结果，对层的约束既不一定正确，更不一定优化。NDTH是一个比较成功的规划系统，它既利用一个格结构来记录被选算子的定序，也采用等级规划，即先形成规划的抽象大纲，再逐步填入越来越细的内容。
向任何求解系统一样，一个规划系统必须具有如下功能：
① 有办法挑选一个可应用的最佳规划；
② 产生新的问题状态，尤其要注意解决好框架问题； ③ 验证是否找到解
④ 检查出死胡同，转而向更有成效的方向努力； ⑤ 检查出一个近似解，并能有办法达到完全解。 4.规划求解系统的实现方法： A）用目标栈的简单规则：
使用目标栈是求解有相互作用的复合问题的最早技术之一。它首先被STRIPS系统所采用。在这种方法中，问题求解程序用一堆栈来存放目标和已提交的用来表达到目标的算子，它描述当前情况和一组由precondition、Add和Delete表说明的算子。
问题求解过程的每一成功步骤均考虑处在栈顶的目标。在为达到目标的算子