解剖大象的眼睛——中国象棋程序设计探索（八）
发布时间：2008-11-20
点击：
来源：本站原创
录入者：黄晨
(八) 后台思考和时间策略
在阅读本章前，建议读者先阅读《象棋百科全书》网站中《对弈程序基本技术》专题的以下几篇译文：
(1) 其他策略——后台思考(Bruce Moreland)。
8.1 后台思考
UCCI协议不需要对后台思考作特别处理，如果引擎接收了指令“go ponder ...”，那么搜索过程中时钟暂时不起作用，直到收到“ponderhit”指令后才启用时钟。因此，后台思考实际上相当于无限制的思考。
ElephantEye从1.04版本开始就不再支持浅红象棋协议，而此功能被适配器UCCI2QH所代替，该程序中的大量的代码是用来解决后台思考问题的，其中状态变量nStatus的控制是关键，该变量的设置规则可参考<ucci2qh.cpp>源程序中的相关注释。
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步内结束)；
在搜索过程中，超时是由Interrupt()函数来控制的。如果时间超过分配时间的两倍，或者即将花完所有剩余时间，则强行中止搜索。另外，搜索过程每进行一段时间，都会由SetOutputMove()函数给出一个新的结果，此时看一下用时是否超过分配时间的一半，超过的话就中止搜索。
由此看出，ElephantEye每步的耗时在 nProperTime / 2 和 nProperTime x 2 之间，而这个时间段在大多数情况下会给出一个新的着法，因此不太会有浪费的时间。如果程序的时间策略仅仅是每步限制固定的时间，那么在做迭代加深时，浅一层搜索早就做完，而深一层搜索迟迟出不了结果，就被强行中止了，那么从浅一层搜索做完到强行中止的这段时间白白浪费了。
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) 根结点不记录到置换表中。
 关闭窗口  打印文档 |
账号登录