#22 カジュアルに乱数を使う方法とその注意点

この記事はtech.kayac.com Advent Calendar 2012の22日目です。

@songmuです。ゲーム作ったりしてると、乱数が必要になってきますがそれについて書きます。

多くの人にとっては当たり前の話も多く出てくるかと思いますがご容赦ください。間違ってる記述があった場合は突っ込みください。

擬似乱数とは何か

計算機は単体では厳密な意味での乱数を生成することができません。実際には一様に分布する乱数の集合を算術的に求めている場合がほとんどです。

その乱数の集合は以下を満たす必要がありますが、そういう小難しいことは偉い人に任せて、巨人の肩に乗って解決してしまえば良いでしょう。

  • 偏りがなく一様に分布している
  • 途中の出力から未来が予測しづらい
  • 高速に算出できるか

つまり?

色々な疑似乱数生成法がありますが、多くの場合、 馬鹿でかい乱数の循環リストがある と考えるとわかりやすいです。

例えばメルセンヌ・ツイスタの場合、219937-1という途轍もない長さの周期(乱数列)を持っています。

もちろん、そんな馬鹿でかい配列はメモリ上には持てないので、計算して求める必要があります。

昔のゲームだとメモリやプログラムサイズの制約のため、255くらいの長さの乱数列を決め打ちで持ったり、すごく単純な計算で乱数列を表現していたりするようです。

乱数の初期化

その循環リストのどの位置から数字を取り出し始めるかを決めることが乱数の初期化です。

その初期位置の決定に使う数値をシードと言ったりします。乱数の種ですね。

例えばPerlでは組み込みの乱数の初期化に srand() を使います。以下をターミナルで実行してみてください。

% perl -E 'srand(1);say rand;say rand;'
0.0416303447718782
0.454492444728629

この場合は、1をシードにして乱数を初期化しています。何度実行して同じ結果が返ってくるはずです。

乱数の初期化のジレンマ

じゃあ、この乱数のシードはどうやって決めるんだという話になります。

もちろんシードはランダムに与えたい。ただ、ランダムに与えるには乱数を使う必要がある。鶏と卵みたいな話です。

エポック秒とマイクロ秒とプロセスIDあたりをうまいこと撹拌してそれをシードにするみたいな話もあります。

ただ、それだとエントロピーが少なく初期値があまり分散しない上、予測されやすいという問題も出てきます。

なので、環境が提供している擬似乱数生成器を利用して、それをシードとするのが好ましいです。

Linuxの場合、/dev/randomというものがあります。これはキーボード入力等をもとに作られたエントロピプールから乱数を生成する優れものになっています。

ただ、エントロピプールが空の場合は、乱数を返せず、処理をブロックしてしまいます。 そのへんをうまいことや仕組みとして、/dev/urandomという乱数生成器が準備されています。 そこまでセキュアな要件が必要じゃない場合はこちらを利用すれば十分です。

細かい話はWikipediaの/dev/randomの項でも読んでください。

Perlの組み込み乱数

ちなみにperlの場合、srand()を引数なしで呼び出すと、/dev/urandomからシードを生成してくれます。(/dev/urandomが使える環境の場合)

しかも、randが初回に呼ばれた時に、srandを暗黙的に呼び出して乱数の初期化までやってくれます。すごい!カジュアル!

じゃあ、ここまでの話は必要なかったんやーとかいうと、そういうわけでもありません。

forkの罠

割と注意しなければならないのは、forkした場合に親の乱数シードを使ってしまうという問題です。 以下のような場合です。

#!/usr/bin/env perl
use 5.014;
use warnings;
use utf8;

use Parallel::ForkManager;

rand; # 親プロセスで乱数が呼ばれると同時にシードも決定される

my $pm = Parallel::ForkManager->new(3);
for my $i (1..12) {
    $pm->start and next;

    say "$$ :". rand; # 同じ値が出続ける!!!

    $pm->finish;
}

この場合はちゃんと子プロセス側で、乱数を初期化してやる必要があります。

#!/usr/bin/env perl
use 5.014;
use warnings;
use utf8;

use Parallel::ForkManager;

rand;

my $pm = Parallel::ForkManager->new(3);
for my $i (1..12) {
    $pm->start and next;

    srand; # ちゃんと子プロセスで初期化する!!!
    say "$$ :". rand; # OK

    $pm->finish;
}

forkされる場所に直接手を入れられない場合などのために、POSIX::AtForkを使う手もあります。

#!/usr/bin/env perl
use 5.014;
use warnings;
use utf8;

use POSIX::AtFork;
POSIX::AtFork->add_to_child(sub { srand }); # magic!!!

use Parallel::ForkManager;

rand;

my $pm = Parallel::ForkManager->new(3);
for my $i (1..12) {
    $pm->start and next;

    say "$$ :". rand; # OK

    $pm->finish;
}

シードを固定することのメリット

シードを固定することにはメリットもあります。

規則性があるということは再現性があるということです。

乱数ジェネレータを同じシードで初期化すれば常に同じ結果が出るということです。

以下の例ではMath::Random::MTを使っていますが、常に同じ結果が出るはずです。

#!/usr/bin/env perl
use 5.014;
use warnings;
use utf8;

use Math::Random::MT;
my $rand_gen = Math::Random::MT->new(10); # 10をシードにして初期化

say $rand_gen->rand;
say $rand_gen->rand;
say $rand_gen->rand;

__DATA__
0.771320643136278
0.298761158483103
0.020751946605742

これは何らかのシミュレータを動かす場合には非常に有用です。シードを記録しておけば、何度実行しても同じ結果が得られるからです。

ゲームのリプレイデータファイルなんかにも、その時に使われた乱数のシードが記録されていたりするそうです。

メルセンヌ・ツイスタ

メルセンヌ・ツイスタは、非常に周期が大きく、乱数も均等に分布していて、かつ計算も早いという優れものの擬似乱数アルゴリズムです。そのPerl実装がMath::Random::MTです。

ちょっと複雑な乱数ジェネレータを作りたい場合は、これを使っておけば十分です。

ただ、規則性を持った疑似乱数であることには変わりないので、単体では暗号化技術にはなりませんし、当然のことながら匿名化技術ではありません。

結論

ということでPerlにおける乱数生成のベタープラクティスは以下の様な感じです。

  • Math::Random::MTを使う
  • シードの生成はsrand()を使う
  • forkした場合は、乱数を初期化するのが吉。POSIX::AtFork使うと捗る