電腦象棋循序漸進
 
象棋百科全書網 ([email protected]) 20084
 
() 掌握象棋規則
 
  與本文配套的示范程序是“象棋小巫師0.2版,程序清單是:
  (1) XQWL02.CPP——C++源程序;
  (2) XQWLIGHT.RC——資源描述文件;
  (3) RESOURCE.H——資源符號定義文件;
  (4) RES目錄——圖標、圖片、聲音等資源。
 
  在閱讀本章前,建議讀者先閱讀象棋百科全書網計算機博弈專欄的以下幾篇譯文:
  (1) 國際象棋程序設計(一):引言(François Dominic Laramée)
  (2) 國際象棋程序設計(二):數據結構(François Dominic Laramée)
  (3) 國際象棋程序設計(三):著法的產生(François Dominic Laramée)
  (4) 數據結構——簡介(Bruce Moreland)
  (5) 數據結構——0x88著法產生方法(Bruce Moreland)
 
2.1 走法生成器
 
  走法生成器是象棋程序中的一個重要組成部分,它可以解決幾乎所有象棋規則的問題。
  假設我們的棋盤使用9x10的數組,按照常規的做法,找到一個馬的所有走法,這將是一件非常痛苦的事:
 
// 判斷馬的下面一格有沒有子
int yDst = ySrc + 2;
if (yDst <= Y_BOTTOM && ucpcSquares[xSrc][ySrc + 1] == 0) {
 int xDst = xSrc + 1;
 if (xDst <= X_RIGHT && !SELF_PIECE(ucpcSquares[xDst][yDst])) {
  ADD_MOVE(xSrc, ySrc, xDest, yDest);
 }
 xDst = xSrc - 1;
 if (xDst >= X_LEFT && !SELF_PIECE(ucpcSquares[xDst][yDst])) {
  ADD_MOVE(xSrc, ySrc, xDest, yDest);
 }
}
// 判斷馬的上面一格有沒有子
……
 
  不僅代碼數量龐大,運行速度緩慢,而且一不小心就容易寫錯。
  好在我們的棋盤是一個大小為16x16的二維數組,只不過寫在程序里的是 ucpcSquares[256] 而已。
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f
20 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2f
30 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3f
40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f
50 51 52 53 54 55 56 57 58 59 5a 5b 5c 5d 5e 5f
60 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f
70 71 72 73 74 75 76 77 78 79 7a 7b 7c 7d 7e 7f
80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f
90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f
a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 aa ab ac ad ae af
b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf
c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 ca cb cc cd ce cf
d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 da db dc dd de df
e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 ea eb ec ed ee ef
f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 fa fb fc fd fe ff
  上表就是9x10的象棋棋盤在16x16的數組中的位置,我們將在這個棋盤上演繹馬是如何走棋的。
  首先,我們預置一個常量數組 ccInBoard[256],表示哪些格子在棋盤外(紫色格子,填0),哪些格子在棋盤內(淺色格子,填1),所以就沒有必要使用 x >= X_LEFT && x <= X_RIGHT && y >= Y_TOP && y <= Y_BOTTOM 之類的語句了,取而代之的是 ccInBoard[sq] != 0
  其次,一維數組的好就是上下左右關系非常簡明——上面一格是 sq - 16,下面一格是 sq + 16,左面一格是 sq - 1,右面一格是 sq + 1。馬可以跳的點只有8個,終點相對起點的偏移值是固定的:
 
const char ccKnightDelta[4][2] = {{-33, -31}, {-18, 14}, {-14, 18}, {31, 33}};
 
  而對應的馬腿的偏移值是:
 
const char ccKingDelta[4] = {-16, -1, 1, 16};
 
  這個數組之所以命名為 ccKingDelta,是因為它也是帥()的偏移值。
  這樣,找到一個馬的所有走法就容易很多了。首先判斷某個方向上的馬腿是否有子,然后判斷該方向上的兩個走法是否能走:
 
for (i = 0; i < 4; i ++) {
 sqPin = sqSrc + ccKingDelta[i];
 if (IN_BOARD(sqPin) && ucpcSquares[sqPin] == 0) {
  for (j = 0; j < 2; j ++) {
   sqDst = sqSrc + ccKnightDelta[i][j];
   if (IN_BOARD(sqDst) && !SELF_PIECE(ucpcSquares[sqDst])) {
    ADD_MOVE(sqSrc, sqDst);
   }
  }
 }
}
 
  用類似的辦法就可以產生其他棋子的所有走法。
 
2.2 判斷走法是否符合規則
 
  盡管我們已經使用了一些炫技,讓走法生成器盡可能地小巧,但它仍然是象棋程序中最耗費時間的運算模塊。有時候走法生成器真是大材小用了,比如用戶點擊鼠標走一步棋的時候,判斷這步棋是否符合走法規則,就有幾種不同的考慮:
  A. 用走法生成器產生全部走法,看看這些走法中有沒有用戶剛才走出的那步棋,如果沒有就說明用戶在亂走;
  B. 前一種做法中,大部分工作都是白費的,因為用戶只是走了一個棋子,走法生成器沒必要生成其他棋子的走法;
  C. 用戶只走了一步棋,而走法生成器會生成一個棋子的所有走法,是不是太浪費了呢?
 
  判斷一個走法是否合理,有更簡單的方法。依然以馬為例,假設用戶的鼠標動作肯定在棋盤內的,那么判斷過程如下:
  (1) 馬是否走了馬步,即位移是否符合 ccKinghtDelta 中的值;
  (2) 根據馬步,找到對應的馬腿位置,判斷馬腿的格子上是否有棋子。
 
  在象棋小巫師中,我們用了一個 KNIGHT_PIN(sqSrc, sqDst) 的函數來獲取馬腿的位置(如果函數返回 sqSrc,則說明不是馬步)。這樣,判斷馬的某個走法是否符合規則,只需要很簡單的兩句話:
 
sqPin = KNIGHT_PIN(sqSrc, sqDst);
return sqPin != sqSrc && ucpcSquares[sqPin] == 0;
 
2.3 判斷將軍
 
  到現在為止,我們剩下一件事沒有做了,那就是判斷勝負。中國象棋的勝負標準就是帥()有沒有被將死或困斃,我們的做法很簡單——生成所有走法,如果走任意一步都會被將軍,那么該局面就是將死或困斃的局面,棋局到此結束。
  那么如何來判斷是否被將軍呢?我們有兩種做法:
  A. 讓對方生成全部走法,看看其中有沒有走法可以吃掉自己的帥()
  B. 按照判斷走法是否符合規則的思路,采用更簡單的做法。
 
  第一種做法沒有什么不對的,但電腦象棋程序每秒種需要分析上萬個局面,對每個局面都去生成全部走法顯然太花時間了,所以我們要嘗試第二種做法。其實判斷帥()是否被將軍的過程并不復雜:
  (1) 假設帥()是車,判斷它是否能吃到對方的車和將()(中國象棋中有將帥不能對臉的規則)
  (2) 假設帥()是炮,判斷它是否能吃到對方的炮;
  (3) 假設帥()是馬,判斷它是否能吃到對方的馬,需要注意的是,帥()的馬腿用的數組是 ccAdvisorDelta,而不是 ccKingDelta
  (4) 假設帥()是過河的兵(),判斷它是否能吃到對方的卒()
  這樣,一個復雜的走法生成過程(方案A)就被簡化成幾個簡單的走法判斷過程(方案B)
  • 上一篇 電腦象棋循序漸進():從圖形界面做起
  • 下一篇 電腦象棋循序漸進():最初級的人工智能
  • 返 回 象棋百科全書——計算機博弈
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果