Interrupting a search and still picking a move

Discussion of anything and everything relating to chess playing software and machines.

Moderator: Ras

JVMerlino
Posts: 1404
Joined: Wed Mar 08, 2006 10:15 pm
Location: San Francisco, California

Interrupting a search and still picking a move

Post by JVMerlino »

Hey All,

An actual programming question!

I've already implemented interrupting a search in progress due to receiving input commands that just stop the search (e.g. "new").

But everything I've tried to implement for interrupting a search due to time considerations (a position exploded and I've already used a lot more time than I initially allocated), or due to other types of input commands (e.g. winboard's "?"), and still select a move is proving quite troublesome. Everything I've tried results in instabilities coming back up the tree.

The main thing I've seen in other engine's code is to use one function for searching the root and another for all other depths. Is part of the reason for this the issue that I'm having?

I don't want to do anything so inelegant as jumping out of the loop, unless it's actually recommended by one of you guys. Another very inelegant solution would be to throw away everything I've done at this iteration and just choose the best move from the previous iteration.

Any thoughts would be very much appreciated,
jm (Myrddin)
User avatar
hgm
Posts: 28388
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Interrupting a search and still picking a move

Post by hgm »

If you start every iteration with the best move of the previous one, what you propos is automatic, even if the search of the first move of the new iteration was interrupted.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: Interrupting a search and still picking a move

Post by sje »

JVMerlino wrote:Another very inelegant solution would be to throw away everything I've done at this iteration and just choose the best move from the previous iteration
Not "the previous iteration", but "the last PV to appear" is what you use.

When the time-out hits, just throw away the tree and keep the last PV.

You don't need any setjmp() ugliness, just have an abort flag that forces a quick unwind.
JVMerlino
Posts: 1404
Joined: Wed Mar 08, 2006 10:15 pm
Location: San Francisco, California

Re: Interrupting a search and still picking a move

Post by JVMerlino »

hgm wrote:If you start every iteration with the best move of the previous one, what you propos is automatic, even if the search of the first move of the new iteration was interrupted.
Yes, I am doing move ordering, starting with the best move of the previous iteration.

jm
JVMerlino
Posts: 1404
Joined: Wed Mar 08, 2006 10:15 pm
Location: San Francisco, California

Re: Interrupting a search and still picking a move

Post by JVMerlino »

sje wrote:
JVMerlino wrote:Another very inelegant solution would be to throw away everything I've done at this iteration and just choose the best move from the previous iteration
Not "the previous iteration", but "the last PV to appear" is what you use.

When the time-out hits, just throw away the tree and keep the last PV.

You don't need any setjmp() ugliness, just have an abort flag that forces a quick unwind.
It's the "throwing away the tree" that apparently caused me to overthink the problem. I tried to do it without sticking code in several places to check for the abort flag, but just getting confirmation that this was the way to do it made me rethink my solution.

Implementing this also caused me to write some code to display the PV every time it changes (not only at the end of the iteration), and obviously this is going to be valuable.

Many thanks to Steven and H.G. for their input! I think I have it working now.

jm
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Interrupting a search and still picking a move

Post by bob »

JVMerlino wrote:Hey All,

An actual programming question!

I've already implemented interrupting a search in progress due to receiving input commands that just stop the search (e.g. "new").

But everything I've tried to implement for interrupting a search due to time considerations (a position exploded and I've already used a lot more time than I initially allocated), or due to other types of input commands (e.g. winboard's "?"), and still select a move is proving quite troublesome. Everything I've tried results in instabilities coming back up the tree.

The main thing I've seen in other engine's code is to use one function for searching the root and another for all other depths. Is part of the reason for this the issue that I'm having?

I don't want to do anything so inelegant as jumping out of the loop, unless it's actually recommended by one of you guys. Another very inelegant solution would be to throw away everything I've done at this iteration and just choose the best move from the previous iteration.

Any thoughts would be very much appreciated,
jm (Myrddin)
Here's what I do.

1. As I back things up the tree, before the "time_up" flag has been set, I do things normally. If the score is > alpha then things get backed up, otherwise no.

2. once the "time_up" flag is set, I no longer back up anything. After each recursive call to Search() or Quiesce() I check this flag and if set, I do a return(0) and do not modify the previous best score or PV. When I get back to the root, I just use the last thing backed up to the root, which was the best move found prior to time running out.

Once the "time_up" flag gets set, you can no longer trust any information you have that is incomplete, so it has to be discarded.
JVMerlino
Posts: 1404
Joined: Wed Mar 08, 2006 10:15 pm
Location: San Francisco, California

Re: Interrupting a search and still picking a move

Post by JVMerlino »

Thanks, Bob. That's now what I do and it seems to be working just fine.

My engine is coming along pretty nicely, I think, and that's kind of an underlying problem that I expect all engine writers have when they're starting out -- expectation / comparison.

How can I tell if my engine is doing as well as it should be given the features/functions I have implemented? Should I be spending time trying to find issues in what I've currently implemented (because it isn't performing as well as it should), or is it ok to move on and add new things?

Extremely nagging when I don't know if my fledgling engine is supposed to be able to see that Ne1 or Nd2 lead to Mate in 5 (although the first three moves in the mating sequence for black are non-captures and non-checks) and avoid moving the f3 Knight to either of those squares in this position in a reasonable amount of time.

[d]3rkb1r/1p2npp1/p1q5/4P3/3BP1p1/2PB1N2/PP3PP1/R2Q1RK1 w k - 0 18

Myrddin, unfortunately, on a P4-3.0, takes quite a long time, as you can see, to even see that moving the Knight isn't winning. It then chooses a different move that just leads to a slightly longer mate.

Code: Select all

