《棋战顺序基本手艺》专题
 
迭代加深
 
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