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

[Chrilly]

> 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.
>
Yes, There is a poor-mans parallel algorithm in chess/Alpha-Beta. The 
programms just share a hashtable. Otherwise there is no explicit parallel 
communication. The move-ordering is only slightly different in the 
processes. Thats all. This works reasonable for 2 processors. For 4 the 
speedup is not impressive.
One can refine this algorithm. When a processor starts to calculate a move, 
the move is entered as "open" in the hashtable. The other processes do not 
calculate an open move as long as they have something other to do (Only the 
first move is calculated always).
Maybe a similar idea can be used in UCT.

Chrilly