1</FONT><FONT color=#0000ff>】</FONT>，這個局面是殺棋，所以把它設為<FONT 
  face="Times New Roman">LOSS</FONT>。在我們要討論的這個局面中，根本不能檢查到什么。在主循環的第一次遍歷中，會為“白王在<FONT 
  face="Times New Roman">g3</FONT>，黑王在<FONT 
  face="Times New Roman">g1</FONT>，白車在<FONT 
  face="Times New Roman">a2</FONT>”<FONT color=#0000ff>【</FONT><FONT 
  face="Times New Roman" color=#0000ff>8/8/8/8/8/6K1/R7/6k1 w - - 0 
  1</FONT><FONT color=#0000ff>】</FONT>產生所有著法，發現走了<FONT 
  face="Times New Roman">Rb2-b1</FONT>后就是<FONT 
  face="Times New Roman">LOSS</FONT>局面，根據規則這個局面就設為<FONT 
  face="Times New Roman">WIN</FONT>。下一步，為黑王在<FONT 
  face="Times New Roman">h1</FONT>的局面<FONT color=#0000ff>【</FONT><FONT 
  face="Times New Roman" color=#0000ff>8/8/8/8/8/6K1/R7/7k b - - 0 1</FONT><FONT 
  color=#0000ff>】</FONT>找后續局面，發現所有的后續局面都是<FONT 
  face="Times New Roman">WIN</FONT>局面<FONT 
  face="Times New Roman">(</FONT>這個局面的后續局面只有一個<FONT 
  face="Times New Roman">)</FONT>。最后把這個局面設成<FONT 
  face="Times New Roman">LOSS</FONT>，就得到了正確的結果。 
  <DT>　 
  <DT><FONT face=楷體_GB2312 size=5><STRONG>索引函數</STRONG></FONT> 
  <DT>　 
  <DT>　　索引函數對這個算法非常重要，你無法存儲整個局面并對他們設定結果，因為結果只需要<FONT 
  face="Times New Roman">2</FONT>位，而整個局面需要用大量存儲器來描述。如果你存儲整個局面，你就會浪費大量的存儲器。用了索引函數以后，你就能夠簡單地用一個數字來代表局面了，你不需要把結果和索引數字都記下來，而只需要以索引數字為數組的指標，只在數組中存儲結果。那么如何才能找到符合上述性質的索引函數呢？看上去這是個很嚇人的工作，實際上用簡單的方法來構造索引函數是可行的。對于棋子各不相同的殘局<FONT 
  face="Times New Roman">(</FONT>例如白王、白車和黑王<FONT 
  face="Times New Roman">)</FONT>，就非常簡單，把格子標號為<FONT 
  face="Times New Roman">0</FONT>到<FONT 
  face="Times New Roman">63</FONT>，就可以寫下這樣的公式： 
  <DT>　 
  <DD><FONT size=3>index = wK_index + 64 * wR_index + 64 * 64 * bK_index;</FONT> 

  <DT>　 
  <DT>　　這個函數完成了局面到數字的轉換，并且它是可逆的<FONT face="Times New Roman">(wK_index = index % 
  64, wR_index = (index / 64) % 64</FONT>，等等<FONT 
  face="Times New Roman">)</FONT>，但是它會產生一些不合理局面<FONT 
  face="Times New Roman">(</FONT>例如幾個子在同一個格子上，或兩個王緊挨著<FONT 
  face="Times New Roman">)</FONT>。這個函數也沒有利用棋盤的對稱性。這些細節問題是完全可以解決的，但是在這里我不想多說了。那么如果棋盤上有多于一個的相同棋子，例如王雙車對王，怎么辦呢？我們照樣寫： 

  <DT>　 
  <DD><FONT size=3>index = wK_index + 64 * wR1_index + 64 * 64 * wR2_index + 64 
  * 64 * 64 * bK_index; </FONT>
  <DT>　 
  <DT>　　這樣當然很管用，但是非常愚笨，因為<FONT face="Times New Roman">1</FONT>號車在<FONT 
  face="Times New Roman"><EM>x</EM></FONT>格而<FONT 
  face="Times New Roman">2</FONT>號車在<FONT 
  face="Times New Roman"><EM>y</EM></FONT>格，情況跟<FONT 
  face="Times New Roman">2</FONT>號車在<FONT 
  face="Times New Roman"><EM>x</EM></FONT>格而<FONT 
  face="Times New Roman">1</FONT>號車在<FONT 
  face="Times New Roman"><EM>y</EM></FONT>格是一樣的。這樣我們的索引就比必要的數多了一倍！為了解決這個問題，我們用組合公式來表示<FONT 
  face="Times New Roman">2</FONT>個相同的子在<FONT 
  face="Times New Roman">64</FONT>個位置上的情況：在數學課上你肯定學過用<FONT 
  face="Times New Roman"><EM>N</EM> = 64 × 63 / 2</FONT>來做。因此我們可以寫成： 
  <DD>　 
  <DD><FONT size=3>index = wK_index + 64 * combinedindex + 64 * N * bK_index; 
  </FONT>
  <DD>　 
  <DT>　　剩下來的問題就是由車的具體位置來計算“組合的車的索引”了，它是<FONT 
  face="Times New Roman">0</FONT>到<FONT face="Times New Roman">64 × 63 / 2 
  </FONT><FONT face=Symbol>-</FONT><FONT face="Times New Roman"> 
  1</FONT>之間的數。用<FONT face="Times New Roman"><EM>r</EM><SUB>1</SUB></FONT>和<FONT 
  face="Times New Roman"><EM>r</EM><SUB>2</SUB></FONT>表示兩個車的位置，并且<FONT 
  face="Times New Roman"><EM>r</EM><SUB>1</SUB> &lt; 
  <EM>r</EM><SUB>2</SUB>(</FONT>這樣就等同于除以<FONT 
  face="Times New Roman">2</FONT>了<FONT face="Times New Roman">!)</FONT>。我們有： 
  <DD>　 
  <DD><FONT size=3>combinedindex = bicoef(r1, 1) + bicoef(r2, 2);</FONT> 
  <DT>　 
  <DT>　　這里<FONT face="Times New Roman">bicoef(<EM>x</EM>, 
  <EM>y</EM>)</FONT>代表<FONT face="Times New Roman"><EM>x</EM></FONT>和<FONT 
  face="Times New Roman"><EM>y</EM>(<EM>x</EM> &gt; 
  <EM>y</EM>)</FONT>的二項式系數，即<FONT face="Times New Roman"><EM>x</EM>! × 
  <EM>y</EM>! / (<EM>x</EM> </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> 
  <EM>y</EM>)!</FONT>，任意數量的棋子都可以由這個組合索引公式產生。它的逆公式有點復雜，如果是<FONT 
  face="Times New Roman"><EM>k</EM></FONT>個子在<FONT 
  face="Times New Roman"><EM>n</EM></FONT>個格子上的組合索引，我們就必須用順序搜索的辦法來分析它的組成：因為組合索引的最后一項總是最大的，所以我們要依次計算<FONT 
  face="Times New Roman"><EM>i</EM> = <EM>n</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 1, <EM>n</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 2, ...</FONT>的<FONT 
  face="Times New Roman">bicoef(<EM>i</EM>, 
  <EM>k</EM>)</FONT>，直到比組合索引數小為止。一旦找到了<FONT 
  face="Times New Roman"><EM>i</EM></FONT>，我們就知道它在第<FONT 
  face="Times New Roman"><EM>i</EM></FONT>格上，然后在組合索引上減去<FONT 
  face="Times New Roman">bicoef(<EM>i</EM>, <EM>k</EM>)</FONT>。然后我們依次計算<FONT 
  face="Times New Roman"><EM>j</EM> = <EM>i</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 1, <EM>i</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 2, ...</FONT>的<FONT 
  face="Times New Roman">bicoef(<EM>j</EM>, <EM>k</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 
  1)</FONT>，因為我們已經在建立索引函數的時候知道<FONT face="Times New Roman"><EM>j</EM> &lt; 
  <EM>i</EM></FONT>了。 
  <DT>　 
  <DT><FONT face=楷體_GB2312 size=5><STRONG>壓縮</STRONG></FONT> 
  <DT>　 
  <DT>　　當你開始生成殘局庫時，你一定會馬上意識到你要建立的殘局庫是非常龐大的。例如，<FONT 
  face="Times New Roman">8</FONT>子的西洋跳棋殘局庫如果沒有壓縮，就需要大約<FONT 
  face="Times New Roman">40GB</FONT>的磁盤空間。如果你需要在<FONT 
  face="Times New Roman">1GB</FONT>的<FONT 
  face="Times New Roman">RAM</FONT>的計算機上使用這個殘局庫，你就必須對它進行壓縮。壓縮這類殘局庫的標準方法是“行程編碼”<FONT 
  face="Times New Roman">(RLE</FONT>，<FONT face="Times New Roman">Run-Length 
  Encoding)</FONT>：當你在查找后退式分析所產生的數組時，它看上去會是這樣的： 
  <DD>　 
  <DD><FONT size=3>....WWWBWWLLDBDBDDDWLBLLLWWBDDD...</FONT> 
  <DT>　 
  <DT>　　這里<FONT 
  face="Times New Roman">WLDB</FONT>代表勝負和壞，壞的意思是局面不合理，使用有間隙的索引，或者不走棋的一方被將軍了，這種情況就會發生。要對此進行壓縮，我們首先注意到對壞的標志可以任意處理，因為它們沒有用，因此我們將它們設定為最方便壓縮的值： 

  <DD>　 
  <DD><FONT size=3>....WWWWWWLLDDDDDDDWLLLLLWWDDDD...</FONT> 
  <DT>　 
  <DT>　　行程編碼存儲的就是一對對數值和長度，上面的例子就轉換為： 
  <DD>　 
  <DD><FONT size=3>(W,6) (L,2) (D,7) (W,1) (L,5) (W,2) (D,4)</FONT> 
  <DT>　 
  <DT>　　如果行程非常長<FONT face="Times New Roman">(</FONT>我沒有耐心來造一個行程非常長的例子<FONT 
  face="Times New Roman">)</FONT>，那么這種壓縮的效果就非常好。<FONT 
  face="Times New Roman">8</FONT>子的西洋跳棋殘局庫可以壓縮到大約<FONT 
  face="Times New Roman">4GB</FONT>，壓縮因子是<FONT face="Times New Roman">10</FONT>。 

  <DT>　 
  <DT><FONT face=楷體_GB2312 size=5><STRONG>在搜索中讀取數據庫</STRONG></FONT> 
  <DT>　 
  <DT>　　壓縮完殘局庫以后，你必須寫一個飛躍式<FONT 
  face="Times New Roman">(on-the-fly)</FONT>的解壓縮程序，根據局面找到結果。或許這還不夠，如果殘局庫大到超過你的<FONT 
  face="Times New Roman">RAM</FONT>，你就必須為自己的殘局庫寫一個存儲器管理程序。你不會指望<FONT 
  face="Times New Roman">Windows(</FONT>或其他操作系統<FONT 
  face="Times New Roman">)</FONT>來幫你管理殘局庫，因為你自己寫的程序是高效的。管理殘局庫的通常做法是把壓縮的殘局庫分成一個個幾千字節的塊<FONT 
  face="Times New Roman">(Chunks)</FONT>，如果你需要知道某個局面的結果，就一次讀取整個塊。從磁盤讀取<FONT 
  face="Times New Roman">1</FONT>字節或<FONT 
  face="Times New Roman">1</FONT>千字節是沒有差別的，速度只取決于磁盤的尋找時間，而跟傳輸速度無關。一次讀取整個塊，就把很多相似的局面裝入存儲器，這些局面可能是你以后要用到的。一般來說，你會用“最近最少用到”<FONT 
  face="Times New Roman">(Least-Recently-Used)</FONT>的策略，來決定在裝入一個塊的時候哪個塊應該被覆蓋掉。即便你用了塊，由于磁盤比起存儲器來說實在太慢，你無法對所有局面都去查找殘局庫。通常你只會在第<FONT 
  face="Times New Roman"><EM>x</EM></FONT>層以外去讀取磁盤上的殘局庫局面，而在<FONT 
  face="Times New Roman"><EM>x</EM></FONT>層以內你只會在存儲器中查找這些局面。 
  <DT>　 
  <DT>　　原文：<A href="http://www.fierz.ch/strategy3.htm" target=_blank><FONT 
  face="Times New Roman">http://www.fierz.ch/strategy3.htm</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/other_ponder.htm">其他策略——后臺思考</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/other_book.htm">其他策略——開局庫</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>