中国象棋程序设计探索
　
象棋百科全书网 (webmaster@xqbase.com)
2005年6月初稿，2007年5月修订
　
(三) 搜索与置换表
　
　　在阅读本章前，建议读者先阅读象棋百科全书网中《对弈程序基本技术》专题的以下几篇译文：
　　(1) 基本搜索方法——简介(一)(David Eppstein)；
　　(2) 基本搜索方法——简介(二)(David Eppstein)；
　　(3) 基本搜索方法——简介(三)(David Eppstein)；
　　(4) 基本搜索方法——最小-最大搜索(Bruce Moreland)；
　　(5) 基本搜索方法——Alpha-Beta搜索(Bruce Moreland)；
　　(6) 基本搜索方法——迭代加深(Bruce Moreland)；
　　(7) 基本搜索方法——置换表(Bruce Moreland)；
　　(8) 高级搜索方法——简介(二)(David Eppstein)；
　　(9) 高级搜索方法——搜索的不稳定性(Bruce Moreland)；
　　(10) 其他策略——胜利局面(David Eppstein)。
　
3.1 搜索技术概述
　
　　搜索算法是象棋程序的核心算法，在众多搜索算法中，如何选择适合自己的算法，并有效地把它们组合起来，是决定搜索效率的关键所在。要做好这点，首先必须明确搜索的概念，把各种搜索算法作一下分类。
　　象棋程序的搜索算法都是基于“最小-最大”策略的，因此衍生出以Alpha-Beta为基础的完全搜索算法以及带裁剪的搜索算法。尽管Alpha-Beta算法也有裁剪的过程，但是这种裁剪被证明是绝对可靠的，没有无负面作用，即通常所说的“截断”(Cut-off)，它属于申朗所说的A策略。
　　我们现在所说的“裁剪”(Pruning)，特指“向前裁剪”(Forward Pruning)，即需要承担风险地对某些线路作的裁剪，也就是申朗所说的B策略。尽管它是完全搜索算法的对立面，但为了克服完全搜索中的“水平线效应”(Horizon Effect)，它是程序中必不可少的部分。把裁剪反过来，对某些重要线路进行“延伸”(Extension)，这种思想和裁剪有异曲同工之妙。
　　如今，“带置换表的启发式Alpha-Beta搜索”成了象棋程序的主流，这种思想强调对着法排序的重要性，排序着法是由“启发”(Heuristic)算法来完成的，它同“置换表”(Transposition Table)一起，使搜索效率有大幅度的提高。
　　因此，搜索算法大致可以分为以下四类：
　　(1) 完全搜索算法，即Alpha-Beta搜索及其变种，诸如期望窗口、PVS、MTD(f)等；
　　(2) 启发算法，对着法顺序进行优化，尽可能地提高Alpha-Beta搜索的效率，中国象棋中的启发算法有置换表启发、吃子启发、杀手着法启发和历史表启发等；
　　(3) 裁剪算法，运用棋类知识略去对某些着法的搜索，以提高搜索深度，中国象棋中最常用的裁剪算法是空着裁剪，当然还有其他方法。
　　(4) 置换表。
　　以上算法中，置换表被独立归为一类，因为它不但功能特殊，而且值得研究问题最多。置换表的初衷是利用置换现象来减少搜索(即置换裁剪，属于裁剪算法的范畴)，然而在象棋的中局阶段，置换现象并不那么普遍，因此它的主要功效在于启发(即置换表启发，属于启发算法的范畴)。另外，置换现象会导致搜索的不稳定性，因而会产生很多负面作用(毕竟是裁剪的一种形式)，而要彻底研究清楚并非那么容易。
　
3.2 超出边界的Alpha-Beta搜索
　
　　置换表的大部分问题出在边界上，直到目前笔者还无法彻底明白该如何设置边界，因此想把这个问题留给读者。首先我们从不带置换表的超出边界(Fail-Soft)的Alpha-Beta搜索说起：
　
int AlphaBeta(int Alpha, int Beta, int Depth) {
　if (GameOver() || Depth <= 0) {
　　Value = Evaluate();
　　// if (Value >= Beta) return Beta;
　　// if (Value <= Alpha) return Alpha;
　　return Value;
　}
　Best = -MaxValue;
　GenMoves();
　while (MovesLeft()) {
　　MakeNextMove();
　　Value = -AlphaBeta(-Beta, -Alpha, Depth - 1);
　　UndoMakeMove();
　　if (Value >= Beta) {
　　　// return Beta;
　　　return Value;
　　}
　　if (Value > Best) {
　　　Best = Value;
　　　if (Value > Alpha) {
　　　　Alpha = Value;
　　　}
　　}
　}
　// return Alpha;
　return Best;
}
　
　　以上代码中，蓝色的被注释掉的部分是不超出边界的Alpha-Beta搜索，红色的代码就是超出边界的Alpha-Beta搜索了。如果不使用置换表，那么这种改动和原来没有区别，但是在置换表的作用下，情况就会有微妙的变化。探索置换表的形式(是否超出边界)应该与Alpha-Beta的形式保持一致：
　
int ProbeHash(int Alpha, int Beta, int Depth) {
　……
　if (Hash.Flag == HASH_BETA) {
　　if (Hash.Value >= Beta) {
　　　// return Beta;
　　　return Hash.Value;
　　}
　} else if (Hash.Flag == HASH_ALPHA) {
　　if (Hash.Value <= Alpha) {
　　　// return Alpha;
　　　return Hash.Value;
　　}
　} else if (Hash.Flag == HASH_PV) {
　　// if (Hash.Value >= Beta) return Beta;
　　// if (Hash.Value <= Alpha) return Alpha;
　　return Hash.Value;
　}
}
　
　　同样的问题出现在记录置换表时：
　
int AlphaBeta(int Alpha, int Beta, int Depth) {
　……
　while (……) {
　　……
　　if (Value >= Beta) {
　　　// RecordHash(Beta, HASH_BETA, Depth);
　　　RecordHash(Value, HASH_BETA, Depth);
　　　return ……;
　　}
　　……
　}
　// RecordHash(Alpha, HashFlag, Depth);
　RecordHash(Best, HashFlag, Depth);
　return ……;
}
　
　　在带置换表的Alpha-Beta搜索中，到底超出边界(Fail-Soft)和不超出边界(Fail-Hard)哪个效率更高，到现在为止还很难有定论。从上面的代码中可以看出，采用超出边界算法时，置换表的边界变窄了，即Beta结点的可能值从(Beta, MATE_VALUE缩小为(Value, MATE_VALUE)，本来低于Beta才会命中的结点，现在只要低于Value就能命中了。但是很多试验表明，某些局面在使用了超出边界算法时，搜索的结点数反而增加了。因为置换现象会产生搜索的不稳定性，置换表命中率高也会导致不稳定性的增强，搜索的结点数增加就是其中一个表现。
　
3.3 胜利局面的特殊处理
　
　　胜利局面就是程序能搜索到的有杀局的局面，它具有特殊的分值——最大值减去“根结点”到“将死结点”的步数(简称杀棋步数或DTM)。而当这个数值记录到置换表的时候，就必须转化为最大值减去“当前结点”到“将死结点”的步数。
　　除此以外杀局还有一个显著的特点——对一个局面进行某一深度的搜索后，如果已经证明它是杀局，那么就不必进行更深层次的搜索了。利用这点，可以改进探索置换表的程序，提高置换表的命中率，从而提高搜索效率：
　
const int WIN_VALUE = MATE_VALUE - 100;
　
int ProbeHash(int Alpha, int Beta, int Depth) {
　……
　MateNode = false;
　if (Hash.Value > WIN_VALUE) {
　　Hash.Value -= Ply;
　　MateNode = true;
　} else if (Hash.Value < -WIN_VALUE) {
　　Hash.Value += Ply;
　　MateNode = true;
　}
　if (MateNode || Hash.Depth > Depth) {
　　……
　}
}
　
　　这样做似乎在中局阶段并不能起到很好的效果，但是在处理杀局和残局时，搜索的结点数大幅度降低了，ElephantEye在使用了这种方法以后，杀局和残局的处理能力有了很大的提高。
　
3.4 长将禁手局面的特殊处理
　
　　由于单方面长将不变作负的规则，从表面上看，如果发生这种情况就应该，给予-MATE_VALUE的值，再根据杀棋步数作调整。但是由于长将判负并不是对某个单纯局面的评分，而是跟路径有关的，所以使用置换表时就会产生非常严重的后果，这也是搜索不稳定性的一个来源。简而言之，即同一局面由于形成路径不同而有不同的分值。
　　最简单的解决办法就是不要把“利用长将判负策略搜索到的局面”记录到置换表中，为此把长将判负的局面定为BAN_VALUE，定义为MATE_VALUE - 50，再根据杀棋步数作调整。考虑到搜索层数通常不会超过50层，因此如果某个局面分值在WIN_VALUE(即MATE_VALUE - 100)和BAN_VALUE之间，那么这个局面就是“利用长将判负策略搜索到的局面”，不记录到置换表中。根据这个思路，代码就应该写成：
　
const int BAN_VALUE = MATE_VALUE - 50;
　
void RecordHash(int HashFlag, int Value, int Depth) {
　if (Value > WIN_VALUE) {
　　if (Ply > 0 && Value <= BAN_VALUE) {
　　　return;
　　}
　　Value += Ply;
　} else if (Value < -WIN_VALUE) {
　　if (Ply > 0 && Value >= -BAN_VALUE) {
　　　return;
　　}
　　Value -= Ply;
　}
　……
}
　
　　之所以允许Ply == 0的结点写入置换表，是因为这样的结点是根结点，ElephantEye需要依靠它来获得最佳着法。
　
3.5 置换表的覆盖策略
　
　　置换表的覆盖策略通常有两种：深度优先和始终覆盖。ElephantEye以前几个版本只用了深度优先的策略，因此代码并不复杂，并且在搜索时间不太长的情况下，这种策略非常有效。但当置换表接近填满的时候，把深度优先和始终覆盖两种策略结合起来，效果就会很明显了。那么如何把这两种覆盖策略结合起来呢？
　　ElephantEye参考了国际象棋程序Fruit的做法，采用多层结构的置换表。简而言之，一个m层的置换表有n个Hash位置，每个Hash位置记录m个局面，那么整个Hash表可记录m × n个局面信息。记录一个局面时，找到它对应的Hash位置中的m个局面，不考虑该局面本身的搜索深度，而直接覆盖深度最小的那个局面。这种策略的本质就是将深度优先和始终覆盖结合起来——原先深度最小的那个局面是始终覆盖的，而其余m - 1个搜索深度更深的局面则被保留下来。
  • 上一篇　中国象棋程序设计探索(二)：棋盘结构和着法生成器
  • 下一篇　中国象棋程序设计探索(四)：启发算法
  • 返　回　象棋百科全书——电脑象棋
    •

    www.xqbase.com