电脑象棋循序渐进(二)：掌握象棋规则

(二) 掌握象棋规则

与本文配套的示范程序是“象棋小巫师”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] 而已。

上表就是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)。