- 电脑象棋循序渐进
-
-
- (六) 精益求精
-
- 与本文配套的示范程序是“象棋小巫师”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之间，那么这个局面就是“利用长将判负策略搜索到的局面”。
- 我们仍旧把部分“利用长将判负策略搜索到的局面”记录到置换表，因为这些局面提供的最佳走法是有启发价值的。反过来说，如果“利用长将判负策略搜索到的局面”没有最佳走法，那么这种局面就没有必要记录到置换表了。
- 经过这种处理，我们的程序在杀棋阶段不再会走出莫名其妙的走法了，最后一个疑难杂症终于攻克了。
上一篇 电脑象棋循序渐进(五)：质的飞跃
下一篇
返 回 象棋百科全书——计算机博弈
