基本搜索方法——迭代加深

《对弈程序基本技术》专题 　 迭代加深 　 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) 　　类型：全译加译注