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 <christ...@modeltwozero.com
> 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
<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/
_______________________________________________
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/
