Quiescent search, and side to move is in check

[zullil]

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

It is comforting to this novice that at least what I asked about made some sense. If my fix buys my engine a "handful" of ELO points, then there's a good chance that it might break the 1000 level. In other words, my program is pretty poor at chess. Then again, so am I.

[Sven]

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

1. At qsearch root the moving side is not in check (due to check extension in full-width search).
2. You do not generate extra non-capturing check moves within qsearch.
3. So at any qsearch node below the qsearch root the moving side can be in check through some capture.
4. You have normal legality checking after making a move, so missing illegal moves is not an issue for you.
5. Now three of your choices are:

a) Continue to use stand-pat, do not detect being in check, and possibly miss that you are mated (you will see that you have no legal capture moves but since you do not know that you are in check and you also do not know whether there are legal quiet evasions available you will return the stand-pat score).

b) Detect being in check first, and if you are, always search all check evasions, do not use stand-pat, and do not miss being mated. Continue normal qsearch below those check evasions.

c) Like b) but restrict this to the first N plies of qsearch and switch to a) below N.

I think Bob meant that some authors apply variant c). I don't know for sure but what I remember is that some authors generate extra non-capturing check moves within the first N plies of qsearch. That's something entirely different, and I'm not sure whether this is what Bob had in mind. At least I don't really believe that the tree explodes when searching all check evasions during qsearch. Generating extra check moves for more than a few plies will cause tree explosion, for sure, but here we are talking about check evasions as a reaction on captures that happen to be also checks. There is certainly a significant additional computation effort for check detection. The big question is what is more important: the inaccuracy of occasionally missing a mate caused by a checking capture, or the slowdown by testing for in-check and additionally searching some more moves (i.e., all quiet evasions) when being in check.

In Surprise I did a). In KnockOut I started with a) but later on switched to b), and it did not hurt (but was also not a huge improvement). In my current engine I plan to use b) and possibly experiment with c).

Sven

[zullil]

1. At qsearch root the moving side is not in check (due to check extension in full-width search).
2. You do not generate extra non-capturing check moves within qsearch.
3. So at any qsearch node below the qsearch root the moving side can be in check through some capture.
4. You have normal legality checking after making a move, so missing illegal moves is not an issue for you.

Sven

Yes, 1--4 all hold for my current implementation. Thanks for presenting this succinctly.

Now here's what I was doing in my qsearch function:

a) Without any test to see if side-to-move is in check, calculate a stand pat score using static evaluation.

b) If stand pat score > beta return beta.

c) If stand pat score > alpha, let alpha = stand pat score.

d) Generate all legal captures.

e) If no captures exist, see if any legal moves exist. If so, return alpha. If not, test if in check, and return -MATE_SCORE if yes or DRAW_SCORE if no.

f) If captures do exist, sort in some fashion from best to worst and score each by calling qsearch recursively.


So by e), it seems that I can't miss it if side-to-go is in checkmate (or stalemate). But what if I reach e) and side-to-go's only move is to block check by interposing the queen, which will then be captured next move?

In this case I might return a stand-pat score that completely misses the fact that I'm about to lose my queen.

Isn't this the weakness in my current implementation? But if so, it seems I would need test for being in check at the start of my qsearch routine, and I would need to generate and search all check evasions, not just captures. Is the time spent on the extra checking and move generation worthwhile?

Thanks.

[AlvaroBegue]

I've been writing a chess engine from scratch for the last three weeks or so. I am trying to get all the basics down, without anything too fancy.

This is the exact code of my current quiescence search:

Code: Select all

