Chess Quiescence Search ist too extensive

Question

I have been creating a simple chess engine in c# over the last month and made some nice progress on it. It is using a simple Alpha-Beta algorithm.

In order to correct the Horizon-Effect, I tried to implement the Quiescence Search (and failed several times before it worked). The strength of the engine seems to have improved quiet a bit from that, but it is terribly slow!

Before, I could search to a 6 ply depth in about 160 secs (somewhere in a midgame state), with the quiescent search, it takes the computer about 80secs to get a move on search depth 3!

The brute-force node counter is at about 20000 Nodes at depth 3, while the quiescent node counter is up to 20 millions!

Since this is my first chess engine, I don't really know if those numbers are normal or if I might have made a mistake in my Quiescence-Algorithm. I would appreciate if someone more experienced could tell me what the usual ratio of BF Nodes/Quiescent nodes is.

Btw, just to have a look at: (this Method is called by the BF tree whenever the searchdepth is 0)

public static int QuiescentValue(chessBoard Board, int Alpha, int Beta)
    {
        QuiescentNodes++;

        int MinMax = Board.WhoseMove; // 1 = maximierend, -1 = minimierend
        int Counter = 0;
        int maxCount;


        int tempValue = 0;
        int currentAlpha = Alpha;
        int currentBeta = Beta;
        int QuietWorth = chEvaluation.Evaluate(Board);

        if(MinMax == 1) //Max
        {
            if (QuietWorth >= currentBeta)
                return currentBeta;
            if (QuietWorth > currentAlpha)
                currentAlpha = QuietWorth;
        }

        else            //Min
        {
            if (QuietWorth <= currentAlpha)
                return currentAlpha;
            if (QuietWorth < currentBeta)
                currentBeta = QuietWorth;
        }




        List<chMove> HitMoves = GetAllHitMoves(Board);
        maxCount = HitMoves.Count;

        if(maxCount == 0)
            return chEvaluation.Evaluate(Board);


        chessBoard tempBoard;

        while (Counter < maxCount)
        {
            tempBoard = new chessBoard(Board);
            tempBoard.Move(HitMoves[Counter]);
            tempValue = QuiescentValue(tempBoard, currentAlpha, currentBeta);

            if (MinMax == 1) //maximierend
            {
                if (tempValue >= currentBeta)
                {
                    return currentBeta;
                }

                if (tempValue > currentAlpha)
                {
                    currentAlpha = tempValue;
                }

            }

            else            //minimierend
            {
                if (tempValue <= currentAlpha)
                {
                    return currentAlpha;
                }
                if (tempValue < currentBeta)
                {
                    currentBeta = tempValue;
                }
            }

            Counter++;
        }

        if (MinMax == 1)
            return currentAlpha;
        else
            return currentBeta;

    }

Answer 1

I am not familliar with the english terminology - is a HitMove a move where you remove a piece from the board?

In that case it seems to me that you use GetAllHitMoves to get a list of the "noisy" moves for the quiescence search which are then evaluated further than the usual 3 or 6 plies. This is called recursively though, so you evaluate this over and over as long as there are possible HitMoves leftover. Giving a limit to your quiescence search should fix your performance issues.

As for choosing the limit for the quiescence search - wiki states:

Modern chess engines may search certain moves up to 2 or 3 times deeper than the minimum.