解剖大象的眼睛——中国象棋程序设计探索（三）
发布时间：2008-11-20
点击：
来源：本站原创
录入者：黄晨
(三) 搜索与置换表
在阅读本章前，建议读者先阅读《象棋百科全书》网站中《对弈程序基本技术》专题的以下几篇译文：
(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参考了中国象棋程序“纵马奔流”的做法，采用双层结构的置换表。
简单地说，双层置换表的第一层使用了深度优先策略，第二层使用了始终覆盖策略。记录置换表时，如果第一层没能覆盖(因为深度太浅)，那么覆盖第二层；读取置换表时，如果第一层没有命中，那么读取第二层。当然，“纵马奔流”还作了新的尝试，当第一层置换表被覆盖时(由于深度足够)，原来被覆盖的表项就保存到第二层。换句话说，无论深度如何，写入置换表的深度总会和第一层比较，深的留在第一层，浅的被放入第二层。
ElephantEye就使用这个策略，并且用两个变量dwHitFirst和dwHitSecond来分别说明第一层和第二层置换表的命中结点数。当搜索结点数不多时，第一层命中结点数占绝大多数，但随着搜索深度的增长，搜索结点数不断上升，此时第二层命中结点数多了起来，直到和第一层差不多，这就说明第二层置换表对搜索效率的提高起到了作用。
 关闭窗口  打印文档 |
账号登录