How to treat check giving mov in Qsearch of MC-AB search?

[smatovic]

Heyho,

i wonder what to do with check giving moves in the Qsearch of an MC-AB search?

Until now i extended the Qsearch to an full search with all moves,
but this seems to produce tree explosions.

So how to limit these?

--
Srdja

MC-AlphaBeta:
http://chessprogramming.wikispaces.com/MC%CE%B1%CE%B2

[Don]

Heyho,

i wonder what to do with check giving moves in the Qsearch of an MC-AB search?

Until now i extended the Qsearch to an full search with all moves,
but this seems to produce tree explosions.

So how to limit these?

--
Srdja

MC-AlphaBeta:
http://chessprogramming.wikispaces.com/MC%CE%B1%CE%B2

In quies you only try checks (and out of check.) If you want to do checks you should restrict it pretty severely (unless they are captures.) The way you do that it that you only try captures AND checks, perhaps just on the first ply of quies.

I assume that you understand about the "stand pat" thing. Let's say you look only at captures. The way stand pat works is that can treat "stopping the search" as a move. If none of the captures are good, then "standing pat" with the current score is a valid move. Of course since standing pat is the cheapest "move" of all, you could take a beta cutoff if one is possible. Most programs do not stand pat in check and will try all responses.

It's a big win to make a specialized capture move generator and one for out of checks. Also, if you doing checks in quies you may want a specialized checks only generator. Since a capture might also be a check you might consider a special "quiet check" generator since the capture checks are already covered.

Does that answer your question?

[smatovic]

The way you do that it that you only try captures AND checks, perhaps just on the first ply of quies.

Ok, i think i got it. Thanks.

--
Srdja

[Don]

The way you do that it that you only try captures AND checks, perhaps just on the first ply of quies.

Ok, i think i got it. Thanks.

--
Srdja

I just want to make sure because for some reason "stand pat" confuses people.

A simple way to implement it is to set the best score found to the current static score - pretending that you already searched a move which returned that score. So the only issue is whether you can beat this with some capture.

But first you should check to see if "standing pat" produces a beta cutoff so that you many not have to try any moves at all.

If it doesn't, you search the captures and when you have searched all them you return the best score. The best score may have been one of the captures or it may simply be the original "stand pat" score.

If you are in check you should not do the stand pat stuff since it does not make sense to assume that everything is ok even though you are in check. It may perhaps be reasonable to stand pat anyway if you can determine very quickly that you are not checkmated, but my guess i that this is a bad idea because you are likely to lose a tempo and could be facing nasty tactics. I have never tried this.

[Eelco de Groot]

If you are in check you should not do the stand pat stuff since it does not make sense to assume that everything is ok even though you are in check. It may perhaps be reasonable to stand pat anyway if you can determine very quickly that you are not checkmated, but my guess i that this is a bad idea because you are likely to lose a tempo and could be facing nasty tactics. I have never tried this.

In both Fruit an Stockfish type of evaluations, the output of the static evaluation will not make any sense if you are in check. So there is no reliable way to use it to determine if you are above beta, there is no static evaluation possible.

If you would then as a stopgap, take static eval of the parent node maybe that would be possible. This is a bit like Rebel's Lazy Eval idea and distantly related to incremental updating I think. But this is also related to another question I am wondering about, if it is always necessary to do a full static evaluation in the middle of a tactical exchange?. If your queen for example in qsearch is under threat, does it make sense to do a full static evaluation, mobility, pawn structure etc.? Since a lot a time is spent in quiescence search, it should be possible to do a bit of time saving but I am not sure exactly how. SEE was also not the complete answer. And how this relates to the possibility of doing nullmove in quiescence search, to determine threats I am not sure yet. It will give you an opportunity to determine a threatmove and this is done in Rainbow Serpent's version of nullmove in quisecence search as well, but beyond that I do not yet know.

Eelco

[Don]

If you are in check you should not do the stand pat stuff since it does not make sense to assume that everything is ok even though you are in check. It may perhaps be reasonable to stand pat anyway if you can determine very quickly that you are not checkmated, but my guess i that this is a bad idea because you are likely to lose a tempo and could be facing nasty tactics. I have never tried this.

In both Fruit an Stockfish type of evaluations, the output of the static evaluation will not make any sense if you are in check. So there is no reliable way to use it to determine if you are above beta, there is no static evaluation possible.

In such a case one would not be able to test this idea unless they were willing to fix the static eval to work in this case.

If you would then as a stopgap, take static eval of the parent node maybe that would be possible. This is a bit like Rebel's Lazy Eval idea and distantly related to incremental updating I think.

Lazy eval is not a rebel idea, it has been done for years even in Rexchess and way before that.

You can save time with evaluation by using lazy evaluation of course. You could even structure it tiers, having a very fast evaluation and the progressive levels that add more information but become more an more expensive. The idea being to avoid going to the next tier.

The primary thing in lazy eval is to have the best estimate possible of what the score would be if you called the evaluation, another estimate of how far off this is likely to be, and then you do a comparison with the appropriate window. If you are trying to get a beta cutoff in quies and the fast evaluation is a rook ahead, you don't need to do the evaluation, just take the cutoff.

Komodo does something like that which we call capture futility. It's not the same thing but it is related, we will avoid making a capture in quies if some liberal estimate of how much the capture will be worth to us will not be enough to raise the score to alpha. But it only works for us if we first determine that the move will not check the opponent because in such cases the move is much more dangerous and could in fact be the point of some tactic that ends in the quies search with a mate or something.

But this is also related to another question I am wondering about, if it is always necessary to do a full static evaluation in the middle of a tactical exchange?. If your queen for example in qsearch is under threat, does it make sense to do a full static evaluation, mobility, pawn structure etc.? Since a lot a time is spent in quiescence search, it should be possible to do a bit of time saving but I am not sure exactly how. SEE was also not the complete answer. And how this relates to the possibility of doing nullmove in quiescence search, to determine threats I am not sure yet. It will give you an opportunity to determine a threatmove and this is done in Rainbow Serpent's version of nullmove in quisecence search as well, but beyond that I do not yet know.

Eelco