Author: Robert Hyatt
Date: 20:20:52 07/31/04
Go up one level in this thread
On July 30, 2004 at 18:17:47, Sune Fischer wrote: >On July 30, 2004 at 18:08:22, Uri Blass wrote: > >>On July 30, 2004 at 17:53:37, Sune Fischer wrote: >> >>>On July 30, 2004 at 10:32:36, Robert Hyatt wrote: >>> >>>>On July 30, 2004 at 03:12:54, Sune Fischer wrote: >>>> >>>>>On July 29, 2004 at 20:00:04, Robert Hyatt wrote: >>>>> >>>>>>>Then why did it not work, which part failed, what is your analysis? >>>>>> >>>>>>I did the null-window search. It returned almost instantly without a fail-low. >>>>>>I have time left. What do I do with it? >>>>> >>>>>Now the idea is to simply stop searching and save the remaining time. >>>>> >>>>>There is not much point in doing anything thing else because you don't have >>>>>enough time to resolve a real score and go to the next ply. >>>> >>>>That is where we disagree. I don't know how to make such a statement without >>>>actually trying the search to see... And lo and behold, sometimes I get well >>>>into the next search, far enough to change my mind in fact. >>> >>>And lo and behold 95% of the time you waste your time. >>> >>>>> >>>>>>I simply think that turning a boundary condition into a special-case, when all >>>>>>the "rules" are not known (tree size, fail low time, etc) is at least no better >>>>>>than just ignoring things. >>>>> >>>>>I think it is a little bit of the best of both worlds. >>>>>You get the information you want regarding a fail-low, and you get to save some >>>>>of the time. >>>> >>>>Perhaps. But if you don't fail low, you won't know you are not until you >>>>actually fail high. By the time you fail high I'll be close to having the true >>>>score and can look at other moves. Seems simpler and with no disadvantage I can >>>>see. >>> >>>I can see the disadvantage. >>> >>>> And I don't have to predict when to resort to this "end of iteration" >>>>trick as I just use my normal code. >>> >>>Vanilla search has its advantages :) >>> >>>>>>The issue is when time is low, doing a null-window search rather than a normal >>>>>>search. That is _exactly_ what happened in the old program. >>>>> >>>>>You haven't tested it like I suggested, so you haven't tested it - period. >>>> >>>>OK. I'm not going to argue the point further, other than to say if I start >>>>_every_ iteration with a null-window search, I _clearly_ start the last one the >>>>same way. >>> >>>Very good, but how can you seperate the influence of the two? >>> >>>What you have tested and found is that a + b < 0. >>> >>>I'm proposing that a > 0. >>> >>>This is indeed possible, solution space is b = -(a+p) , p>0. >>> >>>>>>What happens >>>>>>_before_ time is low is irrelevant. >>>>> >>>>>How do you know that? >>>>>Why should this not waste a lot of time and make the whole thing look bad? >>>> >>>>Then we can _never_ compare results. Our searches are different. >>> >>>yes, but more importantly our experiments are different. >>> >>>I think if you want to test "a" there is no reason to be testing "a+b" and then >>>say we can't possible compare. >>> >>>>>If branch factor goes up it works even better, it's the other way that can cause >>>>>problems. >>>> >>>>No it doesn't. It will go up for the null-window search just as well, and you >>>>have the same problem. >>> >>>Yes it will, but the null-move search will _still_ be faster than the aspiration >>>search, so it saves time no matter how you twist and turn it. >>> >>>> Except what threshold do you use to say "I don't believe >>>>I can complete the next iteration because I have less than xx percent of the >>>>total time left..." >>> >>>That's the big question of course, one very important parameter. Perhas a more >>>sophisticated algorithm would even be needed. >>> >>>Some experimentation would have to be conducted, or one could start by >>>collecting a bunch of data from real games and then grind the numbers. >>> >>>Starting off by a careful estimate, eg. 20%, should be safe and good enough to >>>assert if it works or not. >>> >>>>What do you do when the EBF for iteration N is 9, while if you search iteration >>>>N+1 it drops back to 2.5? Again I can post excerpts from game logs to show >>>>exactly that... >>> >>>I think the main reason for a branch factor explosion is due to a lot of failing >>>lows/fail-highs through the ply when there is bad move ordering. >>> >>>A single move probably doesn't explode at one ply and then at the next ply it is >>>suddenly a lot cheaper. >> That move explodes because of a lot of extensions and >>>those will likely happen again at the next ply. >> >>Or it explodes because of bad order of moves after it and the order will be >>better next ply thanks to hash tables so it is not going to explode. >> >>extensions like pruning rules may be different when the score is different. >> >>I think that it is safe to assume that in most cases that you have high >>branching factor you will have a smaller branching factor one ply later. > >I have never measured branch factor on individual moves, only on whole plies. > >But I'm not sure about your analysis. > >It is possible to have bad move ordering that gets better, but you also need to >go an extra ply deep the next time. Perhaps things change around again, I think >some nodes are very unstable with regard to move ordering. This is one idea Hsu used to trigger "panic time" in deep thought and deep blue. He never explained it precisely, but when DT/DB noticed that the branching factor was varying, it searched deeper and used more time to try to search through the instability. Sounds reasonable and it is on my list of things to play with at some point in time... > >>It is possible to get some data about it and to try to give best estimate of the >>branching factor based on previous information that is in the search. > >I guess it is better to use a low and safe estimate to start with, one can >always try a optimize it more aggressively later. > >A proof of method would be the first step, the rest is "just testing" :) > >-S. >>Uri
This page took 0 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.