《对弈程序基本技术》专题
 
迭代加深
 
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
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 基本搜索方法——Alpha-Beta搜索
  • 下一篇 基本搜索方法——置换表
  • 返 回 象棋百科全书——电脑象棋
  • www.xqbase.com