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

[Don Dailey]

Here are a couple of ideas that are efficient in terms of parallelism:

  IDEA 1

   1. Start all nodes searching the root position.
   2. At timeout, combine all the stats from each node.

  IDEA  2

   1. Start all nodes searching the root position for a predetermined 
      small chunk of time, perhaps a second or two.

   2. Merge all the tree's produced together into a single tree.

   3. Distribute new tree to all nodes and repeat.

- Don
  


On Mon, 2006-10-02 at 10:45 +0200, sylvain.gelly at m4x.org wrote:
> Le Lundi 02 Octobre 2006 10:25, Darren Cook a écrit :
> > > as we have access here to an interesting cluster, I have worked several
> > > weeks on a way to efficiently distribute UCT. ...
> > > I have tried a lot of solutions, which seemed good ideas, but none of
> > > theses were so far successful.
> >
> > I was about to suggest the first few ideas that came to mind but you've
> > probably already thought of them. 
> Perhaps, but often the first few ideas are the best, so please go ahead :-).
> 
> > Would you be willing to post about the 
> > ideas you've already tried that failed?
> I'll try. I hope it will be clear enough.
> 
> - basic try: giving to each machine one possible move (assume that you have 
> enough machine), and each machine compute the value for this move. It is not 
> a real parallelization of UCT, but it was so simple that I tried. You don't 
> win so much this way.
> 
> - Basic unit: a node (a position). This is the chunk. Then the client compute 
> all possible results for this position, that is to say, for each possible 
> move, the result of one simulation. Then the data to send back is only 
> numberOfMoves bits. 
>   - Then imagine you have one server which keep the tree, and n clients. 
>   - The server use normal UCT, and when it encounters a leaf in its tree, if 
> this node is not already in a client, send it to a client, and do its 
> simulation as usual. 
>   - When the data from the client comes back, you update the tree as if all 
> the simulations where done by the server.
> The BIG problem here is that you introduce a big bias in the algorithm.
> 
> - Variant: instead of computing all the possible moves from a child, compute 
> only a part (m moves). The problem is that if m is too small, the network 
> delay is too big, and if m is too big, you have the previous problem.
> - Variant: when the message comes back, instead of updating tree as UCT would 
> update it, keep the same number of simulations for each node, but update the 
> probability using the new simulations you get.
> - Variant: when the message comes back you don't update the tree, but keep the 
> result in an hashtable for further use. Then the UCT algorithm is not changed 
> at all, but you don't win so much speed that way.
> 
> I have tried some others small variants on this idea. I have also though about 
> keeping a tree for each machine, and try to synchronize it as often as 
> possible using the information from the others. But I think it would be very 
> complicated, and I am not so convinced that it would be possible to keep the 
> tree consistent.
> 
> I hope the ideas are not too badly exposed.
> 
> Sylvain
> 
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/