Quoting Sylvain Gelly <[EMAIL PROTECTED]>:
Hello Magnus,
I am glad to hear your experiment in 19x19.
Your pruning is based on expert go knowledge or another statistic?
Do have some statistics of the level of your pruning method against another
program (let's say gnugo :)) in 19x19?
There are several ways it prunes. The Valkyria code itself refuses to
play some
really bad moves in the simulations such as destroying its own eyeshape. These
moves are also pruned at the root. In the opening a lot of moves can be pruned
by pattern matching and these I can make by hand (go knowledge - but
not really
at expert level). Finally I use a pruning method I have been using with non-MC
programs where moves evaluated bad at ply n is pruned when they are evaluate
again at ply n + 2 and their local neighborhood has not been changed. This
method is a little crude and perhaps a little risky, but the gains clearly
outweighs the disadvantages.
I have not made any test yet, since it is all in development. None of the
methods above changes the UCT-search itself. It is just some crude means to
generate fewer moves.
But I have been thinking about the UCT-search and think it has a problem that
maybe some mathematical guy like you can fix in sound way. The thing is
that on
19x19 there can be several 100 candidate moves. Given inifinite time
the search
will find the best move. But when it is very little time *left* to search I
think it is a waste of time to spend effort on the moves that are the worst
since they seem very unlikely to become the best move before we run out
of time
(at some point in time it is even impossible). I think the ideal algorithm
should be sensitive to the time left and start to prune moves accordingly. UCT
already does this to some extent, but I believe it does so only with very long
thinking times.
The only idea I had in this direction is that is probably never bad to
prune the
worst candidate in every position after some effort has been made. But
how many
moves with bad evaluations canbe pruned and under what conditions?
-Magnus
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
