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@computer-go.org > > http://www.computer-go.org/mailman/listinfo/computer-go/ > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
