3

这是一个双重问题。我已经组装了一个简单的国际象棋引擎，它执行 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 和 Quiescence 例程。它们基于国际象棋编程维基。

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

1 回答 1

2

好吧，quiscence 搜索必须有性能损失，因为它沿着一些更深的线搜索以稳定位置的评估。但它不应该那么多：“捕获”线相当罕见，不能像整个 6 层一样多。

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

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

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

于 2013-07-07T09:07:29.217 回答