On Sat, May 23, 2009 at 12:34 PM, Brian Sheppard <sheppar...@aol.com> wrote:
> >My general impression (also based on experiences from chess): > >Distributing time rather balanced over the moves is a stable > >strategy. I have found in Chess that you also want to spend more time up front. Part, but not all of the reason for this is that you don't know how long a game will last and you do not want to be on the losing end of a short game where you have a lot of time left. This by itself makes early moves more important. Also, early decisions shape the game more than later decisions. In 9x9 GO I have found that it's VERY beneficial to spend more time on early moves. This seem to be more true than in chess. I think it is because the early game is much harder to play than the ending and you don't want to have a lot of time built up playing easy moves. Like everything else, the trick is to find the right balance. With 19x19, time allocation is probably more difficult. With sudden death time controls, a reasonable algorithm is to set some percentage of the remaining time on the clock as your goal time. For chess I have used numbers like 1/30th of the remaining time. In my opinion the number should be a low estimate on how many moves you expect to have to make. Although games can be really short or really long, in general you expect that most games will take at least about 30 moves and not exceed 60 or 70 moves. This does not allocate time evenly, which is good. Each move will be played slightly faster than the previous. But it will NEVER run out of time either, at least mathematically since there is always some time left over. This fraction can be tuned of course to your comfort level. I remember one older program used 1/60 but a couple of years later the author reported to me that it was way too high. This was a program that dominated computer chess for a few years. You can get a feel for this by just doing the math to see how much time you would have for an unusually short game or an unusually long game. If your program supports multiple board sizes you pick a divisor that is some function of the board size, such as 1 / (N*N) (which is probably far too conservative.) So perhaps 1 / ((N*N) * 0.6) where you tune the 0.6 constant. So I'm saying that this is good in Chess and I believe based on Brian's comments and my own experience that it is ESPECIALLY good in GO. - Don > > > Reasoning on the basis of experience in chess is OK, but you must > account for the differences between the domains. > > Chess is more or less uniformly difficult across the whole game. > Go is not. It is definitely more difficult in the opening, especially > for MCTS programs. Trials take longer in the opening, and the > variance is larger, and the differences between moves is smaller > (usually) which means that fewer moves are obviously forced. You have > to spend more time on early moves in MCTS Go programs. > > Pebbles calculates the time required to uniformly spread the remaining > time over the game. It then *doubles* that amount, and allocates that > much time for the current play. This policy is not as extreme as you > might think; it results in more-or-less uniform numbers of trials > across the whole game. I have some experimental evidence that suggests > that doubling is not enough. Perhaps the optimum multiplier is 2.5 or 3. > > Now, this usually does not result in having to play blitz moves later > in the game. (It can happen, if the opponent drags out a losing effort > into 100+ turns, but that doesn't matter.) > > Mogo might have gone too far, but maybe not. There are a lot of ways > to lose games. > > Best, > Brian > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
