电脑象棋循序渐进(三)：最初级的人工智能

(三) 最初级的人工智能

与本文配套的示范程序是“象棋小巫师”0.3版，程序清单是：

(1) XQWL03.CPP — C++源程序；

(2) XQWLIGHT.RC — 资源描述文件；

(3) RESOURCE.H — 资源符号定义文件；

(4) RES目录 — 图标、图片、声音等资源。

在阅读本章前，建议读者先阅读象棋百科全书网计算机博弈专栏的以下几篇译文：

(1) 国际象棋程序设计(四)：基本搜索方法(François Dominic Laramée)；

(2) 国际象棋程序设计(六)：局面评估函数(François Dominic Laramée)；

(3) 基本搜索方法—简介(一)(David Eppstein)；

(4) 基本搜索方法—简介(二)(David Eppstein)；

(5) 基本搜索方法—最小-最大搜索(Bruce Moreland)；

(6) 基本搜索方法—Alpha-Beta搜索(Bruce Moreland)；

(7) 基本搜索方法—迭代加深(Bruce Moreland)；

(8) 高级搜索方法—简介(二)(David Eppstein)；

(9) 其他策略—胜利局面(David Eppstein)；

(10) 局面评估函数—简介(一)(David Eppstein)。

3.1 局面评价函数

根据国际象棋程序的经验，局面评价函数中最关键的因素是子力价值(后9车5象马3兵1)。这个经验同样也适合于中国象棋，并且适当调整就可以得到更好的效果——子力价值是跟它的绝对位置相关的。最明显的例子是中国象棋中的兵(卒)，过河前我们给它很低的分数，过河后分数大涨，越接近九宫分数就越高，九宫中心甚至接近一个马或炮的值。

如此一来，每个兵种就都会有一个与绝对位置相关的价值数组，因此我们的程序里有一个常量数组 cucvlPiecePos[7][256]，它是从开源的象棋程序 ElephantEye 中照搬过来的。

现在要开始进行局面评价了，我们是不是应该这样做：

vlEvaluate = 0; // 相对于红方来说的局面评价值
for (sq = 0; sq < 256; sq ++) {
　pc = ucpcSquares[sq];
　if (IS_RED(pc)) {
　　vlEvaluate += cucvlPiecePos[PIECE_TYPE(pc)][sq];
　} else if (IS_BLACK(pc)) {
　　vlEvaluate -= cucvlPiecePos[PIECE_TYPE(pc)][SQUARE_FLIP(sq)];
　}
}

这样做太浪费时间了，因为根本没有必要每次都把棋盘扫描一遍。在我们的程序里，每走一步棋都会调用两到三次 AddPiece (放一枚棋子)和 DelPiece (取走一枚棋子)，可以趁这个机会更新 vlEvaluate(将上面代码中红色的部分放到 AddPiece 和 DelPiece 中)。

对于象棋小巫师来说，这样的局面评价函数已经足够好了。

3.2 Alpha-Beta搜索复杂吗？

我们可以很容易地写出一个Alpha-Beta搜索函数：

int AlphaBeta(int vlAlpha, int vlBeta, int nDepth) {
　if (nDepth == 0) {
　　return 局面评价函数;
　}
　生成全部走法;
　排序全部走法;
　for (每个生成的走法) {
　　走这个走法;
　　int vl = -AlphaBeta(-vlBeta, -vlAlpha, nDepth - 1);
　　撤消这个走法;　
　　if (vl >= vlBeta) {
　　　return vlBeta;
　　}
　　if (vl > vlAlpha) {
　　　vlAlpha = vl;
　　}
　}
　return vlAlpha;
}

但是，这样的程序根本走不出棋来，因为它返回的是一个分数而不是一个走法。另外，我们还发现几个问题：

(1) 排序的依据是什么？

(2) 是不是每个生成的走法都可以走？

(3) 如果什么走法都走不出来，那么返回vlAlpha合理吗？

针对以上几个问题，我们对程序做如下改进：

(0) 如果函数在根节点处被调用，就把最佳走法作为电脑要走的棋；

(1) 国际象棋程序的经验证明，历史表是很好的走法排序依据；

(2) 由于我们的走法生成器并没有考虑自杀(被将军)的情况，因此走完一步后要检查是否被将军了，被将军时应立即退回来；

(3) 如果没有走出过任何走法，说明当前局面是杀棋或困毙局面，应该返回杀棋的分数。

下面是改进过的程序，改进的地方用红色标出：

int AlphaBeta(int vlAlpha, int vlBeta, int nDepth) {
　if (nDepth == 0) {
　　return 局面评价函数;
　}
　生成全部走法;
　按历史表排序全部走法;
　for (每个生成的走法) {
　　走这个走法;
　　if (被将军) {
　　　撤消这个走法;
　　} else {
　　　int vl = -AlphaBeta(-vlBeta, -vlAlpha, nDepth - 1);
　　　撤消这个走法;　
　　　if (vl >= vlBeta) {
　　　　将这个走法记录到历史表中;
　　　　return vlBeta;
　　　}
　　　if (vl > vlAlpha) {
　　　　设置最佳走法;
　　　　vlAlpha = vl;
　　　}
　　}
　}
　if (没有走过任何走法) {
　　return 杀棋的分数;
　}
　将最佳走法记录到历史表中;
　if (根节点) {
　　最佳走法就是电脑要走的棋;
　}
　return vlAlpha;
}

3.3 杀棋的分数

遇到将死或困毙的局面时，应该返回 nDistance - INFINITY，这样程序就能找到最短的搜索路线。nDistance 是当前节点距离根节点的步数，每走一个走法，nDistance 就增加1，每撤消一个走法，nDistance 就减少1。

如果程序中使用了置换表，这个问题将变得更加复杂，我们以后再讨论。

3.4 历史表

国际象棋程序的经验证明，历史表是很好的走法排序依据。那么，什么样的走法要记录到历史表中去呢？象棋小巫师选择了以下两类走法：

A. 产生Beta截断的走法；

B. 不能产生Beta截断，但它是所有PV走法(vl > vlAlpha)中最好的走法。

象棋小巫师的历史表是一个大小为65536的数组，正好能将走法的数值(mv)作为指标，因此根据走法取得历史表的值非常容易，即nHistoryTable[mv]。那么，一个走法记录到历史表，究竟该给 nHistoryTable 中的这个元素加多少分的值呢？我们仍旧沿用国际的经验——深度的平方。所以，更新历史表的代码非常简单：

nHistoryTable[mv] += nDepth * nDepth;

3.5 迭代加深和时间控制

迭代加深具有一石多鸟的功效，目前最明显的供效是充分发挥历史表的作用——浅一层搜索结束后，历史表中积累了大量非常宝贵的数据，这将大幅度减少深一层搜索的时间。

在迭代加深的基础上实现时间控制，这将是非常简单的：

for (i = 1; i < MAX_DEPTH; i ++) {
　AlphaBeta(-INFINITY, INFINITY, i);
　if (超过最短搜索时间) {
　　break;
　}
}

当然，我们还可以加入其他结束迭代加深的条件，例如当程序算出了杀棋(分值接近INFINITY或-INFINITY)时，就没有必要进行更深的搜索了。