电脑象棋循序渐进
　
象棋百科全书网 (webmaster@xqbase.com)　2008年4月
　
(二) 掌握象棋规则
　
　　与本文配套的示范程序是“象棋小巫师”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.xqbase.com