α-β搜索过程

《α-β搜索过程》由会员分享，可在线阅读，更多相关《α-β搜索过程（4页珍藏版）》请在金锄头文库上搜索。

1、 -搜索过程 在极小极大搜索方法中， 由于要先生成指定深度以内的所有节点，其节点数将随着搜索深度的 增加承指数增长。 这极大地限制了极小极大搜索方法的使用。能否在搜索深度不变的情况下，利用 已有的搜索信息减少生成的节点数呢？ 设某博弈问题如下图所示， 应用极小极大方法进行搜索。 假设搜索的顺序为从下到上，从左到 右。当计算完 a 的值为 0 后，由于 b 是极大节点，马上就可以知道b 的值大于等于 0。接下来求 c 的值。由于 c 是极小节点，由 d 的值为 -3，知道 c 的值小于等于 -3。而 a 和 c 都是 b 的子节点，所 以即便不扩展节点e，也可以知道 b的值一定为 0 了。所以在

2、这种情况下， 没有生成节点 e 的必要。 同样，在知道 b 的值为 0 后，由于 k 是极小节点，所以立即知道k 的值要小于等于 0。而通过节点 f、g，知道 h的值至少为 3。这样即便不扩展A 所包围的那些节点，也能知道k 的值一定为 0。所 以 A 包围的那些节点也没有生成的必要，不管这些节点取值如何，都不影响k 的值。如果在搜索 的过程中，充分利用这些信息，不就可以少生成很多节点，从而提高搜索的空间利用率吗？ -过 程正是这样一种搜索方法。MINIMAX过程是把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树， 然后再进行端节点静态估值和倒推值计算，这显然会导致低效率。如图

3、3.8 中，其中一个 MIN 节 点要全部生成 A、B、C、D 四个节点，然后还要逐个计算其静态估值，最后在求倒推值阶段，才 赋给这个 MIN 节点的倒推值 。其实，如果生成节点A 后，马上进行静态估值，得知f（A） 之后，就可以断定再生成其余节点及进行静态计算是多余的，可以马上对MIN 节点赋倒推值 ，而丝毫不会影响MAX 的最好优先走步的选择。这是一种极端的情况，实际上把生成和倒推 估值结合起来进行， 再根据一定的条件判定， 有可能尽早修剪掉一些无用的分枝，同样可获得类似 的效果，这就是 -过程的基本思想。下面再用一字棋的例子来说明 -剪枝方法。图 3.9 一字棋第一阶段 - 剪枝方法为了

4、使生成和估值过程紧密结合，采用有界深度优先策略进行搜索，这样当生成达到规定深度 的节点时，就立即计算其静态估值函数， 而一旦某个非端节点有条件确定其倒推值时就立即计算赋 值。从图 3.9 中标记的节点生成顺序号（也表示节点编号）看出，生成并计算完第6 个节点后，第1 个节点倒推值完全确定，可立即赋给倒推值1。这时对初始节点来说，虽然其他子节点尚未生 成，但由于 s 属极大值层，可以推断其倒推值不会小于1，我们称极大值层的这个下界值为 ， 即可以确定 s 的 1。这说明 s实际的倒推值决不会比 1 更小，还取决于其他后继节点的倒推 值，因此继续生成搜索树。当第8 个节点生成出来并计算得静态估值为

5、1 后，就可以断定第 7 个 节点的倒推值不可能大于1，我们称极小值层的这个上界值为 ，即可确定节点的 1。有 了极小值层的 值，很容易发现若时，节点 7 的其他子节点不必再生成，这不影响高一层极 大值的选取， 因 s的极大值不可能比这个值还小，再生成无疑是多余的，因此可以进行剪枝。 这 样一来，只要在搜索过程记住倒推值的上下界并进行比较，就可以实现修剪操作，称这种操作为 剪枝。类似的还有剪枝，统称为 -剪枝技术。在实际修剪过程中， 、还可以随时修正，但 极大值层的倒推值下界永不下降，实际的倒推值取其后继节点最终确定的倒推值中最大的一个 倒推值。而极小值层的倒推值上界永不上升，其倒推值则取后继

