MT or KISS ?

[Daniel Shawul]

No need for complex PRNG if you need it only for zobrist hashing. Heck I even use the default LCG for monte carlo simulations. Make sure you take the upper bits when you form a 64 bit random number. Here is code for the Microsoft version of rand that generates 64 bit numbers too.

Code: Select all

#define MY_RAND_MAX  0x7fff

struct PRNG {
	U32 randn;

	void seed(int sd) {
		randn = sd;
	}

	U32 rand() {
		randn *= 214013;
		randn += 2531011;
		return ((randn >> 16) & MY_RAND_MAX);
	}

	U64 rand64() {
		return((U64)rand()) ^ 
			  (&#40;U64&#41;rand&#40;) << 15&#41; ^ (&#40;U64&#41;rand&#40;) << 30&#41; ^
			  (&#40;U64&#41;rand&#40;) << 45&#41; ^ (&#40;U64&#41;rand&#40;) << 60&#41;;
	&#125;
&#125;;

[petero2]

I'm presently working on a Java engine which I'd like to keep fairly streamlined. Thus I'm looking to replace several pages of 0xblah, blah blah random numbers with a few lines of code: my_prng()

This is what I use in CuckooChess to generate the "random" numbers used for Zobrist hashing:

Code: Select all

    private final static long getRandomHashVal(int rndNo) {
        try {
            MessageDigest md = MessageDigest.getInstance("SHA-1");
            byte[] input = new byte[4];
            for &#40;int i = 0; i < 4; i++)
                input&#91;i&#93; = &#40;byte&#41;(&#40;rndNo >> &#40;i * 8&#41;) & 0xff&#41;;
            byte&#91;&#93; digest = md.digest&#40;input&#41;;
            long ret = 0;
            for &#40;int i = 0; i < 8; i++)
                ret ^= (&#40;long&#41;digest&#91;i&#93;) << &#40;i * 8&#41;;
            return ret;
        &#125; catch &#40;NoSuchAlgorithmException ex&#41; &#123;
            throw new UnsupportedOperationException&#40;"SHA-1 not available");
        &#125;
    &#125;

This is of course quite a slow way to generate pseudo random numbers, but it is still way faster than needed.

[Dan Honeycutt]

Thanks, all, for your suggestions. I settled on George Marsaglia's KISS routine. I found a FORTRAN (which, like Java that I'm working in, uses signed integers) version at:

http://compgroups.net/comp.lang.fortran ... ngs/601519

Someone had done a Java translation though it wasn't very compact. George gave a test value which was handy since I managed to screw it up on the first try. Anyhow, after some twiddling I ended up with:

Code: Select all

//Java adaptation of Fortran version by George Marsaglia posted at:
//compgroups.net/comp.lang.fortran/64-bit-kiss-rngs/601519
static long kiss_x = 1234567890987654321L;
static long kiss_y = 362436362436362436L;
static long kiss_z = 1066149217761810L;
static long kiss_c = 123456123456123456L; 

static long kiss() {
  long t = &#40;kiss_x << 58&#41; + kiss_c;
  long s_x = kiss_x >>> 63;
  if &#40;s_x == &#40;t >>> 63&#41;) &#123;
    kiss_c = &#40;kiss_x >>> 6&#41; + s_x;
  &#125; else &#123;
    kiss_c = &#40;kiss_x >>> 6&#41; + 1L - (&#40;kiss_x + t&#41; >>> 63&#41;;
  &#125;
  kiss_x += t;
  kiss_y ^= &#40;kiss_y << 13&#41;;
  kiss_y ^= &#40;kiss_y >>> 17&#41;;
  kiss_y ^= &#40;kiss_y << 43&#41;;   
  kiss_z = 6906969069L * kiss_z + 1234567L;
  return &#40;kiss_x + kiss_y + kiss_z&#41;;
&#125; 

static void test_kiss&#40;) &#123;
  long n1 = 0L;
  int i1;
  for &#40;i1 = 0 ; i1 < 100000000; i1++) &#123;
      n1 = kiss&#40;);
  &#125;
  if &#40;n1 == 1666297717051644203L&#41; &#123;
      System.out.println&#40;"100 million uses of Kiss OK");
  &#125; else &#123;
      System.out.println&#40;"Fail");
  &#125;
&#125; 

Here are George's C and FORTRAN versions from the link above in case they might be of interest to someone:

Code: Select all

#include <stdio.h>

static unsigned long long
x=1234567890987654321ULL,c=123456123456123456ULL,
y=362436362436362436ULL,z=1066149217761810ULL,t;

#define MWC &#40;t=&#40;x<<58&#41;+c, c=&#40;x>>6&#41;, x+=t, c+=&#40;x<t&#41;, x&#41;
#define XSH ( y^=&#40;y<<13&#41;, y^=&#40;y>>17&#41;, y^=&#40;y<<43&#41; )
#define CNG ( z=6906969069LL*z+1234567 )
#define KISS &#40;MWC+XSH+CNG&#41;

int main&#40;void&#41;
&#123;int i;
for&#40;i=0;i<100000000;i++) t=KISS;
&#40;t==1666297717051644203ULL&#41; ?
printf&#40;"100 million uses of KISS OK")&#58;
printf&#40;"Fail");
&#125;

Code: Select all

program testkiss
implicit integer*8(a-z)
do i=1,100000000; t=KISS(); end do
if(t.eq.1666297717051644203_8) then
print*,"100 million calls to KISS() OK"
else; print*,"Fail"
end if; end

function KISS()
implicit integer*8(a-z)
data x,y,z,c /1234567890987654321_8, 362436362436362436_8,&
1066149217761810_8, 123456123456123456_8/
save x,y,z,c
m(x,k)=ieor(x,ishft(x,k)) !statement function
s(x)=ishft(x,-63) !statement function
t=ishft(x,58)+c
if(s(x).eq.s(t)) then; c=ishft(x,-6)+s(x)
else; c=ishft(x,-6)+1-s(x+t); endif
x=t+x
y=m(m(m(y,13_8),-17_8),43_8)
z=6906969069_8*z+1234567
KISS=x+y+z
return; end

Best
Dan H.

[lucasart]

Hi all,

Anyone have a preference between the Mersenne twister, KISS, or some other PRNG?

Thanks
Dan H.

I think it's all a matter of taste. You can even hardcode all the numbers that you need. After all, what we need is just to fill an array of zobrist of size NB_COLOR x NB_PIECE x NB_SQUARE, plus a few other special keys (en pasant, castling, and turn of play). All we need is that these numbers are drawn from sufficiently random source, so that recombining them with XOR operation "rarely" leads to collisions.
I think Mersenne Twister, KISS generators, and a ton of other possibilities are all good for the job, so long as they don't have any obvious flaw, and are *properly seeded*.
As a matter of taste, I'd rather use a nice KISS that is elegant and uses only a few lines of code, rather than an obfuscated mersene twister (speed doesn't matter because we only calc a few nubers at program initialization). I use the following KISS generator, attributed to Heinz Van Saanen, that I found in StockFish (though I seed it more simply than SF)

Code: Select all

static inline uint64_t rol(uint64_t x, unsigned k)
&#123; return &#40;x << k&#41; | &#40;x >> &#40;64 - k&#41;); &#125;

uint64_t rand64&#40;)
// 64-bit KISS RNG by Heinz Van Saanen
&#123;
	static uint64_t	// seeds
		a = 0x5bc5cd8748be9fe8,
		b = 0x5164ed10aa17c81,
		c = 0x105730377a2a0e9c,
		d = 0xe6b137acae0d8b76;
	
	const uint64_t e = a - rol&#40;b,  7&#41;;
	a = b ^ rol&#40;c, 13&#41;;
	b = c + rol&#40;d, 37&#41;;
	c = d + e;
	return d = e + a;
&#125;

But even an LCG is OK, so long as you seed it properly and that the numbers a and b (such that your LCG is x(t) = a.x(t-1)+b modulo 2^64) verify the proper conditions that give full period to the LCG. Solutions like taking 2 32 bit LCG and combining them work fine, or a 64 bit one and combining 32 bit of one drawing and 32 bit of the next, etc.

The only real question, is how do you know that your zobrist keys are "good enough" ? The only thing I've found is coding a perft with hash tables, and verifying that different zobrist approach give same result on a lot of positions at high depth. I just did it to reassure myself.

[Rémi Coulom]

I use the following KISS generator, attributed to Heinz Van Saanen, that I found in StockFish (though I seed it more simply than SF)

It is actually by Bob Jenkins:
http://burtleburtle.net/bob/rand/smallprng.html

The only real question, is how do you know that your zobrist keys are "good enough" ? The only thing I've found is coding a perft with hash tables, and verifying that different zobrist approach give same result on a lot of positions at high depth. I just did it to reassure myself.

You can compare different approaches by using only a small number of bits, which increases the probability of collision to a point where it is measurable.

I am not aware of any research that produces better performance than a good rng, though.

Rémi

[lucasart]

I found a FORTRAN (which, like Java that I'm working in, uses signed integers)

You seem to be quite a competent programmer. So why do you punish yourself with Java

[Dan Honeycutt]

I found a FORTRAN (which, like Java that I'm working in, uses signed integers)

You seem to be quite a competent programmer. So why do you punish yourself with Java

I can't answer right now, got an appointment with my dominatrix in a little while.

Best
Dan H.

[voyagerOne]

@ Peter:

What's the danger of simply using SecureRandom nextLong()?

@All:
I am also starting to implement TT in my engine.
What is appropriate # of buckets? How many entries for each bucket?

Also... can I simply use modulus for the hash function? If so... what's a "good" modulus number to use? Should it be prime?

Bill

[michiguel]

@ Peter:

What's the danger of simply using SecureRandom nextLong()?

@All:
I am also starting to implement TT in my engine.
What is appropriate # of buckets? How many entries for each bucket?

If you are starting, do not do anything fancy. Just one entry that is overwritten. That is very good already. Any improvement over that is not worth the trouble until to pick so many other low hanging fruits.

Miguel

Also... can I simply use modulus for the hash function? If so... what's a "good" modulus number to use? Should it be prime?

Bill

[voyagerOne]

Thanks! My thoughts exactly.