<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>?！?lt;/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:webmaster@elephantbase.net"><FONT 
  face="Times New Roman">webmaster@elephantbase.net</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>