[computer-go] Pay-as-you-go cluster?

[Magnus Persson]

Quoting Chrilly <c.donninger at wavenet.at>:

>
> UCT:
> Why can one not use the Hydra-trick of  hash-table replication. E.g. 
> one broadcasts the result for every node that was visited k-Times? 
> This is the only parallel communication. Would be relative trivial to 
> programm and the results are shared implictly. At the end one simply 
> takes the result of processor 0.

Ok here is a simple idea.
You wrote that the maximum speedup in alpha-beta is 25. So let us 
assume that we
have about 25 processors. Then the following might be reasonable (note that I
have not a single clue of what communications costs might be here).

All processors runs sequencial UCT, except that every time a simulation is
finished it broadcasts the result to all other processors. When it computes a
random game, a second thread keeps updating the tree from incoming broadcasts.

The problem here is that the all processors will often have about the 
same state
and thus play the same sequence which is bad since many sequences outside the
principle variation should only be played once. A simple soulution could be to
add a little noise to the decision UCT makes at every node, such that local in
time it is unlikely that a bad sequence is played simultaneously on two
processors and as soon as it has been broadcasted the risk of duplication will
be gone. If the random noise trick works one avoids any need of 
synchronisation
between the processors.

Magnus