[Pachi] Play multiple games per descent ?

lemonsqueeze lemonsqueeze at free.fr
Wed May 18 14:17:09 CEST 2016


Thanks, that should keep me busy for a while.

Good luck for your Ph.D Erik !


On 05/17/2016 11:56 PM, Petr Baudis wrote:
>    Hi!
>
>    I'd recommend to take a look at the references of
> http://pasky.or.cz/go/prace.pdf which is my answer to the same question
> in about 2011-2012.  For newer works, look at which papers cite your
> most favorite ones that you have found.  For some areas, the AlphaGo
> paper has a pretty rich set of references.
>
> On Tue, May 17, 2016 at 09:56:20PM +0200, lemonsqueeze wrote:
>> 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