[computer-go] Efficiently selecting a point to play in a random playout

[Don Dailey]

But if you are taking the vacant points out it is probably not
too biased as you say.

But what I do is pretty fast.  Always choose a random point but
keep shrinking the list.  When a point is occupied move it out
of the way so it's never selected again.   You have to do some
simple bookeeping - basically swapping the position of elements
and shrinking the list (in your terminology, maintaining a set
of empty points.)

I don't think this is any slower than what you are proposing.

I start a random game by collect vacant points - but after a 
capture move you have to re-do this operation.   Still, it's 2X
faster to collect vacant points together like (even if you are
doing everything else this way.) 



- Don

  

On Tue, 2007-06-05 at 14:45 -0400, Don Dailey wrote:
> On Tue, 2007-06-05 at 10:23 -0700, Peter Drake wrote:
> > While there is a bias in theory, I suspect that you are right that it
> > is not significant in practice if you maintain a list of vacant points
> > (as Orego now does), because almost all vacant points are legal.
> > 
> > 
> > In any case, switching to your technique (generating one random
> > starting point in the list when it's time to choose a random move
> > rather than shuffling the list at the beginning of the run) is a big
> > speed win. 
> 
> This is horribly non-random.    To illustrate,  imagine that only 2 move
> are
> legal and they are right next to each other.   ALL random choices except
> one 
> would choose the move earliest in the list.
> 
> - Don
> 
> 
> 
> 
> > On a multithreaded program like Orego (running on a multicore
> > machine), it moves the nontrivial random number generation out of the
> > synchronized part of the program and into the threads. This one change
> > instantly got me 25-30% more playouts per second.
> > 
> > 
> > Thanks for the tip!
> > 
> > Peter Drake
> > http://www.lclark.edu/~drake/
> > 
> > 
> > 
> > 
> > 
> > On May 27, 2007, at 11:39 AM, Łukasz Lew wrote:
> > 
> > > Hi,
> > > 
> > > 
> > > I've tested many approaches, and the one I implemented is clearly
> > > the best.
> > > The bias that Peter Drake talks about is negligible and doesn't have
> > > a
> > > noticeable impact
> > > on playout results.
> > > (and uniformity of playout isn't something to fight for in MC Go)
> > > 
> > > 
> > > ...
> > > 
> > > 
> > > 
> > > Best Regards,
> > > Lukasz Lew
> > 
> > 
> > _______________________________________________
> > computer-go mailing list
> > computer-go at computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
>