Author: Sune Fischer
Date: 00:18:52 07/28/04
Go up one level in this thread
On July 27, 2004 at 18:26:16, Robert Hyatt wrote: >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 don't understand the question. >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... It also wastes more time so it's not a win-win situation, you really have to do a test to see if it's worth it or not. I too would like to know if there is a big fail-low at the next ply, I just don't see your way as the most efficient way of doing it though. >>>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. The branch factor is irrelevant if you do it right, and often it is pretty safe bet that the next iteration is more expensive or at lest of the same magnitude. Of course if it varied wildly it would be hard to make a good guesstimate. >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. Say you use 20% of the 1.5 sec that is 0.3 sec, well below 1.4 so you could have saved 1.1 second. Not so much on this position of course but fine 70 is an exteme example, in other positions you might save 20 seconds. >> >>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. To see the next ply you have to extend time, which you won't be able to do if you run out of time before the search returns. >> >>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. The only question is if it can be refined and improved further, I'm not saying Crafty is broken because of this :) >> >>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. Compared to what? >>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... That one should be obvious. >Might as well have done the right search to start with. ..and then bite the dust when the fail-low doesn't have time to return or the time is simply wasted :) -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.