《對弈程序基本技術》專題
 
殘局庫
 
Martin Fierz */
* 瑞士Windisch應用科學學院(Aargau學院)
 
簡介
 
  殘局庫在很多棋類游戲中扮演著非常重要的角色,例如九人MorrisAwari和西洋跳棋(Checkers)(其中九人Morris已經完全可解了,這要歸功于殘局庫的使用)。在其他棋類中,殘局庫就不那么重要了(例如國際象棋),而某些棋類制作殘局庫是不現實的(如連四子棋、黑白棋和圍棋)。你是否已經發現這些棋類的差異了?通常只有在盤面上棋子數量很少的情況下,殘局庫才能實現。適用殘局庫有個確切的棋子數量的界限,它取決于棋類的復雜性。有些棋類隨著對局的進行,棋子數量是減少的,那么殘局庫就是可行的;而有些棋類的棋子數量是增加的或者不變的,那么殘局庫就是無法計算的(除非棋類異常簡單),無論如何殘局庫取決于具體的棋類。例如在國際象棋中,有多達6子的殘局庫(王車兵對王車兵等),而這種殘局(包括其他不超過6子的殘局)在實戰中不是經常出現的,因此殘局庫對棋力的影響并不是很大。而在(盎格魯-薩克森式的)西洋跳棋里,有多達8子的殘局庫,而10子的殘局庫也已經在計算了,這就意味著在有吃必吃的規則下,很多棋局會很快走到有殘局庫的局面中,因此殘局庫使得西洋跳棋的棋力有了很大的提高。要讓某種棋類完全可解,通常總是要借助于殘局庫的——從起始局面開始向前搜索,結合殘局庫,就能解出這盤棋。Gasser用這種辦法解決了九人Morris,而Chinook(最著名的西洋跳棋程序)的小組正在用這個方法解西洋棋。
 
殘局庫的不同類型
 
  殘局庫有不同的類型,而它們都可以知道殘局庫中某個特定的局面是贏棋、是輸棋還是和棋。如果這就是殘局庫包含的所有信息,就稱為“勝負和”(WLD)殘局庫;如果知道多少步以后棋局會結束,就稱為“殺棋步數”(DTMDistance-to-Mate)殘局庫;如果只知道多少步以后會轉換為另一種類型的局面,就稱為“轉換步數”(DTCDistance-to-Conversion)殘局庫。WLD殘局庫有個問題,即便程序處于勝利局面,也未必能贏下棋局。盡管殘局庫知道某個局面已經是勝利局面,并且知道走哪步能繼續保持勝利局面,但是保持勝利局面的著法可能會距離殺棋更遠,而程序又不知道該選擇哪步保持勝利局面的著法。【譯注:更具體的說明請參閱《勝利局面中的強制過程》一文。】DTM殘局庫顯然在這個方面做得比較好,因為你只要選擇DTM(轉換步數)最少的那個保持勝利局面的著法。DTC殘局庫也能夠在勝利局面下走出取得勝利的著法,但程序走的步數可能會比必要的步數多。至今還有人使用WLD殘局庫,你可能很懷疑。原因很簡單,儲存勝負和的信息只需要很小的空間,如果殘局庫比計算機的存儲器大得多(通常如此),那么殘局庫有很多部分可以放入存儲器。從磁盤上讀取殘局庫不是一個好的選擇,因為磁盤跟存儲器比起來慢得多。
 
