[Pachi] Play multiple games per descent ?

Petr Baudis pasky at ucw.cz
Tue May 17 23:56:09 CEST 2016


  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
> >
> 

-- 
				Petr Baudis
	If you have good ideas, good data and fast computers,
	you can do almost anything. -- Geoffrey Hinton


More information about the Pachi mailing list