I just discovered a design flaw in my engine

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Michael Sherwin
Posts: 3191
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

I just discovered a design flaw in my engine

Post by Michael Sherwin » Fri Mar 27, 2020 1:14 am

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

Ras
Posts: 1372
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: I just discovered a design flaw in my engine

Post by Ras » 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.
Rasmus Althoff
https://www.ct800.net

Michael Sherwin
Posts: 3191
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: I just discovered a design flaw in my engine

Post by Michael Sherwin » Fri Mar 27, 2020 1:36 am

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!
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

jdart
Posts: 3923
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: I just discovered a design flaw in my engine

Post by jdart » 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.

Michael Sherwin
Posts: 3191
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: I just discovered a design flaw in my engine

Post by Michael Sherwin » Fri Mar 27, 2020 3:35 am

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?
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

jdart
Posts: 3923
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: I just discovered a design flaw in my engine

Post by jdart » 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

Michael Sherwin
Posts: 3191
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: I just discovered a design flaw in my engine

Post by Michael Sherwin » Fri Mar 27, 2020 6:05 am

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!
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

User avatar
hgm
Posts: 24443
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: I just discovered a design flaw in my engine

Post by hgm » 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.

Michael Sherwin
Posts: 3191
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: I just discovered a design flaw in my engine

Post by Michael Sherwin » Fri Mar 27, 2020 4:53 pm

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

User avatar
hgm
Posts: 24443
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: I just discovered a design flaw in my engine

Post by hgm » Fri Mar 27, 2020 8:40 pm

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.

Post Reply