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)
Interrupting a search and still picking a move
Moderator: Ras
-
- Posts: 1404
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
-
- 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
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.
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Interrupting a search and still picking a move
Not "the previous iteration", but "the last PV to appear" is what you use.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
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.
-
- Posts: 1404
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: Interrupting a search and still picking a move
Yes, I am doing move ordering, starting with the best move of the previous iteration.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.
jm
-
- Posts: 1404
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: Interrupting a search and still picking a move
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.sje wrote:Not "the previous iteration", but "the last PV to appear" is what you use.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
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.
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
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Interrupting a search and still picking a move
Here's what I do.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)
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.
-
- Posts: 1404
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: Interrupting a search and still picking a move
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.
Any thoughts would be very much appreciated.
jm
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
jm
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Interrupting a search and still picking a move
Are you saying that the above is a mate in six? It's not.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
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Interrupting a search and still picking a move
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.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.
Any thoughts would be very much appreciated.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
jm
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.
-
- Posts: 1404
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: Interrupting a search and still picking a move
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.sje wrote:Are you saying that the above is a mate in six? It's not.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
jm