Page 1 of 1

I just discovered a design flaw in my engine

Posted: Fri Mar 27, 2020 1:14 am
by 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?

Re: I just discovered a design flaw in my engine

Posted: Fri Mar 27, 2020 1:30 am
by Ras
Michael Sherwin wrote:
Fri Mar 27, 2020 1:14 am
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.

Re: I just discovered a design flaw in my engine

Posted: Fri Mar 27, 2020 1:36 am
by Michael Sherwin
Ras wrote:
Fri Mar 27, 2020 1:30 am
Michael Sherwin wrote:
Fri Mar 27, 2020 1:14 am
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!

Re: I just discovered a design flaw in my engine

Posted: Fri Mar 27, 2020 3:31 am
by 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.

Re: I just discovered a design flaw in my engine

Posted: Fri Mar 27, 2020 3:35 am
by Michael Sherwin
jdart wrote:
Fri Mar 27, 2020 3:31 am
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?

Re: I just discovered a design flaw in my engine

Posted: Fri Mar 27, 2020 3:47 am
by 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

Re: I just discovered a design flaw in my engine

Posted: Fri Mar 27, 2020 6:05 am
by Michael Sherwin
jdart wrote:
Fri Mar 27, 2020 3:47 am
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!

Re: I just discovered a design flaw in my engine

Posted: Fri Mar 27, 2020 6:45 am
by 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.

Re: I just discovered a design flaw in my engine

Posted: Fri Mar 27, 2020 4:53 pm
by Michael Sherwin
hgm wrote:
Fri Mar 27, 2020 6:45 am
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.

Re: I just discovered a design flaw in my engine

Posted: Fri Mar 27, 2020 8:40 pm
by 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.