计算机象棋博弈电脑象棋循序渐进(连载)(三) 最初级的人工智能

电脑象棋循序渐进 　 象棋百科全书网 (webmaster@xqbase.com)　2008年4月 　 (三) 最初级的人工智能 　 　　与本文配套的示范程序是“象棋小巫师”0.3版，程序清单是： 　　(1) XQWL03.CPP——C++源程序； 　　(2) XQWLIGHT.RC——资源描述文件； 　　(3) RESOURCE.H——资源符号定义文件； 　　(4) RES目录——图标、图片、声音等资源。 　 　　在阅读本章前，建议读者先阅读象棋百科全书网计算机博弈专栏的以下几篇译文： 　　(1) 国际象棋程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 (四)：基本搜索方法(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)时，就没有必要进行更深的搜索了。