- 中国象棋程序设计探索
-
- 2005年6月初稿，2007年5月修订
-
- (八) 后台思考和时间策略
-
- 在阅读本章前，建议读者先阅读象棋百科全书网中《对弈程序基本技术》专题的以下几篇译文：
- (1) 其他策略——后台思考(Bruce Moreland)。
-
- 8.1 后台思考
-
- UCCI协议不需要对后台思考作特别处理，如果引擎接收了指令“go ponder ...”，那么搜索过程中时钟暂时不起作用，直到收到“ponderhit”指令后才启用时钟。因此，后台思考实际上相当于无限制的思考。
-
- 8.2 时间策略
-
- 时间策略在各个象棋程序中差异很大，有的程序根本没有时间策略，只能设定固定的搜索深度，或者在固定的时间中止思考，例如浅红象棋协议目前就没有时间策略。UCCI协议可以把时限规则告诉引擎，由引擎自动分配时间，时限规则可以是以下两种：
- (1) 时段制，即在限定时间内走完规定的步数，用“go time <time> movestogo
<moves_to_go>”命令；
- (2) 加时制，即在限定时间内走完整盘棋，但每步会加上几秒，用“go time <time> increment
<increment>”命令。
- ElephantEye的时间策略由<search.h>里的SearchMain()函数来处理，不管处理哪个规则，都会分配一个合适的时间(ProperTime)用来走棋，这个时间是这样计算的：
- (1) 时段制：分配时间
= 剩余时间 / 要走的步数；
- (2) 加时制：分配时间
= 每步增加的时间
+ 剩余时间 / 20 (即假设棋局会在20步内结束)；
-
- 在每次迭代加深的过程中，一个深度结束后，即将进行更深一层的搜索时，需要根据用时来判断是否终止搜索，判断的依据通常有：
- (1) 一般情况下，用时超过分配时间的一半，就要终止搜索；
- (2) 如果连续
n 次的迭代加深返回同样的着法，那么用时超过分配时间的1/4时就可以终止搜索，因为更深一层的搜索很有可能还是得到同样的着法；
- (3) 如果当前深度得到的分值比上一深度到的分值低很多，那么用时超过分配时间才终止搜索(仅仅超过分配时间的一半是不够的)，期待搜索得更深以挽回劣势。
- 另外，搜索程序还会确定一个最大搜索时间(通常是剩余时间的一半)，如果搜索花费的时间超过预先设定的最大搜索时间，则强行中止搜索，这个检测过程由Interrupt()函数来完成。
-
- 8.3 搜索杀棋的策略
-
- ElephantEye没有专门搜索杀棋的功能，如果存在杀棋的话(不管是杀死对方还是被对方杀死)，会在搜索中自动找到。是否能找到杀棋和搜索深度有关，某一深度下找不到杀棋，但深一层搜索就可能找到；但和一般局面不同的是，如果一定深度能找到杀棋，那么再深的深度会得到同样的结果。因此，如果找到杀棋，那么程序要使用不同的策略。ElephantEye处理杀棋局面时，用到以下几个策略：
- (1) 置换表的存取策略，前面曾经介绍过，如果置换表中存储的某个局面已被确认找到杀棋，那么探测到这样的局面时就不需要考虑深度条件。
- (2) 根结点做迭代加深时，找到杀棋后搜索就立即停止。ElephantEye为杀局设定了边界WIN_VALUE，其值略比MATE_VALUE小一些，局面分值在区间(-WIN_VALUE, WIN_VALUE)以外，就说明该局面有杀棋。
- (3) 如果根结点的所有着法中，除了一个着法可以支撑(即分值大于-WIN_VALUE)以外，其余着法都会输掉(即分值都小于-WIN_VALUE)，那么应该立即返回这个唯一着法。
- 最后一点是ElephantEye最有特色之处，这就是说，当迭代加深过程中遇到这种情况时，就没有必要做更深的搜索了。在对某个深度的完全搜索完成后，对最佳着法设为禁着，再对根结点作一次搜索，如果分值小于-WIN_VALUE，则说明除这个最佳着法以外其余着法都会输掉，这种搜索称为“唯一着法检验搜索”，<search.cpp>中需要用变量bCheckUnique来控制。启用唯一着法检验搜索时，有两个地方要注意：
- (1) 使用零窗口的技巧，即用(-WIN_VALUE, 1 - WIN_VALUE)窗口作搜索，以减少搜索的结点数；
- (2) 根结点不记录到置换表中。
上一篇 中国象棋程序设计探索(七)：开局库
下一篇 中国象棋程序设计探索(九)：局面评价函数
返 回 象棋百科全书——电脑象棋
