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

[sylvain.gelly at m4x.org]

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