I just discovered a design flaw in my engine

[Michael Sherwin]

And I'm wondering how serious it is and how other engines handle it. My engine uses pseudo legal move generation and after a pseudo legal move the legality of such move is discovered by the next deeper move generation. The design flaw therefore is at the leaf nodes when starting the Qsearch and there is a stand pat score >= beta. An illegal leaf move is not detected. How serious of a flaw is this?

[Ras]

The design flaw therefore is at the leaf nodes when starting the Qsearch and there is a stand pat score >= beta. An illegal leaf move is not detected. How serious of a flaw is this?

In QS, the side to move has a capture move to take the opposite king, which would raise the score to +infinity, i.e. even much more above beta, which would cause a beta-cutoff. But here you already have a beta-cutoff anyway due to stand-pat, so it doesn't matter how much you go above beta.

[Michael Sherwin]

The design flaw therefore is at the leaf nodes when starting the Qsearch and there is a stand pat score >= beta. An illegal leaf move is not detected. How serious of a flaw is this?

In QS, the side to move has a capture move to take the opposite king, which would raise the score to +infinity, i.e. even much more above beta, which would cause a beta-cutoff. But here you already have a beta-cutoff anyway due to stand-pat, so it doesn't matter how much you go above beta.

I should have realized that. I'm getting stupid in my old age.
Thanks!

[jdart]

In general though, whenever you have any early exit from search, you should take care that you are correctly handling the case of a previous illegal move.

[Michael Sherwin]

In general though, whenever you have any early exit from search, you should take care that you are correctly handling the case of a previous illegal move.

Now I'm confused. What are the considerations?

[jdart]

One example: you detect a draw before you have searched any moves. Now, if the previous move was illegal you don't want to return a draw score. You should return an illegal move indicator of some kind. I return -Illegal, which comes back to the caller (which inverts the score) as the constant Illegal, a value above all other scores.

--Jon

[Michael Sherwin]

One example: you detect a draw before you have searched any moves. Now, if the previous move was illegal you don't want to return a draw score. You should return an illegal move indicator of some kind. I return -Illegal, which comes back to the caller (which inverts the score) as the constant Illegal, a value above all other scores.

--Jon

Thanks!

[hgm]

It can mask stalemate in a leaf node, when you think a pseudo-legal move is just bad, rather than illegal. And if beta < 0 being stalemated would be a fail high, while having a bad but legal move would be a fail low.

[Michael Sherwin]

It can mask stalemate in a leaf node, when you think a pseudo-legal move is just bad, rather than illegal. And if beta < 0 being stalemated would be a fail high, while having a bad but legal move would be a fail low.

I'm thinking of just making another Qsearch just for the first ply of captures where it generates the moves before it does the stand pat check.

[hgm]

You could also just add a test whether you can capture the King, before you do the stand-pat check.

It is true that the time on this would be wasted if you cannot capture the King. (Which will be almost always the case.) OTOH, the test is cheap compared to a full capture generation. And the capture generation would be wasted in nodes where you get a stand-pat cutoff. So my guess is that advance generation would waste more time.

Note, however, that none of this will help when you are doing futility pruning. If you really want to be sure that you detect stalemate at d=1 nodes (which would make a difference if alpha < 0, so that a stalemate would not fail low as well), you should not do futility pruning before you found at least one legal move.