6、节点最终确定的倒推值中最小的 一个倒推值。 归纳一下以上讨论，可将 -过程的剪枝规则描述如下： 在进行 -剪枝时，应注意以下几个问题： （1）比较都是在极小节点和极大节点间进行的，极大节点和极大节点的比较，或者极小节点 和极小节点间的比较是无意义的。 （2）在比较时注意是与 “先辈层 “节点比较，不只是与父辈节点比较。当然，这里的“先辈层 “ 节点，指的是那些已经有了值的节点。 （3）当只有一个节点的 “固定 “以后，其值才能够向其父节点传递。 （4） -剪枝方法搜索得到的最佳走步与极小极大方法得到的结果是一致的， -剪枝并没有 因为提高效率，而降低得到最佳走步的可能性。 （5）在实际搜索时，

7、并不是先生成指定深度的搜索图，再在搜索图上进行剪枝。 如果这样，就失去了 -剪枝方法的意义。在实际程序实现时，首先规定一个搜索深度，然后按照 类似于深度优先搜索的方式，生成节点。在节点的生成过程中，如果在某一个节点处发生了剪枝， 则该节点其余未生成的节点就不再生成了。（1） 剪枝：若任一极小值层节点的值小于或等于它任一先辈极大值居节点的 值，即 （先 辈层）（后继层） ，则可中止该极小值层中这个MIN 节点以下的搜索过程。这个MIN 节点最终 的倒推值就确定为这个值 （2） 剪枝：若任一极大值层节点的值大于或等于它任一先辈极小值层节点的 值，即 （后 继层）（先辈层），则可以中止该极大值层中这

8、个MAX 节点以下的搜索过程。这个MAX 节点 的最终倒推值就确定为这个 值。通过对图 3.10 的搜索，来说明 - 剪枝搜索过程。 在搜索过程中， 假定节点的生成次序是从上到下，从左到右进行的。 图中带圈的数字， 表示节 点的计算次序， 在叙述时， 为了表达上的方便， 该序号也同时表示节点。 当一个节点有两个以上的 序号时，不同的序号，表示的是同一个节点在不同次序下计算的结果。 过程如下：首先，从根节点开始，向下生成出到达指定节点深度的节点1 注释：1应为，2. 32也一样表示 ，由1的值为 0，可知 20，继续扩展生成节点 3 ，由于3的值 5 大于2 的值 0，并 且节点 2 再也没有其

9、它的子节点了，所以4 （与2 是同一个节点）的值确定为0。由4的值，可 以确定 50。扩展节点 5 ，按顺序生成节点 7 、6 ，由6 的值-3，有7 -3。7 是极小节点，其值小于它的先辈节点 5的值，满足 剪枝条件，故 7 的其他子节点被剪掉，不再生成。由于5 不再有其他子节点，所以有80，并因此有 90。扩展节点 9 ，顺序生成节点 12 、11 、10 ， 由10 3 得到11 3 和123 。12 是极大节点， 其值大于其先辈节点 9 的值，满足 剪枝条件， 故12的其他三个子节点及其这些子节点的后继节点全部被剪掉。这样9的子节点也全部搜索完， 得到13 0，并上推到 140。扩展1

10、4的另一个子节点，一直到指定深度。由15 5，有165， 然后顺序生成出 17 、19 ，由17 、19 的值分别得到 184 、20 1。上推得到 211。扩展 21 的另一个子节点， 顺序生成 23 、 22 ， 得到23 -3。23是一个极小节点， 其值小于其先辈节点 21 的值，满足 剪枝条件，所以在 23处发生剪枝（注意，此处即便是23的值不小于 21的值，但 由于23的值小于 14的值，同样也发生 剪枝，因为是后继节点的 值与其先辈节点的值进行 比较，而不只是后辈的值与其父节点的 值进行比较。同样，在 剪枝的情况下，也是后辈节 点的 值与其先辈节点的值进行比较，而不只是后辈的 值与

11、其父节点的 值进行比较）。这 样得到 24 1，251 。扩展 25 的右边子节点及其后继节点，有26 6，276，28 8，29 6，并由此上推到 306。 30是一个极大节点， 其值大于其先辈节点 25的值，满足 剪枝条件， 故在节点 30处发生剪枝。这样使得 31 1， 并使得根节点 32 1。 至此全部搜索结束， 根节点 32 的值就是对当前棋局的评判。由于该值来自于根节点的右边一个子节点31 ，所以搜索得到的最佳 走步应该走向根节点的右边这一个子节点31 。 应该注意的是， 博弈树搜索的目标就是找到当前棋局的一步走法，所以 - 剪枝搜索的结果是得到 了一步最佳走步，而不是象一般的图搜

