《对弈程序基本技术》专题
 
胜利局面中的强制过程
 
David Eppstein */
* 加州爱尔文大学(UC Irvine)信息与计算机科学系
 
  如果棋局到达一个能用强制着法获胜的局面,那么Alpha-Beta搜索会找到它。但是奇怪的是,每次都走一步能赢棋,不是总能赢下来的。这个问题出现在西洋棋或国际象棋中,可以走一步棋到达强制获胜的局面,但是无法使胜利更近一步。
  例如,考虑下面的国际象棋局面:
 
 
  白先走可以立即获胜:把后走到e7格将死黑王。但是白也可以走其他着法只是赢起来慢些,实际上白方只有一种着法不能取得胜利。例如,假设白把王走到e6,黑只能走d8f8,两者都会被白将死。如果黑走d8,那么白王走回d6仍然可以赢。但是在走了“1. Ke6 Kd8 2. Kd6 Ke8”之后,我们回到了一开始!白走了获胜的着法,但是他没有在获胜上取得进展。
  如果Alpha-Beta搜索给任何获胜的局面以相同的评价,就很容易掉进这个陷阱。要防止这种现象,我们需要改变对胜利局面的评价,让着数少的胜法比推延获胜稍微好些。代码很直观:如果我们保留一个层数变量,代表搜索的当前局面距离根局面有多远,我们可以通过减去层数来调整胜利局面的值。以下伪代码用常数 WIN 代表棋类分值的最大值(在国际象棋中,典型的 WIN 可以是兵的价值的1001000)
 
// 根据层数来调整胜利值的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)
  类型:全译
  • 上一篇 局面评估函数——简介()
  • 下一篇 其他策略——主要变例的获取
  • 返 回 象棋百科全书——电脑象棋
  • www.xqbase.com