RKISS

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.
Gerd Isenberg
Posts: 2125
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

RKISS

Post by Gerd Isenberg » Sat Jan 01, 2011 9:39 pm

Hi,

First a happy new computer chess year to all!

Just had a look to the new RKISS prng under GPL used in Stockfish 2.0.
Interesting code, the rotates are all primes. But sub, xor, add looks a bit arbitrary.

Code: Select all

static u64 a,b,c,d;
u64 e;
e = a - (b rol 7);
a = b ^ (c rol 13);
b = c + (d rol 37);
d = e + a;
return d;
Is there any theory about that bit-twiddling available on-line? Or is such stuff more empirical trial and error?

Cheers,
Gerd

Gerd Isenberg
Posts: 2125
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: RKISS

Post by Gerd Isenberg » Sat Jan 01, 2011 10:01 pm

oups, forgot one line c = d + e:

Code: Select all

static u64 a,b,c,d;
u64 e;
e = a - (b rol 7);
a = b ^ (c rol 13);
b = c + (d rol 37);
c = d + e;
d = e + a;
return d;

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: RKISS

Post by mcostalba » Sat Jan 01, 2011 10:43 pm

Gerd Isenberg wrote: Is there any theory about that bit-twiddling available on-line? Or is such stuff more empirical trial and error?
This code was kindly donated to us by Heinz van Saanen that allowed us to license under GPL so to be merged in SF.

We just tested that it works and is 100% an alternative to mersenne.

I don't think it is just trial and error, as reported in the header:

Code: Select all

 ** A small "keep it simple and stupid" RNG with some fancy merits:
 **
 ** Quite platform independent
 ** Passes ALL dieharder tests! Here *nix sys-rand() e.g. fails miserably:-)
 ** ~12 times faster than my *nix sys-rand()
 ** ~4 times faster than SSE2-version of Mersenne twister
 ** Average cycle length: ~2^126
 ** 64 bit seed
 ** Return doubles with a full 53 bit mantissa
 ** Thread safe

And here is the dieharder tests reports:

Code: Select all

                                                                     
                                                                     
                                                                     
                                             
heinz@linux:~/junk/junk> ./a.out | dieharder -g 200 -a
#=============================================================================#
#          dieharder version 3.29.4beta Copyright 2003 Robert G. Brown        #
#=============================================================================#
   rng_name    |rands/second|   Seed   |                                       
stdin_input_raw|  2.13e+07  |4282743765|                                       
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment            
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.14890455|  PASSED              
      diehard_operm5|   5|   1000000|     100|0.02837678|  PASSED              
  diehard_rank_32x32|   0|     40000|     100|0.63612384|  PASSED              
    diehard_rank_6x8|   0|    100000|     100|0.78258674|  PASSED              
   diehard_bitstream|   0|   2097152|     100|0.73291748|  PASSED              
        diehard_opso|   0|   2097152|     100|0.36677569|  PASSED              
        diehard_oqso|   0|   2097152|     100|0.35635353|  PASSED              
         diehard_dna|   0|   2097152|     100|0.40227206|  PASSED              
