|
解剖大象的眼睛——中国象棋程序设计探索
黄晨 * 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)窗口作搜索,以减少搜索的结点数。
|
|