- 电脑象棋循序渐进
-
-
- (五) 质的飞跃
-
- 与本文配套的示范程序是“象棋小巫师”0.5版，程序清单是：
- (1) XQWL05.CPP——C++源程序；
- (2) XQWLIGHT.RC——资源描述文件；
- (3) RESOURCE.H——资源符号定义文件；
- (4) RES目录——图标、图片、声音等资源。
-
- 在阅读本章前，建议读者先阅读象棋百科全书网计算机博弈专栏的以下几篇译文：
- (1) 基本搜索方法——简介(三)(David Eppstein)；
- (2) 基本搜索方法——置换表(Bruce Moreland)；
- (3) 其他策略——胜利局面(Bruce Moreland)。
-
- 5.1 置换表
-
- 没有置换表，就称不上是完整的计算机博弈程序。
- 象棋小巫师的置换表非常简单，以局面的
Zobrist Key % HASH_SIZE 作为索引值。每个置换表项存储的内容无非就是：A. 深度，B. 标志，C. 分值，D. 最佳走法，E. Zobrist Lock 校验码。置换表的处理函数也很传统——一个
ProbeHash 和一个 RecordHash 就足够了。
- 先说 RecordHash，即便采用深度优先的替换策略，RecordHash 也非常简单，在判断深度后，将
Hash 表项中的每个值填上就是了。
- 再看看 ProbeHash 是如何利用置换表信息的：
- (1) 检查局面所对应的置换表项，如果
Zobrist Lock 校验码匹配，那么我们就认为命中(Hit)了；
- (2) 是否能直接利用置换表中的结果，取决于两个因素：A. 深度是否达到要求，B. 非PV节点还需要考虑边界。
- 第二种情况是最好的(完全利用)，ProbeHash 返回一个非 -MATE_VALUE 的值，这样就能不对该节点进行展开了。
- 如果仅仅符合第一种情况，那么该置换表项的信息仍旧是有意义的——它的最佳走法给了我们一定的启发(部分利用)。
-
- 5.2 杀棋分数调整
-
- 象棋小巫师从学会走棋开始，就已经考虑了杀棋分数。不过增加了置换表以后，这个分数要进行调整——置换表中的分值不能是距离根节点的杀棋分值，而是距离当前(置换表项)节点的分值。所以当分值接近
INFINITY 或 -INFINITY 时，ProbeHash 和 RecordHash 都要做细微的调整：
- (1) 对于RecordHash：置换表项记录的杀棋步数
= 实际杀棋步数 - 置换表项距离根节点的步数；
- (2) 对于ProbeHash：实际杀棋步数
= 置换表项记录的杀棋步数
+ 置换表项距离根节点的步数。
-
- 5.3 杀手(Killer)走法
-
- 把这个术语取名为Killer真是有些奇怪，但我们还是沿用这个术语。
- 杀手走法就是兄弟节点中产生Beta截断的走法。根据国际象棋的经验，杀手走法产生截断的可能性极大，所以我们在中国象棋里吸取了这个经验。很显然，兄弟节点中的走法未必在当前节点下能走，所以在尝试杀手走法以前先要对它进行走法合理性的判断。我们在0.2版中就写过 LegalMove 这个函数，这里它将大显身手。如果杀手走法确实产生截断了，那么后面耗时更多的
GenerateMove 就可以不用执行了。
- 如何保存和获取“兄弟节点中产生截断的走法”呢？我们可以把这个问题简单化——距离根节点步数(nDistance)同样多的节点，彼此都称为“兄弟”节点，换句话说，亲兄弟、堂表兄弟以及关系更疏远的兄弟都称为“兄弟”。
- 我们可以把距离根节点的步数(nDistance)作为索引值，构造一个杀手走法表。象棋小巫师的每个杀手走法表项存有两个杀手走法，走法一比走法二优先：存一个走法时，走法二被走法一替换，走法一被新走法替换；取走法时，先取走法一，后取走法二。
-
- 5.4 优化走法顺序
-
- 利用各种信息渠道(如置换表、杀手走法、历史表等)来优化走法顺序的手段称为“启发”。象棋小巫师0.5以前，我们只用历史表作启发，但从这个版本开始，我们采用了多种启发方式：
- (1) 如果置换表中有过该局面的数据，但无法完全利用，那么多数情况下它是浅一层搜索中产生截断的走法，我们可以首先尝试它；
- (2) 然后是两个杀手走法(如果其中某个杀手走法与置换表走法一样，那么可以跳过)；
- (3) 然后生成全部走法，按历史表排序，再依次搜索(可以排除置换表走法和两个杀手走法)。
- 这样，我们就可以构造一个状态机，来描述走法顺序的若干阶段：
- 我们把状态机写在一个叫 Next 的函数中，那么 Alpha-Beta 的循环体就是：
-
- …… // 初始化状态机
- while ((mv = Next()) != 0) {
- MakeMove(mv);
- …… // Alpha-Beta递归调用
- UndoMakeMove(mv);
- …… // Alpha-Beta边界判断
- }
-
- 在 Next 函数中，我们用了不带break的switch ... case结构：
-
- switch (nPhase) {
- case PHASE_HASH:
- nPhase = PHASE_KILLER_1;
- …… // 如果有置换表走法，就可以返回，再次调用就直接跳到
PHASE_KILLER_1
- // 注意：这里没有break！
- case PHASE_KILLER_1:
- nPhase = PHASE_KILLER_2;
- ……
- }
-
- 这就是“基于置换表的启发式Alpha-Beta搜索”，目前顶尖的电脑(国际)象棋程序都逃脱不了这种架构，只不过它们在置换表和启发算法上更加优化而已。
上一篇 电脑象棋循序渐进(四)：稍微聪明些了
下一篇 电脑象棋循序渐进(六)：精益求精
返 回 象棋百科全书——计算机博弈
