[computer-go] Improvement of UCT search algorithm

[Magnus Persson]

Quoting Don Dailey <drd at mit.edu>:

> On Mon, 2006-10-09 at 10:21 +0200, sylvain.gelly at m4x.org wrote:
>
> What I would prefer is a time-control scheme that is even more dynamic.
> Right now I allocate progressively less time to each move as the game
> proceeds, and that is a good thing in general,  but often you waste a
> lot of time considering whether to play the only obvious move and other
> times you play too quickly when the right move needs to be carefully
> considered.    I believe there is much to be gained here too.

Since I implemented pondering (guess the next move of the opponent and think
about that position while the opponent thinks) for Valkyria, thinking too much
on obvious moves are much less of a problem. Since the effort is rewarded on
each ponder hit. In fact the stronger the opponent programs gets the guessing
of the next move of the opponent will become more easy. But maybe 
thinking less
then on obvious moves become important to prevent the opponent from using
ponder?

So my advice is to implement ponder (but be prepared for some frustrated
debugging because GTP is not "ponder-friendly") first and worry about 
this type
of time management later. But I will probably try the "avoid new best 
moves that
has not been searched by thinking longer"-idea that Don proposed.

Someone asked some days ago if Valkyria modifies the way UCT computes the
average for every node. I have not tried to do so because computing a plain
average makes the decision process more conservative. For plain UCT the values
of the nodes below the root changes very slowly, and if this is changed then
one would probably have more problems with best moves that has not been
searched properly. Also I believe that in time trouble a move that took a long
time too refute is still a good move assuming the opponent also will have
trouble to see the refutation. But I have no proof of this so please go ahead
and prove me wrong with some nice experiments.

A nice place to collect ideas to improve UCT is also at the Sensei page I set
up. It would also be fun if you add your program to the list at the bottom:

http://senseis.xmp.net/?UCT

-Magnus