diehard_count_1s_str|   0|    256000|     100|0.15631848|  PASSED              
diehard_count_1s_byt|   0|    256000|     100|0.02576356|  PASSED              
 diehard_parking_lot|   0|     12000|     100|0.33868706|  PASSED              
    diehard_2dsphere|   2|      8000|     100|0.61107903|  PASSED              
    diehard_3dsphere|   3|      4000|     100|0.37099325|  PASSED              
     diehard_squeeze|   0|    100000|     100|0.56722772|  PASSED              
        diehard_sums|   0|       100|     100|0.04022953|  PASSED              
        diehard_runs|   0|    100000|     100|0.39906252|  PASSED              
        diehard_runs|   0|    100000|     100|0.26776626|  PASSED              
       diehard_craps|   0|    200000|     100|0.74060276|  PASSED              
       diehard_craps|   0|    200000|     100|0.43273086|  PASSED              
 marsaglia_tsang_gcd|   0|  10000000|     100|0.38433496|  PASSED              
 marsaglia_tsang_gcd|   0|  10000000|     100|0.21739434|  PASSED              
         sts_monobit|   1|    100000|     100|0.13931802|  PASSED              
            sts_runs|   2|    100000|     100|0.51329448|  PASSED              
          sts_serial|   1|    100000|     100|0.39968488|  PASSED              
          sts_serial|   2|    100000|     100|0.20801423|  PASSED              
          sts_serial|   3|    100000|     100|0.22648504|  PASSED              
          sts_serial|   3|    100000|     100|0.79553793|  PASSED              
          sts_serial|   4|    100000|     100|0.13889241|  PASSED              
          sts_serial|   4|    100000|     100|0.35689448|  PASSED              
          sts_serial|   5|    100000|     100|0.32907831|  PASSED              
          sts_serial|   5|    100000|     100|0.96425371|  PASSED              
          sts_serial|   6|    100000|     100|0.29429007|  PASSED                                      
          sts_serial|   6|    100000|     100|0.67547393|  PASSED                                      
          sts_serial|   7|    100000|     100|0.27652533|  PASSED                                      
          sts_serial|   7|    100000|     100|0.43773829|  PASSED                                      
          sts_serial|   8|    100000|     100|0.00589920|  PASSED                                      
          sts_serial|   8|    100000|     100|0.00606073|  PASSED                                      
          sts_serial|   9|    100000|     100|0.36759888|  PASSED                                      
          sts_serial|   9|    100000|     100|0.41487400|  PASSED                                      
          sts_serial|  10|    100000|     100|0.85082078|  PASSED                                      
          sts_serial|  10|    100000|     100|0.25805178|  PASSED                                      
          sts_serial|  11|    100000|     100|0.52837124|  PASSED                                      
          sts_serial|  11|    100000|     100|0.05334055|  PASSED                                      
          sts_serial|  12|    100000|     100|0.67688469|  PASSED                                      
          sts_serial|  12|    100000|     100|0.84215568|  PASSED                                      
          sts_serial|  13|    100000|     100|0.99153787|  PASSED                                      
          sts_serial|  13|    100000|     100|0.76515469|  PASSED                                      
          sts_serial|  14|    100000|     100|0.26573843|  PASSED                                      
          sts_serial|  14|    100000|     100|0.26842956|  PASSED                                      
          sts_serial|  15|    100000|     100|0.45104274|  PASSED                                      
          sts_serial|  15|    100000|     100|0.40600808|  PASSED                                      
          sts_serial|  16|    100000|     100|0.50489227|  PASSED                                      
          sts_serial|  16|    100000|     100|0.65051872|  PASSED                                      
         rgb_bitdist|   1|    100000|     100|0.90681142|  PASSED                                      
         rgb_bitdist|   2|    100000|     100|0.58916697|  PASSED                                      
         rgb_bitdist|   3|    100000|     100|0.65855068|  PASSED                                      
         rgb_bitdist|   4|    100000|     100|0.98371981|  PASSED                                      
         rgb_bitdist|   5|    100000|     100|0.32509053|  PASSED                                      
         rgb_bitdist|   6|    100000|     100|0.41816883|  PASSED                                      
         rgb_bitdist|   7|    100000|     100|0.13625306|  PASSED                                      
         rgb_bitdist|   8|    100000|     100|0.98116523|  PASSED                                      
         rgb_bitdist|   9|    100000|     100|0.09052981|  PASSED
         rgb_bitdist|  10|    100000|     100|0.71922521|  PASSED
         rgb_bitdist|  11|    100000|     100|0.39864600|  PASSED
         rgb_bitdist|  12|    100000|     100|0.88463093|  PASSED
