[computer-go] Allocating remaining time

[Oliver Lewis]

It seems important to have some way of measuring how good / settled the
current "best move" is, particularly if you're also going to think in your
opponent's time.  Otherwise, you could end up spending significant amounts
of "allocated" time when, for example, a sequence of forced moves is being
played out and little thinking time is actually required.  I'm not sure of
the technical details, but I would have thought that UCT would provide a
good estimate of how confident it is that it has found the best move that
it's ever going to find.

Oliver



On 1/6/07, Eduardo Sabbatella Riccardi <eduardo_sabbatella at yahoo.com.ar>
wrote:
>
> Hello,
>
> I was thinking about this a few days ago and I decided I will try the
> following:
>
> When the engine is searching for best moves there is a "game path" of 3, 4
> or
> up to 10 moves that the engine have found to be the "best moves" so far.
>
> 0) Before start the search, based on total available time, and current
> move,
> engine will decide Tmin time and Tmax time based on some static function.
> 1) Engine will run for Tmin ms.
> 2) if "game path" have not changed in the last n ms, search is finished.
> (n = Tmax-Tmin / c )
> 3) if game path changed, it will extend the search for n ms.
> 4) if total time exceeds Tmax ms. Search is finished.
>
> I think its usefull to avoid "local maximums" that can be hard to avoid,
> perhaps next move is "easier" to get a better move, so it worths to spend
> more time on next move as its "value/time" ratio is better.
>
> My 2 cents.
> Eduardo
>
> PS: Definitely I will spend more time on first moves as they decide the
> rest
> of the game.
>
> On Thursday 04 January 2007 06:04, 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.
> >
> > 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.)
> >
> > 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/
>
>
>
>
>
> __________________________________________________
> Preguntá. Respondé. Descubrí.
> Todo lo que querías saber, y lo que ni imaginabas,
> está en Yahoo! Respuestas (Beta).
> ¡Probalo ya!
> http://www.yahoo.com.ar/respuestas
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070108/01d9e212/attachment.htm