[Pachi] Play multiple games per descent ?

lemonsqueeze lemonsqueeze at free.fr
Tue May 17 21:56:20 CEST 2016

Awesome, thanks for all the answers.
I have a lot to catch up on, so much to read !

Btw, is there a list of influential papers somewhere ?
I'm kindof working my way through references in other papers and somehow 
i have a feeling this may not be the best way to go
about it =)

On 05/17/2016 07:37 PM, Erik S. Steinmetz wrote:
> Greetings,
> Since I’m sorting through these references right now, I can point you at
> a 2008
> paper by Chaslot, Winands, and van den Herik discussing various kinds of
> parallelization where the relevant paragraphs talking about leaf
> parallelization
> are in section 3.1:
> Leaf parallelization introduced by Cazenave and Jouandeau [3] is one of
> the easiest ways to parallelize MCTS. To formulate it in
> machine-dependent terms, only one thread traverses the tree and adds one
> of more nodes to the tree when a leaf node is reached (phase 1 and 2).
> Next, starting from the leaf node, independent simulated games are
> played for each available thread (phase 3). When all games are finished,
> the result of all these simulated games is propagated backwards through
> the tree by one single thread (phase 4). Leaf parallelization is
> depicted in Fig. 2a.
> Leaf parallelization seems interesting because its implementation is
> easy and does not require any mutexes. However, two problems appear.
> First, the time required for a simulated game is highly unpredictable.
> Playing n games using n different threads takes more time in average
> than playing one single game using one thread, since the program needs
> to wait for the longest simulated game. Second, information is not
> shared. For instance, if 16 threads are available, and 8 (faster)
> finished games are all losses, it will be highly probable that most games
> Parallel Monte-Carlo Tree Search 63
> page4image992
> Fig.2. (a) Leaf parallelization (b) Root parallelization (c) Tree
> parallelization with global mutex (d) and with local mutexes
> will lead to a loss. Therefore, playing 8 more games is a waste of
> computational power. To decrease the waiting time, the program might
> stop the simulations that are still running when the results of the
> finished simulations become available. This strategy would enable the
> program to traverse the tree more often, but some threads would be idle.
> Leaf parallelization can be performed inside an SMP environment, or even
> on a cluster using MPI (Message Passing Interface) communication.
> Here’s the ref in bibtex format:
> @inproceedings{Chaslot:2008fk,
>    author    = {Guillaume Chaslot and
>                 Mark H. M. Winands and
>                 H. Jaap van den Herik},
>    title     = {Parallel {M}onte-{C}arlo {T}ree {S}earch},
>    booktitle = {Computers and Games, 6th International Conference, {CG}
> 2008, Beijing,
>                 China, September 29 - October 1, 2008. Proceedings},
>    pages     = {60--71},
>    year      = {2008}
> }
> You may also want to look at Kato 2008 where a client-server model is
> set up, and the result
> propagation does not wait for all the results to come in, thus partially
> alleviating one of the
> above problems:
> @inproceedings{Kato:2008pm,
>    title={Parallel monte-carlo tree search with simulation servers},
>    author={Kato, Hideki and Takeuchi, Ikuo and others},
>    booktitle={13th Game Programming Workshop (GPW-08)},
>    year={2008}
> }
> Obviously, Beijing was the place to be in fall of 2008! :-)
> I hope that helps,
> Erik
>> On May 17, 2016, at 10:12 AM, Petr Baudis <pasky at ucw.cz
>> <mailto:pasky at ucw.cz>> wrote:
>>  This was one of the ideas when people were exploring MCTS
>> parallelization, to batch playouts and play them in parallel after
>> a single descent - it's essentially something very similar to what
>> you described.  But it didn't work really well, the details are in
>> the respective papers.
>> On Tue, May 17, 2016 at 05:05:24PM +0200, lemonsqueeze wrote:
>>> Hi,
>>> Playing with my moggy test suite got me wondering about the difference
>>> between raw playout speed and in-game speed (about 2200 games/s vs
>>> 1600 games/thread/s here)
>>> I guess it's probably unreasonable to expect something similar with the
>>> additional thread synchro and tree logic, but still it got me wondering:
>>> since we're going to visit each node many times, would it make sense
>>> to play
>>> more than one game per descent ? I'm playing with this patch in my
>>> uct_multigames branch, playing 100 games makes it about 10% faster (~1800
>>> games/s)
>>> Does this sound like a good idea at all ?
>>> It seems to be losing a lot though, maybe this just breaks uct badly =)
>>> Cheers
>>> _______________________________________________
>>> Pachi mailing list
>>> Pachi at v.or.cz <mailto:Pachi at v.or.cz>
>>> http://rover.ms.mff.cuni.cz/mailman/listinfo/pachi
>> --
>> Petr Baudis
>> If you have good ideas, good data and fast computers,
>> you can do almost anything. -- Geoffrey Hinton
>> _______________________________________________
>> Pachi mailing list
>> Pachi at v.or.cz <mailto:Pachi at v.or.cz>
>> http://rover.ms.mff.cuni.cz/mailman/listinfo/pachi

More information about the Pachi mailing list