MT or KISS ?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Dan Honeycutt
Posts: 5147
Joined: Mon Feb 27, 2006 3:31 pm
Location: Atlanta, Georgia

MT or KISS ?

Post by Dan Honeycutt » Sat Jun 02, 2012 12:38 am

Hi all,

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

Thanks
Dan H.

diep
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: MT or KISS ?

Post by diep » Sat Jun 02, 2012 4:19 pm

Dan Honeycutt wrote:Hi all,

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

Thanks
Dan H.
Where do you need it for and how many numbers do you want it to generate?

bob
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: MT or KISS ?

Post by bob » Sun Jun 03, 2012 4:07 pm

Dan Honeycutt wrote:Hi all,

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

Thanks
Dan H.
I think all work well for chess. You don't need that many numbers so cycling is not an issue...

User avatar
Dan Honeycutt
Posts: 5147
Joined: Mon Feb 27, 2006 3:31 pm
Location: Atlanta, Georgia

Re: MT or KISS ?

Post by Dan Honeycutt » Sun Jun 03, 2012 6:14 pm

diep wrote:Where do you need it for and how many numbers do you want it to generate?
For hashing. only about a thousand values.

Best
Dan H.

User avatar
michiguel
Posts: 6386
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: MT or KISS ?

Post by michiguel » Mon Jun 04, 2012 4:52 am

Dan Honeycutt wrote:
diep wrote:Where do you need it for and how many numbers do you want it to generate?
For hashing. only about a thousand values.

Best
Dan H.
After trying different things, I settled for hardwiring them with numbers from here http://www.random.org/

Miguel

User avatar
Dan Honeycutt
Posts: 5147
Joined: Mon Feb 27, 2006 3:31 pm
Location: Atlanta, Georgia

Re: MT or KISS ?

Post by Dan Honeycutt » Mon Jun 04, 2012 5:30 am

michiguel wrote:
Dan Honeycutt wrote:
diep wrote:Where do you need it for and how many numbers do you want it to generate?
For hashing. only about a thousand values.

Best
Dan H.
After trying different things, I settled for hardwiring them with numbers from here http://www.random.org/

Miguel
Hi Miguel,

Can you elaborate a bit on "After trying different things"? With my C engines (Simon and Bruja) I do the same thing. 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()

It is my opinion, based solely on gut feel rather than on any basis in probability and statistics, that hashing with numbers generated with a good prng are going to suffer no more than one in a zillion more collisions than hashing with true random numbers. However, I'm entirely open to contrary opinions, especially from someone with some math to back up what they say.


Best
Dan H.

User avatar
michiguel
Posts: 6386
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: MT or KISS ?

Post by michiguel » Mon Jun 04, 2012 5:54 am

Dan Honeycutt wrote:
michiguel wrote:
Dan Honeycutt wrote:
diep wrote:Where do you need it for and how many numbers do you want it to generate?
For hashing. only about a thousand values.

Best
Dan H.
After trying different things, I settled for hardwiring them with numbers from here http://www.random.org/

Miguel
Hi Miguel,

Can you elaborate a bit on "After trying different things"? With my C engines (Simon and Bruja) I do the same thing. 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()

It is my opinion, based solely on gut feel rather than on any basis in probability and statistics, that hashing with numbers generated with a good prng are going to suffer no more than one in a zillion more collisions than hashing with true random numbers. However, I'm entirely open to contrary opinions, especially from someone with some math to back up what they say.

Best
Dan H.
I tried a couple of public domain generators from the net. I don't remember now, but I can dig it from the old source code. Anyway, I do not think they were anything special.

I agree that there should be any difference in strength. I think this is all a matter of taste.

Miguel

User avatar
Dan Honeycutt
Posts: 5147
Joined: Mon Feb 27, 2006 3:31 pm
Location: Atlanta, Georgia

Re: MT or KISS ?

Post by Dan Honeycutt » Mon Jun 04, 2012 6:09 am

michiguel wrote:I think this is all a matter of taste.

Miguel
Okay. Thanks for your input.

Best
Dan H.

diep
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: MT or KISS ?

Post by diep » Mon Jun 04, 2012 8:30 am

diep wrote:
Dan Honeycutt wrote:Hi all,

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

Thanks
Dan H.
Where do you need it for and how many numbers do you want it to generate?
Really lots will work. Just make sure it generates 64 bits numbers and not 32 bits. The standard tests used for RNG's to see them as being ok are more than sufficient for Zobrist.

If you don't want to research all that,
the cheapest safe idea is always to store it in an array in hex and then modify something by hand at 4 AM using the overwrite and write a 0 here and a 1 there an a 'f' somewhere else and do that for all 16 characters.

User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 10:00 am
Location: Slovakia, EU

Re: MT or KISS ?

Post by rvida » Mon Jun 04, 2012 11:20 am

This is what Critter uses:

Code: Select all

const unsigned int rnd_seed[55] = {
  0x5414d5f4, 0xb3935330, 0xd0773e27, 0xac62a182,
  0x5db20c92, 0xc1e618ac, 0xd003926a, 0x171fa3b3,
  0x9ad12101, 0x762172c1, 0xbc5d9dc3, 0x07b72a70,
  0x6e5ac890, 0xf7be54d1, 0x0d6332fa, 0x56ba8fbe,
  0xeba585ec, 0x571421c5, 0x96b3c079, 0x12eb9b92,
  0xc07c0978, 0x0700c5bd, 0x31a43513, 0x74eba4aa,
  0x4ec55db5, 0x2c91c2e9, 0x208771f6, 0x304ee204,
  0x1e004673, 0xf3ac22f9, 0xa8561feb, 0xded13435,
  0xd03e7513, 0xdae66bc2, 0x01c20be1, 0x46638997,
  0xfb26ce62, 0x01f87fc3, 0xc0016099, 0x44429270,
  0xb04f4481, 0xf31b8ad7, 0x86dd7a46, 0x03e72091,
  0x96a22589, 0x74dcb7d4, 0x12d0fc03, 0x474a16e8,
  0x2ff5717c, 0x54bded92, 0x783a9487, 0xe767978c,
  0x3052d5cd, 0x16eca191, 0x8eaf6d15
};

static unsigned int rnd_tab[55];
static int rnd_j, rnd_k;

void init_random() {
  for &#40;int i = 0; i < 55; i++)
    rnd_tab&#91;i&#93; = rnd_seed&#91;i&#93;;
  rnd_j = 23;
  rnd_k = 54;
&#125;

unsigned int random32&#40;) &#123;
  unsigned int rnd = &#40;rnd_tab&#91;rnd_k&#93; += rnd_tab&#91;rnd_j&#93;);
  if (--rnd_j < 0&#41; rnd_j = 54;
  if (--rnd_k < 0&#41; rnd_k = 54;
  return rnd;
&#125;

Key random64&#40;) &#123;
  Key a = random32&#40;), b = random32&#40;);
  return &#40;a << 32 | b&#41;;
&#125; 
PS. "Key" is a typedef for "uint64_t"

Post Reply