[Computer-go] UCT parameters and application to other games

steve uurtamo uurtamo at gmail.com
Tue Apr 5 10:20:18 PDT 2011


> I think you completely miss the point.

that's super unfortunate.

but in case i haven't, let me make myself more clear:

whenever you have a distribution from which you would like to
uniformly sample, if the number of things to be sampled is small
enough, you can simply randomly reorganize them, partition them, and
ship them off to your N friends, each of which can do the sampling for
you. because it is a partition, you can simply add up their partial
results whenever they reach the (normalized) threshhold that you would
have had you sampled the distribution yourself. they don't even all
have to finish at the same time.

no matter where you are in a tree, and no matter what restrictions you
have in place on the subtree(s) to be sampled, the moment you want to
uniformly sample, you can ask your otherwise unoccupied friends to do
so for you, collect their results, and decide what to do next.

the main objection (other than my complete misunderstanding of MCTS)
that i was hearing was the concern that there would not be a uniform
distribution of interesting node expansion among the processors.
however, this concern is not valid, as the chernoff bound involved
shows that the tail events under consideration almost never happen,
especially so if you are willing to uniformly sample from a
several-node-deep view of the tree. adding up the partial results is
super easy, since each sub-sum will be prefixed by its location in the
tree.

i didn't mean anything more or less than this.

over and out for another few months,

s.



More information about the Computer-go mailing list