How much time should a program spend on each move?
I think this is one of the most important and also difficult questions in
game programming. Much effort is done to speed up the node-count by 10%, but
a good time control is a much more effective speedup.
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.
One should at least use t/(m+1). There is also a locial reason for this. If
m is very small, especially m==1 one should have some extra time if the
programm recognizes a problem. In this case it should search deeper.
Generally this t/(m+k) should only be a target time. The final decision
should be based on the results of the search. It is important to recognize
trivial/forced moves and to stop in this cases search earlier. If the
programm sees a problem than it should search longer.
I have made recently a simple (but strong) UCT backgammon programm. UCT
gives much better information for time-control than Alpha-Beta. E.g. if
almost all search effort is concentrated on the best move, one can
reasonable conclude that its a trivial/forced move. If the eval of the best
moves decreases in the last period constantly and there are some chances
that the second best becomes best, one should search on....
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.)
Go-Programmers like it complicated.
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?
One should forget human behaviour. If I would have to make a Turing test -
is the player human or a programm - I would not look at the moves but on the
time behaviour. The fundamental difference is that (good) humans know when
the position is difficult and when its easy. Programms have no understanding
of this at all. Humans play Chess/Go, programm make chess/Go moves.
Consequently humans think for a few moves very long, and play other moves
rather fast. But I think that the time-control of humans is not at all
optimal. Its very human to try to solve an urgent problem even at the risk
that it makes solving a further problem more difficult. Humans tend
therefore to get into Zeitnot.
When playing against GM Adams I proposed 40 Moves in 2 hours. He proposed 40
Moves in 1 hour 40 minutes plus 30 sek/move. In the first moment I could not
see the difference. In both cases one has 2 hours for 40 moves. But at move
30 its different. The flag is falling there already at 1h 55 minutes. Its a
psychological trick to avoid extreme Zeitnot. But if the human would have a
good time-control "algorithm" there is no need for this trick. He could save
this 30 seks for himself.
Chrilly
Note: One should forget human behaviour generally. A programm is a programm
is a programm.
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
