《對弈程序基本技術》專題
 
勝利局面中的強制過程
 
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
  譯者:象棋百科全書網 ([email protected])
  類型:全譯
  • 上一篇 局面評估函數——簡介()
  • 下一篇 其他策略——主要變例的獲取
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果