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

[Eduardo Sabbatella]

Hello


> UCT is in many positions
> very selective. The branching may occur at the root
> but also very deep in the
> tree. For example, if there are two main variations
> most branching may 
> occur at
> ply 3-n for both variations. This very true for 7x7
> wheras for 19x19 this is
> less of a problem.

That implies that different simulations can't be sum
to create a better simulation in a whole, at least for
the next round ?

> A second problem is that UCT opearates on single
> simulations. With a awful lot
> of processors I think they will keep the master
> processor saturated with
> updating the tree. Thus the tree might need to be
> distributed as well and then
> there will be no simple way of doing this.

The whole point on parallel programming is avoid to
one processor wait for information generated from
other.

You don't have to maintain the hash sinchronized at
all in real time. Because it will hurt the whole
cluster.

Think about this from another point of view:

- you have a lot of processor power, you don't have to
optimize processor power, but what you have to
optimize is the comunication between them. the
_sequencial_ dependencies.


The good point about MC is randomness, the probability
of simulating exactly the same game in 2 different
servers is almost impossible. So, you are not wasting
'too much' time. (perhaps you are simulating something
not soo usefull, but at least, a bit bit usefull...
better than just waiting doing nothing).

Another point, ok UCT gives the "direction"/directs MC
to be more efficient. Not simulating useless moves
(like A1 on 8th move).   Ok. Perhaps in some servers
you simulate that. But the whole point is, you don't
need to know _exactly_ in the same moment that its
finished in other server, in all the other servers. So
you can optimize in that way.  

Optimize it in this way: 'lazy' transpositions tables.
Try to update them as soon as possible. But never wait
them to be synchronized. 


> If one finds a good way to paralellize a search
> algorithm, it is probably
> because it was inefficient from the very beginning.

That is not true.

Paralellization is about avoiding
sequencial/inter-dependant parts in an algorithm, not
about algorithm "efficiency" by itself.

Some algoriths have more parts that can be run at the
same time without inter-dependencies... Anothers
algorithms can't.  Its up to the problem/solution
itself, not to the algorithm eficiency per se.


I hope it helps to clarify.
Im not sure about the parallel UCT solution at all...
please give me your comments.

my 2 cents

Eduardo


	
	
		
__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya! 
http://www.yahoo.com.ar/respuestas