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

📄 国际象棋程序设计(五)：高级搜索方法.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://www.elephantbase.net/computer/basic_advanced.htm -->
<HTML><HEAD><TITLE>国际象棋程序设计(五)：高级搜索方法</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY link=#0000ff background=国际象棋程序设计(五)：高级搜索方法_files/background.gif>
<DL>
  <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">Fran</FONT>&ccedil;<FONT face="Times New Roman">ois 
  Dominic Laram</FONT>é<FONT face="Times New Roman">e/</FONT>文 
  </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DT>　　哇，看上去好像有很多人在看我的连载，我的脸都红了！ 
  <DT>　　这是倒数第二篇文章，我们会介绍和搜索有关的高级技术，他们既能提高速度，又能增强棋力<FONT 
  face="Times New Roman">(</FONT>或者只有一个作用<FONT 
  face="Times New Roman">)</FONT>。他们中有很多，概念上<FONT 
  face="Times New Roman">(</FONT>程序代码可能不行<FONT 
  face="Times New Roman">)</FONT>可以运用到任何<FONT 
  face="Times New Roman">2</FONT>人游戏中，然而让它们用到一些具体问题上，对很多读者来说还需要加工。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><B>干吗要那么麻烦？</B></FONT> 
  <DT>　 
  <DT>　　到此为止，我们知道的所有搜索算法，都把局面推演到固定的深度。但是这未必是件好事。例如，假设你的程序最多可以用迭代加深的<FONT 
  face="Times New Roman">Alpha-Beta</FONT>算法搜索到<FONT 
  face="Times New Roman">5</FONT>层，那么来看下这几个例子： 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">1. </FONT>沿着某条路线，你发现在第<FONT 
  face="Times New Roman">3</FONT>层有将死或逼和的局面。显然你不想再搜索下去了，因为游戏的最终目的达到了。搜索<FONT 
  face="Times New Roman">5</FONT>层不仅是浪费时间，而且可能会让电脑自己把自己引入不合理的状态。 
  <DT>　　<FONT face="Times New Roman">2. </FONT>现在假设在<FONT 
  face="Times New Roman">5</FONT>层你吃到了兵。程序可能会认为这个局面稍稍有利，并且会这么走下去。然而，如果你看得更深远些，可能会发现吃了兵以后你的后就处于被攻击的状态，完了！ 

  <DT>　　<FONT face="Times New Roman">3. </FONT>最后，假设你的后被捉了，不管你怎么走，她会在第<FONT 
  face="Times New Roman">4</FONT>层被对手吃掉，但是有一条路线可以让她坚持到第<FONT 
  face="Times New Roman">6</FONT>层。如果你的搜索深度是<FONT 
  face="Times New Roman">5</FONT>，那么后在第<FONT 
  face="Times New Roman">4</FONT>层被吃掉的路线会被检测出来，这些情况会评估成灾难局面，但是唯一能使后在第<FONT 
  face="Times New Roman">6</FONT>层<FONT 
  face="Times New Roman">(</FONT>超出了搜索树<FONT 
  face="Times New Roman">)</FONT>捉到的那条路线，对于电脑来说被吃是不能被发现的，因此它会认为后很安全，从而打一个较高的分数。现在，为了让后被吃的情况排除在搜索树以外，唯一的办法就是调虎离山，这样做是很冒险的——牺牲一些局面，还是有可能让对手犯下错误让你的后溜掉的。那么如果你要通过牺牲一个车来延缓后的被吃呢？对电脑来说，在第<FONT 
  face="Times New Roman">4</FONT>层丢车要比丢后损失小，所以在这个搜索水平上，它情愿丢一个那么大的子，来推迟那个可怜的后的被吃了。<FONT 
  face="Times New Roman">(</FONT>当然在随后一回合里，电脑会发现无论怎么走，它的后会在第<FONT 
  face="Times New Roman">4</FONT>层被吃掉，并且车丢得莫名其妙。<FONT 
  face="Times New Roman">)</FONT>很早以前<FONT face="Times New Roman">Hans 
  Berliner</FONT>就把这个情况称为“水平线效应”，这在很大程度上可以通过后面即将介绍的“静态搜索”来改善。 
  <DT>　 
  <DT>　　最后要说一句：象棋中的很多局面<FONT face="Times New Roman">(</FONT>其他游戏也一样<FONT 
  face="Times New Roman">)</FONT>太不可预测了，实在很难恰当地评估。评价函数只能在“安静”的局面下起作用，即这些局面在不久的将来不可能发生很大的变化。这将是我们介绍下一个内容。 

  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><B>请安静！</B></FONT> 
  <DT>　 
  <DT>　　有两种评估局面的办法——动态评估<FONT face="Times New Roman">(</FONT>看局面会如何发展<FONT 
  face="Times New Roman">)</FONT>和静态评估<FONT 
  face="Times New Roman">(</FONT>看它像什么样子，不去管将来怎样<FONT 
  face="Times New Roman">)</FONT>。动态评估需要深入的搜索。我们刚刚提到，局面在不久的将来不可能发生很大的变化的情况下，静态评估才是可行的。这些相对稳定的局面称为“安静”<FONT 
  face="Times New Roman">(Quiet)</FONT>或“寂静”<FONT 
  face="Times New Roman">(Quiescent)</FONT>的局面，它们需要通过“静态搜索”<FONT 
  face="Times New Roman">(Quiescence Search)</FONT>来达到。 
  <DT>　　静态搜索的最基本的概念是指：当程序搜索到固定深度时<FONT face="Times New Roman">(</FONT>比如<FONT 
  face="Times New Roman">6</FONT>层<FONT 
  face="Times New Roman">)</FONT>，我们选择性地继续各条路线，只搜索“非静态”的着法，直到找到静态着法为止，这样才开始评估。 
  <DT>　　找到静态局面是需要游戏知识的。例如，什么样的着法可能引起棋盘上子力平衡的巨大改变？对于象棋来说，子力平衡会导致局面的剧烈变化，所以任何改变子力的着法就是——吃<FONT 
  face="Times New Roman">(</FONT>特别是吃主要棋子<FONT 
  face="Times New Roman">)</FONT>、兵的升变都是，而将军也是值得一看的<FONT 
  face="Times New Roman">(</FONT>仅仅是能导致将死的将军<FONT 
  face="Times New Roman">)</FONT>。<FONT 
  color=#0000ff>【译注：我认为任何将军都应该考虑进去，因为它会导致抽吃、长将等决定性局面的产生】</FONT>。在西洋棋里，吃子和升变<FONT 
  color=#0000ff>【西洋棋的棋子分兵棋</FONT><FONT face="Times New Roman" 
  color=#0000ff>(Man)</FONT><FONT color=#0000ff>和王棋</FONT><FONT 
  face="Times New Roman" color=#0000ff>(King)</FONT><FONT 
  color=#0000ff>，兵棋冲到底线就变成王棋，因此我断定它是国际象棋的前身】</FONT>都是选择。在黑白棋中，每一步都必须吃子，并且“子力平衡”<FONT 
  color=#0000ff>【仅仅指目前棋子的多少，它和最终棋子的多少没多大联系】</FONT>在短时间内翻覆无常，所以可以说它根本不存在“静态局面”！ 
  <DT>　　我自己的程序用了简单的静态搜索，它只考虑所有带吃子着法的线路<FONT 
  face="Times New Roman">(</FONT>在<FONT 
  face="Times New Roman"><I>x</I></FONT>层完全搜索以后<FONT 
  face="Times New Roman">)</FONT>。由于通常局面下没有太多合理的吃子着法，所以静态搜索的分枝因子非常小<FONT 
  face="Times New Roman">(</FONT>平均在<FONT 
  face="Times New Roman">4-6</FONT>，双方在吃子后会迅速下降到<FONT 
  face="Times New Roman">0)</FONT>。但是，静态搜索算法要分析大量的局面，它可能会占用整个处理器一半以上的时间。当你的程序使用这个方案以前，你要确定你是否需要用它。 

  <DT>　　当没有吃子发生时，我的程序才开始评价局面。其结果就是将层数固定的搜索树作选择性的延伸，它能克服大多数由“水平线效应”产生的后果。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><B>重要的空着</B></FONT> 
  <DT>　 
  <DT>　　有个加快象棋程序速度的有效方法，就是引入空着的概念。 
  <DT>　　简而言之，空着就是自己不走而让对手连走两次。大多数局面中，什么事都不做显然不是办法，你总是必须做点事情来改善局面。<FONT 
  face="Times New Roman">(</FONT>老实说，有一些“走也不是，不走也不是”的局面，空着确实是你的最佳选择，但不能走，这种 
  “被迫移动”<FONT face="Times New Roman">(Zugzwang)</FONT>局面是没有指望的，所以不必对电脑感到失望。<FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　在搜索中让电脑走空着，可以提高速度和准确性。例如： 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">1. 
  </FONT>假设局面对你来说是压倒性优势，即便你什么都不走，对手也无法挽回。<FONT 
  face="Times New Roman">(</FONT>用程序的术语来说，你不走棋也可以产生<FONT 
  face="Times New Roman">Beta</FONT>截断。<FONT 
  face="Times New Roman">)</FONT>假设这个局面本来准备搜索<FONT 
  face="Times New Roman"><I>N</I></FONT>层，而空着取代了整个搜索树<FONT 
  face="Times New Roman">(</FONT>你的所有合理着法用空着取代了<FONT 
  face="Times New Roman">)</FONT>，并且你的分枝因子是<FONT 
  face="Times New Roman"><I>B</I></FONT>，那么搜索空着就相当于只搜索了一个<FONT 
  face="Times New Roman"><I>N</I>-1</FONT>层的分枝，而不是<FONT 
  face="Times New Roman"><I>B</I></FONT>个这样的分枝。在中局阶段通常<FONT 
  face="Times New Roman"><I>B</I>=35</FONT>，所以空着搜索只消耗了完整搜索所需的<FONT 
  face="Times New Roman">3%</FONT>的资源。如果空着搜索表明你已经强大到没有必要再走棋<FONT 
  face="Times New Roman">(</FONT>即会产生截断<FONT 
  face="Times New Roman">)</FONT>的地步，那么你少花了<FONT 
  face="Times New Roman">97%</FONT>的力气。如果没有，你就必须检查合理的着法，这只是多花了<FONT 
  face="Times New Roman">3%</FONT>的力气。平均来说，收益是巨大的。<FONT 
  color=#0000ff>【当然，空着搜索对于处理“被迫移动”局面还是有负面作用的，特别是在残局中，这个作用相当明显。可以参考《对弈程序基本技术》专题之《</FONT><A 
  href="http://www.elephantbase.net/computer/advanced_nullmove.htm" 
  target=_blank><FONT color=#0000ff>高级搜索方法——空着裁剪</FONT></A><FONT 
  color=#0000ff>》一文。】</FONT> 
  <DT>　　<FONT face="Times New Roman">2. 
  </FONT>假设在静态搜索中，你面对一个只有车吃兵一种吃子着法的局面，然而接下来对手就会走马吃车。你最好不去吃子而走其他不吃子的着法对吗？你可以在静态搜索中插入空着来模拟这种情况，如果在某个局面下空着比其他吃子着法有利，那么你继续吃子就是坏的选择。并且由于最佳着法是静态着法，所以这个局面就是评估函数可以作用的局面。 

  <DT>　 
  <DT>　　总的来说，空着启发会减少<FONT face="Times New Roman">20%</FONT>到<FONT 
  face="Times New Roman">75%</FONT>的搜索时间。这当然值得，特别是当你把这个方法用在静态搜索算法上的时候，就像改变“走子的一方”这种代码一样简单，用不了十行就行了。 

  <DT><FONT color=#0000ff>　　【很多书上把“空着”这一技术称为“空着启发”</FONT><FONT 
  face="Times New Roman" color=#0000ff>(Null-Move Heuristic)</FONT><FONT 
  color=#0000ff>，本文就是这个意思，事实上在历史表、迭代加深等启发的作用下，空着启发已经意义不大了。现在绝大多数程序都使用了称为“空着的向前裁剪”</FONT><FONT 
  face="Times New Roman" color=#0000ff>(Null-Move Forward Pruning)</FONT><FONT 
  color=#0000ff>的搜索</FONT><FONT face="Times New Roman" 
  color=#0000ff>(</FONT><FONT color=#0000ff>它跟空着启发是有区别的</FONT><FONT 
  face="Times New Roman" color=#0000ff>)</FONT><FONT 
  color=#0000ff>，尽管是一种不完全搜索，但它却是诸多向前裁剪的搜索中最有效的一个。】</FONT> 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><B>期望搜索和</B></FONT><FONT face=Arial 
  size=5><B>MTD(</B><EM><B>f</B></EM><B>)</B></FONT> 
  <DT>　 
  <DT>　　普通的老式<FONT face="Times New Roman">Alpha-Beta</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">0</FONT>，因为非常均衡。现在来假设对一个内部结点作先前的评价，它的值在<FONT 
  face="Times New Roman">+20,000</FONT><FONT color=#0000ff>【这里的单位应该是“千分兵值”， 
  即</FONT><FONT face="Times New Roman" color=#0000ff>1000</FONT><FONT 
  color=#0000ff>相当于一个兵的价值，那么马和象等于</FONT><FONT face="Times New Roman" 
  color=#0000ff>3000</FONT><FONT color=#0000ff>，车</FONT><FONT 
  face="Times New Roman" color=#0000ff>5000</FONT><FONT 
  color=#0000ff>，后</FONT><FONT face="Times New Roman" 
  color=#0000ff>9000</FONT><FONT color=#0000ff>，其他因素也折算成这个值，而</FONT><FONT 
  face="Times New Roman" color=#0000ff>UCI</FONT><FONT 
  color=#0000ff>协议中则用“百分兵值”，因为没有必要过于精确】</FONT>，那么你可以有充分信心对它截断。 
  <DT>　　这就是“期望搜索”<FONT face="Times New Roman">(Aspiration 
  Search)</FONT>背后的思想，一个<FONT
12

⌨️ 快捷键说明

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