【文章內(nèi)容簡介】 于諸如 knight[90]這樣不變化的位棋盤的初始化，將在 “偽著法生成 ”章節(jié)詳述。此處敘述走棋過程中隨棋局變化的諸多位棋盤的初始化及相關操作。 首先，初始化 “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]。 北京物資學院 2020屆畢業(yè)論文（設計） 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。 … } } 位棋盤的更新 當棋盤局面變動后，某些位棋盤就需要被更新。例如記錄白子所在位置的“WhitePieces”位棋盤。假如我們把 h2 格的紅炮移動到 h9 格（炮二進七），吃掉黑棋的一個馬，需要更新如下位棋盤： allPieces 北京物資學院 2020屆畢業(yè)論文（設計） 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ù)量多得驚人，要存儲每個棋子的位置，需要占用非常大的空間。 一個解決方案是建立一個標簽，通常是 64 位。由于 64 位不足以區(qū)別每個局面，所以仍然存在沖突的標簽 ， 但實戰(zhàn)中這種情況非常罕見 。 Zobrist 鍵值的工作原理 Zobrist 鍵值的工作原理 用 Zobrist 技術產(chǎn)生的鍵 值，表面上與局面沒什么關系。如果一個棋子動過了，就會得到完全不同的鍵值，所以這兩個鍵值不會擠在一塊兒或者沖突。當把它們用作散列表鍵值的時候會非常有效。 另一個優(yōu)點在于，鍵值的產(chǎn)生是可以逐步進行的。例如，紅馬在 e5 格，那么鍵值里一定異或過一個 “zobrist[KNIGHT][RED][E5]”。如果再次異或這個值，那么根據(jù)異或的工作原理，這個 “馬 ”就從鍵值里刪除了。 北京物資學院 2020屆畢業(yè)論文（設計） 10 這就是說，如果有當前局面的鍵值，并且需要把紅馬從 e5 移到 f7，你只要異或一個 “紅馬在 e5”的鍵值，把馬從 e5 格移走，并且異或一個 “紅 馬在 f7”的鍵值，把紅馬放在 f7 上。比起從頭開始一個個棋子去異或，這樣做可以得到同樣的鍵值。 如果要改變著子的一方，只要異或一個 “改變著子方 ”的鍵值就可以了。用這種方法，可以在搜索根結點的時候構造一個 Zobrist 鍵值，在搜索時通過走子函數(shù)“MakeMove()”來更新鍵值，一直讓它保持和當前局面同步。 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 鍵值，首先把鍵值設成零，然后找棋盤上的每個子，并且讓鍵值跟 “zobrist[pc][co][sq]”做異或 (通過 “^”運算符 )運算。 如果局面由紅 方走，那么別去動它，如果是黑方走，你還要在鍵值上異或一個 64 位的隨機常數(shù)。 Java 中 實現(xiàn) Zobrist 鍵值 本系統(tǒng)使用 一個 key 和一個 lock 結合來區(qū)分每個局面，這 樣 發(fā)生沖突（即兩個局面對應的 key 和 lock 一樣）的概率幾乎為 0。示例代碼及相關說明如下 填充數(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)。 北京物資學院 2020屆畢業(yè)論文（設計） 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ù) 當移動（添加、刪除）一個棋子時，將當前局面的 Zobrist 鍵值與鍵值表中該棋子的鍵值進行異或操作，同時也與改變走子方的鍵值進行異或操作。 public class ChessPosition{ long ZobristKey, ZobristLock。 //當前局面的 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。 …… } } 北京物資學院 2020屆畢業(yè)論文（設計） 12 4 系統(tǒng)實現(xiàn) 著法生成 著法生成在不同的象棋引擎中差異較大。 我選擇 使用位棋盤生成著法的基本原理。 之所以 用這種方式生成著法 ， 是 因為 生成著法耗費一定的時間。如果引擎在檢查了一部分著法后發(fā)現(xiàn)了必須走的棋，那它就無需生成余下的棋步了。因此，可能先生成所有吃子的著法，如果沒有滿意的棋再生成余下的著法。 國際象棋引擎 Crafty(其作者是 Robert Hyatt 博士 )使用三個著法生成函數(shù)。一個用來生成所有偽合法吃子著法，一個生成所有偽合法不吃子著法，最后一個生成所有擺脫被將軍狀態(tài)的著法。注意前兩個函數(shù)生成的是偽合法的著法。中國象棋的著法生成與此類似，先生成所有偽合法的著法，存入靜態(tài)數(shù)組中。在對局中可以用 “查表 ”的方式查找生成的偽著法，并對其合法性作出判斷。這樣可以節(jié)省大量的時間。 偽合法著法的生成 偽合法著法包含幾類： 各兵種的不吃子著法 ； 各兵種的吃子著法 ； “將 ”和擺脫 “將 ”的著法 。 其中，馬、相（象）、兵、帥（將）、仕（士）的吃子著法與其對應的不吃子著法規(guī)則相同。（偽合法著法并不考慮被吃的棋子的顏色 ——該棋子是對方的棋子 還是己方的棋子，也不考慮該子是否能動，例如動了該子，雙方的帥將會面。）炮和車的不吃子著法規(guī)則相同，但分為縱向橫向行走兩類。炮的吃子著法分為縱向和橫向兩類，車的吃子著法也分為縱向和橫向兩類。馬和象的著法要考慮蹩馬腿和塞象眼。將軍的著法單獨作為一類。 本程序使用靜態(tài)數(shù)組存儲生成的偽 合法著法，先對其作一些說明。 數(shù)組及其下標的含義 ： 保存帥（將）、仕（士）、相（相）、馬、兵的偽合法靜態(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]。 北京物資學院 2020屆畢業(yè)論文（設計） 13 第一個下標說明棋子所在的格，第二個下標含義不盡相同。帥（將）在某個位置最多有 4 種走法，例如 KingMoves[13][0]=12 表示帥在 13 格（ e1 格）時可以走到 12 格（當然，也可以走到 1 22 格，保存到其他幾個數(shù)組元素中）。第 5種（如果前面只有 3 種著法，則此處是第 4 種）保存的是非法著法即KingMoves[13][4]=1，其作用作為查詢算法的 “哨兵 ”，提高查詢算法的速度。為了速度（以位移運算取代除法運