电脑象棋循序渐进(六)：精益求精

(六) 精益求精

与本文配套的示范程序是“象棋小巫师”0.6版，程序清单是：

(1) XQWL06.CPP——C++源程序；

(2) XQWLIGHT.RC——资源描述文件；

(3) RESOURCE.H——资源符号定义文件；

(4) RES目录——图标、图片、声音等资源；

(5) BOOK.DAT——开局库文件。

在阅读本章前，建议读者先阅读象棋百科全书网计算机博弈专栏的以下几篇译文：

(1) 高级搜索方法——主要变例搜索(Bruce Moreland)；

(2) 高级搜索方法——搜索的不稳定性(Bruce Moreland)。

尽管我们的程序在架构上已经接近完整，但细节上存在不少问题：

(1) 对于同一个局面，总是走固定的走法；

(2) 搜索算法是否能更优化一些(某些读者听说过PVS、Nega-Scout之类的算法)；

(3) 有些杀棋局面会走出莫名其妙的走法。

本章我们将把这些问题一一解决。

6.1 开局库

开局库几乎是每个象棋程序必备的部件，它的好处是：

(1) 即使再笨的程序，开局库能使得它们在开局阶段看上去不那么业余；

(2) 通过随机选择走法，让开局灵活多变，增加对弈的趣味性。

象棋小巫师使用开源象棋程序 ElephantEye 的开局库，开局库文件 BOOK.DAT 的结构是：

struct BookItem {
　DWORD dwLock;
　WORD wmv, wvl;
} BookTable[BOOK_SIZE];

其中，dwLock 记录了局面 Zobrist 校验码中的 dwLock1，wmv 是走法，wvl 是权重(随机选择走法的几率，仅当两个相同的 dwLock 有不同的 wmv 时，wvl 的值才有意义)。

搜索一个局面时，首先不做Alpha-Beta搜索，而是查找 BookTable 中有没有对应的项，有的话就直接返回一个走法。由于 ElephantEye 在制作开局库时是按照 dwLock 排序的，因此可以用二分查找。找到一项以后，把它前后 dwLock 相同的所有项都取出，从中随机选择一个 wmv。

ElephantEye 为了压缩开局库的容量，所有对称的局面只用一项，所以当一个局面在 BookTable 中找不到时，还应该试一下它的对称局面是否在 BookTable 中。

6.2 根节点的特殊处理

现在我们的程序一开局不会总是跳正马了，根据 ElephantEye 提供的开局库，它大部分时候走中炮，有时也走仙人指路(进兵)或飞相。可是当它脱离开局库时，仍然摆脱不了思维的单一性，例如我们第一步走边兵(开局库中当然没有这个局面)，它仍旧只会跳同一边的正马。

一个解决办法是：在根节点处，让一个不是最好的走法也能在一定的几率取代前一个走法。我们的程序是这样写的：

if (vl > vlBest) {
　vlBest = vl;
　对vlBest作小范围的随机浮动;
}

我们把根节点的搜索函数单独分离，这样做有很多好处：

(1) 处理思考的随机性;

(2) 没有必要尝试 Beta 截断(根节点处 Beta 始终是 +INFINITY);

(3) 省略了检查重复局面、获取置换表、空步裁剪等步骤。

6.3 PVS

很多计算机博弈的资料都介绍了PVS算法，但它只有当走法顺序充分优化时才能带来明显的好处，因此象棋小巫师直到最后一个版本才用了这种算法。

6.4 长将判负策略

由于单方面长将不变作负的规则，0.6以前的版本如果发生这种情况，想当然地给予-MATE_VALUE的值，再根据杀棋步数作调整。但是由于长将判负并不是对某个单纯局面的评分，而是跟路线有关的，所以使用置换表时就会产生非常严重的后果——某个局面的信息可能来自另一条不同的路线。

象棋小巫师的解决办法就是：获取置换表时把“利用长将判负策略搜索到的局面”过滤掉。为此这个版本中我们把长将判负的局面定为BAN_VALUE(MATE_VALUE - 100)，如果某个局面分值在WIN_VALUE(MATE_VALUE - 200)和BAN_VALUE之间，那么这个局面就是“利用长将判负策略搜索到的局面”。

我们仍旧把部分“利用长将判负策略搜索到的局面”记录到置换表，因为这些局面提供的最佳走法是有启发价值的。反过来说，如果“利用长将判负策略搜索到的局面”没有最佳走法，那么这种局面就没有必要记录到置换表了。

经过这种处理，我们的程序在杀棋阶段不再会走出莫名其妙的走法了，最后一个疑难杂症终于攻克了。