rgb_minimum_distance|   2|     10000|    1000|0.49191929|  PASSED
rgb_minimum_distance|   3|     10000|    1000|0.34086770|  PASSED
rgb_minimum_distance|   4|     10000|    1000|0.67634721|  PASSED
rgb_minimum_distance|   5|     10000|    1000|0.90504426|  PASSED
    rgb_permutations|   2|    100000|     100|0.53206606|  PASSED
    rgb_permutations|   3|    100000|     100|0.93990686|  PASSED
    rgb_permutations|   4|    100000|     100|0.93641573|  PASSED
    rgb_permutations|   5|    100000|     100|0.33006306|  PASSED
      rgb_lagged_sum|   0|   1000000|     100|0.78918620|  PASSED
      rgb_lagged_sum|   1|   1000000|     100|0.49537040|  PASSED
      rgb_lagged_sum|   2|   1000000|     100|0.84078182|  PASSED
      rgb_lagged_sum|   3|   1000000|     100|0.08149632|  PASSED
      rgb_lagged_sum|   4|   1000000|     100|0.53883616|  PASSED
      rgb_lagged_sum|   5|   1000000|     100|0.18996191|  PASSED
      rgb_lagged_sum|   6|   1000000|     100|0.97313817|  PASSED
      rgb_lagged_sum|   7|   1000000|     100|0.43472782|  PASSED
      rgb_lagged_sum|   8|   1000000|     100|0.32097682|  PASSED
      rgb_lagged_sum|   9|   1000000|     100|0.34552567|  PASSED
      rgb_lagged_sum|  10|   1000000|     100|0.80184011|  PASSED
      rgb_lagged_sum|  11|   1000000|     100|0.21385126|  PASSED
      rgb_lagged_sum|  12|   1000000|     100|0.41010174|  PASSED
      rgb_lagged_sum|  13|   1000000|     100|0.92351903|  PASSED
      rgb_lagged_sum|  14|   1000000|     100|0.97133192|  PASSED
      rgb_lagged_sum|  15|   1000000|     100|0.72265136|  PASSED
      rgb_lagged_sum|  16|   1000000|     100|0.27598576|  PASSED
      rgb_lagged_sum|  17|   1000000|     100|0.80165934|  PASSED
      rgb_lagged_sum|  18|   1000000|     100|0.53501980|  PASSED
      rgb_lagged_sum|  19|   1000000|     100|0.16149694|  PASSED
      rgb_lagged_sum|  20|   1000000|     100|0.62232179|  PASSED
      rgb_lagged_sum|  21|   1000000|     100|0.63703547|  PASSED
      rgb_lagged_sum|  22|   1000000|     100|0.74027501|  PASSED
      rgb_lagged_sum|  23|   1000000|     100|0.48693243|  PASSED
      rgb_lagged_sum|  24|   1000000|     100|0.52278818|  PASSED
      rgb_lagged_sum|  25|   1000000|     100|0.37765179|  PASSED
      rgb_lagged_sum|  26|   1000000|     100|0.17398545|  PASSED
      rgb_lagged_sum|  27|   1000000|     100|0.91595733|  PASSED
      rgb_lagged_sum|  28|   1000000|     100|0.21368217|  PASSED
      rgb_lagged_sum|  29|   1000000|     100|0.15273232|  PASSED
      rgb_lagged_sum|  30|   1000000|     100|0.04442107|  PASSED
      rgb_lagged_sum|  31|   1000000|     100|0.43887837|  PASSED
      rgb_lagged_sum|  32|   1000000|     100|0.35777050|  PASSED
     rgb_kstest_test|  32|     10000|    1000|0.41686471|  PASSED
So I don't think is just random stuff (pun intended ;-) ) and if Heinz would like to add some comments he can for sure explain better then me.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: RKISS

Post by Don » Mon Jan 17, 2011 1:50 pm

I don't see any reference to RKISS on the web. I see lots of references to Marsaglia and KISS in general, but not specifically RKISS.

Who is Heinz van Saanen? I also question whether it's possible to copyright 3 or 4 lines of code that is based on well known heuristics.

I took a look at the generator and unless I missed something it is intialized in a completely deterministic way. I did not look to see how it's used in stockfish so perhaps this is what is intended. But if were used for getting a book move it will always play the same book move after the program is initialized.

