On Tue, May 13, 2008 at 11:57 PM, Hideki Kato <[EMAIL PROTECTED]> wrote:
>
> Álvaro Begué: <[EMAIL PROTECTED]>:
> >Ooops! I hit sent before I finished writing the pseudo code. Sorry.
> >
> >int pick(Move *empties, int num_empties) {
> > int num_candidates = num_empties;
> > int picked;
> >
> > while(1) {
> > picked = rand()%num_candidates;
>
> This code introduces few bias unless num_candidates is a power of two,
> though.
> #Assuming rand() returns [0 .. power of two).
Oh, please. I should probably just take that as a provocation and
ignore it, but I am weak. :)
The pseudo-code I posted was meant to illustrate the process by which
you move an element to the end and then exclude it from the lottery.
rand()%num_candidates is just a quick way of telling the reader "pick
a random integer in [0,num_candidates)".
Besides, some people didn't care if a point had probability that was
twice as large as the rest. In my system, RAND_MAX is 2147483647,
which means that in the worst case, some points will have a
probability that is a factor of 5948709/5948708=1.00000016810372941485
larger than the rest. Even I can live with that.
Preemptive argument: Now someone will point out that the last few bits
of rand() may not be very random in some common implementations, so in
the case where num_candidates is a power of two I may have some
biases. Please, reread two paragraphs above, or substitute rand() with
the Mersenne twister.
Álvaro.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