int Engine::quiescence_search(int alpha, int beta, int from_root) {
  ++nodes_searched;
  bool in_check = board.is_in_check();
  
  if (!in_check) {
    int stand_pat_score = evaluate(board);
    if (stand_pat_score > alpha) {
      alpha = stand_pat_score;
      if (alpha >= beta)
        return alpha;
    }
  }
  
  unsigned moves[256];
  int n_moves = board.generate_captures(moves);
  sort_MVV_LVA(board, moves, n_moves);
  if (in_check)
    n_moves += board.generate_noncaptures(moves + n_moves);
  
  int legal_moves = 0;
  
  for &#40;int i=0; i<n_moves; ++i&#41; &#123;
    if (!in_check && board.SEE&#40;moves&#91;i&#93;) < 0&#41;
      continue;
    int score = -7999 + from_root;
    board.make_move&#40;moves&#91;i&#93;);
    if (!board.is_king_exposed&#40;)) &#123;
      score = -quiescence_search&#40;-beta, -alpha, from_root + 1&#41;;
      ++legal_moves;
    &#125;
    board.undo_move&#40;);
    if &#40;score > alpha&#41; &#123;
      alpha = score;
      if &#40;alpha >= beta&#41;
        break;
    &#125;
  &#125;
  
  if &#40;in_check && legal_moves == 0&#41;
    return -7999 + from_root;
  
  return alpha;
&#125;

[Joost Buijs]

1. At qsearch root the moving side is not in check (due to check extension in full-width search).
2. You do not generate extra non-capturing check moves within qsearch.
3. So at any qsearch node below the qsearch root the moving side can be in check through some capture.
4. You have normal legality checking after making a move, so missing illegal moves is not an issue for you.
5. Now three of your choices are:

a) Continue to use stand-pat, do not detect being in check, and possibly miss that you are mated (you will see that you have no legal capture moves but since you do not know that you are in check and you also do not know whether there are legal quiet evasions available you will return the stand-pat score).

b) Detect being in check first, and if you are, always search all check evasions, do not use stand-pat, and do not miss being mated. Continue normal qsearch below those check evasions.

c) Like b) but restrict this to the first N plies of qsearch and switch to a) below N.

I think Bob meant that some authors apply variant c). I don't know for sure but what I remember is that some authors generate extra non-capturing check moves within the first N plies of qsearch. That's something entirely different, and I'm not sure whether this is what Bob had in mind. At least I don't really believe that the tree explodes when searching all check evasions during qsearch. Generating extra check moves for more than a few plies will cause tree explosion, for sure, but here we are talking about check evasions as a reaction on captures that happen to be also checks. There is certainly a significant additional computation effort for check detection. The big question is what is more important: the inaccuracy of occasionally missing a mate caused by a checking capture, or the slowdown by testing for in-check and additionally searching some more moves (i.e., all quiet evasions) when being in check.

In Surprise I did a). In KnockOut I started with a) but later on switched to b), and it did not hurt (but was also not a huge improvement). In my current engine I plan to use b) and possibly experiment with c).

Sven

In my engine I use variant b) it does not cost much computational wise to search all evasions when in check because these are normally just a very few moves. And you can put some restrictions on the moves you search. For instance if the value of the evaluation is way below alpha it does not make sense to search quiet evasions because you won't get above alpha anyway. You can refine this in any way you want.

I generate direct checking moves at depth 0 and depth-1 (no discovered checks because this is rather time consuming to calculate in my engine). The tree grows a little, but it certainly adds some extra ELO.

[ZirconiumX]

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?

It is a Quiescence Search, to find a quiescent position to evaluate. That is its single purpose in my program.

Trying to detect mates is a little beyond what a QSearch is intended to do. So I simply don't stand-pat when in check, and try all the moves my evasion generator gives me.

Simple, and effective.

Matthew:out

[Sven]

1. At qsearch root the moving side is not in check (due to check extension in full-width search).
2. You do not generate extra non-capturing check moves within qsearch.
3. So at any qsearch node below the qsearch root the moving side can be in check through some capture.
4. You have normal legality checking after making a move, so missing illegal moves is not an issue for you.

Sven

Yes, 1--4 all hold for my current implementation. Thanks for presenting this succinctly.

Now here's what I was doing in my qsearch function:

a) Without any test to see if side-to-move is in check, calculate a stand pat score using static evaluation.

b) If stand pat score > beta return beta.

c) If stand pat score > alpha, let alpha = stand pat score.

d) Generate all legal captures.

e) If no captures exist, see if any legal moves exist. If so, return alpha. If not, test if in check, and return -MATE_SCORE if yes or DRAW_SCORE if no.

f) If captures do exist, sort in some fashion from best to worst and score each by calling qsearch recursively.


