|
|
棋盤的表示
David Eppstein */文
* 加州愛爾文大學(xué)(UC Irvine)信息與計(jì)算機(jī)科學(xué)系
要讓機(jī)器下棋，程序首先必須對兩個(gè)對象進(jìn)行存儲(chǔ)和操作，它們是局面和著法。這兩個(gè)對象的表示使得程序可以進(jìn)行下列操作：
(1) 執(zhí)行一個(gè)著法(不僅僅是用戶所指出的著法，而是在搜索過程中要用到的)；
(2) 撤消一個(gè)著法(作用同上)；
(3) 向用戶顯示棋盤；
(4) 產(chǎn)生所有可能的著法；
(5) 對棋盤的局面作出評(píng)估。
除了顯示棋盤以外，所有的操作都應(yīng)該盡可能地迅速，因?yàn)樗鼈儠?huì)在搜索的循環(huán)內(nèi)被調(diào)用。(而顯示棋盤的操作畢竟不是經(jīng)常要做的。【譯注：在UCI協(xié)議(國際象棋通用引擎協(xié)議)中，引擎從不顯示棋盤，因此這個(gè)操作事實(shí)上是多余的。】)
著法的內(nèi)部表示應(yīng)該是非常簡潔的(因?yàn)槲覀儾恍枰ㄌ嗟臅r(shí)間來生成一系列著法)而且能快速解讀，但是非常重要的是，它應(yīng)該能代表所有的著法！在國際象棋中，機(jī)器內(nèi)典型的著法表示，就是記錄移動(dòng)棋子的起點(diǎn)格子和終點(diǎn)格子，例如王前兵進(jìn)兩格就表示為“e2e4”(e2代表這個(gè)兵起點(diǎn)位置而e4代表終點(diǎn)位置)。不管是否吃子，被吃的棋子都不必記錄，因?yàn)樗梢杂山K點(diǎn)格子來判斷。在機(jī)器中位置能表示為6位的數(shù)值，所以一個(gè)著法可以用2個(gè)字節(jié)表示。盡管很多程序都是這樣表示的，但是這種表示方法不足以表示所有的著法！王車易位時(shí)，有兩個(gè)子要移動(dòng)，此時(shí)我們把它當(dāng)作特殊情況來考慮，只記錄王的移動(dòng)。問題在于，當(dāng)兵從第七行走到第八行時(shí)，可以升變?yōu)楹蟆④嚒ⅠR或象，上述表示方法不能讓我們指定升變?yōu)槟膫€(gè)棋子。因此在設(shè)計(jì)著法表示時(shí)需要非常仔細(xì)，要確認(rèn)這種表示能夠涵蓋棋局中所有可能發(fā)生的特殊情況。
【一般而言，棋類的著法有兩種形式，即添子式和移動(dòng)式。五子棋、圍棋、黑白棋等屬于添子式，記錄著法時(shí)只要記錄棋子所下到的那個(gè)格子。其中五子棋最簡單，下完的棋子不再會(huì)改變；黑白棋稍復(fù)雜些，下完的棋子可能會(huì)被后續(xù)著法所變換黑白，但每下一子棋盤上就多一子；圍棋是最復(fù)雜的，由于存在提子的著法，所以局勢是可逆的，打劫這樣的著法需要很復(fù)雜的處理過程。
國際象棋和中國象棋都屬于移動(dòng)式，相比較而言中國象棋更簡單，當(dāng)一個(gè)棋子從起點(diǎn)移到終點(diǎn)時(shí)，只要簡單地做一下終點(diǎn)的覆蓋即可；而國際象棋由于三條特殊規(guī)則的存在而必須做特別處理，有時(shí)別的特殊位置的棋子要跟著移動(dòng)(王車易位)，有時(shí)別的特殊位置的子要被吃掉(吃過路兵)，有時(shí)移動(dòng)的棋子要被其他棋子所替代(升變)。】
棋盤的表示可能稍許復(fù)雜了些，但也不應(yīng)該太龐大。它必須包括所有相關(guān)的信息，而不僅僅是表觀上的，但無關(guān)的信息不包括在其中。例如在國際象棋里，我們必須知道棋子在棋盤上的位置(表觀上的信息)，而且需要知道一些不可見的信息——現(xiàn)在是誰在走，每方是否還有易位權(quán)，哪個(gè)過路兵可以吃，從吃子或進(jìn)兵到現(xiàn)在一共走了多少步。我們還需要知道以前發(fā)生過哪些重復(fù)的局面(因?yàn)槿沃貜?fù)局面即導(dǎo)致和棋)，而不需要知道以前所有的著法。
【在網(wǎng)絡(luò)通訊中常常用一種稱為FEN串的6段式代碼來記錄局面，在國際象棋中它的6段代碼依次為：棋盤、走子方、王車易位權(quán)、吃過路兵的目標(biāo)格、可逆著法數(shù)以及總回合數(shù)，基本上涵蓋了國際象棋某個(gè)局面的所有信息。但是FEN字符串無法記錄重復(fù)局面，因此UCI協(xié)議中規(guī)定，局面由棋局的最后一個(gè)不可逆局面(發(fā)生吃子、進(jìn)兵或升變的局面)和它的后續(xù)著法共同表示，這樣就涵蓋了重復(fù)局面的信息。】
舉例說明國際象棋中的諸多棋盤表示方法
國際象棋中有很多表示棋盤的方法，以下這些是程序中可能用到的：
一、棋盤格子的8x8數(shù)組
每個(gè)格子的值代表格子中的棋子(例如：enum { empty, wK, wN, wB, wR, wQ, wP, bK, bN, bR, bQ, bP })。它的優(yōu)點(diǎn)在于：(1) 簡單；(2) 容易計(jì)算子力價(jià)值：
for (i = 0; i < 8; i ++)
for( j = 0; j < 8; j ++)
score += value[square[i, j]];
計(jì)算可能的著法有些麻煩但并不非常困難，可以找遍棋盤的每個(gè)格子，根據(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;
...
}
}
}
但是很多檢測邊界的判斷(例如，兵在車一路就不能吃更外側(cè)的子)，使得代碼非常復(fù)雜，速度非常緩慢。
二、擴(kuò)展數(shù)組
包括擴(kuò)展邊界的10x10數(shù)組，在棋子類型中應(yīng)包括“boundary”這個(gè)值。這樣就可以花很少的代價(jià)，來簡化一些判斷。【在下面提到的0x88方法問世以前，最普遍的做法卻是用12x12的數(shù)組(即有雙重的擴(kuò)展邊界)，這樣連馬的著法也不用擔(dān)心跳出棋盤了。】
三、0x88
這個(gè)名稱來自一個(gè)技巧——通過判斷格子編碼是否包含136這個(gè)數(shù)(在16進(jìn)制中是0x88)來檢測著法是否合理。下表就是格子的編碼(用一個(gè)字節(jié))，高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個(gè)格子的數(shù)組(其中64格代表棋盤上存在的格子)，這種表示的優(yōu)勢在于：(1) 數(shù)組僅用1個(gè)指標(biāo)，這樣寫的程序要比用2個(gè)指標(biāo)快；(2) 可以快速簡單地判斷某個(gè)格子i是否在棋盤上——當(dāng)且僅當(dāng)(i & 0x88) == 0時(shí)i在棋盤上。(因?yàn)榱谐龇秶鷷r(shí)i & 0x08不為零，而行超出范圍時(shí)i & 0x80不為零。)這是一個(gè)非常有效而且常用的技巧。
-
- 四、位棋盤
- 我必須在這里多花些筆墨，因?yàn)檫@個(gè)技術(shù)還不被人所熟悉，但是我認(rèn)為它可能會(huì)很好用的。以前用一個(gè)格子數(shù)組，每個(gè)元素含有一個(gè)棋子，現(xiàn)在取而代之的是一個(gè)棋子數(shù)組，每個(gè)元素代表棋盤上哪幾個(gè)格子有這個(gè)棋子，按位壓縮表示。由于棋盤上有64個(gè)格子，所以棋盤可以壓縮成一個(gè)64位的字(即兩個(gè)32位的字)。這種表示最大的優(yōu)勢在于，可以通過布爾操作(位操作)來加快局面評(píng)估和著法生成操作的速度。試想一下，如此煩瑣的事情可以用壓縮的字運(yùn)算來解決，例如下面的局面：
-
-
- 白方的兵(這個(gè)64位數(shù)字記作wP)應(yīng)該由這些位構(gòu)成：
-
- 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
-
- 而被黑方占據(jù)的格子可以用下面的公式來計(jì)算：
-
- bOcc = bP | bN | bB | bR | bQ | bK
-
- (這里bP等等代表黑方不同兵種的棋子)，類似地可以計(jì)算白方占據(jù)的格子，還可以把這兩個(gè)格子作“或”運(yùn)算得到所有被占的格子。這些白兵前進(jìn)一格可能到達(dá)的格子，可以用下面的公式計(jì)算：
-
- single_pawn_moves = (wP << 8) & ~occupied
-
- 現(xiàn)在仔細(xì)看一下過程，先將wP左移8位，來產(chǎn)生每個(gè)兵前面的格子：
-
- 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
-
- 然后求被占格子的“非”運(yùn)算得到空的格子：
-
- 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
-
- 對以上兩個(gè)位棋盤按位作“與”運(yùn)算，就得到這些兵前面的沒有被占的格子了：
-
- 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位，“與”上沒有子的格子，再“與”上一個(gè)只有第四行都占滿的常數(shù)棋盤(這是兵走兩格能到達(dá)的唯一一行)：
-
- 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
-
- 值得注意的是，這個(gè)常數(shù)棋盤是在編譯的時(shí)候生成的，而不需要在每次著法生成的時(shí)候再計(jì)算出來。兵吃子的情況也類似，先左移7位或9位，再“與”上一個(gè)常數(shù)棋盤以過濾左邊線或右邊線的格子【對于左移7位產(chǎn)生吃右邊子時(shí)，需要考慮子在右邊線的情況，此時(shí)左移7位是同一行的左邊線，因此需要排除這個(gè)格子，即“與”上一個(gè)常數(shù)棋盤，代表除左邊線以外的所有格子】，最后“與”上bOcc【前面提到過這個(gè)棋盤，代表黑子所占的格子】。
- 位棋盤這個(gè)技術(shù)不能簡化代碼，但是它能一次就產(chǎn)生兵的所有著法，而不是一次只產(chǎn)生一個(gè)著法。此外，這個(gè)過程中有些表達(dá)式需要多次反復(fù)使用(例如bOcc)，但只要計(jì)算一次就可以了。因此，位棋盤最終變得非常高效，在棋子數(shù)比國際象棋少的棋類中，我想位棋盤的效果會(huì)更好。
- 有個(gè)復(fù)雜的問題產(chǎn)生了：計(jì)算位棋盤中有多少非零位，或者找到【最低或最高的】一個(gè)非零位(例如把兵可以到達(dá)的位棋盤轉(zhuǎn)化為一系列著法)，這些操作往往非常重要。計(jì)算位數(shù)的操作可以一次計(jì)算一個(gè)字節(jié)，做一個(gè)長度為256的數(shù)組，每個(gè)元素代表它的指標(biāo)所含有多少個(gè)非零位，然后通過查表來完成。在找到一個(gè)非零位的計(jì)算中有個(gè)技巧：x ^ (x - 1)(“^”代表異或)，會(huì)得到一個(gè)二進(jìn)制為...000111...的數(shù)，x ^ (x - 1)的第一位就是x的最后一位非零位。如果要求得這個(gè)數(shù)字【x ^ (x - 1)，即型如...000111...的數(shù)】的第一位，就把它對某個(gè)特定的數(shù)M取余數(shù)(不同的...000111...這樣的數(shù)對M取余數(shù)必須不同)，然后去查表。例如，以下的代碼可以找到一個(gè)字節(jié)的最后一個(gè)非零位：
-
- 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];
- }
-
- 【把原作者提到的這個(gè)技巧擴(kuò)展到16位或32位的情況，不妨可以試探一下(只要找得到合適的除數(shù)即可)。但是原作者沒有充分考慮計(jì)算機(jī)的運(yùn)算特點(diǎn)，因此譯者認(rèn)為這不是一個(gè)合理的設(shè)計(jì)。由于“電腦一做除法就成了傻瓜”，所以代碼中取余數(shù)的過程嚴(yán)重影響了效率，為此譯者收集了一些使用炫技的程序，可以迅速完成求位數(shù)和查找位的操作。
- (1) 求一個(gè)32位數(shù)中有幾位非零位的運(yùn)算——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) 求最低位非零位是第幾位的運(yùn)算——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) 求最高位非零位是第幾位的運(yùn)算——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位數(shù)字進(jìn)行操作，把它分解成兩個(gè)32位字，分別對兩個(gè)字調(diào)用上面的函數(shù)就可以了。如果程序能運(yùn)行在64位的處理器上，只要對上面三個(gè)函數(shù)略加改動(dòng)就可以了。】
-
- 如何撤消著法？
-
- 還記得嗎？我們說過在棋盤表示方法中需要涉及撤消著法的操作。現(xiàn)在有兩種解決方案：(1) 用一個(gè)堆棧來保存棋盤，執(zhí)行一個(gè)著法前先將棋盤壓入堆棧，撤消著法就從堆棧彈出棋盤，恐怕這太慢了…… (2) 用一個(gè)堆棧來保存著法，執(zhí)行一個(gè)著法前先將該著法及其相關(guān)信息壓入堆棧，撤消著法就根據(jù)該著法還原棋盤及其相關(guān)信息。例如，在國際象棋中只要保存被吃的棋子(如果吃子的話)，以及王車易位和吃過路兵的權(quán)利等信息。
-
- 重復(fù)檢測
-
- 某些棋類在發(fā)生重復(fù)局面時(shí)要用到特殊的規(guī)則，如圍棋和國際象棋(在國際象棋中，第三次出現(xiàn)重復(fù)局面時(shí)，制造重復(fù)局面的一方就有權(quán)宣布和棋)。那么如何知道是否出現(xiàn)重復(fù)局面呢？答案很簡單：用散列函數(shù)把局面轉(zhuǎn)換成一個(gè)相當(dāng)大的數(shù)(我們以后要談到這個(gè)問題，因?yàn)檫@個(gè)技術(shù)還可以加快搜索速度)，然后保存一系列前面出現(xiàn)過的局面的散列值，從這些值里面找就是了。一個(gè)典型的散列函數(shù)，先隨機(jī)產(chǎn)生一張64x13的表，如果棋子y在位置x上，就把表中[x, y]這個(gè)數(shù)加到散列值上(忽略溢出)[即Zobrist值]。值得注意的是，當(dāng)棋子y從位置x走到位置z時(shí)，可以快速地更新散列值：減去[x, y]并加上[z, y]即可。
|