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?
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] <mailto:[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]
<mailto:[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] <mailto:[email protected]>
http://www.computer-go.org/mailman/listinfo/computer-go/
------------------------------------------------------------------------
_______________________________________________
computer-go mailing list
[email protected] <mailto:[email protected]>
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
[email protected] <mailto:[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/