Code: Select all

 void raninit() {

      s.a = 0xf1ea5eed;
      s.b = s.c = s.d = 0xd4e12c77;
      for &#40;int i = 0; i < 73; i++)
          rand64&#40;);
  &#125;
This just doesn't seem right to me. Instead of looping 73 times it would be more efficient to just set the 4 variables ONE time to the values they are guaranteed to take anyway? Of course I assume that is done only once but I don't see the point of it.

mcostalba wrote:
Gerd Isenberg wrote: Is there any theory about that bit-twiddling available on-line? Or is such stuff more empirical trial and error?
This code was kindly donated to us by Heinz van Saanen that allowed us to license under GPL so to be merged in SF.

We just tested that it works and is 100% an alternative to mersenne.

I don't think it is just trial and error, as reported in the header:

Code: Select all

 ** A small "keep it simple and stupid" RNG with some fancy merits&#58;
 **
 ** Quite platform independent
 ** Passes ALL dieharder tests! Here *nix sys-rand&#40;) e.g. fails miserably&#58;-)
 ** ~12 times faster than my *nix sys-rand&#40;)
 ** ~4 times faster than SSE2-version of Mersenne twister
 ** Average cycle length&#58; ~2^126
 ** 64 bit seed
 ** Return doubles with a full 53 bit mantissa
 ** Thread safe

And here is the dieharder tests reports:

Code: Select all

                                                                     
                                                                     
                                                                     
                                             
heinz@linux&#58;~/junk/junk> ./a.out | dieharder -g 200 -a
#=============================================================================#
#          dieharder version 3.29.4beta Copyright 2003 Robert G. Brown        #
#=============================================================================#
   rng_name    |rands/second|   Seed   |                                       
stdin_input_raw|  2.13e+07  |4282743765|                                       
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment            
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.14890455|  PASSED              
      diehard_operm5|   5|   1000000|     100|0.02837678|  PASSED              
  diehard_rank_32x32|   0|     40000|     100|0.63612384|  PASSED              
    diehard_rank_6x8|   0|    100000|     100|0.78258674|  PASSED              
   diehard_bitstream|   0|   2097152|     100|0.73291748|  PASSED              
        diehard_opso|   0|   2097152|     100|0.36677569|  PASSED              
        diehard_oqso|   0|   2097152|     100|0.35635353|  PASSED              
         diehard_dna|   0|   2097152|     100|0.40227206|  PASSED              
diehard_count_1s_str|   0|    256000|     100|0.15631848|  PASSED              
diehard_count_1s_byt|   0|    256000|     100|0.02576356|  PASSED              
 diehard_parking_lot|   0|     12000|     100|0.33868706|  PASSED              
    diehard_2dsphere|   2|      8000|     100|0.61107903|  PASSED              
    diehard_3dsphere|   3|      4000|     100|0.37099325|  PASSED              
     diehard_squeeze|   0|    100000|     100|0.56722772|  PASSED              
        diehard_sums|   0|       100|     100|0.04022953|  PASSED              
        diehard_runs|   0|    100000|     100|0.39906252|  PASSED              
        diehard_runs|   0|    100000|     100|0.26776626|  PASSED              
       diehard_craps|   0|    200000|     100|0.74060276|  PASSED              
       diehard_craps|   0|    200000|     100|0.43273086|  PASSED              
 marsaglia_tsang_gcd|   0|  10000000|     100|0.38433496|  PASSED              
 marsaglia_tsang_gcd|   0|  10000000|     100|0.21739434|  PASSED              
         sts_monobit|   1|    100000|     100|0.13931802|  PASSED              
            sts_runs|   2|    100000|     100|0.51329448|  PASSED              
          sts_serial|   1|    100000|     100|0.39968488|  PASSED              
          sts_serial|   2|    100000|     100|0.20801423|  PASSED              
          sts_serial|   3|    100000|     100|0.22648504|  PASSED              
          sts_serial|   3|    100000|     100|0.79553793|  PASSED              
          sts_serial|   4|    100000|     100|0.13889241|  PASSED              
          sts_serial|   4|    100000|     100|0.35689448|  PASSED              
          sts_serial|   5|    100000|     100|0.32907831|  PASSED              
          sts_serial|   5|    100000|     100|0.96425371|  PASSED              
          sts_serial|   6|    100000|     100|0.29429007|  PASSED                                      
          sts_serial|   6|    100000|     100|0.67547393|  PASSED                                      
          sts_serial|   7|    100000|     100|0.27652533|  PASSED                                      
          sts_serial|   7|    100000|     100|0.43773829|  PASSED                                      
          sts_serial|   8|    100000|     100|0.00589920|  PASSED                                      
          sts_serial|   8|    100000|     100|0.00606073|  PASSED                                      
          sts_serial|   9|    100000|     100|0.36759888|  PASSED                                      
          sts_serial|   9|    100000|     100|0.41487400|  PASSED                                      
          sts_serial|  10|    100000|     100|0.85082078|  PASSED                                      
          sts_serial|  10|    100000|     100|0.25805178|  PASSED                                      
          sts_serial|  11|    100000|     100|0.52837124|  PASSED                                      
          sts_serial|  11|    100000|     100|0.05334055|  PASSED                                      
          sts_serial|  12|    100000|     100|0.67688469|  PASSED                                      
          sts_serial|  12|    100000|     100|0.84215568|  PASSED                                      
          sts_serial|  13|    100000|     100|0.99153787|  PASSED                                      
          sts_serial|  13|    100000|     100|0.76515469|  PASSED                                      
          sts_serial|  14|    100000|     100|0.26573843|  PASSED                                      
          sts_serial|  14|    100000|     100|0.26842956|  PASSED                                      
          sts_serial|  15|    100000|     100|0.45104274|  PASSED                                      
          sts_serial|  15|    100000|     100|0.40600808|  PASSED                                      
          sts_serial|  16|    100000|     100|0.50489227|  PASSED                                      
          sts_serial|  16|    100000|     100|0.65051872|  PASSED                                      
         rgb_bitdist|   1|    100000|     100|0.90681142|  PASSED                                      
         rgb_bitdist|   2|    100000|     100|0.58916697|  PASSED                                      
         rgb_bitdist|   3|    100000|     100|0.65855068|  PASSED                                      
         rgb_bitdist|   4|    100000|     100|0.98371981|  PASSED                                      
         rgb_bitdist|   5|    100000|     100|0.32509053|  PASSED                                      
         rgb_bitdist|   6|    100000|     100|0.41816883|  PASSED                                      
         rgb_bitdist|   7|    100000|     100|0.13625306|  PASSED                                      
         rgb_bitdist|   8|    100000|     100|0.98116523|  PASSED                                      
         rgb_bitdist|   9|    100000|     100|0.09052981|  PASSED
         rgb_bitdist|  10|    100000|     100|0.71922521|  PASSED
         rgb_bitdist|  11|    100000|     100|0.39864600|  PASSED
         rgb_bitdist|  12|    100000|     100|0.88463093|  PASSED
rgb_minimum_distance|   2|     10000|    1000|0.49191929|  PASSED
rgb_minimum_distance|   3|     10000|    1000|0.34086770|  PASSED
rgb_minimum_distance|   4|     10000|    1000|0.67634721|  PASSED
rgb_minimum_distance|   5|     10000|    1000|0.90504426|  PASSED
    rgb_permutations|   2|    100000|     100|0.53206606|  PASSED
    rgb_permutations|   3|    100000|     100|0.93990686|  PASSED
    rgb_permutations|   4|    100000|     100|0.93641573|  PASSED
    rgb_permutations|   5|    100000|     100|0.33006306|  PASSED
      rgb_lagged_sum|   0|   1000000|     100|0.78918620|  PASSED
      rgb_lagged_sum|   1|   1000000|     100|0.49537040|  PASSED
      rgb_lagged_sum|   2|   1000000|     100|0.84078182|  PASSED
      rgb_lagged_sum|   3|   1000000|     100|0.08149632|  PASSED
      rgb_lagged_sum|   4|   1000000|     100|0.53883616|  PASSED
      rgb_lagged_sum|   5|   1000000|     100|0.18996191|  PASSED
      rgb_lagged_sum|   6|   1000000|     100|0.97313817|  PASSED
      rgb_lagged_sum|   7|   1000000|     100|0.43472782|  PASSED
      rgb_lagged_sum|   8|   1000000|     100|0.32097682|  PASSED
      rgb_lagged_sum|   9|   1000000|     100|0.34552567|  PASSED
      rgb_lagged_sum|  10|   1000000|     100|0.80184011|  PASSED
      rgb_lagged_sum|  11|   1000000|     100|0.21385126|  PASSED
      rgb_lagged_sum|  12|   1000000|     100|0.41010174|  PASSED
      rgb_lagged_sum|  13|   1000000|     100|0.92351903|  PASSED
      rgb_lagged_sum|  14|   1000000|     100|0.97133192|  PASSED
      rgb_lagged_sum|  15|   1000000|     100|0.72265136|  PASSED
      rgb_lagged_sum|  16|   1000000|     100|0.27598576|  PASSED
      rgb_lagged_sum|  17|   1000000|     100|0.80165934|  PASSED
      rgb_lagged_sum|  18|   1000000|     100|0.53501980|  PASSED
      rgb_lagged_sum|  19|   1000000|     100|0.16149694|  PASSED
      rgb_lagged_sum|  20|   1000000|     100|0.62232179|  PASSED
      rgb_lagged_sum|  21|   1000000|     100|0.63703547|  PASSED
      rgb_lagged_sum|  22|   1000000|     100|0.74027501|  PASSED
      rgb_lagged_sum|  23|   1000000|     100|0.48693243|  PASSED
      rgb_lagged_sum|  24|   1000000|     100|0.52278818|  PASSED
      rgb_lagged_sum|  25|   1000000|     100|0.37765179|  PASSED
      rgb_lagged_sum|  26|   1000000|     100|0.17398545|  PASSED
      rgb_lagged_sum|  27|   1000000|     100|0.91595733|  PASSED
      rgb_lagged_sum|  28|   1000000|     100|0.21368217|  PASSED
      rgb_lagged_sum|  29|   1000000|     100|0.15273232|  PASSED
      rgb_lagged_sum|  30|   1000000|     100|0.04442107|  PASSED
      rgb_lagged_sum|  31|   1000000|     100|0.43887837|  PASSED
      rgb_lagged_sum|  32|   1000000|     100|0.35777050|  PASSED
     rgb_kstest_test|  32|     10000|    1000|0.41686471|  PASSED
So I don't think is just random stuff (pun intended ;-) ) and if Heinz would like to add some comments he can for sure explain better then me.

UncombedCoconut
Posts: 319
Joined: Fri Dec 18, 2009 10:40 am
Location: Naperville, IL

Re: RKISS

Post by UncombedCoconut » Mon Jan 17, 2011 2:27 pm

Don wrote:I don't see any reference to RKISS on the web. I see lots of references to Marsaglia and KISS in general, but not specifically RKISS.
My experience is about the same; Googling, say, the coefficients doesn't find that exact RNG. (Googling the author does give lots of hits, however. :) He's credited in bitboard.cpp as well, so I guess the SF team knows him.)
I took a look at the generator and unless I missed something it is intialized in a completely deterministic way. I did not look to see how it's used in stockfish so perhaps this is what is intended. But if were used for getting a book move it will always play the same book move after the program is initialized.
That part's OK; the Book::Book() constructor calls the RNG a system-time-dependent number of times. I agree the initial fixed loop is a little strange.

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

