其他策略――胜利局面

胜利局面中的强制过程

David Eppstein */文

*加州爱尔文大学(UC Irvine)信息与计算机科学系

如果棋局到达一个能用强制着法获胜的局面，那么Alpha-Beta搜索会找到它。但是奇怪的是，每次都走一步能赢棋，不是总能赢下来的。这个问题出现在西洋棋或国际象棋中，可以走一步棋到达强制获胜的局面，但是无法使胜利更近一步。

例如，考虑下面的国际象棋局面：

白先走可以立即获胜：把后走到e7格将死黑王。但是白也可以走其他着法只是赢起来慢些，实际上白方只有一种着法不能取得胜利。例如，假设白把王走到e6，黑只能走d8和f8，两者都会被白将死。如果黑走d8，那么白王走回d6仍然可以赢。但是在走了“1. Ke6 Kd8 2. Kd6 Ke8”之后，我们回到了一开始!白走了获胜的着法，但是他没有在获胜上取得进展。

如果Alpha-Beta搜索给任何获胜的局面以相同的评价，就很容易掉进这个陷阱。要防止这种现象，我们需要改变对胜利局面的评价，让着数少的胜法比推延获胜稍微好些。代码很直观：如果我们保留一个层数变量，代表搜索的当前局面距离根局面有多远，我们可以通过减去层数来调整胜利局面的值。以下伪代码用常数WIN代表棋类分值的最大值(在国际象棋中，典型的WIN可以是兵的价值的100或1000倍)。

// 根据层数来调整胜利值的Alpha-Beta搜索
int ply; // 全局变量，在开始搜索时设为零
int alphabeta(int depth, int alpha, int beta) {
　if (棋局结束 && 当前棋手获胜) {
　　return WIN - ply;
　} else if (棋局结束 && 当前棋手失利) {
　　return -WIN + ply;
　} else if (depth <= 0) {
　　return eval();
　}
　ply ++;
　for (每个可能的着法 m) {
　　执行着法 m;
　　alpha = max(alpha, alphabeta(depth 1, beta, alpha));
　　撤消着法 m;
　　if (alpha >= beta) {
　　　break;
　　}
　}
　ply --;
　return alpha;
}

现在再来看上面的例子，ply = 1时立即将死，得到的分值是999(WIN-1)，而把王走到e6可以在ply = 3时获胜，分值是997。程序会使局面到达最大的分值，因此选择立即将死。

对于像黑白棋一样的棋类，棋局的长度有个适当的限制，每着棋都会在棋盘上增加一个子，因此棋局结束前最多只有64着棋。对于这些棋类，没有可能使局面产生无限循环，因此我们可以只用WIN或-WIN而不必考虑层数的调整。

这个层数调整的技巧有一个更为复杂的情况：如何跟散列表发生作用?问题是在散列表中存储的局面，其层数可能跟我们搜索到的局面有所不同。为了得到正确的层数调整值，我们应该在散列表中存储相对于当前局的分值，而不是相对于根局面的。

这样，把局面存储到散列表中，就用下面的伪代码，这里MAX_PLY是比搜索中可能的最大深度还大的常数(WIN = 1000的话，可以让MAX_PLY = 100)。变量x只是当前局面在散列表中的指标。

if (score > WIN - MAX_PLY) {
　hash[x].score = score + ply;
} else if (score < -WIN + MAX_PLY) {
　hash[x].score = score - ply;
} else {
　hash[x].score = score;
}

从散列表中获取局面时，需要做相反的调整：

if (hash[x].score > WIN - MAX_PLY) {
　score = hash[x].score - ply;
} else if (hash[x].score <-WIN + MAX_PLY) {
　score = hash[x].score + ply;
} else {
　score = hash[x].score;
}

原文：www.ics.uci edu/~eppstein/180a/990202a.html

译者：象棋百科全书网

类型：全译