《棋战顺序基本手艺》专题
 
胜利局势中的自愿历程
 
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