胜利局面中的强制过程
发布时间：2008-11-20
点击：
来源：本站原创
录入者：David Eppstein
如果棋局到达一个能用强制着法获胜的局面，那么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;
}
原文：
译者：黄晨 (webmaster@{域名已经过期})
类型：全译
 关闭窗口  打印文档 |
账号登录