Problems when implementing checks in qsearch

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Problems when implementing checks in qsearch

Post by metax » Wed Feb 03, 2010 4:05 pm

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
Posts: 776
Joined: Sat Jul 01, 2006 5:11 am

Re: Problems when implementing checks in qsearch

Post by jwes » Wed Feb 03, 2010 6:07 pm

metax wrote: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.).

User avatar
hgm
Posts: 23081
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Problems when implementing checks in qsearch

Post by hgm » Wed Feb 03, 2010 7:48 pm

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
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: Problems when implementing checks in qsearch

Post by Edmund » Wed Feb 03, 2010 8:10 pm

hgm wrote: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

Re: Problems when implementing checks in qsearch

Post by jesper_nielsen » Thu Feb 04, 2010 9:25 am

Edmund wrote:
hgm wrote: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
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Re: Problems when implementing checks in qsearch

Post by metax » Thu Feb 04, 2010 1:25 pm

Unfortunately, I am using a mailbox board.

User avatar
Greg Strong
Posts: 388
Joined: Sun Dec 21, 2008 5:57 pm
Location: Washington, DC

Re: Problems when implementing checks in qsearch

Post by Greg Strong » Fri Feb 05, 2010 12:06 am

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

Re: Problems when implementing checks in qsearch

Post by jesper_nielsen » Fri Feb 05, 2010 8:19 am

Greg Strong wrote: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! :D

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 :oops:, that are not deep searchers, this could help with the tactical abilities. It certainly helps Pupsi.

Kind regards,
Jesper

Uri Blass
Posts: 8349
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Problems when implementing checks in qsearch

Post by Uri Blass » Fri Feb 05, 2010 8:56 am

metax wrote: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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Problems when implementing checks in qsearch

Post by mcostalba » Fri Feb 05, 2010 9:20 am

jesper_nielsen wrote: 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.

Post Reply