Problems when implementing checks in qsearch

[metax]

A few days ago I implemented checks in the first two plies of quiescence search. This fixed serious tactical weaknesses in my engine. However, I recognized that my nps went down significantly after implementing this. This is because calls to my rather inefficient function that checks for check have increased very much because I generate all moves in the first two plies of qsearch and have to make them all, then check whether the move delivers check, and throw it out if not. This is very expensive. Is there a better way of trying checks in quiescence?

[jwes]

A few days ago I implemented checks in the first two plies of quiescence search. This fixed serious tactical weaknesses in my engine. However, I recognized that my nps went down significantly after implementing this. This is because calls to my rather inefficient function that checks for check have increased very much because I generate all moves in the first two plies of qsearch and have to make them all, then check whether the move delivers check, and throw it out if not. This is very expensive. Is there a better way of trying checks in quiescence?

A couple possibilities. You could use attack tables to see if the move could give check (or discovered check) and only try the non-captures that could, or at the start of the move generation find all the squares that attack the king for each piece type, and only try those non-captures that give check (for possible discovered checks, test if a queen on the from square would give check, calculate the line between the king and the from square, and extend it looking for pieces that can move on that line.).

[hgm]

Getting checking moves is indeed expensive. In joker I get discovered checks by running through the slider list of the stm, (typically 5 pieces), and do a 0x88 alignment test with the opponent King. Usually I am done then, but in the occasional case there is a match, I scan the ray on the board starting at the opponent King until I reach a piece. If that is an opponent piece, I cannot give a discovered check along that ray. (The piece might be pinned, but that is not interesting at that moment.) If it is my own piece, I continue the ray scan until I reach another piece; if that is the original slider, moving the first piece off the ray would be a discovered check.

So I remember that piece, and the direction of the ray. After that, the discovered checks are easily generated.

For direct checks, I did not find anything to speed it up above doinf the 0x88 test between toSquare and opponent King for enery individual move. I thought about making a table indexed by the 0x88 step from piece to opponent King for each piece type, tabulating where that piece could deliver check if the board were empty. For most pieces that is 2 squares (indicated relative to, say, opponent King), and you would then have to do separate 0x88 tests for the first and second step. That means for each piece you have to try only 2 moves. But for Queens it is not competitive, as there are potentially 12 squares where it could deliver a check...

A better approach might be to integrate this with the evaluation code for the Pawn shield. By making the program aware of open rays to your King, (e.g. marking them on an auxiliary board), you have a simple test if moves land on a square where a piece of that type does deliver check. It is expensive to update this when an exposed King moves, but as King moves tend to produce low scores, you could sort them in the back, so you won't get to search them so often.

[Edmund]

Getting checking moves is indeed expensive. In joker I get discovered checks by running through the slider list of the stm, (typically 5 pieces), and do a 0x88 alignment test with the opponent King. Usually I am done then, but in the occasional case there is a match, I scan the ray on the board starting at the opponent King until I reach a piece. If that is an opponent piece, I cannot give a discovered check along that ray. (The piece might be pinned, but that is not interesting at that moment.) If it is my own piece, I continue the ray scan until I reach another piece; if that is the original slider, moving the first piece off the ray would be a discovered check.

So I remember that piece, and the direction of the ray. After that, the discovered checks are easily generated.

For direct checks, I did not find anything to speed it up above doinf the 0x88 test between toSquare and opponent King for enery individual move. I thought about making a table indexed by the 0x88 step from piece to opponent King for each piece type, tabulating where that piece could deliver check if the board were empty. For most pieces that is 2 squares (indicated relative to, say, opponent King), and you would then have to do separate 0x88 tests for the first and second step. That means for each piece you have to try only 2 moves. But for Queens it is not competitive, as there are potentially 12 squares where it could deliver a check...

A better approach might be to integrate this with the evaluation code for the Pawn shield. By making the program aware of open rays to your King, (e.g. marking them on an auxiliary board), you have a simple test if moves land on a square where a piece of that type does deliver check. It is expensive to update this when an exposed King moves, but as King moves tend to produce low scores, you could sort them in the back, so you won't get to search them so often.

One could use the constraint that knights and bishops may only be tested if on the same colour-square as the king.

And I remember having the discussion about how to calculate the intersection squares of a certain piece and the opponent king in this forum about a year ago. This would save doing the table lookups. Gerd posted all the results on the chess programming wiki: http://chessprogramming.wikispaces.com/ ... on+Squares

Still you are right, for the queen this doesn't seem to be an option.

[jesper_nielsen]

Getting checking moves is indeed expensive. In joker I get discovered checks by running through the slider list of the stm, (typically 5 pieces), and do a 0x88 alignment test with the opponent King. Usually I am done then, but in the occasional case there is a match, I scan the ray on the board starting at the opponent King until I reach a piece. If that is an opponent piece, I cannot give a discovered check along that ray. (The piece might be pinned, but that is not interesting at that moment.) If it is my own piece, I continue the ray scan until I reach another piece; if that is the original slider, moving the first piece off the ray would be a discovered check.

So I remember that piece, and the direction of the ray. After that, the discovered checks are easily generated.

