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

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

  <DD>　　　e = em; 
  <DD>　　　mm = m; 
  <DD>　　} 
  <DD>　　撤消着法 m; 
  <DD>　} 
  <DD>　return mm; 
  <DD>} 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>负值最大的分析：分枝因子和深度</STRONG></FONT> 
  <DT>　 
  <DT>　　人们通常简单地根据博弈树的形状来对博弈树算法进行分析。我们假设每个中间结点有同样多的子结点，其数量称为分枝因子<FONT 
  face="Times New Roman">(Branching Factor)</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">(</FONT>看上去需要乘上一个系数，以反映调用负值最大时的那个循环，但是这个循环所花的时间已经被包括在递归函数里了。<FONT 
  face="Times New Roman">)</FONT><FONT 
  color=#0000ff>【译者也不理解这句话的意思，但译者认为程序中</FONT><FONT face="Times New Roman" 
  color=#0000ff>eval()</FONT><FONT 
  color=#0000ff>函数所花费的时间最多，而它只是在搜索到叶子结点时才被调用，因此只计算叶子结点的数量就可以了，即</FONT><FONT 
  face="Times New Roman" 
  color=#0000ff><EM>b</EM><SUP><EM>d</EM></SUP></FONT><FONT 
  color=#0000ff>。】</FONT>如果分枝因子是<FONT 
  face="Times New Roman"><EM>b</EM></FONT>，深度是<FONT 
  face="Times New Roman"><EM>d</EM></FONT>，那么这个数就是： 
  <DIV align=center>
  <CENTER></DIV>
  <DT><FONT face="Times New Roman">1 + <EM>b</EM> + <EM>b</EM><SUP>2</SUP> + 
  <EM>b</EM><SUP>3</SUP> + ... + <EM>b</EM><SUP><EM>d</EM></SUP> = 
  <EM>b</EM><SUP><EM>d</EM></SUP> (1 </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> 1 / <EM>b</EM><SUP><EM>d</EM></SUP>) / (1 </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 1 / <EM>b</EM>). 
  </FONT></CENTER>
  <DIV></DIV>
  <DT>　　公式右端括号里的数值接近于<FONT face="Times New Roman">1</FONT>，所以整个运算所花费的时间接近于<FONT 
  face="Times New Roman"><EM>b</EM><SUP><EM>d</EM></SUP></FONT>。 
  <DT>　　如果棋类游戏不符合以上假定，我们可以反过来定义一个“有效分枝因子”<FONT face="Times New Roman">(Effective 
  Branching Factor)</FONT>，使得这个<FONT 
  face="Times New Roman"><EM>b</EM></FONT>能够符合程序运行所花费的时间。更简单些，可以把“分枝因子”描述为某个棋类游戏中“典型”局面的可能着法数的平均值。 

  <DT>　　这个公式可以告诉我们什么呢？首先它是指数形式的，这就意味着我们不可能搜索太多层，如果电脑的速度翻了番，那么我们只能把<FONT 
  face="Times New Roman"><EM>d</EM></FONT>增加很小一点。其次搜索取决于分枝因子<FONT 
  face="Times New Roman"><EM>b</EM></FONT>，在分枝因子很小的棋类中<FONT 
  face="Times New Roman">(</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">30</FONT>种左右的着法<FONT 
  face="Times New Roman">)</FONT>或围棋<FONT 
  face="Times New Roman">(</FONT>一个局面有几百种着法<FONT 
  face="Times New Roman">)</FONT>深得多，因此我们喜欢让<FONT 
  face="Times New Roman"><EM>b</EM></FONT>越小越好。很不幸的是搜索函数更多地决于棋类游戏本身，而不是我们写程序的水平。但是下一次我们要讨论一个算法，称为<FONT 
  face="Times New Roman">Alpha-Beta</FONT>裁剪，它可以很大程度地减少分枝因子，如果运气好的话，它可以减少到没有裁剪的博弈树的平方根那么多，这就意味着我们可以搜索原来深度<FONT 
  face="Times New Roman">(</FONT>即不用<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索的深度<FONT 
  face="Times New Roman">)</FONT>的两倍那么深。<FONT color=#0000ff>【</FONT><FONT 
  face="Times New Roman" color=#0000ff><EM>b</EM></FONT><FONT 
  color=#0000ff>的平方根即</FONT><FONT face="Times New Roman" 
  color=#0000ff><EM>b</EM><SUP>1/2</SUP></FONT><FONT 
  color=#0000ff>，用一下中学数学学过的公式，</FONT><FONT face="Times New Roman" 
  color=#0000ff>(<EM>b</EM><SUP>1/2</SUP>)<SUP><EM>d</EM></SUP> = 
  <EM>b</EM><SUP><EM>d</EM>/2</SUP></FONT><FONT color=#0000ff>，还记得吗？】</FONT> 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>迭代加深</STRONG></FONT> 
  <DT>　 
  <DT>　　负值极大的代码还留给我们一个问题：我们如何来给定搜索深度？简单的棋类程序只把它设成一个固定值，这就可能使得程序走的每步棋时花的时间长短变化非常大。因此你最好根据搜索所需的时间，来决定搜索的深度。幸运的是指数特征的搜索有这样一个好处：通过“迭代加深”<FONT 
  face="Times New Roman">(Iterated 
  Deepening)</FONT>这个手段，可以很容易地对搜索进行控制，刚开始搜索时浅一些，然后增加深度重复搜索直到时间用完为止： 
  <DD>　 
  <DD>depth = 0 
  <DD>while (有足够的时间来进行下一层的搜索) { 
  <DD>　depth ++; 
  <DD>　m = rootsearch(depth); 
  <DD>} 
  <DD>执行着法 m; 
  <DT>　 
  <DT>　　这看上去似乎在浪费时间，因为除了最后一次搜索外，前面的搜索都白费了。但是根据前面分析过的结果，白费的时间是很少的：不同层数所花的时间加起来是 
  <FONT face="Times New Roman">1 + <EM>b</EM> + <EM>b</EM><SUP>2 </SUP>+ 
  ...</FONT>，我们已经知道它接近于最后一项<FONT 
  face="Times New Roman"><EM>b</EM><SUP><EM>d</EM></SUP></FONT>了。所以，迭代加深所花的代价并不多，而它给我们提供了很好的时间控制的手段。它还有一个很大的作用：在做较深的搜索时，可以用浅一层搜索得到的着法顺序，在<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索中，着法顺序是影响搜索的速度的决定性因素。 
  <DT>　　<FONT color=#0000ff>【</FONT><FONT face="Times New Roman" 
  color=#0000ff>Iterative Deepening</FONT><FONT 
  color=#0000ff>，字面意思是“重复加深”，就如上文所讲的。但它最主要的作用是改善着法的顺序，它是</FONT><FONT 
  face="Times New Roman" color=#0000ff>Alpha-Beta</FONT><FONT 
  color=#0000ff>搜索的一种主要的启发方式，浅一层最好的着法在深一层的搜索中首先被尝试，本质上是一种迭代的过程，所以译为“迭代加深”。】</FONT> 

  <DT>　 
  <DT>　　原文：<A href="http://www.ics.uci.edu/~eppstein/180a/970417.html" 
  target=_blank><FONT 
  face="Times New Roman">http://www.ics.uci.edu/~eppstein/180a/970417.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/struct_zobrist.htm">数据结构——<FONT 
face="Times New Roman">Zobrist</FONT>键值</A> 
<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.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>