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;

    }

Did you look at [this SO question](http://stackoverflow.com/questions/17510606/quiscence-search-performance?rq=1)? — DeadZone, Jun 30 '15 at 18:55
One comment not specific to the quiescent search: For a game like chess, it is usually _much_ faster to modify the same board and then undo the move afterwards rather than copying the entire board for each probe. — 500 - Internal Server Error, Jun 30 '15 at 21:08
@DeadZone: I did look at the linked Post, but the problem there seemed to be that the guy was generating all moves in quiescence search (which I don't). — xXliolauXx, Jul 01 '15 at 09:49
@Internal Server Error: Thanks for the suggestion, that might be helpful later on. Right now, I donj't think it matters if I'm copying the Board, since I figured that I could copy the Board about 25 000 000 times per second (while my whole engine is currently searching through 720 000 Nodes/sec. — xXliolauXx, Jul 01 '15 at 09:53

score 2 · Accepted Answer · answered Jul 01 '15 at 07:08

2

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.

answered Jul 01 '15 at 07:08

H W

2,556
3
21
45

Thank you, that seems to be what I've been looking for. I limited the quiescence search to 4 plys and the search suddenly became a lot faster again! I'll mark your answer then. – xXliolauXx Jul 01 '15 at 09:46
Edit: Could you tell me how badly a limited quiescence search affects the search result? ty – xXliolauXx Jul 01 '15 at 09:56
1

In which regard? By setting the limit of the quiescence search you obviously can have some sort of horizon-effect near the quiescence-ply-limit again. However you won't be able to avoid this unless you evaluate every possible move (close to what you did before). – H W Jul 01 '15 at 10:46
Another note regarding the performance - do you reevaluate the whole board every turn or do you store your calculations somewhere so you only need to evaluate one more move from every node? If you store your results, you might be able to increase the ply-depth while keeping the runtime at about 2-3 minutes (or just decrease the time by a LOT). – H W Jul 01 '15 at 10:48
@ H W: 1) Right, I am a bit worried about the horizon effect coming back from the search limit. But it didn't seem to happen yet. 2) I guess you have hashtables/transposition tables in mind, in order to sort the moves? That definitely is one of the next steps, but I will have to look into it a bit more. Thanks for the suggestion though. – xXliolauXx Jul 01 '15 at 10:58
The "2-3 deeper" statement refers to search extensions in my opinion, not really quiescence search. – xjcl Jun 29 '22 at 18:31

Chess Quiescence Search ist too extensive

1 Answers1