Re: RKISS

Post by bob » Mon Jan 17, 2011 2:49 pm

The PRNG I use (from the book "Numerical Recpies") uses an array of numbers that get twisted in odd ways. But a PRNG is _supposed_ to produce the same string of numbers each time it is initialized.

The easiest way to select random book moves is to use the PRNG to initialize everything, then obtain the system time in microseconds or something that is high-resolution, extract the rightmost N bits, and loop calling the PRNG that many times before you start to play the game. Then you start the same PRNG sequence as the PRNG is supposed to deliver, but you skip N numbers before using them for book.

These types of PRNGs are harder to "seed", although one can (in the PRNG I use) alter the initial values of the two array indices, which will certainly change the sequence. But the released version has been tested quite thoroughly, and such a change might easily shorten the PRNG period or randomness, which is undesirable.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: RKISS

Post by Don » Mon Jan 17, 2011 3:01 pm

UncombedCoconut wrote:
Don wrote:I don't see any reference to RKISS on the web. I see lots of references to Marsaglia and KISS in general, but not specifically RKISS.
My experience is about the same; Googling, say, the coefficients doesn't find that exact RNG. (Googling the author does give lots of hits, however. :) He's credited in bitboard.cpp as well, so I guess the SF team knows him.)
I took a look at the generator and unless I missed something it is intialized in a completely deterministic way. I did not look to see how it's used in stockfish so perhaps this is what is intended. But if were used for getting a book move it will always play the same book move after the program is initialized.
That part's OK; the Book::Book() constructor calls the RNG a system-time-dependent number of times. I agree the initial fixed loop is a little strange.
I guess it works, but it seems like a very ugly hack. Is the point that the RNG cannot be initialized with just any constant?

