- 电脑象棋循序渐进
-
-
- (三) 最初级的人工智能
-
- 与本文配套的示范程序是“象棋小巫师”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)时，就没有必要进行更深的搜索了。
上一篇 电脑象棋循序渐进(二)：掌握象棋规则
下一篇 电脑象棋循序渐进(四)：稍微聪明些了
返 回 象棋百科全书——计算机博弈