2   605      0 373       f3g5 f7f5 d1g4
3   635      4 1855      f3g5 h8h4 f2f4 g4f3 g2f3
4   593     14 5772      f3g5 f7f6 e5f6 g7f6
4   679     54 23777     f3h2 g4g3 f2g3 f7f5
5   472    265 115578    f3h2 c6h6 d1a4 b7b5 d3b5 a6b5 a4b5
5   512    365 157982    f3g5 c6h6 d1a4 b7b5 d3b5 a6b5 a4b5
5   578    478 204729    f3e1 c6h6 d1a4 b7b5 a4a5 f7f5
5   588    603 257476    f3d2 c6h6 d1a4 b7b5 a4c2 f7f5
6   510   1323 557416    f3d2 c6h6 f2f4 h6h2 g1f2 h2f4 f2g1 f4g5
6   562   5260 2188606   f3e1 c6h6 f2f3 h6h2 g1f2 g4g3 f2e3 f7f5
7   542   7729 3257141   f3e1 c6h6 f2f3 h6h2 g1f2 e7c6 d1a4 f7f5
8     5  57868 14936668  f3e1 c6h6 f2f4 g4g3 d1a4 e7c6 a4c6 h6c6 e1f3 f8c5
8   300  68423 16928410  d3a6 b7a6 f3d2 c6h6 f2f4 h6h2 g1f2 h2f4 f2g1 f4g5
Any thoughts would be very much appreciated.

jm
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: Interrupting a search and still picking a move

Post by sje »

JVMerlino wrote:Extremely nagging when I don't know if my fledgling engine is supposed to be able to see that Ne1 or Nd2 lead to Mate in 5 (although the first three moves in the mating sequence for black are non-captures and non-checks) and avoid moving the f3 Knight to either of those squares in this position in a reasonable amount of time.
[d]3rkb1r/1p2npp1/p1q5/4P3/3BP1p1/2PB1N2/PP3PP1/R2Q1RK1 w k - 0 18
Are you saying that the above is a mate in six? It's not.
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Interrupting a search and still picking a move

Post by bob »

JVMerlino wrote:Thanks, Bob. That's now what I do and it seems to be working just fine.

My engine is coming along pretty nicely, I think, and that's kind of an underlying problem that I expect all engine writers have when they're starting out -- expectation / comparison.

How can I tell if my engine is doing as well as it should be given the features/functions I have implemented? Should I be spending time trying to find issues in what I've currently implemented (because it isn't performing as well as it should), or is it ok to move on and add new things?

Extremely nagging when I don't know if my fledgling engine is supposed to be able to see that Ne1 or Nd2 lead to Mate in 5 (although the first three moves in the mating sequence for black are non-captures and non-checks) and avoid moving the f3 Knight to either of those squares in this position in a reasonable amount of time.

[d]3rkb1r/1p2npp1/p1q5/4P3/3BP1p1/2PB1N2/PP3PP1/R2Q1RK1 w k - 0 18

Myrddin, unfortunately, on a P4-3.0, takes quite a long time, as you can see, to even see that moving the Knight isn't winning. It then chooses a different move that just leads to a slightly longer mate.

Code: Select all

2   605      0 373       f3g5 f7f5 d1g4
3   635      4 1855      f3g5 h8h4 f2f4 g4f3 g2f3
4   593     14 5772      f3g5 f7f6 e5f6 g7f6
4   679     54 23777     f3h2 g4g3 f2g3 f7f5
5   472    265 115578    f3h2 c6h6 d1a4 b7b5 d3b5 a6b5 a4b5
5   512    365 157982    f3g5 c6h6 d1a4 b7b5 d3b5 a6b5 a4b5
5   578    478 204729    f3e1 c6h6 d1a4 b7b5 a4a5 f7f5
5   588    603 257476    f3d2 c6h6 d1a4 b7b5 a4c2 f7f5
6   510   1323 557416    f3d2 c6h6 f2f4 h6h2 g1f2 h2f4 f2g1 f4g5
6   562   5260 2188606   f3e1 c6h6 f2f3 h6h2 g1f2 g4g3 f2e3 f7f5
7   542   7729 3257141   f3e1 c6h6 f2f3 h6h2 g1f2 e7c6 d1a4 f7f5
8     5  57868 14936668  f3e1 c6h6 f2f4 g4g3 d1a4 e7c6 a4c6 h6c6 e1f3 f8c5
8   300  68423 16928410  d3a6 b7a6 f3d2 c6h6 f2f4 h6h2 g1f2 h2f4 f2g1 f4g5
Any thoughts would be very much appreciated.

jm
I don't think there is any good "metric" for this. Some things are significant, like null move or reductions or search extensions, somethings are more modest such as different pieces of evaluation knowledge.

null-move will do a lot to speed up your search. But this really is an evolutionary rather than revolutionary process. Every little idea will make it better, but the ideas that work will come slower and slower as you get more things included.
JVMerlino
Posts: 1404
Joined: Wed Mar 08, 2006 10:15 pm
Location: San Francisco, California

Re: Interrupting a search and still picking a move

Post by JVMerlino »

sje wrote:
JVMerlino wrote:Extremely nagging when I don't know if my fledgling engine is supposed to be able to see that Ne1 or Nd2 lead to Mate in 5 (although the first three moves in the mating sequence for black are non-captures and non-checks) and avoid moving the f3 Knight to either of those squares in this position in a reasonable amount of time.
[d]3rkb1r/1p2npp1/p1q5/4P3/3BP1p1/2PB1N2/PP3PP1/R2Q1RK1 w k - 0 18
Are you saying that the above is a mate in six? It's not.
No, the position is not a Mate in 6. What my engine can't see in a reasonable time is that if it moves the Knight to e1 or d2 that Black has a Mate in 5.

jm