[computer-go] 10k UCT bots

[Hideki Kato]

I didn't against you, Álvaro, rather I just made a caution for 
programmers who will use your pseudo code as is. :)

First, I prefer SFMT (SIMD-oriented Fast Mersenne Twister) rather 
than integer pseudo random number generators in practice where the 
quality of play-out is important.  Modern processors execute floating 
operations as fast as interger ones and
	picked = mt_rand() * (double) num_candidates;
is the simplest and safe. 
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html
#Converting int to double is, in fact, not so fast that 
using double num_candidate through out the code may be faster.

When using integer pseudo random number generators and keeping exact 
uniform distribution, following code can be used (slower twice).  
This discards extra random numbers that bias the distribution.
#As Álvaro wrote, if n << RAND_MAX the bias is very small and may be 
ignored.

unsigned long exactly_uniform_random(unsigned long n) { 
  unsigned long m, r; 
  if  (n == 0) return 0; 
  m = RAND_MAX % n; 
  do { 
    r = rand(); 
  } while (r <= m) ; 
  return r % n; 
} 

In addition, xor_shift is better than builtin rand() and faster and 
much smaller than MT.  #Hiroshi, the author of Aya, uses this.
http://en.wikipedia.org/wiki/Xorshift
http://www.jstatsoft.org/v08/i14/paper

unsigned long xorshiftrand(void) { 
  static unsigned long
    x=123456789, y=362436069,
    z=521288629, w=88675123; 
  unsigned long t; 
  t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
} 

-Hideki

Álvaro Begué: <7b0793ea0805140305h75008e92i395d73238c8bf09e at mail.gmail.com>:
>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.
>_______________________________________________
>computer-go mailing list
>computer-go at computer-go.org
>http://www.computer-go.org/mailman/listinfo/computer-go/
--
gg at nue.ci.i.u-tokyo.ac.jp (Kato)