Page 1 of 3

Quiescent search, and side to move is in check

Posted: Fri Feb 08, 2013 6:52 pm
by zullil
My qsearch starts by evaluating the current position statically, to determine a "stand pat" score. If this doesn't exceed beta, I update alpha if necessary, and then generate and sort all captures and continue by calling qsearch recursively. If no captures exist, I return alpha if there are any legal moves at all, and either -MATE_SCORE or STALEMATE_SCORE if no legal moves exist. Note that I don't look at the very start to see if the side to move is in check (which seems bad of me, since in that case the stand pat score may well overestimate the value of the position). In my main search, if the depth is 1 (ie, one step away from a leaf) and the side-to-go is in check, I increment depth to 2 before recursing, so that qsearch isn't called with the side-to-move in check.

But now it occurs to me that qsearch calls itself recursively, and as implemented currently, might do so with the side-to-go in check (ie, an initial capture has placed the opposing king in check, and now I'm calling qsearch again).

So it now seems to me that I need to redo my qsearch, because I must consider two different states at the outset, depending on whether or not the side-to-go is in check when qsearch starts. My check extension in the regular search won't save me, since qsearch also calls itself. Is this correct?

I hope this post makes sense. But if not, I'm certain to learn something or to clear up some misunderstanding I have. :D Thanks.

Re: Quiescent search, and side to move is in check

Posted: Fri Feb 08, 2013 7:13 pm
by ZirconiumX
zullil wrote:My qsearch starts by evaluating the current position statically, to determine a "stand pat" score. If this doesn't exceed beta, I update alpha if necessary, and then generate and sort all captures and continue by calling qsearch recursively. If no captures exist, I return alpha if there are any legal moves at all, and either -MATE_SCORE or STALEMATE_SCORE if no legal moves exist.
All very standard stuff.
Note that I don't look at the very start to see if the side to move is in check (which seems bad of me, since in that case the stand pat score may well overestimate the value of the position).
It's a little worse than that. You _cannot_ stand-pat in a check position - it isn't quiescent.
In my main search, if the depth is 1 (ie, one step away from a leaf) and the side-to-go is in check, I increment depth to 2 before recursing, so that qsearch isn't called with the side-to-move in check.
I can see why you do that.
But now it occurs to me that qsearch calls itself recursively, and as implemented currently, might do so with the side-to-go in check (ie, an initial capture has placed the opposing king in check, and now I'm calling qsearch again).
That would be fine if it was called in check.
So it now seems to me that I need to redo my qsearch, because I must consider two different states at the outset, depending on whether or not the side-to-go is in check when qsearch starts.
Sort of. As long as you don't stand-pat when in check you'll be OK.
My check extension in the regular search won't save me, since qsearch also calls itself. Is this correct?
Yes. The QSearch may end up in a position far away from where the search ended.

Matthew:out
I hope this post makes sense. But if not, I'm certain to learn something or to clear up some misunderstanding I have. :D Thanks.

Re: Quiescent search, and side to move is in check

Posted: Fri Feb 08, 2013 7:47 pm
by zullil
Thanks, Matthew.

But it also seems to me that if side-to-move is in check at the start of qsearch then I should search all legal moves, not just captures. Right?
And there's no reason to compute a stand_pat score here, since I must search all the moves and I can't return the stand_pat score in any case.

Re: Quiescent search, and side to move is in check

Posted: Fri Feb 08, 2013 7:53 pm
by kbhearn
One option is not to have a seperate qsearch, but just extra condition(s) in the main search for the parts that qsearch needs:
1) in check - generate all evasions and try them regardless of depth remaining, do not reduce depth remaining
2) if depth is in qsearch generate stand pat score and cutoff if possible
3) try captures
4) try noncaptures if not qsearch

Re: Quiescent search, and side to move is in check

Posted: Fri Feb 08, 2013 7:53 pm
by ZirconiumX
zullil wrote:Thanks, Matthew.

But it also seems to me that if side-to-move is in check at the start of qsearch then I should search all legal moves, not just captures. Right?
And there's no reason to compute a stand_pat score here, since I must search all the moves and I can't return the stand_pat score in any case.
Some people do call AlphaBeta with a depth of 1 for that. I, personally, do not. It hugely drains your speed.

Matthew:out

Re: Quiescent search, and side to move is in check

Posted: Fri Feb 08, 2013 7:58 pm
by zullil
ZirconiumX wrote:
zullil wrote:Thanks, Matthew.

But it also seems to me that if side-to-move is in check at the start of qsearch then I should search all legal moves, not just captures. Right?
And there's no reason to compute a stand_pat score here, since I must search all the moves and I can't return the stand_pat score in any case.
Some people do call AlphaBeta with a depth of 1 for that. I, personally, do not. It hugely drains your speed.

Matthew:out
May I ask what you do? Or is it a trade secret? :D

Re: Quiescent search, and side to move is in check

Posted: Fri Feb 08, 2013 8:08 pm
by bob
zullil wrote:My qsearch starts by evaluating the current position statically, to determine a "stand pat" score. If this doesn't exceed beta, I update alpha if necessary, and then generate and sort all captures and continue by calling qsearch recursively. If no captures exist, I return alpha if there are any legal moves at all, and either -MATE_SCORE or STALEMATE_SCORE if no legal moves exist. Note that I don't look at the very start to see if the side to move is in check (which seems bad of me, since in that case the stand pat score may well overestimate the value of the position). In my main search, if the depth is 1 (ie, one step away from a leaf) and the side-to-go is in check, I increment depth to 2 before recursing, so that qsearch isn't called with the side-to-move in check.

But now it occurs to me that qsearch calls itself recursively, and as implemented currently, might do so with the side-to-go in check (ie, an initial capture has placed the opposing king in check, and now I'm calling qsearch again).

So it now seems to me that I need to redo my qsearch, because I must consider two different states at the outset, depending on whether or not the side-to-go is in check when qsearch starts. My check extension in the regular search won't save me, since qsearch also calls itself. Is this correct?

I hope this post makes sense. But if not, I'm certain to learn something or to clear up some misunderstanding I have. :D Thanks.
Here's a simple idea.

Make the value of a king something large. Larger than your mate score. Now when you reach q-search, if you can capture the opponent's king, that move will ALWAYS refute the move at the previous ply. And this works anywhere in the q-search so that you don't have branches that contain illegal moves...

Re: Quiescent search, and side to move is in check

Posted: Fri Feb 08, 2013 8:09 pm
by bob
zullil wrote:Thanks, Matthew.

But it also seems to me that if side-to-move is in check at the start of qsearch then I should search all legal moves, not just captures. Right?
And there's no reason to compute a stand_pat score here, since I must search all the moves and I can't return the stand_pat score in any case.
Simply too expensive. Some of us do this sort of thing at the first ply or two or three, but beyond that, the tree will explode and your depth will tank...

Re: Quiescent search, and side to move is in check

Posted: Fri Feb 08, 2013 8:41 pm
by zullil
Thanks for the help. I think I've gotten it clear in my head now.

Re: Quiescent search, and side to move is in check

Posted: Fri Feb 08, 2013 8:48 pm
by Evert
I recently fixed this exact same issue in Jazz.

I already generated all evasions when in check (not just captures), but I was still allowing stand-pat while in check. Fixing that (and not calling the static evaluation when it isn't needed, as when you are in check) was worth a handful of elo points (I don't remember exactly, something in the order of 10 I think).