RKISS copyright?

[Giorgio Medeot]

Hi all,
I was doing some googling for PRNG implementations, and I stumbled on this page:

http://www.burtleburtle.net/bob/rand/smallprng.html

Please note the part in which the author (Bob Jenkins?) says:

I wrote this PRNG. I place it in the public domain.

Now, this implementation is exactly the same as in the RKiss header file included in Stockfish 2.1 and credited there to Heinz van Saanen.

I guess that someone could be interested in being notified of this.

Regards,

• Giorgio

[jshriver]

I may stand corrected, but a lot of engines seem to incorporate other people's code. Not saying chess specific code as that is what makes it "100% the author" but things like random number generators, compression code, egtb support (gaviota and nalimov), common data structures.

-Josh

[wgarvin]

I'm just guessing that Heinz van Saanen was the one who integrated that code into Stockfish. He is mentioned on the Stockfish blog on Jul 5, 2009. I doubt there was any intention to claim that code as his own.

Since the PRNG code was released into the public domain by its author, using it in Stockfish (or any other engine) should be perfectly fine.

[Edit]: Okay, the comment in the rkiss.h file may be misleading. Here it is:

Code: Select all

/*
  Stockfish, a UCI chess playing engine derived from Glaurung 2.1
  Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
  Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad

  Stockfish is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  Stockfish is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program.  If not, see <http://www.gnu.org/licenses/>.

  This file is based on original code by Heinz van Saanen and is
  available under the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

 ** 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
 **
 ** (c) Heinz van Saanen

*/

I will however, point out that the Bob Jenkins code is for a 32-bit number and Heinz van Saanen's version is for 64-bit numbers, and the rotate amounts are different. The operations themselves may be dictated by the math behind the PRNG construction (I'm not an expert in this; ask a cryptographer I guess).

[Giorgio Medeot]

I will however, point out that the Bob Jenkins code is for a 32-bit number and Heinz van Saanen's version is for 64-bit numbers, and the rotate amounts are different. The operations themselves may be dictated by the math behind the PRNG construction (I'm not an expert in this; ask a cryptographer I guess).

Nope. In the page I quoted in the OP it is also presented a 64 bit version, that is the same as the Stockfish one (even same rotate amounts and seed values); try to scroll down until half the page.

• Giorgio

[Gerd Isenberg]

Hi all,
I was doing some googling for PRNG implementations, and I stumbled on this page:

http://www.burtleburtle.net/bob/rand/smallprng.html

Please note the part in which the author (Bob Jenkins?) says:

I wrote this PRNG. I place it in the public domain.

Now, this implementation is exactly the same as in the RKiss header file included in Stockfish 2.1 and credited there to Heinz van Saanen.

I guess that someone could be interested in being notified of this.

Regards,

• Giorgio

Interesting. Heinz van Saanen's GPL Version doesn't have the ror macros and all embedded inside a class.

Code: Select all

class RKISS {

  // Keep variables always together
  struct S { uint64_t a, b, c, d; } s;

  // Return 64 bit unsigned integer in between [0,2^64-1]
  uint64_t rand64() {

      const uint64_t
        e = s.a - ((s.b <<  7) | (s.b >> 57));
      s.a = s.b ^ ((s.c << 13) | (s.c >> 51));
      s.b = s.c + ((s.d << 37) | (s.d >> 27));
      s.c = s.d + e;
      return s.d = e + s.a;
  }

  // Init seed and scramble a few rounds
  void raninit() {

      s.a = 0xf1ea5eed;
      s.b = s.c = s.d = 0xd4e12c77;
      for (int i = 0; i < 73; i++)
          rand64();
  }

Bob Jenkins public domain 2009 (?) version has a bit different raninit seed.

Code: Select all

typedef unsigned long long u8;
typedef struct ranctx { u8 a; u8 b; u8 c; u8 d; } ranctx;

#define rot(x,k) (((x)<<(k))|((x)>>(64-(k))))
u8 ranval( ranctx *x ) {
    u8 e = x->a - rot(x->b, 7);
    x->a = x->b ^ rot(x->c, 13);
    x->b = x->c + rot(x->d, 37);
    x->c = x->d + e;
    x->d = e + x->a;
    return x->d;
}

void raninit( ranctx *x, u8 seed ) {
    u8 i;
    x->a = 0xf1ea5eed, x->b = x->c = x->d = seed;
    for (i=0; i<20; ++i) {
        (void)ranval(x);
    }
}

I would clearly prefer such stuff (like bitscan, popcount, etc.) in the public domain. Looks like Heinz van Saanen took this public domain snippet from 2009, obfuscated the ror and put it under GPL?

[wgarvin]

I was hasty... I didn't see the 64-bit code down the page on Bob Jenkins' page.

Maybe the Stockfish team should add a comment giving attribution to the original source?

[mcostalba]

Maybe the Stockfish team should add a comment giving attribution to the original source?

I have asked Heinz to give a look at this thread and please write me his comments...

As soon as we have more news I will post here.

[Gerd Isenberg]

Maybe the Stockfish team should add a comment giving attribution to the original source?

I have asked Heinz to give a look at this thread and please write me his comments...

As soon as we have more news I will post here.

Thanks!

Seems Heinz found the seed of 0xd4e12c77 with 79 post increment init cycles, and embedded all into a nice class.

Guess we are now free to use any other seed and cycles with Bob Jenkins' code

[Alessandro Damiani]

Is RKISS better than RanRot (http://www.agner.org/random/theory/)?

[Gerd Isenberg]

Is RKISS better than RanRot (http://www.agner.org/random/theory/)?

http://www.agner.org/random/discuss/read.php?i=138

Depends on the application. RKISS is much faster and has shorter code, and keeps its state in a 256 bit variable and is thread safe. For some Zobrist keys certainly good enough.