Author: Robert Hyatt
Date: 08:02:36 07/28/04
Go up one level in this thread
On July 28, 2004 at 03:18:52, Sune Fischer wrote: >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. you said I wasted time by starting the next search which won't fail low most of the time. I said you waste time by doing iteration N+1 that doesn't change the best move most of the time. See the fallacy in the argument? I _know_ going to depth N+1 won't change the best move most of the time. But it will likely change the best move when it is important to do so... > >>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 never said "win-win". I said it works better for me after testing. And I have done _lots_ of testing with various approaches. That's how I settled on the current approach. I'm not much for tea leaves and Tarot cards. > >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. That's ok. All engines are different in some respect. I base my decisions on what to do on testing. That's all I can say. Nothing says that what works for my program will work for yours or vice-versa. But what I do works for mine pretty well... > >>>>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. I don't have to extend the time. You proposed the 15% rule. It breaks above and I'd stop 2 plies too soon, even though I could finish _both_. > >>> >>>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 :) Again, I use aspiration search in addition to PVS. My fail lows happen _very_ quickly in 99% of the cases. And with my approach I have no special-case "last iteration" stuff to deal with. I just search until the search returns "time up" and go with what I have. That's the KISS part of this. > >-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.