quiescence search (best practices)

Code, algorithms, languages, construction...
Post Reply
thevinenator
Posts: 68
Joined: Tue Jun 02, 2015 11:02 pm
Real Name: Vince

quiescence search (best practices)

Post by thevinenator » Thu Jul 02, 2015 12:57 am

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?
"An Engine's strength flows from the Search. But beware, pruning, extensions, reductions; the dark side of the Search are they. Once you start down the dark path, it will dominate and consume you, as it has to so many developers before.” -- Yoda

Toadofsky
Posts: 5
Joined: Thu Jul 02, 2015 4:35 pm
Real Name: Daniel Dugovic

Re: quiescence search (best practices)

Post by Toadofsky » Thu Jul 02, 2015 5:25 pm

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
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: quiescence search (best practices)

Post by hyatt » Fri Jul 03, 2015 1:59 am

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
Posts: 68
Joined: Tue Jun 02, 2015 11:02 pm
Real Name: Vince

Re: quiescence search (best practices)

Post by thevinenator » Mon Jul 06, 2015 1:47 pm

hyatt wrote: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?
"An Engine's strength flows from the Search. But beware, pruning, extensions, reductions; the dark side of the Search are they. Once you start down the dark path, it will dominate and consume you, as it has to so many developers before.” -- Yoda

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: quiescence search (best practices)

Post by hyatt » Tue Jul 07, 2015 3:37 am

thevinenator wrote:
hyatt wrote: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
Posts: 68
Joined: Tue Jun 02, 2015 11:02 pm
Real Name: Vince

Re: quiescence search (best practices)

Post by thevinenator » Tue Jul 07, 2015 1:09 pm

hyatt wrote:
thevinenator wrote:
hyatt wrote: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.
"An Engine's strength flows from the Search. But beware, pruning, extensions, reductions; the dark side of the Search are they. Once you start down the dark path, it will dominate and consume you, as it has to so many developers before.” -- Yoda

thevinenator
Posts: 68
Joined: Tue Jun 02, 2015 11:02 pm
Real Name: Vince

Re: quiescence search (best practices)

Post by thevinenator » Thu Aug 27, 2015 2:10 am

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)
...
"An Engine's strength flows from the Search. But beware, pruning, extensions, reductions; the dark side of the Search are they. Once you start down the dark path, it will dominate and consume you, as it has to so many developers before.” -- Yoda

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: quiescence search (best practices)

Post by hyatt » Thu Aug 27, 2015 5:05 pm

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
Posts: 68
Joined: Tue Jun 02, 2015 11:02 pm
Real Name: Vince

Re: quiescence search (best practices)

Post by thevinenator » Mon Apr 25, 2016 12:53 am

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".
"An Engine's strength flows from the Search. But beware, pruning, extensions, reductions; the dark side of the Search are they. Once you start down the dark path, it will dominate and consume you, as it has to so many developers before.” -- Yoda

H.G.Muller
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: quiescence search (best practices)

Post by H.G.Muller » Thu May 12, 2016 6:53 am

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.)

Post Reply