基本搜索方法——简介(三).htm

象棋程序设计全资料集(介绍编写象棋程序的方法思路）

  face="Times New Roman">(lower_bound)</FONT>代表评分至少是<FONT 
  face="Times New Roman">Beta</FONT>，“上界标志”<FONT 
  face="Times New Roman">(up_bound)</FONT>代表评分最多是<FONT 
  face="Times New Roman">Alpha</FONT>，我们用 <FONT 
  face="Times New Roman">entry_type 
  </FONT>这个域来表示评分属于哪个类型。如果搜索散列表时返回这两个类型，那么我们需要看它是否在搜索结点之前发生裁剪，如果能发生裁剪，那么直接返回该评分，否则继续搜索。下面是用散列技术的<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索的伪代码，散列表的索引值<FONT 
  face="Times New Roman"><EM>x</EM></FONT>和校验值<FONT 
  face="Times New Roman"><EM>y</EM></FONT>是全局变量，并且在执行着法和撤消着法的时候更新。 
  <DD>　 
  <DD>double alphabeta(int depth, double alpha, double beta) { 
  <DD>　if (depth &lt;= 0 || 棋局结束) { 
  <DD>　　return evaluation(); 
  <DD>　} 
  <DD>　if (hashtable[x].checksum == y &amp;&amp; hashtable[x].depth &gt;= depth) 
  { 
  <DD>　　switch (hashtable[x].entry_type) { 
  <DD>　　case exact: //<FONT color=#0000ff>【就C语言的语法而言是错的，应该写成“case 
  hashtable[x].exact:”，下同】</FONT> 
  <DD>　　　return hashtable[x].eval; 
  <DD>　　case lower_bound: 
  <DD>　　　if (hashtable[x].eval &gt;= beta) { 
  <DD>　　　　return (hashtable[x].eval); 
  <DD>　　　} 
  <DD>　　　break; 
  <DD>　　case upper_bound: 
  <DD>　　　if (hashtable[x].eval &lt;= alpha) { 
  <DD>　　　　return (hashtable[x].eval); 
  <DD>　　　} 
  <DD>　　　break; 
  <DD>　　} 
  <DD>　} 
  <DD>　int eval_is_exact = 0; 
  <DD>　就当前局面，生成并排序一系列着法; 
  <DD>　for (每个着法 m) { 
  <DD>　　执行着法 m; 
  <DD>　　double val = -alphabeta(depth - 1, -beta, -alpha); 
  <DD>　　撤消着法 m; 
  <DD>　　if (val &gt;= beta) { 
  <DD>　　　hashtable[x].checksum = y; 
  <DD>　　　hashtable[x].depth = depth; 
  <DD>　　　hashtable[x].entry_type = lower_bound; 
  <DD>　　　hashtable[x].eval = val; //<FONT color=#0000ff>【译者认为 eval = beta 
  更加合理。】</FONT> 
  <DD>　　　return val; 
  <DD>　　} 
  <DD>　　if (val &gt; alpha) { 
  <DD>　　　alpha = val; 
  <DD>　　　eval_is_exact = 1; 
  <DD>　　} 
  <DD>　} 
  <DD>　hashtable[x].checksum = y; 
  <DD>　hashtable[x].depth = depth; 
  <DD>　if (eval_is_exact) { 
  <DD>　　hashtable[x].entry_type = exact; 
  <DD>　} else { 
  <DD>　　hashtable[x].entry_type = upper_bound; 
  <DD>　} 
  <DD>　hashtable[x].eval = alpha; 
  <DD>　return alpha; 
  <DD>} 
  <DT>　 
  <DT><FONT face=Arial size=5><STRONG>Alpha-beta</STRONG></FONT><FONT 
  face=楷体_GB2312 size=5><STRONG>和着法顺序</STRONG></FONT> 
  <DT>　 
  <DT>　　我们现在就回到<FONT 
  face="Times New Roman">Alpha-Beta</FONT>。上次我们的分析指出，在最乐观的情况下，如果能裁剪的地方都裁剪了，那么搜索深度将增加一倍。“能裁剪的地方都裁剪了”这个条件说得再简单一些，就是好的着法在坏的着法之前搜索。着法没有必要完全排序好，但是最好的着法必须首先搜索，或者最好的几个着法必须在比较前面的几个位置搜索。如果不这样做，就不会有裁剪并且不会搜索得很深。 

  <DT>　　我们把结点分为<FONT face="Times New Roman">A</FONT>型<FONT 
  face="Times New Roman">(</FONT>所有的子结点都搜索过<FONT 
  face="Times New Roman">)</FONT>和<FONT face="Times New Roman">B</FONT>型<FONT 
  face="Times New Roman">(</FONT>在搜索到好的子结点后即裁剪掉了<FONT 
  face="Times New Roman">)</FONT>，那么着法的顺序对两种结点都很重要：在<FONT 
  face="Times New Roman">B</FONT>型结点中，需要从最好的子结点开始，以裁剪掉剩余的节点；而在<FONT 
  face="Times New Roman">A</FONT>型结点中，需要找到足够好的结点，来告诉其他结点，它们都是<FONT 
  face="Times New Roman">B</FONT>型的。 
  <DT>　　找到最好的着法当然是很难的，这就是我们需要进行搜索的原因。<FONT 
  color=#0000ff>【言下之意，要在搜索之前找到最好的着法，理论上是不可能的。】</FONT>但是我们可以根据以下线索来找：<FONT 
  face="Times New Roman">(1) </FONT>迭代加深时，散列表会记录前面一次搜索过的结点，散列表中的值可以用来作近似<FONT 
  face="Times New Roman">(</FONT>因为这是相同局面浅一些的搜索<FONT 
  face="Times New Roman">)</FONT>；<FONT 
  color=#0000ff>【原作者在散列表中没有记录最佳着法，其实这个着法最应该被首先搜索。】</FONT><FONT 
  face="Times New Roman">(2) 
  </FONT>针对特定的棋类游戏，我们需要一些知识，例如在国际象棋中，吃子的着法往往是好的着法，应该首先尝试；<FONT 
  face="Times New Roman">(3) </FONT>杀手启发：如果相邻结点有好的着法，并且在现在的结点上该着法也合理，那么应该首先尝试。 
  <DT>　　因此在搜索子结点之前要加上一步：按照着法的质量来排序，然后按照这个顺序来搜索。<FONT 
  face="Times New Roman">(</FONT>有时你们可以直接修改着法生成器，让它进行粗略的排序，比如先生成吃子的着法，从而节省下重新排序的时间。<FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　还有一个诀窍：如果你希望发生裁剪，那么你不必对所有着法排序，只要排序前面很少几个着法就可以了。那么你应该用这样的搜索算法，最佳着法可以一个一个地挑出，然后早早地停止排序，例如选择排序和堆排序。<FONT 
  color=#0000ff>【译者认为冒泡排序是最符合原作者的意图的，因为排序时每扫描一趟即可找到一个最佳着法，在扫描第二趟之前先搜索这个着法。而几乎没有程序是用堆排序的，尽管它的复杂度是所有排序算法中最低的，并且不消耗额外的存储器，但是对</FONT><FONT 
  face="Times New Roman" color=#0000ff>100</FONT><FONT 
  color=#0000ff>个以下的数进行排序，它的速度是非常缓慢的。】</FONT> 
  <DT>　 
  <DT>　　原文：<A href="http://www.ics.uci.edu/~eppstein/180a/970424.html" 
  target=_blank><FONT 
  face="Times New Roman">http://www.ics.uci.edu/~eppstein/180a/970424.html</FONT></A> 

  <DT>　　译者：黄晨 <FONT face="Times New Roman">(</FONT><A 
  href="mailto:[e-mail]"><FONT 
  face="Times New Roman">[e-mail]</FONT></A><FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　类型：全译加译注 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/search_intro2.htm">基本搜索方法——简介<FONT 
face="Times New Roman">(</FONT>二<FONT face="Times New Roman">)</FONT></A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/search_minimax.htm">基本搜索方法——最小<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>