殘局庫的生成
 
  殘局庫的生成是一個相對比較簡單的過程,盡管有很多細節,但這不影響生成過程的理解。殘局庫生成的基本算法稱為“后退式分析”(Retrograde Analysis),它是由Ken Thompson發明的(至少是首先使用的)。以下就是整個過程:
  以我們要生成“王車對王”的殘局為例,你要從“索引函數”(Index Function)開始,每個可能的王車對王局面都有一個數字。索引函數必須能倒過來映射到以數字x為代表的局面。理想情況下,索引函數會把所有N個合理的王車對王局面映射為0, 1, ..., N - 1。如果是這種情況,我們稱之為“無間隙”(Gapless)的索引。一般情況下,索引函數把所有合理局面編號為0, 1, ..., M - 1,而M > N,我們稱其為“有間隙”(Gapped)的索引。有間隙的索引往往更簡單,因為構造一個有間隙的索引函數要比無間隙的索引函數簡單得多。后退式分析需要的存儲器跟索引號的最大值成正比,因此如果構造了一個MN大得多的索引函數,那么你會浪費很多存儲器。
  一旦有了索引函數,后退式分析算法就只要做以下幾件事:
 
  (1) 初始化:生成兩個長度都為N的數組,分別存放結果(WIN/LOSS/DRAW,代表勝負和)DTC。把所有的結果都設成UNKNOWN(代表未知),所有的DTC計數器都設成0。你會發現,你需要4個數來表示結果,因此數組的數據類型是4個值的數(2)。當然,還有些根本不存在的局面,你需要自行處理。
  (2) 殺棋遍歷:逐一檢查每個局面是否是殺棋局面,如果是的,就把這個局面的結果設成LOSS,表示即將走的一方輸了。如果棋類允許“逼和”的存在,也必須作逼和的檢查,并賦值為DRAW。把每個UNKNOWN局面的DTC計數器加1
  (3) 對每個UNKNOWN的局面,生成所有后續局面并看它們都有哪些結果。只要其中有一個后續局面是LOSS,就把這個局面設成WIN。如果所有后續局面都是WIN,就把這個局面設成LOSS。如果你遍歷了所有局面但沒有一個局面能設WINLOSS的,就跳到第5步。
  (4) 把每個UNKNOWN局面的DTC計數器加1,并回到第3步。
  (5) 把每個UNKNOWN局面設成DRAW,算法就結束了。
 
  這個算法顯然是確保完成的。在第3步里當吃子發生時,你就要讀取少一個子的殘局庫。很明顯,沒有王車對王的殘局庫,你無法獨立地生成王車對王馬的殘局庫。如果你只要生成WLD殘局庫,就可以不要DTC計數器。如果你需要生成DTM殘局庫,你就需要在局面轉換時傳遞DTM值。以上算法有很多優化方案,但是我不想展開討論,最基本的算法已經非常簡單明了了,為什么再舍棄它呢?
  明白了整個算法后,你就知道為什么叫做“后退式”了——該算法總是從已知局面(殺棋或能轉換為低級別的殘局庫局面)向后找,按照上述算法的第3和第4步,每次遍歷就后退半步。我們拿一個局面舉例說明,白王在g3,黑王在h1,白車在a2,黑先走8/8/8/8/8/6K1/R7/7k b - - 0 1。在遍歷殺棋局面時,按照上述算法找到白王在g3,白車在a1,黑王在g1,黑先走8/8/8/8/8/6K1/8/R5k1 b - - 0 1,這個局面是殺棋,所以把它設為LOSS。在我們要討論的這個局面中,根本不能檢查到什么。在主循環的第一次遍歷中,會為“白王在g3,黑王在g1,白車在a28/8/8/8/8/6K1/R7/6k1 w - - 0 1產生所有著法,發現走了Rb2-b1后就是LOSS局面,根據規則這個局面就設為WIN。下一步,為黑王在h1的局面8/8/8/8/8/6K1/R7/7k b - - 0 1找后續局面,發現所有的后續局面都是WIN局面(這個局面的后續局面只有一個)。最后把這個局面設成LOSS,就得到了正確的結果。
 
索引函數
 
  索引函數對這個算法非常重要,你無法存儲整個局面并對他們設定結果,因為結果只需要2位,而整個局面需要用大量存儲器來描述。如果你存儲整個局面,你就會浪費大量的存儲器。用了索引函數以后,你就能夠簡單地用一個數字來代表局面了,你不需要把結果和索引數字都記下來,而只需要以索引數字為數組的指標,只在數組中存儲結果。那么如何才能找到符合上述性質的索引函數呢?看上去這是個很嚇人的工作,實際上用簡單的方法來構造索引函數是可行的。對于棋子各不相同的殘局(例如白王、白車和黑王),就非常簡單,把格子標號為063,就可以寫下這樣的公式:
 
index = wK_index + 64 * wR_index + 64 * 64 * bK_index;
 
  這個函數完成了局面到數字的轉換,并且它是可逆的(wK_index = index % 64, wR_index = (index / 64) % 64,等等),但是它會產生一些不合理局面(例如幾個子在同一個格子上,或兩個王緊挨著)。這個函數也沒有利用棋盤的對稱性。這些細節問題是完全可以解決的,但是在這里我不想多說了。那么如果棋盤上有多于一個的相同棋子,例如王雙車對王,怎么辦呢?我們照樣寫:
 
