[computer-go] 10k UCT bots

[Álvaro Begué]

On Tue, May 13, 2008 at 11:57 PM, Hideki Kato <hideki_katoh at ybb.ne.jp> wrote:
>
>  Álvaro Begué: <7b0793ea0805131100l4d804937k6814b9f4f481a89d at mail.gmail.com>:
>  >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.