quiscence搜索效果 [英] Quiscence Search Performance

问题描述

这是两个问题。我整理了一个简单的国际象棋引擎，该引擎执行Alpha-Beta搜索，然后在最后进行静态搜索。静态搜索正在影响性能。问题是，这是否可以接受对性能的影响？如果不是，那么该怎么做才能解决此问题？

This is a two-fold question. I have put together a simple chess engine which performs Alpha-Beta search followed by Quiescence search at the end. Quiescence search is impacting the performance. The question is, is it an acceptable performance impact? If not, then what should be done to remedy this problem?

性能影响如下图所示。

请注意，这些统计数据是在比赛中期考虑的。 FEN为：

Note that these stats were considered in middle of a game. The FEN is:

r3k2r / pb2qpbp / 1pn1pnp1 / 2PpP3 / 2B2B2 / 2N2N2 / PPPQ1PPP / R3K2R w KQkq-0 1

无静态：

Without Quiescence:

• 在82,069毫秒（〜82秒）中6层


• 在5,298毫秒（〜5.3秒）中5层

具有休眠状态：

With Quiescence:

• 5层在83,502毫秒内（〜 83秒）

我没有使用静态搜索对6层的统计数据，但如果需要的话，也不会介意进行计算。

I haven't done stats for 6 plies using quiescence search, but wouldn't mind calculating it if need be.

要注意的关键是添加静态搜索等同于搜索额外的层。这是正常现象吗？

The key thing to note is that adding quiescence search is equivalent to searching an extra ply. Is this normal?

下面列出了C＃中的Alpha-Beta和Quiescent例程。它们基于 chess编程Wiki 。

The Alpha-Beta and Quiescence routines in C# are listed below. They are based on chess programming wiki.

    public static int AlphaBeta(Board board, int alpha, int beta, int depthLeft, int side)
    {
        if (depthLeft == 0)
        {
            return Quiescence(board, side, alpha, beta);
        }
        List<Move> moves = board.GenerateMoves(side);

        //nodesCount += moves.Count;

        BoardState state;
        int score;
        int oppositeSide = -1 * side;

        for (int i = 0; i < moves.Count; i++)
        {
            state = board.GetCurrentBoardState();
            if (!board.MakeMove(moves[i]))
            {
                continue;
            }
            score = -AlphaBeta(board, -beta, -alpha, depthLeft - 1, oppositeSide);
            board.RestoreState(state);
            if (score >= beta)
            {
                return beta; 
            }
            if (score > alpha)
            {
                alpha = score; 
            }
        }
        return alpha;
    }

静态：

    private static int Quiescence(Board board, int side, int alpha, int beta)
    {
        int standingPat = Evaluation.EvaluateFromPerspectiveOf(board, side);

        if (standingPat >= beta)
        {
            return beta;
        }

        if (alpha < standingPat)
        {
            alpha = standingPat;
        }

        int oppositeSide = -1 * side;

        List<Move> moves = board.GenerateMoves(side);
        int score;
        BoardState state;
        for (int i = 0; i < moves.Count; i++)
        {
            if (!board.IsCaptureMove(moves[i]))
            {
                continue;
            }

            //nodesCount++;

            state = board.GetCurrentBoardState();
            if (!board.MakeMove(moves[i]))
            {
                continue;
            }
            score = -Quiescence(board, oppositeSide, -beta, -alpha);
            board.RestoreState(state);

            if (score >= beta)
            {
                return beta;
            }
            if (score > alpha)
            {
                alpha = score;
            }
        }
        return alpha;
    }

推荐答案

那么，静默搜索必须具有因为它沿着更深的某些线搜索以稳定排名的评估，所以会产生性能损失。但这不应该那么多：捕获行非常少见，不能像整个第六层一样多。

Well, quiscence search must have a performance penalty since it searches along some lines deeper to stabilize position's evaluation. But it shouldn't be that much: 'capture' lines are rather rare and cannot be as numerous as the whole 6-th ply.

您可能希望输出评估职位的数量，然后查看Quiscence处理了多少职位。这个数字不能太大。确保您的Quiscence搜索也使用alpha-beta修剪。

You might want to output amount of evaluated positions and then see how many positions are processed by Quiscence. This number shouldn't be large. Make sure your Quiscence search uses alpha-beta pruning as well.

此外，这些搜索时间（5层深度为5秒，6层深度为82秒）似乎很慢。 Beta截止或搜索中的移动顺序可能存在问题（也就是说，您正在搜索完整的树），或者编译器未执行任何优化。任何现代国际象棋引擎都可以立即达到5的深度。

Also, these search times (5 seconds for 5-ply depths and 82 seconds for 6-ply depth) seem to be very slow. Maybe there is something wrong with beta cut-off or with move ordering in the search (that is you're searching the complete tree) or your compiler doesn't perform any optimizations. Any modern chess engine reaches depth of 5 in no time.

另外一个提示：Quiscence搜索通常使用单独的移动生成器，该生成器仅生成捕获，检查和典当促销（这样的生成器比普通的生成器更简单，更快。）

One more hint: usually, Quiscence search uses a separate move generator that generates only captures, checks and pawn promotions (such a generator is simpler and faster than the normal one).

这篇关于quiscence搜索效果的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！