index = wK_index + 64 * wR1_index + 64 * 64 * wR2_index + 64 * 64 * 64 * bK_index;
 
  這樣當然很管用,但是非常愚笨,因為1號車在x格而2號車在y格,情況跟2號車在x格而1號車在y格是一樣的。這樣我們的索引就比必要的數多了一倍!為了解決這個問題,我們用組合公式來表示2個相同的子在64個位置上的情況:在數學課上你肯定學過用N = 64 × 63 / 2來做。因此我們可以寫成:
 
index = wK_index + 64 * combinedindex + 64 * N * bK_index;
 
  剩下來的問題就是由車的具體位置來計算“組合的車的索引”了,它是064 × 63 / 2 - 1之間的數。用r1r2表示兩個車的位置,并且r1 < r2(這樣就等同于除以2!)。我們有:
 
combinedindex = bicoef(r1, 1) + bicoef(r2, 2);
 
  這里bicoef(x, y)代表xy(x > y)的二項式系數,即x! × y! / (x - y)!,任意數量的棋子都可以由這個組合索引公式產生。它的逆公式有點復雜,如果是k個子在n個格子上的組合索引,我們就必須用順序搜索的辦法來分析它的組成:因為組合索引的最后一項總是最大的,所以我們要依次計算i = n - 1, n - 2, ...bicoef(i, k),直到比組合索引數小為止。一旦找到了i,我們就知道它在第i格上,然后在組合索引上減去bicoef(i, k)。然后我們依次計算j = i - 1, i - 2, ...bicoef(j, k - 1),因為我們已經在建立索引函數的時候知道j < i了。
 
壓縮
 
  當你開始生成殘局庫時,你一定會馬上意識到你要建立的殘局庫是非常龐大的。例如,8子的西洋跳棋殘局庫如果沒有壓縮,就需要大約40GB的磁盤空間。如果你需要在1GBRAM的計算機上使用這個殘局庫,你就必須對它進行壓縮。壓縮這類殘局庫的標準方法是“行程編碼”(RLERun-Length Encoding):當你在查找后退式分析所產生的數組時,它看上去會是這樣的:
 
....WWWBWWLLDBDBDDDWLBLLLWWBDDD...
 
  這里WLDB代表勝負和壞,壞的意思是局面不合理,使用有間隙的索引,或者不走棋的一方被將軍了,這種情況就會發生。要對此進行壓縮,我們首先注意到對壞的標志可以任意處理,因為它們沒有用,因此我們將它們設定為最方便壓縮的值:
 
....WWWWWWLLDDDDDDDWLLLLLWWDDDD...
 
  行程編碼存儲的就是一對對數值和長度,上面的例子就轉換為:
 
(W,6) (L,2) (D,7) (W,1) (L,5) (W,2) (D,4)
 
  如果行程非常長(我沒有耐心來造一個行程非常長的例子),那么這種壓縮的效果就非常好。8子的西洋跳棋殘局庫可以壓縮到大約4GB,壓縮因子是10
 
在搜索中讀取數據庫
 
  壓縮完殘局庫以后,你必須寫一個飛躍式(on-the-fly)的解壓縮程序,根據局面找到結果。或許這還不夠,如果殘局庫大到超過你的RAM,你就必須為自己的殘局庫寫一個存儲器管理程序。你不會指望Windows(或其他操作系統)來幫你管理殘局庫,因為你自己寫的程序是高效的。管理殘局庫的通常做法是把壓縮的殘局庫分成一個個幾千字節的塊(Chunks),如果你需要知道某個局面的結果,就一次讀取整個塊。從磁盤讀取1字節或1千字節是沒有差別的,速度只取決于磁盤的尋找時間,而跟傳輸速度無關。一次讀取整個塊,就把很多相似的局面裝入存儲器,這些局面可能是你以后要用到的。一般來說,你會用“最近最少用到”(Least-Recently-Used)的策略,來決定在裝入一個塊的時候哪個塊應該被覆蓋掉。即便你用了塊,由于磁盤比起存儲器來說實在太慢,你無法對所有局面都去查找殘局庫。通常你只會在第x層以外去讀取磁盤上的殘局庫局面,而在x層以內你只會在存儲器中查找這些局面。
 
  原文:http://www.fierz.ch/strategy3.htm
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 其他策略——后臺思考
  • 下一篇 其他策略——開局庫
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果