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

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0054)http://www.elephantbase.net/computer/eleeye_ponder.htm -->
<HTML><HEAD><TITLE>解剖大象的眼睛——中国象棋程序设计探索(八)：后台思考和时间策略</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.536" name=GENERATOR></HEAD>
<BODY background=解剖大象的眼睛——中国象棋程序设计探索(八)：后台思考和时间策略_files/background.gif>
<DL>
  <DIV align=center>
  <CENTER>
  <DT><FONT face=隶书 size=6>解剖大象的眼睛</FONT><FONT 
  size=6><STRONG>——</STRONG></FONT><FONT face=隶书 size=6>中国象棋程序设计探索</FONT> 
  </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>黄晨 <FONT face="Times New Roman">*</FONT>　<FONT 
  face="Times New Roman">2005</FONT>年<FONT 
  face="Times New Roman">6</FONT>月初稿，<FONT 
  face="Times New Roman">2005</FONT>年<FONT face="Times New Roman">11</FONT>月修订 
  </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face="Times New Roman">( * </FONT>联系地址：复旦大学化学系表面化学实验室，<FONT 
  face="Times New Roman">eMail</FONT>：<A 
  href="mailto:webmaster@elephantbase.net"><FONT 
  face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT 
  face="Times New Roman">)</FONT> </CENTER></DT></DIV>
  <DT>　 
  <DT><FONT face=Arial size=5><STRONG>(</STRONG></FONT><FONT face=楷体_GB2312 
  size=5><STRONG>八</STRONG></FONT><FONT face=Arial size=5><STRONG>) 
  </STRONG></FONT><FONT face=楷体_GB2312 size=5><STRONG>后台思考和时间策略</STRONG></FONT> 
  <DT>　 
  <DT>　　在阅读本章前，建议读者先阅读《<A href="http://www.elephantbase.net/" 
  target=_blank>象棋百科全书</A>》网站中《<A 
  href="http://www.elephantbase.net/computer/outline.htm" 
  target=_blank>对弈程序基本技术</A>》专题的以下几篇译文： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT><A 
  href="http://www.elephantbase.net/computer/other_ponder.htm" 
  target=_blank>其他策略——后台思考</A><FONT face="Times New Roman">(Bruce 
  Moreland)</FONT>。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>8.1 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>后台思考</STRONG></FONT> 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">UCCI</FONT>协议不需要对后台思考作特别处理，如果引擎接收了指令“<FONT 
  face="Times New Roman">go ponder ...</FONT>”，那么搜索过程中时钟暂时不起作用，直到收到“<FONT 
  face="Times New Roman">ponderhit</FONT>”指令后才启用时钟。因此，后台思考实际上相当于无限制的思考。 
  <DT>　　<FONT face="Times New Roman">ElephantEye</FONT>从<FONT 
  face="Times New Roman">1.04</FONT>版本开始就不再支持浅红象棋协议，而此功能被适配器<FONT 
  face="Times New Roman">UCCI2QH</FONT>所代替，该程序中的大量的代码是用来解决后台思考问题的，其中状态变量<FONT 
  face="Times New Roman">nStatus</FONT>的控制是关键，该变量的设置规则可参考<FONT 
  face="Times New Roman">&lt;ucci2qh.cpp&gt;</FONT>源程序中的相关注释。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>8.2 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>时间策略</STRONG></FONT> 
  <DT>　 
  <DT>　　时间策略在各个象棋程序中差异很大，有的程序根本没有时间策略，只能设定固定的搜索深度，或者在固定的时间中止思考，例如浅红象棋协议目前就没有时间策略。<FONT 
  face="Times New Roman">UCCI</FONT>协议可以把时限规则告诉引擎，由引擎自动分配时间，时限规则可以是以下两种： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>时段制，即在限定时间内走完规定的步数，用“<FONT 
  face="Times New Roman">go time &lt;time&gt; movestogo 
  &lt;moves_to_go&gt;</FONT>”命令； 
  <DT>　　<FONT face="Times New Roman">(2) 
  </FONT>加时制，即在限定时间内走完整盘棋，但每步会加上几秒，用“<FONT face="Times New Roman">go time 
  &lt;time&gt; increment &lt;increment&gt;</FONT>”命令。 
  <DT>　　<FONT face="Times New Roman">ElephantEye</FONT>的时间策略由<FONT 
  face="Times New Roman">&lt;search.h&gt;</FONT>里的<FONT 
  face="Times New Roman">SearchMain()</FONT>函数来处理，不管处理哪个规则，都会分配一个合适的时间<FONT 
  face="Times New Roman">(ProperTime)</FONT>用来走棋，这个时间是这样计算的： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>时段制：分配时间 <FONT 
  face="Times New Roman">= </FONT>剩余时间 <FONT face="Times New Roman">/ 
  </FONT>要走的步数； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>加时制：分配时间 <FONT 
  face="Times New Roman">= </FONT>每步增加的时间 <FONT face="Times New Roman">+ 
  </FONT>剩余时间 <FONT face="Times New Roman">/ 20 (</FONT>即假设棋局会在<FONT 
  face="Times New Roman">20</FONT>步内结束<FONT face="Times New Roman">)</FONT>； 
  <DT>　　在搜索过程中，超时是由<FONT 
  face="Times New Roman">Interrupt()</FONT>函数来控制的。如果时间超过分配时间的两倍，或者即将花完所有剩余时间，则强行中止搜索。另外，搜索过程每进行一段时间，都会由<FONT 
  face="Times New Roman">SetOutputMove()</FONT>函数给出一个新的结果，此时看一下用时是否超过分配时间的一半，超过的话就中止搜索。 

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

  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>8.3 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>搜索杀棋的策略</STRONG></FONT> 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">ElephantEye</FONT>没有专门搜索杀棋的功能，如果存在杀棋的话<FONT 
  face="Times New Roman">(</FONT>不管是杀死对方还是被对方杀死<FONT 
  face="Times New Roman">)</FONT>，会在搜索中自动找到。是否能找到杀棋和搜索深度有关，某一深度下找不到杀棋，但深一层搜索就可能找到；但和一般局面不同的是，如果一定深度能找到杀棋，那么再深的深度会得到同样的结果。因此，如果找到杀棋，那么程序要使用不同的策略。<FONT 
  face="Times New Roman">ElephantEye</FONT>处理杀棋局面时，用到以下几个策略： 
  <DT>　　<FONT face="Times New Roman">(1) 
  </FONT>置换表的存取策略，前面曾经介绍过，如果置换表中存储的某个局面已被确认找到杀棋，那么探测到这样的局面时就不需要考虑深度条件。 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>根结点做迭代加深时，找到杀棋后搜索就立即停止。<FONT 
  face="Times New Roman">ElephantEye</FONT>为杀局设定了边界<FONT 
  face="Times New Roman">WIN_VALUE</FONT>，其值略比<FONT 
  face="Times New Roman">MATE_VALUE</FONT>小一些，局面分值在区间<FONT 
  face="Times New Roman">(</FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">WIN_VALUE, WIN_VALUE)</FONT>以外，就说明该局面有杀棋。 
  <DT>　　<FONT face="Times New Roman">(3) </FONT>如果根结点的所有着法中，除了一个着法可以支撑<FONT 
  face="Times New Roman">(</FONT>即分值大于<FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">WIN_VALUE)</FONT>以外，其余着法都会输掉<FONT 
  face="Times New Roman">(</FONT>即分值都小于<FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">WIN_VALUE)</FONT>，那么应该立即返回这个唯一着法。 
  <DT>　　最后一点是<FONT 
  face="Times New Roman">ElephantEye</FONT>最有特色之处，这就是说，当迭代加深过程中遇到这种情况时，就没有必要做更深的搜索了。在对某个深度的完全搜索完成后，对最佳着法设为禁着，再对根结点作一次搜索，如果分值小于<FONT 
  face=Symbol>-</FONT><FONT 
  face="Times New Roman">WIN_VALUE</FONT>，则说明除这个最佳着法以外其余着法都会输掉，这种搜索称为“唯一着法检验搜索”，<FONT 
  face="Times New Roman">&lt;search.cpp&gt;</FONT>中需要用变量<FONT 
  face="Times New Roman">bCheckUnique</FONT>来控制。启用唯一着法检验搜索时，有两个地方要注意： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>使用零窗口的技巧，即用<FONT 
  face="Times New Roman">(</FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">WIN_VALUE, 1 </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> WIN_VALUE)</FONT>窗口作搜索，以减少搜索的结点数； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>根结点不记录到置换表中。 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/eleeye_book.htm">中国象棋程序设计探索<FONT 
face="Times New Roman">(</FONT>七<FONT face="Times New Roman">)</FONT>：开局库</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/eleeye_evaluate.htm">中国象棋程序设计探索<FONT 
face="Times New Roman">(</FONT>九<FONT face="Times New Roman">)</FONT>：局面评价函数</A> 

<LI>返　回　<A href="http://www.elephantbase.net/computer.htm">象棋百科全书——电脑象棋</A> 
</LI></DIR>
<DIV align=center>
<CENTER>
<TABLE border=0>
  <TBODY>
  <TR>
    <TD>
      <P align=center><A href="http://www.elephantbase.net/" target=_blank><IMG 
      height=31 src="解剖大象的眼睛——中国象棋程序设计探索(八)：后台思考和时间策略_files/elephantbase.gif" 
      width=88 border=0></A></P></TD></TR>
  <TR>
    <TD><A href="http://www.elephantbase.net/" target=_blank><FONT face=Arial 
      size=2><STRONG>www.elephantbase.net</STRONG></FONT></A></TD></TR></TBODY></TABLE></CENTER></DIV></BODY></HTML>
💿 文件大小 859 K
👤 上传用户 Emouse
📂 所属分类文件格式
🏷️ 相关标签

#程序设计 #程序 #编写
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -