《對弈程序基本技術》專題
 
迭代加深
 
Bruce Moreland /
 
一個聽起來不怎樣的思想
 
  如果你準備開始搜索一個國際象棋的局面了,你要搜索多深呢?事先預測搜索將進行多少時間,這有些困難,因為完成D層搜索所需要的時間取決于很多不確定的因素。在復雜的中局局面里,你可能不會搜索得很深,而在殘局中你可能會搜索得非常深,在某些王兵殘局里你可能會搜索100多層【譯注:這也太夸張了點吧】
  有一個思想,就是一開始只搜索一層,如果搜索的時間比分配的時間少,那么搜索兩層,然后再搜索三層,等等,直到你用完時間為止。
  這足以保證很好地運用時間了。如果你可以很快搜索到一個深度,那么你在接下來的時間可以搜索得更深,或許你可以完成。如果局面比你想象的復雜,那么你不必搜索得太深,但是至少有合理的著法可以走了,因為你不太可能連1層搜索也完不成。
  這個思想稱為“迭代加深”(Iterative Deepening),因為你在迭代搜索,每次都比一次前一次加深1(1層沒有什么奧妙的,當然你可以試試多兩層,但是1層比較好)
  代碼如下:
 
for (depth = 1; ; depth ++) {
 val = AlphaBeta(depth, -INFINITY, INFINITY);
 if (TimedOut()) {
  break;
 }
}
 
  這是一個非常有效的搜索方法,你可能會感到吃驚。如果你能增強Alpha-Beta使得它返回一條“主要變例”,你可以用主要變例中的著法來做下一次迭代搜索。
  例如,一層的搜索顯示“1. e4”是最好的著法,那么在做兩層的搜索時你先搜索“1. e4”。如果返回“1. e4 e5”,那么你在做三層的搜索時仍舊先搜索這條路線。
  這樣做之所以有好的效果,是因為第一次搜索的線路通常是好的,而Alpha-Beta對著法的順序特別敏感。如果著法順序很壞,那么在國際象棋中你的“分枝因子”將接近35。如果你的著法很好,那么分枝因子將接近于6。前一次迭代的搜索函數得到的主要變例通常是非常好的著法。
  迭代加深的思想給了你一個簡單的方法,它可以在時間用完時中斷搜索,并且會提高你的搜索效率。
  【有可能的話,你可以把檢測超時的程序做到“AlphaBeta”函數里去,而“TimeOut”只是由“AlphaBeta”函數返回的超時檢測結果(如果超時的話,就直接跳出函數體了)。很多情況下,程序沒有必要搜索整個一層才給出最佳著法。由于迭代加深的原因,新的一層搜索的第一個著法總是上一層搜索得到的最佳著法,如果新的一層可以搜索出另一個更好的著法,就已經很滿意了,有時沒有必要找到最好的著法。換句話說,即使你沒有足夠的時間把這一層搜索完,得到的著法至少不會比上一層最好著法要壞。】
 
  原文:http://www.seanet.com/~brucemo/topics/iterative.htm
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 基本搜索方法——Alpha-Beta搜索
  • 下一篇 基本搜索方法——置換表
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果