The proper initialization should be inside the class, not outside of it. Even if all it does is to make a zillion calls of the RNG the ugliness could be isolated inside the class.

Anyway, I'm just nit-picking - I have uglier things in my own code.

Don

UncombedCoconut
Posts: 319
Joined: Fri Dec 18, 2009 10:40 am
Location: Naperville, IL

Re: RKISS

Post by UncombedCoconut » Mon Jan 17, 2011 3:17 pm

Don wrote:I guess it works, but it seems like a very ugly hack. Is the point that the RNG cannot be initialized with just any constant?
As Bob points out, fiddling with the initial internal state can turn a well-tested RNG into an untested RNG. Time-shifting its output sequence cannot. So the "roll a zillion dice" idea is at least a good convention.
The proper initialization should be inside the class, not outside of it. Even if all it does is to make a zillion calls of the RNG the ugliness could be isolated inside the class.
Stockfish uses this RNG twice: once to pick openings (should be random), once to pick Zobrist keys (should "look random" but be the same every time). How best to achieve this is a matter of taste, but I don't think SF's is bad. Even pre-computing the effect of raninit() (an idea I like) is roughly a break-even in terms of code beauty.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: RKISS

Post by Don » Mon Jan 17, 2011 3:36 pm

bob wrote:The PRNG I use (from the book "Numerical Recpies") uses an array of numbers that get twisted in odd ways. But a PRNG is _supposed_ to produce the same string of numbers each time it is initialized.

