Quiscence Search Performance

Question

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?

The performance impact is given in the figures below.

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:

• 6 plies in 82,069 ms (~82 secs)
• 5 plies in 5,298 ms (~5.3 secs)

With Quiescence:

• 5 plies in 83,502 ms (~83 secs)

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?

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

Quiescence:

    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

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.

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.

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.

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).