- 《对弈程序基本技术》专题
-
- 静态搜索
-
- 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)
- 类型：全译加译注
上一篇 高级搜索方法——简介(二)
下一篇 高级搜索方法——空着裁剪
返 回 象棋百科全书——电脑象棋
