- 《对弈程序基本技术》专题
-
- 胜利局面中的强制过程
-
- 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;
- }
-
- 原文：http://www.ics.uci.edu/~eppstein/180a/990202a.html
- 译者：象棋百科全书网 (webmaster@xqbase.com)
- 类型：全译
上一篇 局面评估函数——简介(二)
下一篇 其他策略——主要变例的获取
返 回 象棋百科全书——电脑象棋
