2009/5/24 Christian Nentwich <[email protected]> > Jason, > > I used this time management code on CGOS and for off-line test tournaments > so far. I cannot claim that I have made additional efforts to model/address > network lag in it, so I don't yet know what else I need to do with KGS, etc. > Perhaps a percentage applied to the result computed by the curve, for > safety, or perhaps subtract two seconds from the time estimate sent by the > server? >
The extra time in CGOS is designed so that you don't have to add your own compensation for network lag, and so that you don't lose a game purely on communication time with the server. The amount of time currently configured is 3/4 second. You only get the amount of this credit that you use. So if you have a fast network and you take 1/4 second to move from the servers point of view, you only get 1/4 second of that time, not the full 3/4. Think of this like a Bronstein clock, which does exactly the same thing. It's not designed to be "fair" because if you have a fast network you will still have an advantage over an opponent with a slow network. It is designed to prevent programs with a slow network from losing on time even though they are playing instantly. I think the best way to deal with it using your algorithm is to either ignore it and just use your algorithm as is, or if you are confident that you have a fast network add an additional 3/4 second to each move (or some fraction of that if you want to be safer.) Add the time after you do your normal calculation. - Don > > > You're right about the initial move estimates, it's just another thing I > overlooked. The initial move estimate is (9 x 9 x 1.6) / 2. However, later > in the game the initial move estimate (when the original falls below a > threshold) is set to all playable empty points, not half. This is because > you cannot let your opponent force you to run out of time by passing when > playing with Tromp Taylor rules. It's not a problem usually, because by the > time you get to the threshold, you are playing filling moves. > > I am actually not convinced that I have the right approach to estimating > the right number of moves left, but the time curve itself works well. > Refining the move estimation is a nicer problem to have. Because the curve > equates the time under it to the total time available, it can play optimally > at least in the sense that it will neither use too much, *nor* too little > time as far as the whole game is concerned. Where it spends the time is up > to the curve control parameters. > > Christian > > > > On 23/05/2009 22:57, Jason House wrote: > > How have you tested your time management code? CGOS is very bad for testing > time management because it gives a gift of time on every move (to compensate > for assumed network lag) > > I think you might be missing a factor of two in your computations. Only > half the moves in a game count against your time. > > Sent from my iPhone > > On May 23, 2009, at 4:26 PM, Christian Nentwich < > [email protected]> wrote: > > > This time management business is quite interesting. I looked into this in > some detail a while ago and came up with something I think is reasonable for > 9x9. I'd love to hear what you all think about it. > > My algorithm relies on two key parameters: the time left (which is either > reported by a server periodically, or maintained by the engine), and an > estimate of how many moves are left. The estimate of moves left is set to > 1.6 * board area (i.e. 9 x 9 x 1.6) initially based on the average length of > playouts in experiments. Towards the end of the game, especially with Tromp > Taylor rules, the algorithm instead counts the number of empty intersections > left, plus a haircut for captures. This is usually quite accurate. > > So, given the time left, T, and the number of estimated moves left, M, the > task is to find out how much time to spend on the current move. We know we > want to spend (a lot) more on early moves, and less later. > > Now assume you have moves numbered along the x axis, from 1 to M, and the y > axis shows how much time to spend on a move. I used a downward sloping curve > with the following form: 1 / x ^ (1 / n) where 'n' controls the steepness of > the curve. We know the total area under the curve *must* be equal to T, so > that you provably never run out of time given your estimated number of > moves. > > Integrating over dx and some algebra gives (remember n is a steepness > constant, M is the number of moves left, T is time left): > > time(current move) = T * (n - 1) / (n * (M ^ (n-1 / n) - 1) > > Add a haircut of 5-10%, just in case of network funnies. Works very nicely > for me, at least as far as time management is concerned, my code is not > strong yet but it never loses on time :-) Plus, it gets to spend > super-linear time in the beginning. If you plot the initial curve equation, > you can see how it works. > > Christian > > > > On 23/05/2009 18:38, Don Dailey wrote: > > > > On Sat, May 23, 2009 at 12:34 PM, Brian Sheppard <[email protected]>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 >> [email protected] >> http://www.computer-go.org/mailman/listinfo/computer-go/ >> > > ------------------------------ > > _______________________________________________ > computer-go mailing > [email protected]http://www.computer-go.org/mailman/listinfo/computer-go/ > > > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ > > ------------------------------ > > _______________________________________________ > computer-go mailing > [email protected]http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ >
_______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
