quiescence search (best practices)

[thevinenator]

i implemented a quiescence search extension based on a number of code snippets found here and there including Mr. Moreland's code in Gerbil.

all seemed to work well till I ran across a condition where a capture also caused a check. well, things went sour after that and my Move Generator added a BxK (king) move. I don't bother to check for that in the make move code because it can't really happen, but since i'm only checking captures in the QS, it manifested itself.

so i searched a bit more and found a comment in Gerbil code about ignoring "checks", but in this case, that would also ignore a perfectly good capture.

i could tweak the move generator to ignore King captures, but that could mess up moves down the tree, or i could do what was written regarding Cray Blitz in the Computer Chess Compendium

"if the side on the move is in check, all moves must be tried so that search can be sure that is not mate; and, these two checking plies do not count checking moves that are also captures."

or, are there more options?

[Toadofsky]

I don't claim to know the best practice, but a practical solution may be to allow generation of illegal moves such as BxK (which would only occur in illegal positions) and to disallow move generation when the player to move has no king.

[hyatt]

You are slightly misunderstanding "ignoring checks." What he means is that he will play the move, but doesn't look to see if it checks the opponent. That wastes time. All you have to do is generate moves in the capture search, and if you happen to generate a move that captures the opponent's king, the move he played at the previous ply was simply illegal. Back up to the previous ply and try a different move immediately...

[thevinenator]

You are slightly misunderstanding "ignoring checks." What he means is that he will play the move, but doesn't look to see if it checks the opponent. That wastes time. All you have to do is generate moves in the capture search, and if you happen to generate a move that captures the opponent's king, the move he played at the previous ply was simply illegal. Back up to the previous ply and try a different move immediately...

i agree, checking to see if the king is in check is expensive here. i do that in my main move generation but i removed it for the QSearch. what you are describing, i'm guessing, how the pseudo-legal tree searches are performed. that, i'll admit, i haven't tried before, so bear with me in my next paragraph when i ask about returning values.

i can detect the "bad" capture prior to making it, so that is fine. When you say "back up to the previous ply", do you mean the side that tried to capture the king or the side that has the king being captured? if i catch the bad move prior to making it, i'm still in the loop of the side that was trying to capture the king. i would simply skip that move, but i don't think that is what you meant so that implies returning to the previous ply, but if so, what value do i return? depending on the perspective, taking a king is ether really good or really bad! LOL is returning a value all that is required so the previous level can continue trying other moves?

[hyatt]

You are slightly misunderstanding "ignoring checks." What he means is that he will play the move, but doesn't look to see if it checks the opponent. That wastes time. All you have to do is generate moves in the capture search, and if you happen to generate a move that captures the opponent's king, the move he played at the previous ply was simply illegal. Back up to the previous ply and try a different move immediately...

i agree, checking to see if the king is in check is expensive here. i do that in my main move generation but i removed it for the QSearch. what you are describing, i'm guessing, how the pseudo-legal tree searches are performed. that, i'll admit, i haven't tried before, so bear with me in my next paragraph when i ask about returning values.

i can detect the "bad" capture prior to making it, so that is fine. When you say "back up to the previous ply", do you mean the side that tried to capture the king or the side that has the king being captured? if i catch the bad move prior to making it, i'm still in the loop of the side that was trying to capture the king. i would simply skip that move, but i don't think that is what you meant so that implies returning to the previous ply, but if so, what value do i return? depending on the perspective, taking a king is ether really good or really bad! LOL is returning a value all that is required so the previous level can continue trying other moves?

The side that "hung the king". IE I capture your king, I return +infinity as the score, which gets back to you as -infinity through the recursive negamax call, and there's no way you would accept that score over either standing pat or trying another capture... Since most captures are not illegal, this saves time over testing every capture for legality which is slower overall. Results should be exactly the same, except for the time expended.

[thevinenator]

You are slightly misunderstanding "ignoring checks." What he means is that he will play the move, but doesn't look to see if it checks the opponent. That wastes time. All you have to do is generate moves in the capture search, and if you happen to generate a move that captures the opponent's king, the move he played at the previous ply was simply illegal. Back up to the previous ply and try a different move immediately...

i agree, checking to see if the king is in check is expensive here. i do that in my main move generation but i removed it for the QSearch. what you are describing, i'm guessing, how the pseudo-legal tree searches are performed. that, i'll admit, i haven't tried before, so bear with me in my next paragraph when i ask about returning values.

i can detect the "bad" capture prior to making it, so that is fine. When you say "back up to the previous ply", do you mean the side that tried to capture the king or the side that has the king being captured? if i catch the bad move prior to making it, i'm still in the loop of the side that was trying to capture the king. i would simply skip that move, but i don't think that is what you meant so that implies returning to the previous ply, but if so, what value do i return? depending on the perspective, taking a king is ether really good or really bad! LOL is returning a value all that is required so the previous level can continue trying other moves?

The side that "hung the king". IE I capture your king, I return +infinity as the score, which gets back to you as -infinity through the recursive negamax call, and there's no way you would accept that score over either standing pat or trying another capture... Since most captures are not illegal, this saves time over testing every capture for legality which is slower overall. Results should be exactly the same, except for the time expended.

Thank you for the clarification. Makes perfect sense now that you've explained it. i'll implement it.

[thevinenator]

on one of Bruce Moreland's chess programming page topics on QSearch, he makes a call to "AlphaBeta" when the side to move is in check.

i'm i correct to assume that this version of AB would not be using the TT either for entry or exit?

int Quies(int alpha, int beta)
{
if (InCheck())
return AlphaBeta(1, alpha, beta);
val = Evaluate();
if (val >= beta)
...

[hyatt]

Probably it does, for simplicity. If you want yet another search routine, then you can do whatever you want. I don't store qsearch nodes myself, period. So I have a separate q-search (QuiesceEvasions()) that gets me out of check by the usual legal move generator approach to avoid the slowness of 80% (or more) of the moves hanging the king.

[thevinenator]

it's been a while since I looked into this thread but I still haven't figured out all the possible outcomes.

Bruce states that his use of the AlphaBeta() can detect mate if they involve capture. The AlphaBeta() is called from within QSearch when the STM is in check. The checking move by the opponent doesn't necessarily need to be a capture in order to facilitate mate.

Also what does AlphaBeta() return in the case when a mate isn't found, the Eval() ? The opponent can be in check but have "outs".

[H.G.Muller]

AlphaBeta has a depth parameter, and from an in-check QS node it would be called with depth=1. Which is enough to play all evasions, and call QS after them. QS would see capture of a King, and presumably return a +INF score on that. So all illegal evasions would be punished, and won't increase the bestScore (which starts at -INF for a d=1 AlphaBeta search). So if there are no legal evasions (and you are thus chackmated), the bestScore will remain at -INF. If one of the evasions is legal, QS will return the QS score, and the AlphaBeta will return the best of these. Which could be the static eval of the position after the evasion, but could also be better, if there still are good captures there (e.g. because the check was a Knight's fork, and after you stepped the King out of check N x Q follows). In that case the static eval of a later node will be returned. (It could of course be that such a follow-up capture checks again, and accidentally checkmates.)