解剖大象的眼睛——中国象棋程序设计探索(七)：后台思考和时间策略

auntyellow

解剖大象的眼睛——中国象棋程序设计探索

　

黄晨 *　2005年6月

　

(七) 后台思考和时间策略

　

　　(1) 其他策略——后台思考(Bruce Moreland)。

　

7.1 后台思考

　

　　ElephantEye支持两种协议，UCCI协议不需要对后台思考作特别处理，如果引擎接收了指令“go ponder ...”，那么搜索过程中时钟暂时不起作用，直到收到“ponderhit”指令后才启用时钟。因此，后台思考实际上相当于无限制的思考。

　　而在浅红象棋协议中，后台思考完全是由引擎自己来支配的，ElephantEye的主模块<eleeye09.cpp>中，大量的代码是用来解决这个问题的。实现后台思考需要用到两个标志，在<eleeye09.cpp>中它们是QhPonder(引擎处于后台思考状态)和QhPonderFin(后台思考搜索完毕)，分别说明两个着法QhPonderMove和QhPonderFinMove有效。这些变量的设置规则如下：

　　(1) 当程序思考完一个局面时，马上进入后台思考，QhPonder置1，而QhPonderMove则是猜测着法，QhPonderFin置0；

　　(2) 如果对手给出的着法让后台思考命中，而后台思考并未结束(QhPonderFin置0)，则QhPonder置0，转入正常思考；

　　(3) 如果对手给出的着法没有让后台思考命中，而后台思考并未结束，则QhPonder置0，后台思考中断，程序重新开始思考；

　　(4) 如果后台思考在对手给出着法之前结束，则QhPonderFin置1，而QhPonderMove则保存后台思考的结果；

　　(5) 如果对手给出的着法让后台思考命中，而后台思考已经结束(QhPonderFin置1)，则程序直接给出QhPonderFinMove着法，QhPonder和QhPonderMove都置0；

　　(6) 如果对手给出的着法没有让后台思考命中，而后台思考已经结束，则程序重新开始思考，QhPonder和QhPonderMove都置0。

　

7.2 时间策略

　

　　时间策略在各个象棋程序中差异很大，有的程序根本没有时间策略，只能设定固定的搜索深度，或者在固定的时间中止思考，例如浅红象棋协议目前就没有时间策略。UCCI协议可以把时限规则告诉引擎，由引擎自动分配时间，时限规则可以是以下两种：

　　(1) 时段制，即在限定时间内走完规定的步数，用“go time <time> movestogo <moves_to_go>”命令；

　　(2) 加时制，即在限定时间内走完整盘棋，但每步会加上几秒，用“go time <time> increment <increment>”命令。

　　ElephantEye的时间策略由<ccsearch.h>里的Control()函数来处理，不管处理哪个规则，都会分配一个合适的时间(ProperTime)用来走棋，这个时间是这样计算的：

　　(1) 时段制：分配时间 = 剩余时间 / 要走的步数；

　　(2) 加时制：分配时间 = 每步增加的时间 + 剩余时间 / 20 (即假设棋局会在20步内结束)；

　　在搜索过程中，超时是由Interrupt()函数来控制的。如果时间超过分配时间的两倍，或者即将花完所有剩余时间，则强行中止搜索。另外，搜索过程每进行一段时间，都会由PopInfo()函数给出一个新的结果，此时看一下用时是否超过分配时间的一半，超过的话就中止搜索。

　　由此看出，ElephantEye每步的耗时在 ProperTime / 2 和 ProperTime x 2 之间，而这个时间段在大多数情况下会给出一个新的着法，因此不太会有浪费的时间。如果程序的时间策略仅仅是每步限制固定的时间，那么在做迭代加深时，浅一层搜索早就做完，而深一层搜索迟迟出不了结果，就被强行中止了，那么从浅一层搜索做完到强行中止的这段时间白白浪费了。

　

7.3 搜索杀棋的策略

　

　　ElephantEye没有专门搜索杀棋的功能，如果存在杀棋的话(不管是杀死对方还是被对方杀死)，会在搜索中自动找到。是否能找到杀棋和搜索深度有关，某一深度下找不到杀棋，但深一层搜索就可能找到；但和一般局面不同的是，如果一定深度能找到杀棋，那么再深的深度会得到同样的结果。因此，如果找到杀棋，那么程序要使用不同的策略。ElephantEye处理杀棋局面时，用到以下几个策略：

　　(1) 置换表的存取策略，前面曾经介绍过，如果置换表中存储的某个局面已被确认找到杀棋，那么探测到这样的局面时就不需要考虑深度条件。

　　(2) 根结点做迭代加深时，找到杀棋后搜索就立即停止。ElephantEye为杀局设定了边界MateValue，其值略比MaxValue小一些，局面分值在区间(-MateValue, MateValue)以外，就说明该局面有杀棋。

　　(3) 如果根结点的所有着法中，除了一个着法可以支撑(即分值大于-MateValue)以外，其余着法都会输掉(即分值都小于-MateValue)，那么应该立即返回这个唯一着法。这就是说，当迭代加深时遇到这种情况，那么没有必要做更深的搜索了。0.94版本的ElephantEye还没有用到这种策略，但笔者可以简单介绍一下实现思路：在搜索完成后，对最佳着法设为禁着，再对根结点作一次搜索，如果分值小于-MateValue，则说明除这个最佳着法以外其余着法都会输掉。这里可以使用一个空着裁剪中的诀窍，即用(-MateValue, 1 - MateValue)窗口作搜索，以减少搜索的结点数。