Author: Robert Hyatt
Date: 15:26:16 07/27/04
Go up one level in this thread
On July 27, 2004 at 16:51:17, Sune Fischer wrote:
>On July 27, 2004 at 16:08:32, Robert Hyatt wrote:
>
>>>Because you could normally save 20% of your time?!
>>>
>>>Only way to know is to try it, I can only say it works for me :)
>>
>>How do you save _anything_?? By stopping early? I'd just as soon continue the
>>search, run out of time, make the move, and pick back up at the point of
>>interruption by hashing...
>>
>>I _never_ want to stop early. Every second I spend beyond "early" is a second
>>invested to detect tactical problems not yet noticed...
>
>Hmm, but the thing is... that you most often get nothing from that, only wasted
>time.
Aha. And exactly how many times do you do the N+1 iteration and get the _same_
best move? For crafty that is about 85% of the time. So I should cut the
search off one ply early? Or is that 15% critical?
I claim _any_ fail-low where the score is equal or winning for me is something
that I'd like to know about. My approach finds a few of them. A few more than
stopping early would find...
>
>
>>>>100 seconds per move. 15% is 15 seconds. For the first N iterations that is
>>>>more than enough time. How to accurately predict when you are starting the
>>>>_last_ iteration?
>>>
>>>Well, e.g. compare time remaining with the time spent on the last iteration, use
>>> a bit of logic and you might eventually get there... :)
>>>
>>
>>Again, been there, done that, got the T-shirt. Odd/even effects. I can show
>>you searches where iteration N+1 takes 1/2 the time of iteration N, because N
>>changed its mind too often. Feel free to use what you want, of course. I
>>simply use what experience says (to me) produces the best results. When I see
>>something I don't like, I fix it or live with it depending.
>
>You can find an exception if you look hard enough, every rule has exceptions :)
>Luckily the nullwindow search would pick this up :)
>
>>>>Try fine 70 for a quick counter-example...
>>>
>>>Howso?
>>>
>>>-S.
>>
>>
>>
>>Run it. Compare the times. it is one of many such positions where the first
>>move doesn't always take 90% of the total time.
>
>Actually I think it does. There are only 3 legal moves and the last two are
>searched with a nullwindow.
>Probably it's more like 95% of the time that is spent on the first move, so I
>don't see why this position should be any sort of counter example.
>
I was talking specifically about the branching factor also. it is way less than
2.0 here. And that some iterations take _less_ time than the previous
iteration. At least for my code.
>Of course all those numbers are easily adjusted anyway, just think in
>percentages and not in absolutes.
>
>>Particularly when the branching
>>factor drops as low as it does for fine 70. And then there is the odd/even
>>problem where sometimes odd or even iterations take _way_ longer than the
>>previous iteration, wrecking that percentage calculation you mentioned above...
>
>Ok, so let's say you plan to search for 1 minute on fine 70, you have 3 seconds
>left and searched last ply in 12 seconds.
>My (safe) guess here is that you are about to begin you the last ply.
Here is real data for that scenario:
35-> 15.93 8.92 1. Kb1 Kb7 2. Kc1 Kb8 3. Kc2 Kb7 4.
Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kc7 7. Kf3
Kd7 8. Kg3 Ke7 9. Kh4 Kf6 10. Kh5 Kf7
11. Kg5 Kg7 12. Kxf5 Kf7 13. Ke4 Ke8
14. Kd3 Ke7 15. Kc4 <HT>
36 17.33 8.92 1. Kb1 Kb7 2. Kc1 Kb8 3. Kc2 Kb7 4.
Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kc7 7. Kf3
Kd7 8. Kg3 Ke7 9. Kh4 Kf6 10. Kh5 Kf7
11. Kg5 Kg7 12. Kxf5 Kf7 13. Ke4 <HT>
36-> 17.33 8.92 1. Kb1 Kb7 2. Kc1 Kb8 3. Kc2 Kb7 4.
Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kc7 7. Kf3
Kd7 8. Kg3 Ke7 9. Kh4 Kf6 10. Kh5 Kf7
11. Kg5 Kg7 12. Kxf5 Kf7 13. Ke4 <HT>
37 18.68 8.92 1. Kb1 Kb7 2. Kc1 Kb8 3. Kc2 Kb7 4.
Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kc7 7. Kf3
Kd7 8. Kg3 Ke7 9. Kh4 Kf6 10. Kh5 Kf7
11. Kg5 Kg7 12. Kxf5 Kf7 13. Ke4 <HT>
37-> 18.70 8.92 1. Kb1 Kb7 2. Kc1 Kb8 3. Kc2 Kb7 4.
Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kc7 7. Kf3
Kd7 8. Kg3 Ke7 9. Kh4 Kf6 10. Kh5 Kf7
11. Kg5 Kg7 12. Kxf5 Kf7 13. Ke4 <HT>
15 seconds used through depth 35. 36 takes 1.5 seconds to complete. 37 takes
1.4 seconds to complete. You get the idea... not so easy to decide when to
quit here.
>
>So the question is, do you use those 3 seconds for the next ply or do you save
>them for next move?
Give me the next two plies, in fact. (see above). They might be just what I
need to see a better (winning) move, or that my best move loses.
>
>You can begin to search like you would normally, but in >90% of the cases you
>won't get a return unless it's a FL, and it's even doubtful you'll get that FL
>in time.
I get them often enough to have concluded that this is a good idea. That's all
I can say. Experimental data from my program supports the idea. Others might
not.
>
>I think it's more interesting to do the null-window search in those last 3 secs,
>that way you probably get a return (or you can even extend and wait for the
>returned score).
>You FH -> great stop the search, everything looks normal up here too.
Takes too long.
>You FL -> trouble ahead, need to extend a few seconds, perhaps a full ply, move
>the window down and try normal aspiration.
Need a score to start with...
Might as well have done the right search to start with.
>
>-S.
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.