?? 其他策略——殘局庫.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0051)http://www.elephantbase.net/computer/other_egtb.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 background=其他策略——殘局庫_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT>《對弈程序基本技術》專題 </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<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">Martin Fierz */ </FONT>文 </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">* </FONT>瑞士<FONT
face="Times New Roman">Windisch</FONT>應用科學學院<FONT
face="Times New Roman">(Aargau</FONT>學院<FONT face="Times New Roman">)</FONT>
</CENTER></DT></DIV>
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>簡介</STRONG></FONT>
<DT>
<DT> 殘局庫在很多棋類游戲中扮演著非常重要的角色，例如九人<FONT
face="Times New Roman">Morris</FONT>，<FONT
face="Times New Roman">Awari</FONT>和西洋跳棋<FONT
face="Times New Roman">(Checkers)(</FONT>其中九人<FONT
face="Times New Roman">Morris</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>如連四子棋、黑白棋和圍棋<FONT
face="Times New Roman">)</FONT>。你是否已經發現這些棋類的差異了？通常只有在盤面上棋子數量很少的情況下，殘局庫才能實現。適用殘局庫有個確切的棋子數量的界限，它取決于棋類的復雜性。有些棋類隨著對局的進行，棋子數量是減少的，那么殘局庫就是可行的；而有些棋類的棋子數量是增加的或者不變的，那么殘局庫就是無法計算的<FONT
face="Times New Roman">(</FONT>除非棋類異常簡單<FONT
face="Times New Roman">)</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">(</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">-</FONT>薩克森式的<FONT
face="Times New Roman">)</FONT>西洋跳棋里，有多達<FONT
face="Times New Roman">8</FONT>子的殘局庫，而<FONT
face="Times New Roman">10</FONT>子的殘局庫也已經在計算了，這就意味著在有吃必吃的規則下，很多棋局會很快走到有殘局庫的局面中，因此殘局庫使得西洋跳棋的棋力有了很大的提高。要讓某種棋類完全可解，通常總是要借助于殘局庫的——從起始局面開始向前搜索，結合殘局庫，就能解出這盤棋。<FONT
face="Times New Roman">Gasser</FONT>用這種辦法解決了九人<FONT
face="Times New Roman">Morris</FONT>，而<FONT
face="Times New Roman">Chinook(</FONT>最著名的西洋跳棋程序<FONT
face="Times New Roman">)</FONT>的小組正在用這個方法解西洋棋。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>殘局庫的不同類型</STRONG></FONT>
<DT>
<DT> 殘局庫有不同的類型，而它們都可以知道殘局庫中某個特定的局面是贏棋、是輸棋還是和棋。如果這就是殘局庫包含的所有信息，就稱為“勝負和”<FONT
face="Times New Roman">(WLD)</FONT>殘局庫；如果知道多少步以后棋局會結束，就稱為“殺棋步數”<FONT
face="Times New Roman">(DTM</FONT>，<FONT
face="Times New Roman">Distance-to-Mate)</FONT>殘局庫；如果只知道多少步以后會轉換為另一種類型的局面，就稱為“轉換步數”<FONT
face="Times New Roman">(DTC</FONT>，<FONT
face="Times New Roman">Distance-to-Conversion)</FONT>殘局庫。<FONT
face="Times New Roman">WLD</FONT>殘局庫有個問題，即便程序處于勝利局面，也未必能贏下棋局。盡管殘局庫知道某個局面已經是勝利局面，并且知道走哪步能繼續保持勝利局面，但是保持勝利局面的著法可能會距離殺棋更遠，而程序又不知道該選擇哪步保持勝利局面的著法。<FONT
color=#0000ff>【譯注：更具體的說明請參閱《</FONT><A
href="http://www.elephantbase.net/computer/other_winning.htm"
target=_blank><FONT color=#0000ff size=3>勝利局面中的強制過程</FONT></A><FONT
color=#0000ff>》一文。】</FONT><FONT
face="Times New Roman">DTM</FONT>殘局庫顯然在這個方面做得比較好，因為你只要選擇<FONT
face="Times New Roman">DTM(</FONT>轉換步數<FONT
face="Times New Roman">)</FONT>最少的那個保持勝利局面的著法。<FONT
face="Times New Roman">DTC</FONT>殘局庫也能夠在勝利局面下走出取得勝利的著法，但程序走的步數可能會比必要的步數多。至今還有人使用<FONT
face="Times New Roman">WLD</FONT>殘局庫，你可能很懷疑。原因很簡單，儲存勝負和的信息只需要很小的空間，如果殘局庫比計算機的存儲器大得多<FONT
face="Times New Roman">(</FONT>通常如此<FONT
face="Times New Roman">)</FONT>，那么殘局庫有很多部分可以放入存儲器。從磁盤上讀取殘局庫不是一個好的選擇，因為磁盤跟存儲器比起來慢得多。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>殘局庫的生成</STRONG></FONT>
<DT>
<DT> 殘局庫的生成是一個相對比較簡單的過程，盡管有很多細節，但這不影響生成過程的理解。殘局庫生成的基本算法稱為“后退式分析”<FONT
face="Times New Roman">(Retrograde Analysis)</FONT>，它是由<FONT
face="Times New Roman">Ken Thompson</FONT>發明的<FONT
face="Times New Roman">(</FONT>至少是首先使用的<FONT
face="Times New Roman">)</FONT>。以下就是整個過程：
<DT> 以我們要生成“王車對王”的殘局為例，你要從“索引函數”<FONT face="Times New Roman">(Index
Function)</FONT>開始，每個可能的王車對王局面都有一個數字。索引函數必須能倒過來映射到以數字<FONT
face="Times New Roman"><EM>x</EM></FONT>為代表的局面。理想情況下，索引函數會把所有<FONT
face="Times New Roman"><EM>N</EM></FONT>個合理的王車對王局面映射為<FONT
face="Times New Roman">0, 1, ..., <EM>N</EM> </FONT><FONT
face=Symbol>-</FONT><FONT face="Times New Roman">
1</FONT>。如果是這種情況，我們稱之為“無間隙”<FONT
face="Times New Roman">(Gapless)</FONT>的索引。一般情況下，索引函數把所有合理局面編號為<FONT
face="Times New Roman">0, 1, ..., <EM>M</EM> </FONT><FONT
face=Symbol>-</FONT><FONT face="Times New Roman"> 1</FONT>，而<FONT
face="Times New Roman"><EM>M</EM> > <EM>N</EM></FONT>，我們稱其為“有間隙”<FONT
face="Times New Roman">(Gapped)</FONT>的索引。有間隙的索引往往更簡單，因為構造一個有間隙的索引函數要比無間隙的索引函數簡單得多。后退式分析需要的存儲器跟索引號的最大值成正比，因此如果構造了一個<FONT
face="Times New Roman"><EM>M</EM></FONT>比<FONT
face="Times New Roman"><EM>N</EM></FONT>大得多的索引函數，那么你會浪費很多存儲器。
<DT> 一旦有了索引函數，后退式分析算法就只要做以下幾件事：
<DT>
<DT> <FONT face="Times New Roman">(1) </FONT>初始化：生成兩個長度都為<FONT
face="Times New Roman">N</FONT>的數組，分別存放結果<FONT
face="Times New Roman">(WIN/LOSS/DRAW</FONT>，代表勝負和<FONT
face="Times New Roman">)</FONT>和<FONT
face="Times New Roman">DTC</FONT>。把所有的結果都設成<FONT
face="Times New Roman">UNKNOWN(</FONT>代表未知<FONT
face="Times New Roman">)</FONT>，所有的<FONT
face="Times New Roman">DTC</FONT>計數器都設成<FONT
face="Times New Roman">0</FONT>。你會發現，你需要<FONT
face="Times New Roman">4</FONT>個數來表示結果，因此數組的數據類型是<FONT
face="Times New Roman">4</FONT>個值的數<FONT face="Times New Roman">(</FONT>即<FONT
face="Times New Roman">2</FONT>位<FONT
face="Times New Roman">)</FONT>。當然，還有些根本不存在的局面，你需要自行處理。
<DT> <FONT face="Times New Roman">(2)
</FONT>殺棋遍歷：逐一檢查每個局面是否是殺棋局面，如果是的，就把這個局面的結果設成<FONT
face="Times New Roman">LOSS</FONT>，表示即將走的一方輸了。如果棋類允許“逼和”的存在，也必須作逼和的檢查，并賦值為<FONT
face="Times New Roman">DRAW</FONT>。把每個<FONT
face="Times New Roman">UNKNOWN</FONT>局面的<FONT
face="Times New Roman">DTC</FONT>計數器加<FONT face="Times New Roman">1</FONT>。
<DT> <FONT face="Times New Roman">(3) </FONT>對每個<FONT
face="Times New Roman">UNKNOWN</FONT>的局面，生成所有后續局面并看它們都有哪些結果。只要其中有一個后續局面是<FONT
face="Times New Roman">LOSS</FONT>，就把這個局面設成<FONT
face="Times New Roman">WIN</FONT>。如果所有后續局面都是<FONT
face="Times New Roman">WIN</FONT>，就把這個局面設成<FONT
face="Times New Roman">LOSS</FONT>。如果你遍歷了所有局面但沒有一個局面能設<FONT
face="Times New Roman">WIN</FONT>或<FONT
face="Times New Roman">LOSS</FONT>的，就跳到第<FONT
face="Times New Roman">5</FONT>步。
<DT> <FONT face="Times New Roman">(4) </FONT>把每個<FONT
face="Times New Roman">UNKNOWN</FONT>局面的<FONT
face="Times New Roman">DTC</FONT>計數器加<FONT
face="Times New Roman">1</FONT>，并回到第<FONT face="Times New Roman">3</FONT>步。
<DT> <FONT face="Times New Roman">(5) </FONT>把每個<FONT
face="Times New Roman">UNKNOWN</FONT>局面設成<FONT
face="Times New Roman">DRAW</FONT>，算法就結束了。
<DT>
<DT> 這個算法顯然是確保完成的。在第<FONT
face="Times New Roman">3</FONT>步里當吃子發生時，你就要讀取少一個子的殘局庫。很明顯，沒有王車對王的殘局庫，你無法獨立地生成王車對王馬的殘局庫。如果你只要生成<FONT
face="Times New Roman">WLD</FONT>殘局庫，就可以不要<FONT
face="Times New Roman">DTC</FONT>計數器。如果你需要生成<FONT
face="Times New Roman">DTM</FONT>殘局庫，你就需要在局面轉換時傳遞<FONT
face="Times New Roman">DTM</FONT>值。以上算法有很多優化方案，但是我不想展開討論，最基本的算法已經非常簡單明了了，為什么再舍棄它呢？
<DT> 明白了整個算法后，你就知道為什么叫做“后退式”了——該算法總是從已知局面<FONT
face="Times New Roman">(</FONT>殺棋或能轉換為低級別的殘局庫局面<FONT
face="Times New Roman">)</FONT>向后找，按照上述算法的第<FONT
face="Times New Roman">3</FONT>和第<FONT
face="Times New Roman">4</FONT>步，每次遍歷就后退半步。我們拿一個局面舉例說明，白王在<FONT
face="Times New Roman">g3</FONT>，黑王在<FONT
face="Times New Roman">h1</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/7k b - - 0 1</FONT><FONT
color=#0000ff>】</FONT>。在遍歷殺棋局面時，按照上述算法找到白王在<FONT
face="Times New Roman">g3</FONT>，白車在<FONT
face="Times New Roman">a1</FONT>，黑王在<FONT
face="Times New Roman">g1</FONT>，黑先走<FONT color=#0000ff>【</FONT><FONT
face="Times New Roman" color=#0000ff>8/8/8/8/8/6K1/8/R5k1 b - - 0
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -