Quoting [EMAIL PROTECTED]:
I'm curious about the full width depth and the principal variation depth to
compare UCT wilth alpha-beta.
The comparison is not so easy to do I think, because using MC as an
evaluation
function for alpha beta, you have to do several simulations for one
evaluation and take the average. So the question is "how many simulations to
do" (tradeoff "false alpha-beta cuts"/"depth")? The right should be "the
number which makes the stronger player". I did not made such experiments.
Perhaps someone did?
My old program Viking5 used alphabeta with monte carlo evaluation and
alpha-beta
search. Valkyria uses UCT and similar code for Monte Carlo evaluation. One
cannot compared these programs directly since they do not share code. But I
would guess that alkyria would search the principle variation to
20-100% deeper
depth than Viking5 would. The cost is that Valkyria might sometimes get
stuck on
the second best move. In the opening the difference is probably small becuase
UCT searches quite uniform, but if there is fighting where critical stones are
very unstable the seacrh can get very deep if there are many forcing moves. I
know at least one 9x9 position where Valkyria can search forced
sequences to 15
ply, but normally perhaps it might get 4-5 meaningful nodes deep where Viking5
would get 3 ply.
It is also tricky to compare the principal eval of UCT with alpha-beta because
near the leaf the number of visits to the nodes are less than what could be
considered "sound" MC-eval. When I print out principal variations I stop as
soon as the number of visits for a node is less than 1000. This means that the
moves in the pruned principle variation is of high quality.
For alpha-beta a similar effect can be seen by choosing different amounts of
simulations for the eval. Normally a few 100 simulations is necessary but one
could make 1 simulation eval that spits out very deep evals that unfortunately
is almost random.
-Magnus
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
