Esta es una pregunta doble. He reunido un motor de ajedrez simple que realiza una búsqueda Alpha-Beta seguida de una búsqueda Quiescence al final. La búsqueda de la inactividad está afectando el rendimiento. La pregunta es, ¿es un impacto aceptable en el rendimiento? Si no, ¿qué se debe hacer para remediar este problema?

El impacto en el rendimiento se da en las siguientes figuras.

Tenga en cuenta que estas estadísticas se consideraron en medio de un juego. El FEN es:

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

Sin la quiescencia

6 capas en 82,069 ms (~ 82 segundos)5 capas en 5,298 ms (~ 5.3 segundos)

Con la quiescencia:

5 capas en 83,502 ms (~ 83 segundos)

No he hecho estadísticas para 6 capas usando la búsqueda de inactividad, pero no me importaría calcularlo si fuera necesario.

La clave a tener en cuenta es que agregar una búsqueda de inactividad es equivalente a buscar una capa adicional. ¿Esto es normal?

Las rutinas Alpha-Beta y Quiescence en C # se enumeran a continuación. Se basan enprogramación de ajedrez 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;
    }

Quietud:

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