Quiscence 搜索性能

Question

这是一个双重问题。我组装了一个简单的国际象棋引擎，它执行 Alpha-Beta 搜索，最后执行静止搜索。静止搜索正在影响性能。问题是，这是可以接受的性能影响吗？如果不是，那么应该采取什么措施来解决这个问题？

性能影响如下图所示。

请注意，这些统计数据是在游戏中间考虑的。 FEN 是：

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

无静止：

• 6 层需要 82,069 毫秒（约 82 秒）
• 5 层需要 5,298 毫秒（约 5.3 秒）

静止：

• 5 层需要 83,502 毫秒（约 83 秒）

我还没有使用静止搜索对 6 层进行统计，但如果需要的话，我不介意计算它。

需要注意的关键是，添加静止搜索相当于搜索额外的层。这正常吗？

下面列出了 C# 中的 Alpha-Beta 和静止例程。它们基于国际象棋编程维基。

        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;
        }

Answer 1

嗯，静止搜索肯定会带来性能损失，因为它会沿着某些线路进行更深的搜索以稳定位置的评估。但它不应该那么多：“捕获”线相当罕见，而且不可能与整个第 6 层一样多。

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

此外，这些搜索时间（5 层深度为 5 秒，6 层深度为 82 秒）似乎非常慢。也许 beta 截止或搜索中的移动顺序有问题（即您正在搜索完整的树），或者您的编译器没有执行任何优化。任何现代国际象棋引擎都会立即达到 5 的深度。

还有一个提示：通常，Quiscence 搜索使用单独的移动生成器，仅生成捕获、检查和棋子升级（这样的生成器比普通生成器更简单、更快）。