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

[Peter Drake]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070605/170a3c84/attachment.htm