Это двойной вопрос. Я собрал простой шахматный движок, который выполняет альфа-бета-поиск с последующим поиском покоя в конце. Поиск покоя влияет на производительность. Вопрос в том, приемлемое ли это влияние на производительность? Если нет, то что нужно сделать, чтобы решить эту проблему?

Влияние на производительность приведено на рисунках ниже.

Обратите внимание, что эта статистика была рассмотрена в середине игры. 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 слоев, используя поиск покоя, но нене против рассчитать его, если это будет необходимо.

Ключевым моментом, который стоит отметить, является то, что добавление поиска покоя эквивалентно поиску дополнительного слоя. Это нормально?

Процедуры Alpha-Beta и Quiescence в C # перечислены ниже. Они основаны нашахматное программирование вики.

    public static int AlphaBeta(Board board, int alpha, int beta, int depthLeft, int side)
    {
        if (depthLeft == 0)
        {
            return Quiescence(board, side, alpha, beta);
        }
        List 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 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;
    }