For direct checks, I did not find anything to speed it up above doinf the 0x88 test between toSquare and opponent King for enery individual move. I thought about making a table indexed by the 0x88 step from piece to opponent King for each piece type, tabulating where that piece could deliver check if the board were empty. For most pieces that is 2 squares (indicated relative to, say, opponent King), and you would then have to do separate 0x88 tests for the first and second step. That means for each piece you have to try only 2 moves. But for Queens it is not competitive, as there are potentially 12 squares where it could deliver a check...

A better approach might be to integrate this with the evaluation code for the Pawn shield. By making the program aware of open rays to your King, (e.g. marking them on an auxiliary board), you have a simple test if moves land on a square where a piece of that type does deliver check. It is expensive to update this when an exposed King moves, but as King moves tend to produce low scores, you could sort them in the back, so you won't get to search them so often.

One could use the constraint that knights and bishops may only be tested if on the same colour-square as the king.

And I remember having the discussion about how to calculate the intersection squares of a certain piece and the opponent king in this forum about a year ago. This would save doing the table lookups. Gerd posted all the results on the chess programming wiki: http://chessprogramming.wikispaces.com/ ... on+Squares

Still you are right, for the queen this doesn't seem to be an option.

If you are using bitboards, it can be quite easy to find checking moves. At least if your move generator takes a bitboard mask with potential to-squares.

So for captures the mask is opponent pieces.
And for non-captures the mask is the empty squares.

So the general algorithm for generating checks with sliding pieces (pawns and knights are simple to do!) is this:
1. Generate a bitboard mask with the queen moves as if the king you want to check was a queen.
2. Call "GenerateQueenMoves" with the mask is input. That way pseudo legal queen moves that actually end up giving check is generated.
3. Call "GenerateRookMoves" with the mask AND unhinderedRookMoves[kingSquare].
4. Call "GenerateBishopMoves" with the mask AND unhinderedBishopMoves[kingSquare]

In my implementation when I generate the queen move mask, I only consider moves to empty squares, since captures that give check are generated as part of the normal q-search.

Kind regards,
Jesper

Edit: This of course do not consider discovered checks!

[metax]

Unfortunately, I am using a mailbox board.

[Greg Strong]

Interesting discussion. Let me ask a related question ...

Let's say I can generate all checks except discovered checks very quickly. Is it possible that generating some but not all checks could still give a program a boost in stregth, or is generating checks in the first level (or two) of qsearch an all-or-nothing proposition?

[jesper_nielsen]

Interesting discussion. Let me ask a related question ...

Let's say I can generate all checks except discovered checks very quickly. Is it possible that generating some but not all checks could still give a program a boost in stregth, or is generating checks in the first level (or two) of qsearch an all-or-nothing proposition?

I do not think it is all-or-nothing.

My own tests indicate that my program is definitely stronger generating one set of checks in q-search, even though I do not generate discovered checks. But maybe it is time to recheck it!

And there are other applications of this check generation code besides in q-search.

It can be used to do a slightly safer type of pruning. If the evalution of a position is far below alpha, then instead of pruning the subtree completely, it is possible to just prune the quiet moves.
In this case only generate captures and checks. So in essence only try moves that potentially influence the evaluation of the position in a major way. Since these are the moves most likely to get the score above alpha.

And for engines, such as my own , that are not deep searchers, this could help with the tactical abilities. It certainly helps Pupsi.

Kind regards,
Jesper

[Uri Blass]

A few days ago I implemented checks in the first two plies of quiescence search. This fixed serious tactical weaknesses in my engine. However, I recognized that my nps went down significantly after implementing this. This is because calls to my rather inefficient function that checks for check have increased very much because I generate all moves in the first two plies of qsearch and have to make them all, then check whether the move delivers check, and throw it out if not. This is very expensive. Is there a better way of trying checks in quiescence?

You do not need to make all legal moves to find the checks and this is a bad implementation.

You can start by finding the discovered check that are checks by a piece that does not move.

In most cases it is easy to find that you have no discovered check by queen roook or bishop based on the squares of these pieces or based on the fact thqat there is no single piece with the same color between them and the opponent king.

In case that you find that there are discovered checks you also find the piece that need to move and it is easy to find based on the to square of the piece if the piece threat indirect check.

Later you can find knight direct checks.

usually it is easy to find that there is no knight direct check based on a special table that you can build for knight distance between squares.

for example if there is knight at b1 and king at g8 it is obvious based on the knight distance between b1 and g8 that the knight at b1 cannot check the king at g8.

Even if the knight can give checks you can build a special table to save making non check moves by the knight

For example if the white knight is at e4 and the black king is at e8 you can have in your array:
knightchecks[e4][e8][0]=d6(e4 e8 d6 are of course represented by numbers in your program)
knightchecks[e4][e8][1]=f6

This mean that you only need to check if e4d6 e4f6 are legal and they may be illegal because there may be piece of the same color at one of them.

Later you can find direct checks by other pieces and again you can use tables that you should build for that purpose.


Uri

[mcostalba]

It can be used to do a slightly safer type of pruning. If the evalution of a position is far below alpha, then instead of pruning the subtree completely, it is possible to just prune the quiet moves.
In this case only generate captures and checks. So in essence only try moves that potentially influence the evaluation of the position in a major way. Since these are the moves most likely to get the score above alpha.

Can you please explain how this differs from reducing more low scored nodes ?


Just to be more clear, if you reduce depth more you reach qsearch earlier and you have the same result but in an uniform and coherent way without adding yet another (redundant) trick.