I just discovered a design flaw in my engine
Moderators: hgm, Rebel, chrisw
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
I just discovered a design flaw in my engine
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?
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 2487
- Joined: Tue Aug 30, 2016 8:19 pm
- Full name: Rasmus Althoff
Re: I just discovered a design flaw in my engine
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 wrote: ↑Fri Mar 27, 2020 2:14 amThe 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?
Rasmus Althoff
https://www.ct800.net
https://www.ct800.net
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: I just discovered a design flaw in my engine
I should have realized that. I'm getting stupid in my old age.Ras wrote: ↑Fri Mar 27, 2020 2:30 amIn 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 wrote: ↑Fri Mar 27, 2020 2:14 amThe 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?
Thanks!
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 4366
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: I just discovered a design flaw in my engine
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.
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: I just discovered a design flaw in my engine
Now I'm confused. What are the considerations?
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 4366
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: I just discovered a design flaw in my engine
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
--Jon
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: I just discovered a design flaw in my engine
Thanks!jdart wrote: ↑Fri Mar 27, 2020 4: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
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: I just discovered a design flaw in my engine
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.
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: I just discovered a design flaw in my engine
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.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: I just discovered a design flaw in my engine
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.
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.