The easiest way to select random book moves is to use the PRNG to initialize everything, then obtain the system time in microseconds or something that is high-resolution, extract the rightmost N bits, and loop calling the PRNG that many times before you start to play the game. Then you start the same PRNG sequence as the PRNG is supposed to deliver, but you skip N numbers before using them for book.
That seems incredible inefficient if you want to have more than a few possible seed states but if your software only initializes the RNG once at program startup (which most but not all software needs to do) and speed is not an issue, you could probably still have at least a few thousands states without increasing startup time by more than a fraction of a second.

For selecting opening book moves only, this is not an issue of course. But it makes the generator impractical as a general purpose RNG.

It makes me wonder even more how a few lines of code like this can be copyrighted, when it's not even a very usable general purpose RNG if it cannot be initialized in constant time and it can only be initialized to a point very close to the beginning of it's enormous period length. O(n) puts a severe limit on the number of practical starting states you can have and it's not even distributed over the entire sequence or period of the generator!

In any application requiring a significant number of RNG calls it's going to always visit the same sequences once you are beyond first few thousand that you initialized it with. Here is an example:

Suppose I wanted to simulate 100 billion dice throws and I use the slow O(n) initializer to provide 1 million starting states. No matter how many times I run the simulation, I'm STILL going to generate almost the same results - the only difference being the tiny fraction of differences caused by where I start and end in the sequence.

Anyway, don't get me wrong - I'm not being critical, now that I understand it I can see that it's practical and fine for what it's being used for.

These types of PRNGs are harder to "seed", although one can (in the PRNG I use) alter the initial values of the two array indices, which will certainly change the sequence. But the released version has been tested quite thoroughly, and such a change might easily shorten the PRNG period or randomness, which is undesirable.

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: RKISS

Post by mcostalba » Mon Jan 17, 2011 3:44 pm

UncombedCoconut wrote: Even pre-computing the effect of raninit() (an idea I like) is roughly a break-even in terms of code beauty.
I agree, because you break the symmetry:

Code: Select all

s.b = s.c = s.d = 0xd4e12c77;
A code beautification could be instead:

Code: Select all

s.a = s.b = s.c = s.d = xxxxx;
but, as reported above you get un untested PRNG instead of a well tested and proved one.

Post Reply