Quiescence Search Review

[aberent]

Could someone please have a look at my Quiescence and let me know if you see any glaring mistakes. Mainly I am concerned with when I am supposed to flip the score for black (SideToMoveScore).

Code: Select all

private static int SideToMoveScore(int score, ChessPieceColor color)
        {
            if (color == ChessPieceColor.Black)
                return -score;

            return score;
        }

Code: Select all

internal static int Quiescence(Board examineBoard, int alpha, int beta, ChessPieceColor movingSide, ref int nodesSearched)
        {
            nodesSearched++;

            //Evaluate Score
            Evaluation.EvaluateBoardScore(examineBoard);
            //Invert Score to support Negamax
            examineBoard.Score = SideToMoveScore(examineBoard.Score, movingSide);

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

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

            List<Position> positions = EvaluateMoves(movingSide, examineBoard, true);

            if (positions.Count == 0)
            {
                return examineBoard.Score;
            }

            positions.Sort(Sort);

            foreach (Position move in positions)
            {
                //Make a copy
                Board board = examineBoard.FastCopy();

                //Move Piece
                Board.MovePiece(board, move.SrcPosition, move.DstPosition, ChessPieceType.Queen);

                //We Generate Valid Moves for Board
                PieceValidMoves.GenerateValidMoves(board);

                int value = -Quiescence(board, -beta, -alpha, GetOppositeColor(movingSide), ref nodesSearched);

                if (value >= beta)
                {
                    return beta;
                }
                if (value > alpha)
                    alpha = value;
            }
            return alpha;
        }

[Aleks Peshkov]

It is better to generate moves just near the place you sort them. No need to generate moves if you return with stand pat static score.

Not sure about 'movingSide' variable and all negamax signs, because you actually generate move from opposite side.

[aberent]

Anyone please have a look, I think I have a bug in there somewhere. My engine makes a stupid move in a test position when Quiescence is enabled. I can't seem to figure out what I am doing wrong. All of the code examples I found don't flip the score for black so I am not sure if what I am doing is correct.

[Gian-Carlo Pascutto]

Code: Select all

                //Move Piece
                Board.MovePiece(board, move.SrcPosition, move.DstPosition, ChessPieceType.Queen);

                //We Generate Valid Moves for Board
                PieceValidMoves.GenerateValidMoves(board);

2 weird things here:

1) ChessPieceType.Queen?

2) I suppose the GenerateValidMoves generates valid moves for *both* sides, otherwise the code is most likely wrong as you didn't swap movingSide after executing the move, so moves for the wrong side would get generated. If that's not it, this call should probably go before EvaluateMoves for performance reasons anyway. (And possibly correctness, if it isn't called at the top level first before starting a search).

[Sven]

GenerateValidMoves() would not be able to generate moves for only one side without knowing for which, so I expect that the Board class contains the sideToMove information. But in this case it is confusing to have another sideToMove variable or parameter, and also it would be absolutely necessary to do the side switch explicitly when making a move, at the place where the new board copy is created.

If the Board class is not supposed to contain sideToMove information then GenerateValidMoves() is clearly missing that as parameter, or does some unknown magic to determine for which side it shall generate moves.

Moving the move generation code to a different place, as already proposed, would also be my proposal, but be aware that this may also be necessary in the search code "above" quiescence search.

Sven

[aberent]

Code: Select all

                //Move Piece
                Board.MovePiece(board, move.SrcPosition, move.DstPosition, ChessPieceType.Queen);

                //We Generate Valid Moves for Board
                PieceValidMoves.GenerateValidMoves(board);

2 weird things here:

1) ChessPieceType.Queen?

2) I suppose the GenerateValidMoves generates valid moves for *both* sides, otherwise the code is most likely wrong as you didn't swap movingSide after executing the move, so moves for the wrong side would get generated. If that's not it, this call should probably go before EvaluateMoves for performance reasons anyway. (And possibly correctness, if it isn't called at the top level first before starting a search).

1) ChessPieceType.Queen tells the MovePiece Method to promote to Queen if promotion is available. I have to fix this in the future but for now my chess engine always promotes and assumes you will promote to queen.

2) I think you are correct, I don't actully need the MovingSide variable since it should always be equal to examineBoard's MovingSide variable. The GenerateValid moves always uses the chess boards Moving Side variable and the MovePiece method flips it.

[Sven]

2) I think you are correct, I don't actully need the MovingSide variable since it should always be equal to examineBoard's MovingSide variable. The GenerateValid moves always uses the chess boards Moving Side variable and the MovePiece method flips it.

Which is what I expected. (EDIT: I think you actually answered on my previous post although it looks as if you replied to GCP.)

Does GenerateValidMoves() generate all moves, or just captures and promotions? In the former case, how do you select captures and promotions as the only moves to be made during qsearch?

Sven

[aberent]

2) I think you are correct, I don't actully need the MovingSide variable since it should always be equal to examineBoard's MovingSide variable. The GenerateValid moves always uses the chess boards Moving Side variable and the MovePiece method flips it.

Which is what I expected. (EDIT: I think you actually answered on my previous post although it looks as if you replied to GCP.)

Does GenerateValidMoves() generate all moves, or just captures and promotions? In the former case, how do you select captures and promotions as the only moves to be made during qsearch?

Sven

Generate Valid Moves generates all valid moves including non captures.

Evaluate Moves (this method assings a pseudo score to all the moves for sorting) takes a boolean flag called capturesOnly (its always true in Quiescence). If true then Evaluate Moves returns only capture moves.

Is that wrong should I be filtering out captures in GenerateValidMoves(). This would be faster but will miss some data that I need in the Score Evaluation like what piece is protecting what piece.

[Gian-Carlo Pascutto]

Evaluate Moves (this method assings a pseudo score to all the moves for sorting) takes a boolean flag called capturesOnly (its always true in Quiescence). If true then Evaluate Moves returns only capture moves.

In this case the code posted looks correct to me.

I'd proceed with feeding it positions with known result, starting with a position with no (possible) captures, one winning capture, a capture sequence of 2 captures, etc, until it goes wrong.

[aberent]

Evaluate Moves (this method assings a pseudo score to all the moves for sorting) takes a boolean flag called capturesOnly (its always true in Quiescence). If true then Evaluate Moves returns only capture moves.

In this case the code posted looks correct to me.

I'd proceed with feeding it positions with known result, starting with a position with no (possible) captures, one winning capture, a capture sequence of 2 captures, etc, until it goes wrong.

That is a good idea, do you know any websites that post FENs for positions like that?