⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 解剖大象的眼睛——中国象棋程序设计探索(五)：克服水平线效应.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://www.elephantbase.net/computer/eleeye_horizon.htm -->
<HTML><HEAD><TITLE>解剖大象的眼睛——中国象棋程序设计探索(五)：克服水平线效应</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2817" 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/advanced_intro1.htm" 
  target=_blank>高级搜索方法——简介<FONT face="Times New Roman">(</FONT>一<FONT 
  face="Times New Roman">)</FONT></A><FONT face="Times New Roman">(David 
  Eppstein)</FONT>； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT><A 
  href="http://www.elephantbase.net/computer/advanced_quiescent.htm" 
  target=_blank>高级搜索方法——静态搜索</A><FONT face="Times New Roman">(Bruce 
  Moreland)</FONT>； 
  <DT>　　<FONT face="Times New Roman">(3) </FONT><A 
  href="http://www.elephantbase.net/computer/advanced_nullmove.htm" 
  target=_blank>高级搜索方法——空着裁剪</A><FONT face="Times New Roman">(Bruce 
  Moreland)</FONT>； 
  <DT>　　<FONT face="Times New Roman">(4) </FONT><A 
  href="http://www.elephantbase.net/computer/other_repetition.htm" 
  target=_blank>其他策略——重复检测</A><FONT face="Times New Roman">(Bruce 
  Moreland)</FONT>； 
  <DT>　　<FONT face="Times New Roman">(5) </FONT><A 
  href="http://www.elephantbase.net/computer/other_contempt.htm" 
  target=_blank>其他策略——藐视因子</A><FONT face="Times New Roman">(Bruce 
  Moreland)</FONT>。 
  <DT>　 
  <DT>　　在象棋程序的搜索技术中，裁剪和延伸是最有挖掘潜力之处，在各个程序中的差异也比较大。<FONT 
  face="Times New Roman">ElephantEye</FONT>在这方面没有花太多的笔墨，空着裁剪、静态搜索和选择性延伸跟其他程序大同小异，读者可能会认为“历史表裁剪”<FONT 
  face="Times New Roman">(History Pruning)</FONT>是<FONT 
  face="Times New Roman">ElephantEye</FONT>的亮点，但是笔者对该算法的原理并未完全把握，而且很多细节还有待摸索，所以这里就不作介绍，有兴趣的读者可参考<FONT 
  face="Times New Roman">ElephantEye</FONT>源程序中<FONT 
  face="Times New Roman">&lt;search.cpp&gt;</FONT>的相关注释。笔者将对几个比较成熟可靠的算法作一些介绍。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>5.1 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>无害裁剪</STRONG></FONT> 
  <DT>　 
  <DT>　　很多局面不需要搜索即可知道它的确切评价值，或者至少超出<FONT 
  face="Times New Roman">Alpha-Beta</FONT>窗口，此时就可以把该结点以下的搜索树裁剪掉，而不影响搜索结果，这类裁剪称为“无害裁剪”，<FONT 
  face="Times New Roman">ElephantEye</FONT>使用了以下几种无害裁剪： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>杀棋步数<FONT 
  face="Times New Roman">(DTM)</FONT>裁剪。由于<FONT 
  face="Times New Roman">DTM</FONT>调整的缘故，在深度为<FONT 
  face="Times New Roman">Ply</FONT>的结点中，搜索结果不会落在窗口<FONT 
  face="Times New Roman">(Ply </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> MATE_VALUE, MATE_VALUE </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> Ply)</FONT>外，所以当<FONT 
  face="Times New Roman">(Alpha, 
  Beta)</FONT>窗口和该窗口没有交叠时，立即可以作出裁剪。裁剪有两种情况，要么<FONT 
  face="Times New Roman">MATE_VALUE </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> Ply &lt;= Alpha</FONT>，要么<FONT 
  face="Times New Roman">Ply </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> MATE_VALUE &gt;= Beta</FONT>，<FONT 
  face="Times New Roman">ElephantEye</FONT>只考虑了后者。 
  <DT>　　<FONT face="Times New Roman">(2) 
  </FONT>重复裁剪。如果出现重复局面，那么应当根据规则直接判和或判某方长打作负，所以应当返回相应的分值。尽管象棋规则规定局面重复三次或更多次才予以判定，但在搜索过程中只要遇到一次重复，继续搜索下去就会有第二次、第三次，所以<FONT 
  face="Times New Roman">ElephantEye</FONT>只要遇到一次重复就不再搜索下去，但根结点要另外处理<FONT 
  face="Times New Roman">(</FONT>否则一个着法也没搜索，就出不了子了<FONT 
  face="Times New Roman">)</FONT>。 
  <DT>　　<FONT face="Times New Roman">(3) 
  </FONT>和棋裁剪。如果双方都没有明显可以杀死对方的子力，即可返回和棋分值<FONT 
  face="Times New Roman">(0</FONT>或藐视因子<FONT 
  face="Times New Roman">)</FONT>，而不必继续往下搜索。<FONT 
  face="Times New Roman">ElephantEye</FONT>把双方都只剩下仕<FONT 
  face="Times New Roman">(</FONT>士<FONT face="Times New Roman">)</FONT>相<FONT 
  face="Times New Roman">(</FONT>象<FONT 
  face="Times New Roman">)</FONT>的局面规定为和棋局面。 
  <DT>　　<FONT face="Times New Roman">(4) 
  </FONT>置换裁剪。置换表的一个作用就是利用置换现象裁剪掉某些分枝，前面已经作了详细的介绍。这里要提的是，由于存在“搜索的不稳定性”的原因，置换裁剪并非绝对无害的，<FONT 
  face="Times New Roman">ElephantEye</FONT>就不记录“利用长将判负策略搜索到的局面”，前面也有所介绍。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>5.2 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>带检验的空着裁剪</STRONG></FONT> 
  <DT>　 
  <DT>　　“带检验的空着裁剪”<FONT face="Times New Roman">(Verified Null-Move 
  Pruning)</FONT>指的是检验空着裁剪是否安全的算法，它首先由<FONT 
  face="Times New Roman">Tabibi</FONT>发表在<FONT 
  face="Times New Roman">2002</FONT>年的<FONT 
  face="Times New Roman">ICGA(</FONT>原<FONT 
  face="Times New Roman">ICCA)</FONT>杂志上<FONT 
  face="Times New Roman">(</FONT>参阅<FONT face="Times New Roman">Tabibi OD, 
  Netanyahu NS: <EM><STRONG>Verified Null-Move Pruning</STRONG></EM><EM>, ICGA 
  J.</EM> 25 (3): 153-161, <STRONG>2002</STRONG></FONT>，可以从互联网上找到<FONT 
  face="Times New Roman">)</FONT>。其内容可以概括为： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>用<FONT 
  face="Times New Roman"><EM>R</EM> = 3</FONT>的空着裁剪进行搜索； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>如果高出边界，那么做浅一层的搜索<FONT 
  face="Times New Roman">(</FONT>这就意味着一层的搜索是无法做带验证的空着裁剪的<FONT 
  face="Times New Roman">)</FONT>； 
  <DT>　　<FONT face="Times New Roman">(3) </FONT>做浅一层的搜索时，子结点用<FONT 
  face="Times New Roman"><EM>R</EM> = 3</FONT>的不带验证的空着裁剪； 
  <DT>　　<FONT face="Times New Roman">(4) 
  </FONT>如果浅一层的搜索高出边界，那么带验证的空着裁剪是成功的，否则必须重新做完全的搜索。 
  <DT>　　笔者认为这里存在很多问题： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>用<FONT 
  face="Times New Roman"><EM>R</EM> = 3</FONT>非常冒进，还是用<FONT 
  face="Times New Roman"><EM>R</EM> = 2</FONT>比较合适； 
  <DT>　　<FONT face="Times New Roman">(2) 
  </FONT>检验时做浅一层的搜索太浪费时间，裁剪的层数可以跟空着裁剪一样的<FONT 
  face="Times New Roman"><EM>R</EM></FONT>值一样，而且窗口也用以<FONT 
  face="Times New Roman">Beta</FONT>为界的零窗口； 
  <DT>　　<FONT face="Times New Roman">(3) 
  </FONT>做检验时，子结点仍旧应该做带检验的空着裁剪，否则“连停着杀”就检测不出来了。 
  <DT>　　<FONT face="Times New Roman">ElephantEye</FONT>是否启用空着裁剪，分三种情况讨论： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>我方进攻子力达到<FONT 
  face="Times New Roman">3</FONT>个，就使用不带检验的空着裁剪； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>我方进攻子力小于<FONT 
  face="Times New Roman">3</FONT>个，则使用带检验的空着裁剪；
12

⌨️ 快捷键说明

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