Quiescence Search & Transposition Tables

[aberent]

I believe that Quiescence the slowest portion of my search. I think it is because of 2 reasons:

1. My Quiescence Search does not make use of Transposition Tables.
2. I call the Evaluate Function at every node.

My question(s) is how do I implement Transposition Tables for Quiescence Search? Is it the same as regular search? Do I create a separate Table for Quiescence so it does not pollute the main table? I am guessing it has to be different because can you really have exact entries?

I have included my code below, please help:

Code: Select all

 
        private static int Quiescence(Board examineBoard, int alpha, int beta, ref int nodesSearched)
        {
            nodesSearched++;

            //Evaluate Score
            Evaluation.EvaluateBoardScore(examineBoard);

            //Invert Score to support Negamax
            examineBoard.Score = SideToMoveScore(examineBoard.Score, examineBoard.WhoseMove);


            if (examineBoard.Score >= beta)
                return beta;

            if (examineBoard.Score > alpha)
                alpha = examineBoard.Score;

            
            List<Position> positions;

            if &#40;examineBoard.WhiteCheck || examineBoard.BlackCheck&#41;
            &#123;
                positions = EvaluateMoves&#40;examineBoard, 0&#41;;
            &#125;
            else
            &#123;
                positions = EvaluateMovesQ&#40;examineBoard&#41;;    
            &#125;
            

            if &#40;positions.Count == 0&#41;
            &#123;
                return examineBoard.Score;
            &#125;
            positions.Sort&#40;Sort&#41;;

            foreach &#40;Position move in positions&#41;
            &#123;
                //Make a copy
                Board board = examineBoard.FastCopy&#40;);

                //Move Piece
                Board.MovePiece&#40;board, move.SrcPosition, move.DstPosition, ChessPieceType.Queen&#41;;

                //We Generate Valid Moves for Board
                PieceValidMoves.GenerateValidMoves&#40;board&#41;;

                if &#40;board.BlackCheck&#41;
                &#123;
                    if &#40;examineBoard.WhoseMove == ChessPieceColor.Black&#41;
                    &#123;
                        //Invalid Move
                        continue;
                    &#125;
                &#125;

                if &#40;board.WhiteCheck&#41;
                &#123;
                    if &#40;examineBoard.WhoseMove == ChessPieceColor.White&#41;
                    &#123;
                        //Invalid Move
                        continue;
                    &#125;
                &#125;
               
                int value = -Quiescence&#40;board, - beta, -alpha, ref nodesSearched&#41;;

                if &#40;value >= beta&#41;
                &#123;
                    KillerMove&#91;2, 0&#93;.SrcPosition = move.SrcPosition;
                    KillerMove&#91;2, 0&#93;.DstPosition = move.DstPosition;

                    return beta;
                &#125;
                if &#40;value > alpha&#41;
                &#123;
                    alpha = value;
                &#125;
            &#125;

            return alpha;
        &#125;

[/code]

[hgm]

Most engines use the same table for QS and main search (so you can get hits on deeper entries with QS probes). Exact values in QS are just as exact as any exact score from main search. Of course less depth means the scores are less accurate, but that is another matter.

[bob]

Obvious questions:

(1) what are "killer moves" in q-search?

(2) you are testing for black and white being in check at _every_ node in the case where whitecheck returns false. Also, further down, you call both after making the move? That doesn't make any sense. qsearch nodes make up > 75% of the nodes searched, you don't want to do _any_ unnecessary work there.

[aberent]

Obvious questions:

(1) what are "killer moves" in q-search?

(2) you are testing for black and white being in check at _every_ node in the case where whitecheck returns false. Also, further down, you call both after making the move? That doesn't make any sense. qsearch nodes make up > 75% of the nodes searched, you don't want to do _any_ unnecessary work there.

The Killer Moves are used for sorting. If a move has caused a beta cut off I try this move first next time I enter Quiescence. Is this wrong?

About the Check test. This is just a boolean variable lookup not an evaluation. The first "Check Test" is to see if I should be looking at every move or just captures. If I am in check I evaluate all moves not just captures. I found this corrected some weird issues I was having before.

The second "Check Test" happens after a move is made. If the move caused a check then it is not a valid move so I do not want to persue it any further.

Is what I am doing here correct? Please help.

[bob]

Obvious questions:

(1) what are "killer moves" in q-search?

(2) you are testing for black and white being in check at _every_ node in the case where whitecheck returns false. Also, further down, you call both after making the move? That doesn't make any sense. qsearch nodes make up > 75% of the nodes searched, you don't want to do _any_ unnecessary work there.

The Killer Moves are used for sorting. If a move has caused a beta cut off I try this move first next time I enter Quiescence. Is this wrong?

In the q-search, yes. It is better to order the captures based on expected material gain. Most use SEE and eliminate captures that have a score < 0, but they we are using MVV/LVA to order the captures that SEE thinks does not lose material.

About the Check test. This is just a boolean variable lookup not an evaluation. The first "Check Test" is to see if I should be looking at every move or just captures. If I am in check I evaluate all moves not just captures. I found this corrected some weird issues I was having before.

The second "Check Test" happens after a move is made. If the move caused a check then it is not a valid move so I do not want to persue it any further.

Is what I am doing here correct? Please help.

Hard to say without seeing the rest of your code, but the guiding principle for q-search is to minimize work done because it is done so very often...

[aberent]

I do already use MVV/LVA for move ordering. That happens in the EvaluateMovesQ method.

What is this: SEE you are talking about?

Also I am still not sure how to use Transposition Tables in my Quiescence Search, can someone give me a verbal description or a code example.

[bob]

I do already use MVV/LVA for move ordering. That happens in the EvaluateMovesQ method.

What is this: SEE you are talking about?

Also I am still not sure how to use Transposition Tables in my Quiescence Search, can someone give me a verbal description or a code example.

SEE == Static Exchange Evaluator

It just plays out captures on one square to see if a potential move loses material, wins material, or is neutral.

Hashing in q-search works exactly like hashing in normal search. You probe at the front of q-search before doing anything. After completing the q-search you store the result so that if you reach this position again, you can avoid repeating the search.

[Greg Strong]

For SEE, look at this page:

http://chessprogramming.wikispaces.com/ ... Evaluation

It's important to note that when "playing out" captures to a square to evaluate the exchange, the moves are not actually made on the board. That would be too slow. It's a crude (but effective) estimate of the value of the trade. It generally doesn't consider things such as if one of the capturing pieces is pinned ...

[aberent]

Thanks I will look into this SEE it looks like it might be my best chance at improving my Quiescence Search.

[jwes]

Something that has not been mentioned is that TT probes are slow. You would need to test to see if it made your program faster.
Also have you seen http://chessprogramming.wikispaces.com/?
It has much good information for beginning (or expert) chess programmers.