中国象棋人机博弈系统的设计与实现

第三章 系统分析和设计

11

MAX 5 5

MIN

5 7 9 5 8 3 4 图3.2 α裁剪树

的叶节点倒推得到第一层MAX节点的值为5，可表示此时的着法最佳值，记为α，显然此α值可作为MAX方着法指标的下界。在搜索中路分枝时，因为第二层着法的选择是取第三层节点的最小值，即取Min(8，3，“□”)，而无论“□”中为何值，都不会比5大(最大为3)，故可以将“□”表示的节点及其后继节点剪掉，不再考虑此节点的延伸。同理搜索右路分枝，也可以进行剪枝操作，此类剪枝称为α-剪枝。

5 MIN MAX

5

7 9 5 8 3 4 图3.2 α裁剪树

如图3.2所示的极大极小树片段中，由左路分枝的叶节点倒推得到第一层MIN节点的值为n，可表示此时对方着法的钳制值，记为β。显然此β值可作为MIN方可能实现着法指标的上界。在搜索中路分枝时，因为第二层着法的选择是取第三层节点的最大值，即取MAX(5，12，“○”)，而无论“○”中为何值，都不会比11小(至少为12)，故可以将“○”表示的节点及其后继节点剪掉，不再考虑此节点的延伸。同理搜索右路分枝，进行剪枝操作。此类剪枝称为β-剪枝。

但是这个算法严重依赖于走法的寻找顺序。很明显，搜索空间的大小和第一节点的估价值有关。如果你最先搜到的总是最坏的节点，那么就不可能找到值比beta还要坏的节点，就不会有任何裁剪，该算法会和极大极小值算法一样，遍历

12 中国象棋人机博弈系统的设计与实现

整个博弈树，搜索效率很低。但是如果我们最先搜到的总是最好的节点，这就是Alpha-Beta算法的搜索效率最好的情况。在数学的角度来看，搜索效率能提高到原来的平方根。在最好的情况下，把搜索的深度设为d，，节点的数量为极大极小值搜索算法的一半。在最坏的情况下，alpha-beta搜索算法和极大极小值搜索算法是一样的。多大程度的减小搜索空间取决于一个节点的子节点在有序的节点列表中如何发展下去。为了提高搜索的效率，可以调整子节点的节点列表。这就要涉及到启发式搜索了。 3.5.3 启发式搜索及走法排序

我们前面介绍的alpha-beta剪枝搜索是极大极小值搜索的改进，在一定程度上提高了效率，但是有着明显的缺点（在上文中有介绍），如果要提高搜索深度和搜索效率，就要配合搜索过程中得到的一些启发信息。

利用启发信息来决定哪一个是下一步要做扩展的节点，这种搜索总是选择“最有希望”的节点来作为下一个被扩展的节点。如何快速的找出那个“最有希望”的节点，灵活的运用启发信息，这就需要我们应用某些准则来重新排列节点列表中节点的顺序。根据这些搜索要求，我们出现了一些启发式搜索的形式。这些策略加快了搜索的速度。如下：

历史启发，在搜索的过程中，很有可能会出现一些相似的局面，这些局面可能是前面已经出现的，我们可以对它用估值函数来给予这些局面一个估值，但现在我们有一种更好的办法可以快速判断这些局面是否还有继续下去的可能性。历史启发这种搜索策略就是在搜索的过程中，如果产生比较好的走法，那么如果以后产生相似的局面，这些走法也是比较好的，所以我们可以将这些走法存储下来，并给予一个参数来记录它的得分，称为历史得分，这些局面出现的次数越多它的历史得分就越高。当我们进行一个新的局面评估时，我们要对它们进行排列，并且保证历史得分最高的在前面，这样就可以尽快的进行alpha-beta裁剪，提高搜索速率。

杀手启发，这种搜索策略是一种特殊的历史启发，和历史启发不同的是杀手启发优先搜索造成每一层剪枝最多的走法。在搜索的 过程中，有一些走法很糟糕，它如果被搜索到就会被剪掉。将这些走法记录下来，当下一次搜索到同一层时，

第三章 系统分析和设计 13

如果杀手走法是当前局面的一个合理走法，那就优先搜索杀手节点，然后将其裁剪掉。

置换表，这种搜索策略是将搜索过程中的搜索信息记录下来。在以后的搜索中，如果搜索到的节点在记录表中已有记录，那就可以直接引用记录。置换表搜索策略和以上两个搜索策略不同的地方是，这个搜索策略不需要清空记录表，而是一直保存，为以后所用。

在本文文中，我们采用的历史启发这个搜索策略。我们可以使用各种排序算法对于走法进行排序，在此程序中采用了归并排序。归并排序的时间复杂度为O(nlog2n)，空间复杂度为O(n)，具有较高的效率。