Stockfish DD – rkiss | やねうら王公式サイト

今回は擬似乱数生成器です。世間では「乱数と言えばMT(Mersenne twister : メルセンヌツイスター)乱数だろ」と思われているかも知れませんが、MT乱数は生成に結構コストがかかるので、ベストなソリューションとは言えません。かと言って、組み込み系の乱数は乱数の精度が今ひとつですのでそういう部分で偏りが出るのは困ります。(定跡選択で乱数を使うので、乱数に偏りがあると連続自己対戦の勝率に偏りが生じかねない)

Stockfishで採用されているのはRKISSという乱数で、この乱数の実装を見るためだけにでも、Stockfishのソースコードを読む価値はあると私は思います。

/*
  Stockfish, a UCI chess playing engine derived from Glaurung 2.1
  Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
  Copyright (C) 2008-2013 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.
*/

#ifndef RKISS_H_INCLUDED
#define RKISS_H_INCLUDED

#include "types.h"

/// RKISS is our pseudo random number generator (PRNG) used to compute hash keys.
/// George Marsaglia invented the RNG-Kiss-family in the early 90's. This is a
/// specific version that Heinz van Saanen derived from some public domain code
/// by Bob Jenkins. Following the feature list, as tested by Heinz.
///
/// - 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

// RKISSはhash keyを計算するために使う擬似乱数発生器(PRNG)である。
// George Marsaglは、90年代はじめにRNG-Kiss-familyを発明した。
// これはBob Jenkinsのpublic domainのコードからHeinz van Saanenが派生させた
// 特殊化バージョンである。Heinzによりテストされたように、以下の特徴がある。
//
/// - きわめてプラットフォームに依存しない
/// - すべてのdie harderテストをパスした！ *nix(UNIX/Linux等のこと)のsys-rand()なんかは悲惨な結果になる。
/// - *nixのsys-rand()より12倍ぐらい速い。
/// - SSE2-version of Mersenne twisterのSSE2版より4倍ぐらい速い
/// - 平均周期 : 2^126ぐらい
/// - 64 bitの乱数シード
/// - フル53 bitの仮数からなるdouble型を返せる(※　暗黙の型変換子が書いてあるので何型でも返せる)
/// - スレッドセーフ

class RKISS {

  uint64_t a, b, c, d;

  uint64_t rotate(uint64_t x, uint64_t k) const {
    return (x << k) | (x >> (64 - k));
  }

  uint64_t rand64() {

    const uint64_t e = a - rotate(b,  7);
    a = b ^ rotate(c, 13);
    b = c + rotate(d, 37);
    c = d + e;
    return d = e + a;
  }

public:
  // コンストラクタ。
  // 乱数シードを変更して使うなら変更して使ってもいいが…。
  RKISS(int seed = 73) {

    a = 0xF1EA5EED, b = c = d = 0xD4E12C77;

    for (int i = 0; i < seed; ++i) // Scramble a few rounds
        rand64();
  }

  // 生成した乱数を取り出すための暗黙の型変換子。
  // int64_t以外にもdoubleなどにも代入できる。
  template<typename T> T rand() { return T(rand64()); }
};

#endif // #ifndef RKISS_H_INCLUDED

Stockfish, a UCI chess playing engine derived from Glaurung 2.1

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 .

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.

#ifndef RKISS_H_INCLUDED

#define RKISS_H_INCLUDED

#include "types.h"

/// RKISS is our pseudo random number generator (PRNG) used to compute hash keys.

/// George Marsaglia invented the RNG-Kiss-family in the early 90's. This is a

/// specific version that Heinz van Saanen derived from some public domain code

/// by Bob Jenkins. Following the feature list, as tested by Heinz.

///

/// - 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

// RKISSはhash keyを計算するために使う擬似乱数発生器(PRNG)である。

// George Marsaglは、90年代はじめにRNG-Kiss-familyを発明した。

// これはBob Jenkinsのpublic domainのコードからHeinz van Saanenが派生させた

// 特殊化バージョンである。Heinzによりテストされたように、以下の特徴がある。

/// - きわめてプラットフォームに依存しない

/// - すべてのdie harderテストをパスした！ *nix(UNIX/Linux等のこと)のsys-rand()なんかは悲惨な結果になる。

/// - *nixのsys-rand()より12倍ぐらい速い。

/// - SSE2-version of Mersenne twisterのSSE2版より4倍ぐらい速い

/// - 平均周期 : 2^126ぐらい

/// - 64 bitの乱数シード

/// - フル53 bitの仮数からなるdouble型を返せる(※　暗黙の型変換子が書いてあるので何型でも返せる)

/// - スレッドセーフ

class RKISS {

uint64_t a, b, c, d;

uint64_t rotate(uint64_t x, uint64_t k) const {

return (x << k) | (x >> (64 - k));

}

uint64_t rand64() {

const uint64_t e = a - rotate(b, 7);

a = b ^ rotate(c, 13);

b = c + rotate(d, 37);

c = d + e;

return d = e + a;

}

public:

// コンストラクタ。

// 乱数シードを変更して使うなら変更して使ってもいいが…。

RKISS(int seed = 73) {

a = 0xF1EA5EED, b = c = d = 0xD4E12C77;

for (int i = 0; i < seed; ++i) // Scramble a few rounds

rand64();

}

// 生成した乱数を取り出すための暗黙の型変換子。

// int64_t以外にもdoubleなどにも代入できる。

template T rand() { return T(rand64()); }

};

#endif // #ifndef RKISS_H_INCLUDED

やねうら王公式サイト

コンピューター将棋やねうら王公式サイト

Stockfish DD – rkiss

「Stockfish DD – rkiss」への2件のフィードバック

コメントを残すコメントをキャンセル

「Stockfish DD – rkiss」への2件のフィードバック

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル