|
|
棋盤的表示
David Eppstein */文
* 加州愛爾文大學(UC Irvine)信息與計算機科學系
要讓機器下棋，程序首先必須對兩個對象進行存儲和操作，它們是局面和著法。這兩個對象的表示使得程序可以進行下列操作：
(1) 執行一個著法(不僅僅是用戶所指出的著法，而是在搜索過程中要用到的)；
(2) 撤消一個著法(作用同上)；
(3) 向用戶顯示棋盤；
(4) 產生所有可能的著法；
(5) 對棋盤的局面作出評估。
除了顯示棋盤以外，所有的操作都應該盡可能地迅速，因為它們會在搜索的循環內被調用。(而顯示棋盤的操作畢竟不是經常要做的。【譯注：在UCI協議(國際象棋通用引擎協議)中，引擎從不顯示棋盤，因此這個操作事實上是多余的?！?/font>)
著法的內部表示應該是非常簡潔的(因為我們不需要花太多的時間來生成一系列著法)而且能快速解讀，但是非常重要的是，它應該能代表所有的著法！在國際象棋中，機器內典型的著法表示，就是記錄移動棋子的起點格子和終點格子，例如王前兵進兩格就表示為“e2e4”(e2代表這個兵起點位置而e4代表終點位置)。不管是否吃子，被吃的棋子都不必記錄，因為它可以由終點格子來判斷。在機器中位置能表示為6位的數值，所以一個著法可以用2個字節表示。盡管很多程序都是這樣表示的，但是這種表示方法不足以表示所有的著法！王車易位時，有兩個子要移動，此時我們把它當作特殊情況來考慮，只記錄王的移動。問題在于，當兵從第七行走到第八行時，可以升變為后、車、馬或象，上述表示方法不能讓我們指定升變為哪個棋子。因此在設計著法表示時需要非常仔細，要確認這種表示能夠涵蓋棋局中所有可能發生的特殊情況。
【一般而言，棋類的著法有兩種形式，即添子式和移動式。五子棋、圍棋、黑白棋等屬于添子式，記錄著法時只要記錄棋子所下到的那個格子。其中五子棋最簡單，下完的棋子不再會改變；黑白棋稍復雜些，下完的棋子可能會被后續著法所變換黑白，但每下一子棋盤上就多一子；圍棋是最復雜的，由于存在提子的著法，所以局勢是可逆的，打劫這樣的著法需要很復雜的處理過程。
國際象棋和中國象棋都屬于移動式，相比較而言中國象棋更簡單，當一個棋子從起點移到終點時，只要簡單地做一下終點的覆蓋即可；而國際象棋由于三條特殊規則的存在而必須做特別處理，有時別的特殊位置的棋子要跟著移動(王車易位)，有時別的特殊位置的子要被吃掉(吃過路兵)，有時移動的棋子要被其他棋子所替代(升變)。】
棋盤的表示可能稍許復雜了些，但也不應該太龐大。它必須包括所有相關的信息，而不僅僅是表觀上的，但無關的信息不包括在其中。例如在國際象棋里，我們必須知道棋子在棋盤上的位置(表觀上的信息)，而且需要知道一些不可見的信息——現在是誰在走，每方是否還有易位權，哪個過路兵可以吃，從吃子或進兵到現在一共走了多少步。我們還需要知道以前發生過哪些重復的局面(因為三次重復局面即導致和棋)，而不需要知道以前所有的著法。
【在網絡通訊中常常用一種稱為FEN串的6段式代碼來記錄局面，在國際象棋中它的6段代碼依次為：棋盤、走子方、王車易位權、吃過路兵的目標格、可逆著法數以及總回合數，基本上涵蓋了國際象棋某個局面的所有信息。但是FEN字符串無法記錄重復局面，因此UCI協議中規定，局面由棋局的最后一個不可逆局面(發生吃子、進兵或升變的局面)和它的后續著法共同表示，這樣就涵蓋了重復局面的信息。】
舉例說明國際象棋中的諸多棋盤表示方法
國際象棋中有很多表示棋盤的方法，以下這些是程序中可能用到的：
一、棋盤格子的8x8數組
每個格子的值代表格子中的棋子(例如：enum { empty, wK, wN, wB, wR, wQ, wP, bK, bN, bR, bQ, bP })。它的優點在于：(1) 簡單；(2) 容易計算子力價值：
for (i = 0; i < 8; i ++)
for( j = 0; j < 8; j ++)
score += value[square[i, j]];
計算可能的著法有些麻煩但并不非常困難，可以找遍棋盤的每個格子，根據棋子的顏色和類型來做分枝：
for (i = 0; i < 8; i++) {
for(j = 0; j < 8; j++) {
switch (board[i, j]) {
case wP:
if (board[i + 1, j] = empty) {
生成到(i + 1, j)的著法;
}
if (i == 2 && board[i + 1, j] == empty && board[i + 2, j] empty) {
生成到(i + 2, j)的著法;
}
if (j > 0 && board[i + 1, j - 1]有黑子) {
生成吃(i + 1, j - 1)子的著法;
}
if (j < 7 && board[i + 1, j + 1]有黑子) {
生成吃(i + 1, j + 1)子的著法;
}
break;
...
}
}
}
但是很多檢測邊界的判斷(例如，兵在車一路就不能吃更外側的子)，使得代碼非常復雜，速度非常緩慢。
二、擴展數組
包括擴展邊界的10x10數組，在棋子類型中應包括“boundary”這個值。這樣就可以花很少的代價，來簡化一些判斷。【在下面提到的0x88方法問世以前，最普遍的做法卻是用12x12的數組(即有雙重的擴展邊界)，這樣連馬的著法也不用擔心跳出棋盤了。】
三、0x88
這個名稱來自一個技巧——通過判斷格子編碼是否包含136這個數(在16進制中是0x88)來檢測著法是否合理。下表就是格子的編碼(用一個字節)，高4位表示行，低4位表示列。
-
| 120 |
121 |
122 |
123 |
124 |
125 |
126 |
127 |
| 96 |
97 |
98 |
99 |
100 |
101 |
102 |
103 |
| 80 |
81 |
82 |
83 |
84 |
85 |
86 |
87 |
| 64 |
65 |
66 |
67 |
68 |
69 |
70 |
71 |
| 48 |
49 |
50 |
51 |
52 |
53 |
54 |
55 |
| 32 |
33 |
34 |
35 |
36 |
37 |
38 |
39 |
| 16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
-
- 這樣，格子i的左邊一格是i - 1，右邊是i + 1，上邊是i + 16，下邊是i - 16，等等。棋盤被表示為128個格子的數組(其中64格代表棋盤上存在的格子)，這種表示的優勢在于：(1) 數組僅用1個指標，這樣寫的程序要比用2個指標快；(2) 可以快速簡單地判斷某個格子i是否在棋盤上——當且僅當(i & 0x88) == 0時i在棋盤上。(因為列超出范圍時i & 0x08不為零，而行超出范圍時i & 0x80不為零。)這是一個非常有效而且常用的技巧。
-
- 四、位棋盤
- 我必須在這里多花些筆墨，因為這個技術還不被人所熟悉，但是我認為它可能會很好用的。以前用一個格子數組，每個元素含有一個棋子，現在取而代之的是一個棋子數組，每個元素代表棋盤上哪幾個格子有這個棋子，按位壓縮表示。由于棋盤上有64個格子，所以棋盤可以壓縮成一個64位的字(即兩個32位的字)。這種表示最大的優勢在于，可以通過布爾操作(位操作)來加快局面評估和著法生成操作的速度。試想一下，如此煩瑣的事情可以用壓縮的字運算來解決，例如下面的局面：
-
-
- 白方的兵(這個64位數字記作wP)應該由這些位構成：
-
- 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0
- 0 0 0 0 0 1 0 0
- 0 0 0 0 0 1 0 0
- 0 0 0 0 1 0 0 0
- 0 0 0 0 0 0 0 0
- 1 1 1 0 0 0 0 1
- 0 0 0 0 0 0 0 0
-
- 而被黑方占據的格子可以用下面的公式來計算：
-
- bOcc = bP | bN | bB | bR | bQ | bK
-
- (這里bP等等代表黑方不同兵種的棋子)，類似地可以計算白方占據的格子，還可以把這兩個格子作“或”運算得到所有被占的格子。這些白兵前進一格可能到達的格子，可以用下面的公式計算：
-
- single_pawn_moves = (wP << 8) & ~occupied
-
- 現在仔細看一下過程，先將wP左移8位，來產生每個兵前面的格子：
-
- 0 0 0 0 0 0 0 0
- 0 0 0 0 0 1 0 0
- 0 0 0 0 0 1 0 0
- 0 0 0 0 1 0 0 0
- 0 0 0 0 0 0 0 0
- 1 1 1 0 0 0 0 1
- 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0
-
- 然后求被占格子的“非”運算得到空的格子：
-
- 0 0 1 1 0 0 1 0
- 1 0 1 0 1 0 0 0
- 1 1 1 0 0 0 1 1
- 1 0 1 1 1 0 1 1
- 1 0 1 1 0 1 1 1
- 1 0 1 1 1 0 1 1
- 0 0 0 1 1 1 1 0
- 0 1 0 1 0 0 1 0
-
- 對以上兩個位棋盤按位作“與”運算，就得到這些兵前面的沒有被占的格子了：
-
- 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0
- 0 0 0 0 1 0 0 0
- 0 0 0 0 0 0 0 0
- 1 0 1 0 0 0 0 1
- 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0
-
- 參照兵走一格的方法，可以找到兵走兩格的著法，即再左移8位，“與”上沒有子的格子，再“與”上一個只有第四行都占滿的常數棋盤(這是兵走兩格能到達的唯一一行)：
-
- 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0
- 1 1 1 1 1 1 1 1
- 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0
-
- 值得注意的是，這個常數棋盤是在編譯的時候生成的，而不需要在每次著法生成的時候再計算出來。兵吃子的情況也類似，先左移7位或9位，再“與”上一個常數棋盤以過濾左邊線或右邊線的格子【對于左移7位產生吃右邊子時，需要考慮子在右邊線的情況，此時左移7位是同一行的左邊線，因此需要排除這個格子，即“與”上一個常數棋盤，代表除左邊線以外的所有格子】，最后“與”上bOcc【前面提到過這個棋盤，代表黑子所占的格子】。
- 位棋盤這個技術不能簡化代碼，但是它能一次就產生兵的所有著法，而不是一次只產生一個著法。此外，這個過程中有些表達式需要多次反復使用(例如bOcc)，但只要計算一次就可以了。因此，位棋盤最終變得非常高效，在棋子數比國際象棋少的棋類中，我想位棋盤的效果會更好。
- 有個復雜的問題產生了：計算位棋盤中有多少非零位，或者找到【最低或最高的】一個非零位(例如把兵可以到達的位棋盤轉化為一系列著法)，這些操作往往非常重要。計算位數的操作可以一次計算一個字節，做一個長度為256的數組，每個元素代表它的指標所含有多少個非零位，然后通過查表來完成。在找到一個非零位的計算中有個技巧：x ^ (x - 1)(“^”代表異或)，會得到一個二進制為...000111...的數，x ^ (x - 1)的第一位就是x的最后一位非零位。如果要求得這個數字【x ^ (x - 1)，即型如...000111...的數】的第一位，就把它對某個特定的數M取余數(不同的...000111...這樣的數對M取余數必須不同)，然后去查表。例如，以下的代碼可以找到一個字節的最后一個非零位：
-
- int T = { -1, 0, 7, 1, 3, -1, 6, 2, 5, 4, -1, -1 };
- int last_bit(unsigned char b) {
- return T[(b^(b-1)) % 11];
- }
-
- 【把原作者提到的這個技巧擴展到16位或32位的情況，不妨可以試探一下(只要找得到合適的除數即可)。但是原作者沒有充分考慮計算機的運算特點，因此譯者認為這不是一個合理的設計。由于“電腦一做除法就成了傻瓜”，所以代碼中取余數的過程嚴重影響了效率，為此譯者收集了一些使用炫技的程序，可以迅速完成求位數和查找位的操作。
- (1) 求一個32位數中有幾位非零位的運算——Count32操作：
-
- int Count32(unsigned long Arg) {
- Arg = ((Arg >> 1) & 0x55555555) + (Arg & 0x55555555);
- Arg = ((Arg >> 2) & 0x33333333) + (Arg & 0x33333333);
- Arg = ((Arg >> 4) & 0x0f0f0f0f) + (Arg & 0x0f0f0f0f);
- Arg = ((Arg >> 8) & 0x00ff00ff) + (Arg & 0x00ff00ff);
- return (Arg >> 16) + (Arg & 0x0000ffff);
- }
-
- (2) 求最低位非零位是第幾位的運算——Lsb32操作(LSB = Least Significant Bit)：
-
- int Lsb32(unsigned long Arg) {
- int RetVal = 31;
- if (Arg & 0x0000ffff) { RetVal -= 16; Arg &= 0x0000ffff; }
- if (Arg & 0x00ff00ff) { RetVal -= 8; Arg &= 0x00ff00ff; }
- if (Arg & 0x0f0f0f0f) { RetVal -= 4; Arg &= 0x0f0f0f0f; }
- if (Arg & 0x33333333) { RetVal -= 2; Arg &= 0x33333333; }
- if (Arg & 0x55555555) RetVal -=1;
- return RetVal;
- }
-
- (3) 求最高位非零位是第幾位的運算——Msb32操作(MSB = Most Significant Bit)：
-
- int Msb32(unsigned long Arg) {
- int RetVal = 0;
- if (Arg & 0xffff0000) { RetVal += 16; Arg &= 0xffff0000; }
- if (Arg & 0xff00ff00) { RetVal += 8; Arg &= 0xff00ff00; }
- if (Arg & 0xf0f0f0f0) { RetVal += 4; Arg &= 0xf0f0f0f0; }
- if (Arg & 0xcccccccc) { RetVal += 2; Arg &= 0xcccccccc; }
- if (Arg & 0xaaaaaaaa) RetVal += 1;
- return RetVal;
- }
-
- 對64位數字進行操作，把它分解成兩個32位字，分別對兩個字調用上面的函數就可以了。如果程序能運行在64位的處理器上，只要對上面三個函數略加改動就可以了?！?/font>
-
- 如何撤消著法？
-
- 還記得嗎？我們說過在棋盤表示方法中需要涉及撤消著法的操作?，F在有兩種解決方案：(1) 用一個堆棧來保存棋盤，執行一個著法前先將棋盤壓入堆棧，撤消著法就從堆棧彈出棋盤，恐怕這太慢了…… (2) 用一個堆棧來保存著法，執行一個著法前先將該著法及其相關信息壓入堆棧，撤消著法就根據該著法還原棋盤及其相關信息。例如，在國際象棋中只要保存被吃的棋子(如果吃子的話)，以及王車易位和吃過路兵的權利等信息。
-
- 重復檢測
-
- 某些棋類在發生重復局面時要用到特殊的規則，如圍棋和國際象棋(在國際象棋中，第三次出現重復局面時，制造重復局面的一方就有權宣布和棋)。那么如何知道是否出現重復局面呢？答案很簡單：用散列函數把局面轉換成一個相當大的數(我們以后要談到這個問題，因為這個技術還可以加快搜索速度)，然后保存一系列前面出現過的局面的散列值，從這些值里面找就是了。一個典型的散列函數，先隨機產生一張64x13的表，如果棋子y在位置x上，就把表中[x, y]這個數加到散列值上(忽略溢出)[即Zobrist值]。值得注意的是，當棋子y從位置x走到位置z時，可以快速地更新散列值：減去[x, y]并加上[z, y]即可。
|