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

📄 高级搜索方法——空着裁剪.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0058)http://www.elephantbase.net/computer/advanced_nullmove.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 dir=ltr>
  <DIV align=center>
  <CENTER>
  <DT><FONT size=3>《对弈程序基本技术》专题</FONT> </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><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">Bruce Moreland (</FONT><A 
  href="mailto:brucemo@seanet.com"><FONT 
  face="Times New Roman">brucemo@seanet.com</FONT></A><FONT 
  face="Times New Roman">) / </FONT>文 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DT><FONT face=楷体_GB2312 size=5><STRONG>没有副作用即可获得额外的速度</STRONG></FONT> 
  <DT>　 
  <DT>　　空着向前裁剪<FONT face="Times New Roman">(Null-Move Forward 
  Pruning)</FONT>，运用可能忽视重要路线的冒险策略，使得国际象棋的分枝因子锐减，它导致搜索深度的显著提高，因为大多数情况下它明显降低了搜索的数量。它的工作原理是裁剪大量无用着法而只保留好的。 

  <DT>　　这个技术在很多刊物上报道过，但是使得大家都来关注空着的，则是由<FONT face="Times New Roman">Chrilly 
  Donniger</FONT>发表在<FONT face="Times New Roman">1993</FONT>年<FONT 
  face="Times New Roman">9</FONT>月的<FONT 
  face="Times New Roman">ICCA</FONT>杂志上的一篇文章。 
  <DT>　　试想国际象棋搜索树中的某个局面，你的程序将以<FONT 
  face="Times New Roman"><EM>D</EM></FONT>层搜索这个局面的每个着法。如果其中任何一个着法的分数超过<FONT 
  face="Times New Roman">Beta</FONT>，你就会马上返回<FONT 
  face="Times New Roman">Beta</FONT>。如果任何一个超过<FONT 
  face="Times New Roman">Alpha</FONT>，但是没有超过<FONT 
  face="Times New Roman">Beta</FONT>，你就要记住着法和分值，因为这有可能是主要变例的一部分。如果它们全部小于或等于<FONT 
  face="Times New Roman">Alpha</FONT>，你就要返回<FONT 
  face="Times New Roman">Alpha</FONT>。 
  <DT>　　空着向前裁剪是你搜索任何着法之前要做的事。你要问一个问题：“如果我在这里什么都不做，对手能做什么？” 
  <DT>　　记得在刚才，你没有问这个问题。你只是去找最佳的着法去打击对手。问对手是否会打击你，这个问题却有所不同。 
  <DT>　　但是事实证明很多情况下对手无法打击你。比如说你送了一个车，而其他棋子都没有作用，在这种情况下，对手随便走哪步你都吃亏，因为你丢了一个车。空着向前裁剪的要点，就是简单地去掉那些没用的着法，而不要在这上面多花时间。 

  <DT>　　这就好比像打架时，根据自己的能力给对手一个出击的机会，来增加自己的信心。如果任凭对手攻击也无法击倒你，那么你攻击他的时候他会输掉。 
  <DT>　　我们不讨论这个策略了，现在来谈它是如何运用在电脑国际象棋中的。在你搜索着法以前<FONT 
  face="Times New Roman">(</FONT>事实上在你生成着法以前<FONT 
  face="Times New Roman">)</FONT>，你做一个减少深度的搜索，让对手先走，如果这个搜索的结果大于或等于<FONT 
  face="Times New Roman">Beta</FONT>，那么你简单地返回<FONT 
  face="Times New Roman">Beta</FONT>而不需要搜索任何着法。 
  <DT>　　这个思想就给了对手出击的机会，如果你的局面仍然好到超过<FONT 
  face="Times New Roman">Beta</FONT>的程度，你就假设如果你搜索了所有的着法也会超过<FONT 
  face="Times New Roman">Beta</FONT>。 
  <DT>　　这个方法能节省时间的原因是，开始时用了减少深度的搜索。深度减少因子称为<FONT 
  face="Times New Roman"><EM>R</EM></FONT>，因此跟你用深度<FONT 
  face="Times New Roman"><EM>D</EM></FONT>搜索所有的着法相比，现在你是先以<FONT 
  face="Times New Roman"><EM>D</EM> </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> <EM>R</EM></FONT>搜索对手的着法。一个比较好<FONT 
  face="Times New Roman"><EM>R</EM></FONT>是<FONT 
  face="Times New Roman">2</FONT>，如果你要对所有的着法搜索<FONT 
  face="Times New Roman">6</FONT>层，你最终只对对手所有的着法搜索了<FONT 
  face="Times New Roman">4</FONT>层。<FONT 
  color=#0000ff>【译注：因为放弃着法后层数应该减1，所以实际在对手上面搜索的层数是</FONT><FONT 
  face="Times New Roman" color=#0000ff><EM>D</EM> </FONT><FONT face=Symbol 
  color=#0000ff>-</FONT><FONT face="Times New Roman" color=#0000ff> 1 
  </FONT><FONT face=Symbol color=#0000ff>-</FONT><FONT face="Times New Roman" 
  color=#0000ff> <EM>R</EM></FONT><FONT color=#0000ff>。】</FONT> 
  <DT>　　这就使得很多时间节约下来了，实践证明可以使搜索增加一到两层。效果真的非常可观！ 
  <DT>　　代码如下，醒目的文字是在<FONT face="Times New Roman">Alpha-Beta</FONT>搜索的基础上增加的部分： 
  <DD>　 
  <DD><FONT face=宋体 color=#ff0000>#define R 2</FONT> 
  <DD><FONT face=宋体>int AlphaBeta(int depth, int alpha, int beta) {</FONT> 
  <DD><FONT face=宋体>　if (depth == 0) {</FONT> 
  <DD><FONT face=宋体>　　return Evaluate();</FONT> 
  <DD>　} 
  <DD><FONT face=宋体 color=#ff0000>　MakeNullMove();</FONT> 
  <DD><FONT face=宋体 color=#ff0000>　val = -AlphaBeta(depth - 1 - R, -beta, -beta 
  + 1);</FONT> 
  <DD><FONT face=宋体 color=#ff0000>　UnmakeNullMove();</FONT> 
  <DD><FONT face=宋体 color=#ff0000>　if (val &gt;= beta) {</FONT> 
  <DD><FONT face=宋体 color=#ff0000>　　return beta;</FONT> 
  <DD><FONT color=#ff0000>　}</FONT> 
  <DD><FONT face=宋体>　GenerateLegalMoves();</FONT> 
  <DD><FONT face=宋体>　while (MovesLeft()) {</FONT> 
  <DD><FONT face=宋体>　　MakeNextMove();</FONT> 
  <DD><FONT face=宋体>　　val = -AlphaBeta(depth - 1, -beta, -alpha);</FONT> 
  <DD><FONT face=宋体>　　UnmakeMove();</FONT> 
  <DD><FONT face=宋体>　　if (val &gt;= beta) { // 
  </FONT>把这部分去掉，就用纯粹的最小-最大代替了Alpha-Beta。 
  <DD><FONT face=宋体>　　　return beta;</FONT> 
  <DD><FONT face=宋体>　　</FONT>} 
  <DD><FONT face=宋体>　　if (val &gt; alpha) {</FONT> 
  <DD><FONT face=宋体>　　　alpha = val;</FONT> 
  <DD><FONT face=宋体>　　}</FONT> 
  <DD><FONT face=宋体>　</FONT>} 
  <DD><FONT face=宋体>　return alpha;</FONT> 
  <DD><FONT face=宋体>}</FONT> 
  <DT>　 
  <DT>　　在这个代码中我用了一个诀窍。我需要知道空着搜索的值是否是<FONT 
  face="Times New Roman">Beta</FONT>或更好，如果还不如<FONT 
  face="Times New Roman">Beta</FONT>，我不关心它到底比<FONT 
  face="Times New Roman">Beta</FONT>有多糟，因此我用了极小窗口，试图让裁剪做得更快。实际上我用<FONT 
  face="Times New Roman">(Beta </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> 1, Beta)</FONT>调用了搜索，但是由于递归时必须把<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>颠倒并取负数，这就变成源代码中的样子了。 
  <DT>　　不用说，这个代码在一方被将军时不能发挥作用<FONT 
  face="Times New Roman">(</FONT>因为对手立刻把王吃掉了<FONT 
  face="Times New Roman">)</FONT>。什么地方允许调用空着向前裁剪，必须掌握好分寸，因为如果你允许一次连续地这么做，那么搜索将退化成什么都不做了。一个很简单的尝试，就是当中没有间隔一个实在着法的时候，不要让两个空着搜索连在一起。另一个思想是在一个实在着法之前，允许连续两个空着裁剪。实践证明这两个方法都做得很好。 

  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>嗯，还是有副作用的</STRONG></FONT> 
  <DT>　 
  <DT>　　不幸的是，空着向前裁剪在某些地方不能正常运行。我们作了一个重要的假定——假定走了一步棋会比不走棋有更高的分值。不幸的是，这个假定在很多典型的局面上并不成立，这些局面非常普遍，并且有一个名称——无等着局面<FONT 
  face="Times New Roman">(Zugzwang)</FONT>。无等着局面指的是，如果你不走棋，局势会好些，但是你被强迫走子，这使得你的局势会崩溃。下面是个典型的例子： 

  <DT>　 
  <DIV align=center>
  <CENTER></DIV>
  <DT><IMG height=256 src="高级搜索方法——空着裁剪_files/advanced_nullmove1.gif" width=256> 
  </CENTER>
  <DIV></DIV>
  <DT>　 
  <DT>　　在这个局面里，如果白方被迫走子，他走 <FONT face="Times New Roman">Kb2</FONT>，而黑走 <FONT 
  face="Times New Roman">Kd2 </FONT>助兵变后。如果白方不走棋，那么黑的走 <FONT 
  face="Times New Roman">Kc3</FONT>，局面就是和棋。<FONT 
  face="Times New Roman">(</FONT>事实上这是一个互相的无等着局面，因为双方都被先走棋所困扰，这个问题不在我们的讨论范围内。<FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　如果到达这个局面，而且试图用空着向前裁剪，那么可能会认为黑方没有威胁白方，因为现在黑方确实没威胁白方。而现在黑方在等待白方毁掉局势，这就完全不同了。 

  <DT>　　由于这个原因，空着向前裁剪不能在残局中使用，或者至少不能直接地使用。如果你试图在残局中用，则会出现很糟糕的事情。 
  <DT>　　有一个更困扰人的例子，是这样的： 
  <DIV align=left></DIV>
  <DT>　 
  <DIV></DIV>
  <DIV align=center>
  <CENTER></DIV>
  <DT><IMG height=256 src="高级搜索方法——空着裁剪_files/advanced_nullmove2.gif" width=256> 
  </CENTER>
  <DIV></DIV>
  <DT>　 
  <DT>　　这个局面选自<FONT face="Times New Roman">Goetsch</FONT>和<FONT
12

⌨️ 快捷键说明

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