【文章內(nèi)容簡介】 于諸如 knight[90]這樣不變化的位棋盤的初始化，將在 “偽著法生成 ”章節(jié)詳述。此處敘述走棋過程中隨棋局變化的諸多位棋盤的初始化及相關(guān)操作。 首先，初始化 “BitBoard bitMask[90]”數(shù)組： BitBoard b = new BitBoard(0,0,1)。 for (int c = 0。 c 90。 c ++) { mask[c] = (b,c)。 } 其次，用一個叫 ChessPosition 類記錄棋盤上某一狀態(tài)的所有有用信息。它包含了一個整型數(shù)組 int piece_in_square[90]，還包含了一些位棋盤。 public class ChessPosition { int piece_in_square[90]。 北京物資學(xué)院 2020屆畢業(yè)論文（設(shè)計） 8 int player。 //輪到哪方走棋， 2：紅方走， 1：黑方走 BitBoard allPieces。 BitBoard redKing。//紅帥 BitBoard blackKing。//黑將 BitBoard redRooks。//紅車 BitBoard blackRooks。//黑車 BitBoard redKnights。//紅馬 BitBoard blackKnights。//黑馬 BitBoard redCannon。//紅炮 BitBoard redCannon。//黑炮 BitBoard redBishops。//紅相 BitBoard blackBishops。//黑象 BitBoard redAdvisor。//紅仕 BitBoard blackAdvisor。//黑士 BitBoard redPawns。//紅兵 BitBoard blackPawns。//黑卒 BitBoard redPieces。//所有紅棋子 BitBoard blackPieces。//所有黑棋子 }。 初始化 “piece_in_square[]”數(shù)組。 piece_in_square[0] = RED_ROOK。 piece_in_square[1] = RED_KNIGHT。 piece_in_square[2] = RED_BISHOP。 … piece_in_square[89] = BLACK_ROOK。 現(xiàn)在初始化其他一些位棋盤 : for (c = 0。 c 90。 c ++) { switch (piece_in_square[c]) { case : RED_ROOK = (,bitMask[c])。 (,bitMask[c])。 break。 … } } 位棋盤的更新 當(dāng)棋盤局面變動后，某些位棋盤就需要被更新。例如記錄白子所在位置的“WhitePieces”位棋盤。假如我們把 h2 格的紅炮移動到 h9 格（炮二進(jìn)七），吃掉黑棋的一個馬，需要更新如下位棋盤： allPieces 北京物資學(xué)院 2020屆畢業(yè)論文（設(shè)計） 9 redPieces redCannons blackpieces blackKnights 首先，要把 redPieces， redCannons 位棋盤的 “h2”位清零，然后把他們的 “h9”位置 1。 /* clear a bit with the XOR operation */ = (,bitMask[h2]。 = (,bitMask[h2])。 = (,bitMask[h2]。 /* set a bit with the OR operation */ = (,bitMask[h9])。 = (,bitMask[h9])。 現(xiàn)在我們要將 blackPieces 和 blackKnights 位棋盤的 h9 位清除，因為那里的黑馬被吃掉了。 /* clear the captured piece */ = (,bitMask[h9])。 = (,bitMask[h9] —— Zobrist 鍵值 比較局面的方法 在寫中國象棋程序時，需要比較兩個局面看它們是否相同。如果比較每個棋子的位置，或許不需要花很多時間，但是實戰(zhàn)中每秒種需要做成千上萬次比較，因此這樣會使比較操作變成瓶頸的。另外，需要比較的局面數(shù)量多得驚人，要存儲每個棋子的位置，需要占用非常大的空間。 一個解決方案是建立一個標(biāo)簽，通常是 64 位。由于 64 位不足以區(qū)別每個局面，所以仍然存在沖突的標(biāo)簽 ， 但實戰(zhàn)中這種情況非常罕見 。 Zobrist 鍵值的工作原理 Zobrist 鍵值的工作原理 用 Zobrist 技術(shù)產(chǎn)生的鍵 值，表面上與局面沒什么關(guān)系。如果一個棋子動過了，就會得到完全不同的鍵值，所以這兩個鍵值不會擠在一塊兒或者沖突。當(dāng)把它們用作散列表鍵值的時候會非常有效。 另一個優(yōu)點在于，鍵值的產(chǎn)生是可以逐步進(jìn)行的。例如，紅馬在 e5 格，那么鍵值里一定異或過一個 “zobrist[KNIGHT][RED][E5]”。如果再次異或這個值，那么根據(jù)異或的工作原理，這個 “馬 ”就從鍵值里刪除了。 北京物資學(xué)院 2020屆畢業(yè)論文（設(shè)計） 10 這就是說，如果有當(dāng)前局面的鍵值，并且需要把紅馬從 e5 移到 f7，你只要異或一個 “紅馬在 e5”的鍵值，把馬從 e5 格移走，并且異或一個 “紅 馬在 f7”的鍵值，把紅馬放在 f7 上。比起從頭開始一個個棋子去異或，這樣做可以得到同樣的鍵值。 如果要改變著子的一方，只要異或一個 “改變著子方 ”的鍵值就可以了。用這種方法，可以在搜索根結(jié)點的時候構(gòu)造一個 Zobrist 鍵值，在搜索時通過走子函數(shù)“MakeMove()”來更新鍵值，一直讓它保持和當(dāng)前局面同步。 Zobrist 鍵值的實現(xiàn)方法 實現(xiàn) Zobrist 必須從多維的 64 位數(shù)組開始，每個數(shù)組含有一個隨機數(shù)。在 Java中， “()”函數(shù)返回一個 64 位的隨機數(shù)值。 這個 函數(shù)用來填滿一個 long 型（ 64 位）的三維數(shù)組：棋子的類型、棋子的顏色和棋子的位置： long zobrist[pcMAX][coMAX][sqMAX]。 程序啟動時就把這個數(shù)組用隨機數(shù)填滿。要為一個局面產(chǎn)生 Zobrist 鍵值，首先把鍵值設(shè)成零，然后找棋盤上的每個子，并且讓鍵值跟 “zobrist[pc][co][sq]”做異或 (通過 “^”運算符 )運算。 如果局面由紅 方走，那么別去動它，如果是黑方走，你還要在鍵值上異或一個 64 位的隨機常數(shù)。 Java 中 實現(xiàn) Zobrist 鍵值 本系統(tǒng)使用 一個 key 和一個 lock 結(jié)合來區(qū)分每個局面，這 樣 發(fā)生沖突（即兩個局面對應(yīng)的 key 和 lock 一樣）的概率幾乎為 0。示例代碼及相關(guān)說明如下 填充數(shù)組 上述的三維數(shù)組現(xiàn)在改變?yōu)槎S（將顏色與棋子兵種類型合并） …… public static long ZobristKeyPlayer。//改變走子方的 key public static long ZobristLockPlayer。//改變走子方的 lock public static long[][] ZobristKeyTable = new long[14][90]。 public static long[][] ZobristLockTable = new long[14][90]。 …… static{ …… zobristGen()。 } public static void zobristGen() { int i, j。 Random rand = new Random()。 long RandSeed。 RandSeed = 1。 (RandSeed)。 北京物資學(xué)院 2020屆畢業(yè)論文（設(shè)計） 11 ZobristKeyPlayer = ()。 for (i = 0。 i 14。 i ++) { //0：紅帥 1：紅仕 2：紅相 3：紅馬 4：紅車 5：紅炮 6：紅兵 //7：黑將 8：黑士 9：黑象 10：黑馬 11：黑車 12：黑炮 13：黑卒 for (j = 0。 j 90。 j ++) { ZobristKeyTable[i][j] = ()。 } } ZobristLockPlayer = ()。 for (i = 0。 i 14。 i ++) { for (j = 0。 j 90。 j ++) { ZobristLockTable[i][j] = ()。 } } } 移子函數(shù) 當(dāng)移動（添加、刪除）一個棋子時，將當(dāng)前局面的 Zobrist 鍵值與鍵值表中該棋子的鍵值進(jìn)行異或操作，同時也與改變走子方的鍵值進(jìn)行異或操作。 public class ChessPosition{ long ZobristKey, ZobristLock。 //當(dāng)前局面的 zobrist 鍵值 public ChessPosition{ …… ZobristKey=0。//初始化為 0 ZobristLock=0。 …… } …… public void makeMove(int Square, int Piece, boolean IsAdd) { …… ZobristKey^=ZobristKeyTable[PieceType][Square]。 ZobristLock^=ZobristLockTable[PieceType][Square]。 ZobristKey ^= ZobristKeyPlayer。//改變走子方 ZobristLock ^= ZobristLockPlayer。 …… } } 北京物資學(xué)院 2020屆畢業(yè)論文（設(shè)計） 12 4 系統(tǒng)實現(xiàn) 著法生成 著法生成在不同的象棋引擎中差異較大。 我選擇 使用位棋盤生成著法的基本原理。 之所以 用這種方式生成著法 ， 是 因為 生成著法耗費一定的時間。如果引擎在檢查了一部分著法后發(fā)現(xiàn)了必須走的棋，那它就無需生成余下的棋步了。因此，可能先生成所有吃子的著法，如果沒有滿意的棋再生成余下的著法。 國際象棋引擎 Crafty(其作者是 Robert Hyatt 博士 )使用三個著法生成函數(shù)。一個用來生成所有偽合法吃子著法，一個生成所有偽合法不吃子著法，最后一個生成所有擺脫被將軍狀態(tài)的著法。注意前兩個函數(shù)生成的是偽合法的著法。中國象棋的著法生成與此類似，先生成所有偽合法的著法，存入靜態(tài)數(shù)組中。在對局中可以用 “查表 ”的方式查找生成的偽著法，并對其合法性作出判斷。這樣可以節(jié)省大量的時間。 偽合法著法的生成 偽合法著法包含幾類： 各兵種的不吃子著法 ； 各兵種的吃子著法 ； “將 ”和擺脫 “將 ”的著法 。 其中，馬、相（象）、兵、帥（將）、仕（士）的吃子著法與其對應(yīng)的不吃子著法規(guī)則相同。（偽合法著法并不考慮被吃的棋子的顏色 ——該棋子是對方的棋子 還是己方的棋子，也不考慮該子是否能動，例如動了該子，雙方的帥將會面。）炮和車的不吃子著法規(guī)則相同，但分為縱向橫向行走兩類。炮的吃子著法分為縱向和橫向兩類，車的吃子著法也分為縱向和橫向兩類。馬和象的著法要考慮蹩馬腿和塞象眼。將軍的著法單獨作為一類。 本程序使用靜態(tài)數(shù)組存儲生成的偽 合法著法，先對其作一些說明。 數(shù)組及其下標(biāo)的含義 ： 保存帥（將）、仕（士）、相（相）、馬、兵的偽合法靜態(tài)數(shù)組如下： public static final int[][] KingMoves=new int[90][8]。 public static final int[][] AdvisorMoves=new int[90][8]。 public static final int[][] BishopMoves=new int[90][8]。 public static final int[][] ElephantEyes=new int[90][4]。 public static final int[][] KnightMoves=new int[90][12]。 public static final int[][] HorseLegs=new int[90][8]。 public static final int[][][] PawnMoves=new int[90][2][4]。 北京物資學(xué)院 2020屆畢業(yè)論文（設(shè)計） 13 第一個下標(biāo)說明棋子所在的格，第二個下標(biāo)含義不盡相同。帥（將）在某個位置最多有 4 種走法，例如 KingMoves[13][0]=12 表示帥在 13 格（ e1 格）時可以走到 12 格（當(dāng)然，也可以走到 1 22 格，保存到其他幾個數(shù)組元素中）。第 5種（如果前面只有 3 種著法，則此處是第 4 種）保存的是非法著法即KingMoves[13][4]=1，其作用作為查詢算法的 “哨兵 ”，提高查詢算法的速度。為了速度（以位移運算取代除法運