中国象棋程序设计探索
　
象棋百科全书网 (webmaster@xqbase.com)
2005年6月初稿，2007年12月修订
　
(五) 克服水平线效应
　
　　在阅读本章前，建议读者先阅读象棋百科全书网中《对弈程序基本技术》专题的以下几篇译文：
　　(1) 高级搜索方法——简介(一)(David Eppstein)；
　　(2) 高级搜索方法——静态搜索(Bruce Moreland)；
　　(3) 高级搜索方法——空着裁剪(Bruce Moreland)；
　　(4) 其他策略——重复检测(Bruce Moreland)；
　　(5) 其他策略——藐视因子(Bruce Moreland)。
　
　　在象棋程序的搜索技术中，裁剪和延伸是最有挖掘潜力之处，在各个程序中的差异也比较大。ElephantEye在这方面没有花太多的笔墨，空着裁剪、静态搜索和选择性延伸跟其他程序大同小异，读者可能会认为“历史表裁剪”(History Pruning)是ElephantEye的亮点，但是笔者对该算法的原理并未完全把握，而且很多细节还有待摸索，所以这里就不作介绍，有兴趣的读者可参考ElephantEye源程序中<search.cpp>的相关注释。笔者将对几个比较成熟可靠的算法作一些介绍。
　
5.1 无害裁剪
　
　　很多局面不需要搜索即可知道它的确切评价值，或者至少超出Alpha-Beta窗口，此时就可以把该结点以下的搜索树裁剪掉，而不影响搜索结果，这类裁剪称为“无害裁剪”，ElephantEye使用了以下几种无害裁剪：
　　(1) 杀棋步数(DTM)裁剪。由于DTM调整的缘故，在深度为Ply的结点中，搜索结果不会落在窗口(Ply - MATE_VALUE, MATE_VALUE - Ply)外，所以当(Alpha, Beta)窗口和该窗口没有交叠时，立即可以作出裁剪。裁剪有两种情况，要么MATE_VALUE - Ply <= Alpha，要么Ply - MATE_VALUE >= Beta，ElephantEye只考虑了后者。
　　(2) 重复裁剪。如果出现重复局面，那么应当根据规则直接判和或判某方长打作负，所以应当返回相应的分值。尽管象棋规则规定局面重复三次或更多次才予以判定，但在搜索过程中只要遇到一次重复，继续搜索下去就会有第二次、第三次，所以ElephantEye只要遇到一次重复就不再搜索下去，但根结点要另外处理(否则一个着法也没搜索，就出不了子了)。
　　(3) 和棋裁剪。如果双方都没有明显可以杀死对方的子力，即可返回和棋分值(0或藐视因子)，而不必继续往下搜索。ElephantEye把双方都只剩下仕(士)相(象)的局面规定为和棋局面。
　　(4) 置换裁剪。置换表的一个作用就是利用置换现象裁剪掉某些分枝，前面已经作了详细的介绍。这里要提的是，由于存在“搜索的不稳定性”的原因，置换裁剪并非绝对无害的，ElephantEye就不记录“利用长将判负策略搜索到的局面”，前面也有所介绍。
　
5.2 带检验的空着裁剪
　
　　“带检验的空着裁剪”(Verified Null-Move Pruning)指的是检验空着裁剪是否安全的算法，它首先由Tabibi发表在2002年的ICGA(原ICCA)杂志上(参阅Tabibi OD, Netanyahu NS: Verified Null-Move Pruning, ICGA J. 25 (3): 153-161, 2002，可以从互联网上找到)。其内容可以概括为：
　　(1) 用R = 3的空着裁剪进行搜索；
　　(2) 如果高出边界，那么做浅一层的搜索(这就意味着一层的搜索是无法做带验证的空着裁剪的)；
　　(3) 做浅一层的搜索时，子结点用R = 3的不带验证的空着裁剪；
　　(4) 如果浅一层的搜索高出边界，那么带验证的空着裁剪是成功的，否则必须重新做完全的搜索。
　　笔者认为这里存在很多问题：
　　(1) 用R = 3非常冒进，还是用R = 2比较合适；
　　(2) 检验时做浅一层的搜索太浪费时间，裁剪的层数可以跟空着裁剪一样的R值一样，而且窗口也用以Beta为界的零窗口；
　　(3) 做检验时，子结点仍旧应该做带检验的空着裁剪，否则“连停着杀”就检测不出来了。
　　ElephantEye是否启用空着裁剪，分三种情况讨论：
　　(1) 我方进攻子力达到3个，就使用不带检验的空着裁剪；
　　(2) 我方进攻子力小于3个，则使用带检验的空着裁剪；
　　(3) 我方只有仕(士)相(象)等守子，则禁用空着裁剪。
　　因此，ElephantEye的代码中，和空着裁剪有关的部分如下：
　
const int NULL_REDUCTION = 2
　
int AlphaBeta(int Alpha, int Beta, int Depth, bool Verify = false) {
　……
　if (!Verify && !InCheck() && NullOkay()) {
　　MakeNull();
　　Value = -AlphaBeta(-Beta, 1 - Beta, Depth - 1 - NULL_REDUCTION);
　　UndoNull();
　　if (Value >= Beta && (NullSafe() || AlphaBeta(Beta - 1, Beta, Depth - NULL_REDUCTION, true) >= Beta)) {
　　　return Value;
　　}
　}
　……
}
　
　　这个技术使得ElephantEye在残局中仍旧能启用空着裁剪，而且不会出现走错的情况，因此ElephantEye在几乎不带残局知识的情况下，残局的棋力还是非常高的。
　
5.3 静态搜索
　
　　静态搜索尽管实现起来比较简单，但是很多技术细节仍旧是需要考虑的，问题主要有以下几个：
　　(1) 如果结点被将军，是否要产生全部着法。绝大多数程序都没有考虑结点被将军的情况，因为将军判断是很花费时间的。而ElephantEye在将军判断上有优势，因此在将军时产生全部的着法。因此有些多步连杀的排局，如果每步将军都吃子，那么ElephantEye只需要搜索1层就可以解出了，因此静态搜索中判断将军对于搜索杀棋是很有好处的。
　　(2) 如何使用MVV/LVA启发。MVV/LVA是静态搜索最常用的启发方式，如果棋盘的数据结构精心设计，SEE也是值得尝试的。尽管MVV/LVA很简单，但是究竟根据“被吃子价值-攻击子价值”来排序，还是先排序“被吃子价值”，相同的情况再排序“攻击子价值”呢？ElephantEye是以MVV(LVA)的值为依据的，可参考前一章(吃子启发)。
　　(3) 是否需要用其他搜索或启发算法。常规搜索中的很多搜索算法都不适合于静态搜索，这就是静态搜索简单的缘故。静态搜索本身就是空着启发的(第一个着法总是空着)，但由于没有深度参数，所以不可能使用空着裁剪。另外，几乎所有的程序都不在静态搜索中使用PVS、置换表、杀手着法启发、历史表启发等算法。
　　(4) 是否所有的吃子都需要考虑。如果搜索全部吃子着法，那么程序在叶子结点上花费的时间就非常浪费。ElephantEye在搜索所有吃子着法时，对着法作了过滤——吃不过河的兵和吃仕(士)相(象)的着法都不搜索了，尽管仕(士)和相(象)在ElephantEye的子力评价中分数很高(轻子价值的20%到40%)，但静态搜索本身就是对局面的粗略评价。
　
5.4 选择性延伸
　
　　常用的选择性延伸有这几种策略：(1) 将军延伸；(2) 单一应着延伸；(3) 杀棋威胁延伸；(4) 兑子延伸；(5) 通路兵挺进延伸。ElephantEye只考虑了前两种，代码很简单：
　
int AlphaBeta(int Alpha, int Beta, int Depth) {
　……
　MoveStruct ThisMove = NextMove();
　while (ThisMove != NullMove) {
　　MakeMove(ThisMove);
　　NewDepth = (InCheck() || SingleReply() || MateThreat() || ReCapture() ? Depth : Depth - 1);
　　Value = Search(-Beta, -Alpha, NewDepth);
　　UndoMove();
　　……
　　ThisMove = NextMove();
　}
　……
}
　
　　ElephantEye的早期版本采用了杀棋威胁延伸和兑子延伸(以上代码中的蓝色部分)，尽管现在已经不再使用了，但这里不妨介绍一下。
　　杀棋威胁延伸指的是，对方走出一步催杀的棋时，需要多搜索一层，而判断对方是否催杀则是利用空着裁剪，为此空着裁剪的代码应该作适当的修改：
　
……
MateThreat = false;
if (!InCheck() && NullOkay()) {
　MakeNull();
　Value = -AlphaBeta(-Beta, 1 - Beta, Depth - 1 - NULL_REDUCTION);
　UndoNull();
　if (Value >= Beta) {
　　return Value;
　} else if (Value == Ply + 2 - MATE_VALUE) {
　　MateThreat = true;
　}
}
……
　
　　如果本方走了空着，而立即被对方将死(该结点的深度是Ply + 2)，那么返回值作DTM调整将变成Ply + 2 - MATE_VALUE，因此该值就成为判断是否催杀的依据。
　　兑子延伸指的是，遇到连续两个吃子着法，并且吃同一格子的子，这样的着法称为“吃回”(ReCapture)，需要多搜索一层，为此判断两个着法是否吃回的函数可以写成：
　
inline bool ReCapture(MoveStruct LastMove, MoveStruct ThisMove) {
　return LastMove.Cpt != 0 && LastMove.Dst == ThisMove.Dst
}
  • 上一篇　中国象棋程序设计探索(四)：启发算法
  • 下一篇　中国象棋程序设计探索(六)：并行搜索技术探索
  • 返　回　象棋百科全书——电脑象棋
    •

    www.xqbase.com