12、索或者与或图搜索那样，得到的是从初始节点到目标节点 （集）的一条路径或者解图。根据这些剪枝规则， 很容易给出 -算法描述，显然剪枝后选得的最好优先走步，其结果与不剪枝 的 MINIMAX方法所得完全相同，因而 -过程具有较高的效率。图 3.10 -搜索过程的博弈树图 310 给出一个 d4 的博弈树的 -搜索过程，其中带圆圈的数字表示求静态估值及倒推值过 程的次序编号。该图详细表示出 -剪枝过程的若干细节。初始节点的最终倒推值为1，该值等于 某一个端节点的静态估值。 最好优先走步是走向右分枝节点所代表的棋局，要注意棋局的发展并不 一定要沿着通向静态值为1 的端节点这条路径走下去，这要看对手的实

13、际响应而定。 下面分析一下剪枝的效率问题。若以最理想的情况进行搜索，即对MIN 节点先扩展最低估值的节点（若从左向右顺序进行，则设节点估计值从左向右递增排序），MAX 先扩展最高估值的节 点（设估计值从左向右递减排序），则当搜索树深度为D，分枝因数为 B 时，若不使用 -剪枝技 术，搜索树的端节点数；若使用 - 剪枝技术可以证明理想条件下生成的端节点数最少， 有（D 为偶数）（D 为奇数） 比较后得出最佳 - 搜索技术所生成深度为D 处的端节点数约等于不用 - 搜索技术所生成深度为 D2 处的端节点数。这就是说，在一般条件下使用 -搜索技术，在同样的资源限制下，可以向 前考虑更多的走步数，这样

14、选取当前的最好优先走步，将带来更大的取胜优势。5其他改进方法使用 -剪枝技术，当不满足剪枝条件（即）时。若 值比 值大不了多少或极相近，这时也可以进行剪枝， 以便有条件把搜索集中到会带来更大效果的其他路径上，这就是中止对效益 不大的一些子村的搜索，以提高搜索效率。 其他改善极小极大过程性能的基本方法有： （1）不严格限制搜索的深度，当到达深度限制时，如出现博弈格局有可能发生较大变化时（如出 现兑子格局） ，则应多搜索几层， 使格局进入较稳定状态后再中止，这样可使倒推值计算的结果比 较合理，避免考虑不充分产生的影响，这是等候状态平稳后中止搜索的方法。 （2）当算法给出所选的走步后， 不马上停止搜

15、索， 而是在原先估计可能的路径上再往前搜索几步， 再次检验会不会出现意外，这是一种增添辅助搜索的方法。 （3）对某些博弈的开局阶段和残局阶段，往往总结有一些固定的对弈模式，因此可以利用这些知 识编好走步表， 以便在开局和结局时使用查表法。只是在进入中盘阶段后， 再调用其他有效的搜索 算法，来选择最优的走步。 - 剪枝过程是二人博弈问题的一般搜索方法，实践证明，该方法可以有效地减少在搜索过程 中生成的节点数， 提高搜索效率。 IBM 公司研制的 “深蓝 “国际象棋程序， 采用的就是这样的一种搜 索算法，该程序曾经战胜了国际象棋世界冠军卡斯帕罗夫。以上介绍的各种博弈搜索技术可用于求解所提到的一些双人博弈问题。但是这些方法还不能全 面反映人们弈棋过程实际所使用的一切推理技术，也未涉及棋局的表示和启发函数问题。例如一些 高明的棋手， 对棋局的表示有独特的模式， 他们往往记住的是一个可识别的模式集合，而不是单独 棋子的具体位置。 此外有些博弈过程， 在一个短时期内短兵相接， 进攻和防御的战术变化剧烈，这 些情况如何在搜索策略中加以考虑。 还有基于极小极大过程的一些方法都设想对手总是走的最优走 步，即我方总应考虑最坏的情况，实际上再好的选手也会有失误，如何利用失误加强攻势， 也值得 考虑。再一点就是选手的棋风问题。