高级搜索方法——静态搜索

《对弈程序基本技术》专题 　 静态搜索 　 Bruce Moreland / 文 　 　　国际象棋中会有很多强制的应对。如果有人用马吃掉你的象，那么你最好吃还他的马。 　　Alpha-Beta搜索不是特别针对这种情况的。你把深度参数传递给函数，当深度到达零就做完了，即使一方的后被捉。 　　一个应对的方法称为“静态搜索”(Quiescent Search)。当Alpha-Beta用尽深度后，通过调用静态搜索来代替调用“Evaluate()”。这个函数也对局面作评价，只是避免了在明显有对策的情况下看错局势。 　　简而言之，静态搜索就是应对可能的动态局面的搜索。 　　典型的静态搜索只搜索吃子着法。这会引发一个问题，因为在国际象棋中吃子通常不是强制的。如果局势很平静，而且你面对的吃子只有QxP(后吃兵，导致丢后)，你不会强迫后去吃兵的，所以静态搜索不应该强迫吃子。 　　因此，走子一方可以选择是吃子还是不吃子。这就好比打扑克牌时可以只用手中的牌而不去抓牌【译注：术语“Standing Pat”】。 　　代码如下： 　 int Quies(int alpha, int beta) { 　val = Evaluate(); 　if (val >= beta) { 　　return beta; 　} 　if (val > alpha) { 　　alpha = val; 　} 　GenerateGoodCaptures(); 　while (CapturesLeft()) { 　　MakeNextCapture(); 　　val = -Quies(-beta, -alpha); 　　UnmakeMove(); 　　if (val >= beta) { 　　　return beta; 　　} 　　if (val > alpha) { 　　　alpha = val; 　　} 　} 　return alpha; } 　 　　这看上去和“Alpha-Beta”非常相似，但是区别是很明显的。这个函数调用静态评价，如果评价好得足以截断而不需要试图吃子时，就马上截断(返回Beta)。如果评价不足以产生截断，但是比Alpha好，那么就更新Alpha来反映静态评价。 　　然后尝试吃子着法，如果其中任何一个产生截断，搜索就中止。可能它们没有一个是好的，这也没问题。 　　这个函数有几个可能的结果：可能评价函数会返回足够高的数值，使得函数通过Beta截断马上返回；也可能某个吃子产生Beta截断；可能静态评价比较坏，而任何吃子着法也不会更好；或者可能任何吃子都不好，但是静态评价只比Alpha高一点点。 　　注意这里静态搜索中没有传递“深度”这个参数。正因为如此，如果找到好的吃子，或者有一系列连续的强制性吃子的着法，那么搜索可能会非常深。 　　我的示范程序不检测将军，因此它不能找到杀棋。先询问要走的一方是否被将军，这是可以尝试的做法。如果被将军了，就不能用“Evaluate()”来尝试截断，而应该以一层的深度调用Alpha-Beta。例如： 　 int Quies(int alpha, int beta) { 　if (InCheck()) { 　　return AlphaBeta(1, alpha, beta); 　} 　val = Evaluate(); 　if (val >= beta) { 　　return beta; 　} 　if (val > alpha) { 　　alpha = val; 　} 　GenerateGoodCaptures(); 　while (CapturesLeft()) { 　　MakeNextCapture(); 　　val = -Quies(-beta, -alpha); 　　UnmakeMove(); 　　if (val >= beta) { 　　　return beta; 　　} 　　if (val > alpha) { 　　　alpha = val; 　　} 　} 　return alpha; } 　 　　这个版本会找到带有连续吃子的杀棋。至于用哪个版本，取决于个人喜好和测试结果。 　　“好的”吃子的界定也是仁者见仁智者见智的。如果你允许任何吃子，并且以任何原始的顺序来搜索，那么你会降低搜索效率，并且导致静态搜索的膨胀，从而大幅度降低搜索深度，并使程序崩溃。 　　有一些简单的做法可以避免静态搜索的膨胀。 　 MVV/LVA 　 　　MVV/LVA 意思是“最有价值的受害者/最没价值的攻击者”(Most Valuable Victim/Least Valuable Attacker)。这是一个应用上非常简单的着法排序技巧，从而最先搜索最好的吃子着法。这个技术假设最好的吃子是吃到最大的子。如果不止一个棋子能吃到最大的子，那么假设用最小的子去吃是最好的。 　　这就意味者PxQ(兵吃后)首先考虑(假设王的将军另外处理)。接下来是NxQ或BxQ，然后是RxQ、QxQ、KxQ。接下来是PxR、B/NxR、RxR、QxR、KxR，等等。 　　这个工作总比不做要好，但是很明显有很严重的问题。即使车被保护着，RxR仍旧排在PxB的前面。 　　MVV/LVA 可以解决静态搜索膨胀的问题，但是它仍然留给你比较庞大的静态搜索树。 　　MVV/LVA 的优势在于它实现起来非常方便，而且可以达到很高的NPS值(每秒搜索的结点数)。它的缺点是搜索效率低——你花大量的时间来评估吃亏的吃子，所以你的搜索不会很深。 　 SEE 　 　　SEE 意思是“静态交换评价”(Static Exchange Evaluation)。它比 MVV/LVA 更复杂，但是着法排序更准确，从而很多吃子都不必考虑。 　　在 MVV/LVA 中你无法去掉QxP的着法，因为很可能兵是没保护的，这就意味着QxP是好的着法。当然，如果兵是保护的，我不相信你还能在搜索这步时有什么好的发现。用了 SEE 后，如果QxP是吃亏的着法，你就可以把它挑出来，然后在吃子的顺序里把它排在最后，或简单地把它裁剪掉。 　　现在我还没有 SEE 的示范代码，你可以设计一个处理吃子的过程，然后根据它看上去能得到的价值进行排序。【当考虑吃子着法时，需要考虑能吃到的该子的所有攻击子，也要保护该子的所有防守子，因此处理吃子的过程是相当复杂的。】 　　SEE 能让你非常有效地裁剪掉坏的着法，很多重要的吃子不会被错误地裁剪，并且能改进着法的顺序。你能做的另一件事是，如果着法看起来还不算充分好，那么你可以裁剪掉这些好的着法。如果你领先一个车，那么得一个兵的吃子或许不值得在静态搜索中尝试。 　　我很怀疑用 SEE 的程序能比相同的但用了 MVV/LVA 的程序强。问题在于代码的编写上，需要很好地设计数据结构，才能让 SEE 变得有效。 　 静态搜索不是完美的 　 　　静态搜索极有可能会犯错误。这是一个不幸的现实，但是它更多地在搜索看上去非常愚蠢(例如一层的搜索，它根本不会是非常好的)的情况下会犯错误，因此这不是一个严重的问题。 　　如果可能用更准确的静态搜索而不降低速度，那么我肯定这个程序会比以前更强。但是我们必须明白的是，你在耗费时间的前提下试图让静态搜索更准确，需要找到平衡点。如果为了让静态搜索更聪明，你花费了几层完全搜索的时间，那么这就不值得让它更聪明了。 　 　　原文：http://www.seanet.com/~brucemo/topics/quiescent.htm 　　译者：象棋百科全网 (webmaster@xqbase.com) 　　类型：全译加译注