So by e), it seems that I can't miss it if side-to-go is in checkmate (or stalemate). But what if I reach e) and side-to-go's only move is to block check by interposing the queen, which will then be captured next move?

In this case I might return a stand-pat score that completely misses the fact that I'm about to lose my queen.

Isn't this the weakness in my current implementation? But if so, it seems I would need test for being in check at the start of my qsearch routine, and I would need to generate and search all check evasions, not just captures. Is the time spent on the extra checking and move generation worthwhile?

Thanks.

If the moving side is checkmated but the static eval is >= beta then you return the static eval due to your a)+b), so you miss the mate. Therefore your approach seems to be inconsistent. You'd better decide whether you want to detect checkmate in qsearch, or you don't care. If you care then I'd prefer to start with testing for in-check instead of evaluating.

Furthermore, your approach appears to be very inefficient. If no legal captures exist, i.e. the position is quiet, you try to generate all legal moves, and only if you don't find any, you test for in-check. That effectively turns many qsearch nodes into kind of full-width nodes and is very expensive. I'd rather go the other way as stated above, which also makes your code much clearer:
if (in check) -> perform evasion search with remaining depth 1 [no stand-pat, generate all legal moves, detect mate/stalemate]
else -> perform normal qsearch [use stand-pat, generate captures only, do not detect mate/stalemate]

The point you mentioned as possible weakness (your item e) ) will then be covered by the approach above: when being in check you will search all legal evasions, so you can't miss that the only legal evasion loses the queen by being forced to interpose it.

One more note: when detecting checkmate (in qsearch as well as full-width search) you'd better return -(MATE_SCORE-height), with "height" being the distance to the root node, since otherwise your engine will frequently choose to play a move that mates in more than one ply instead of the mate-in-1 move, which in turn leads to being unable to mate the opponent at all. It is not sufficient to see that you can mate "somehow" but you need to distinguish between shorter and longer paths to mate. You can easily figure this out with a trivial KQK example.

Sven

[Joerg Oster]

1. At qsearch root the moving side is not in check (due to check extension in full-width search).
2. You do not generate extra non-capturing check moves within qsearch.
3. So at any qsearch node below the qsearch root the moving side can be in check through some capture.
4. You have normal legality checking after making a move, so missing illegal moves is not an issue for you.

Sven

Yes, 1--4 all hold for my current implementation. Thanks for presenting this succinctly.

Now here's what I was doing in my qsearch function:

a) Without any test to see if side-to-move is in check, calculate a stand pat score using static evaluation.

b) If stand pat score > beta return beta.

c) If stand pat score > alpha, let alpha = stand pat score.

d) Generate all legal captures.

e) If no captures exist, see if any legal moves exist. If so, return alpha. If not, test if in check, and return -MATE_SCORE if yes or DRAW_SCORE if no.

f) If captures do exist, sort in some fashion from best to worst and score each by calling qsearch recursively.


So by e), it seems that I can't miss it if side-to-go is in checkmate (or stalemate). But what if I reach e) and side-to-go's only move is to block check by interposing the queen, which will then be captured next move?

In this case I might return a stand-pat score that completely misses the fact that I'm about to lose my queen.

Isn't this the weakness in my current implementation? But if so, it seems I would need test for being in check at the start of my qsearch routine, and I would need to generate and search all check evasions, not just captures. Is the time spent on the extra checking and move generation worthwhile?

Thanks.

If the moving side is checkmated but the static eval is >= beta then you return the static eval due to your a)+b), so you miss the mate. Therefore your approach seems to be inconsistent. You'd better decide whether you want to detect checkmate in qsearch, or you don't care. If you care then I'd prefer to start with testing for in-check instead of evaluating.

Furthermore, your approach appears to be very inefficient. If no legal captures exist, i.e. the position is quiet, you try to generate all legal moves, and only if you don't find any, you test for in-check. That effectively turns many qsearch nodes into kind of full-width nodes and is very expensive. I'd rather go the other way as stated above, which also makes your code much clearer:
if (in check) -> perform evasion search with remaining depth 1 [no stand-pat, generate all legal moves, detect mate/stalemate]
else -> perform normal qsearch [use stand-pat, generate captures only, do not detect mate/stalemate]

