[computer-go] Allocating remaining time

[Don Dailey]

On Wed, 2007-01-03 at 22:04 -0800, Peter Drake wrote:
> How much time should a program spend on each move?
> 
> If my program has t milliseconds left to use in a game, and there are  
> an estimated m moves left on the board (e.g., this many vacant  
> spaces), one reasonable choice is t / m.

Excellent question.  I think this really is a reasonable choice.   

I did a LOT of tests
to determine this and it makes sense to front load quite heavily.  
I used a constant, I did not try to estimate how many moves might
be left.   If you use t/m  you really should make m  much smaller
than the number of vacant points left.

It's not a waste to spend a lot of time on early moves.   From
casual observation, I noticed that most games were decided very
quickly, after just a few moves in 9x9.   

Another reason to front load is that the game gets easier and
easier to play correctly as more stones get placed.   It's a
matter of concentrating the most energy where it's needed.

My program notices when the game is pretty much a forgone 
conclusion and when this happens it plays even faster - I do
this so that I can be even more aggressive about earlier moves.


> In practice, this seems to spend too much time on early moves, which  
> (under UCT/MC) is largely wasted time. Would it be better to use  
> something like t / m**k, for some constant k? (Looking at graphs of  
> such functions, k = 1.5 seems reasonable.)

You should test all of this.   That's what I do.  I think self-testing
of different formula's and constants is fine for this kind of thing.

> It would also be interesting to look at the graphs of how much time  
> humans spend on each move; is it usually less for the opening moves  
> than for middle / endgame moves? Is there a smooth curve, or is there  
> a relatively abrupt shift from joseki to analysis?
> 
> Peter Drake
> Assistant Professor of Computer Science
> Lewis & Clark College
> http://www.lclark.edu/~drake/
> 
> 
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/