Quiescent search, and side to move is in check

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
zullil
Posts: 6442
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

Quiescent search, and side to move is in check

Post by zullil » Fri Feb 08, 2013 6:52 pm

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.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

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

Post by ZirconiumX » Fri Feb 08, 2013 7:13 pm

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.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

zullil
Posts: 6442
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

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

Post by zullil » Fri Feb 08, 2013 7:47 pm

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.

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

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

Post by kbhearn » Fri Feb 08, 2013 7:53 pm

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

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

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

Post by ZirconiumX » Fri Feb 08, 2013 7:53 pm

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
Some believe in the almighty dollar.

I believe in the almighty printf statement.

zullil
Posts: 6442
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

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

Post by zullil » Fri Feb 08, 2013 7:58 pm

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

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

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

Post by bob » Fri Feb 08, 2013 8:08 pm

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

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

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

Post by bob » Fri Feb 08, 2013 8:09 pm

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

zullil
Posts: 6442
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

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

Post by zullil » Fri Feb 08, 2013 8:41 pm

Thanks for the help. I think I've gotten it clear in my head now.

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

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

Post by Evert » Fri Feb 08, 2013 8:48 pm

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

Post Reply