The point you mentioned as possible weakness (your item e) ) will then be covered by the approach above: when being in check you will search all legal evasions, so you can't miss that the only legal evasion loses the queen by being forced to interpose it.

One more note: when detecting checkmate (in qsearch as well as full-width search) you'd better return -(MATE_SCORE-height), with "height" being the distance to the root node, since otherwise your engine will frequently choose to play a move that mates in more than one ply instead of the mate-in-1 move, which in turn leads to being unable to mate the opponent at all. It is not sufficient to see that you can mate "somehow" but you need to distinguish between shorter and longer paths to mate. You can easily figure this out with a trivial KQK example.

Sven

Since I've started to work on my own engine as well, these advices are very welcome. Many thanks!

Best, Jörg.

P.S. A really big thank you to Dan Honeycutt for providing the sources of Simon. I use them to get used to Bitboards as well as the search algorithms in a chess engine.

[zullil]

If the moving side is checkmated but the static eval is >= beta then you return the static eval due to your a)+b), so you miss the mate. Therefore your approach seems to be inconsistent. You'd better decide whether you want to detect checkmate in qsearch, or you don't care. If you care then I'd prefer to start with testing for in-check instead of evaluating.

Furthermore, your approach appears to be very inefficient. If no legal captures exist, i.e. the position is quiet, you try to generate all legal moves, and only if you don't find any, you test for in-check. That effectively turns many qsearch nodes into kind of full-width nodes and is very expensive. I'd rather go the other way as stated above, which also makes your code much clearer:
if (in check) -> perform evasion search with remaining depth 1 [no stand-pat, generate all legal moves, detect mate/stalemate]
else -> perform normal qsearch [use stand-pat, generate captures only, do not detect mate/stalemate]

The point you mentioned as possible weakness (your item e) ) will then be covered by the approach above: when being in check you will search all legal evasions, so you can't miss that the only legal evasion loses the queen by being forced to interpose it.

One more note: when detecting checkmate (in qsearch as well as full-width search) you'd better return -(MATE_SCORE-height), with "height" being the distance to the root node, since otherwise your engine will frequently choose to play a move that mates in more than one ply instead of the mate-in-1 move, which in turn leads to being unable to mate the opponent at all. It is not sufficient to see that you can mate "somehow" but you need to distinguish between shorter and longer paths to mate. You can easily figure this out with a trivial KQK example.

Sven

Thanks again for your thorough response. Even before reading all the new replies, I'd decided to change my implementation to test if side-to-go is in check at the very start of qsearch. Whether or not to implement my qsearch in this manner was exactly the point of my original post. Thanks to all who offered assistance.

About returning -(MATE_SCORE-height)---yes, I already do that. Discovered that issue and how to fix it all on my own. I apologize for being a bit sloppy about this matter in my earlier posts.

[lucasart]

My qsearch starts by evaluating the current position statically, to determine a "stand pat" score.

Never do that when in check. Your stand pat code could look something like this, to handle this problem in a non-messy way:

Code: Select all

int stand_pat = in_check ? -INF : eval();
alpha = max(alpha, stand_pat);
if (alpha >= beta)
    return alpha;

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.

It is not so rare that no captures exist. In that case, testing for the availability of legal moves (to find that in 99.9% cases it's a waste of time as neither mate nor stalemate) is overkill.
Instead do as follows:
- if in check generate all legal moves (evasions)
- otherwise generate captures only
If in check and there are no moves generated, then return a "mated in ply" score.

So when in check you detect mates, but when not in check (generating captures only) you will miss the stalemates. But generally don't count too much on the qsearch() to find mates and stalemates, as the standpat option prevents this in most cases (it'll only find mates that result from sequences of captures delivering check so that the opponent can't stand pat for example)

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

Exactly as you say, the check extension will not save you since qsearch captures can deliver check. But I don't think this is the best way to do the check extension. I don't do it like that. I extend checking moves that verify certain properties, rather than extend when in check. Extending when in check is too costly. Anyway, if your engine is weak this is really a finesse that is not worth discussing yet.