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

[sylvain.gelly at m4x.org]

> I have not run any experiment, but this is how I would try:
>
> Have one master node that runs UCT and keeps the tree (or hash table) in
> memory. For each simulation, as soon as it leaves the part of the tree
> that is stored in memory, send the position over the network for
> simulation by a node. For this algorithm to work, it has to be
> asynchronous. That is to say, the master node should not wait for the
> reply of the simulation node before proceeding.
> [...]
> Of course, it is a lot easier to have such an idea than to make it
> actually work.

Yes, it also seems very good, and I have thought at that, but haven't tried 
because it lacks something very important: UCT is a deterministic algorithm, 
so if you don't feed the tree with something, next time UCT will give you 
exactly the same position to evaluate.

To solve that I have thought feeding the tree with a fake result, for example 
the probability found for the parent of the leaf, and when the results come 
back, putting into the tree the true value. We can also put a little random 
in UCT. I am not sure the effect we are going to introduce.

The second problem, is that the CPU cost of transmitting a message by making a 
system call is not negligeable, so you have to send several request in one 
message (buffer). In your proposed algorithm, for one bit of information (the 
result of one simulation) you have to send one position. The message will 
then take like 50 positions, and the client will do 50 simulations. So the 
difference between the behavior of the "true" UCT, and the resulting 
algorithm could be important.

Sylvain