« 2種類の乱数生成メソッド | メイン | タイマー »
2015年03月17日
吉里吉里Z 開発:: 疑似乱数1
Tweet @jin1016をフォロー前回の乱数のエントリーでどう違うのか認識していないのではないかと言う指摘を見たので、説明を試みる。
Math.random/Math.RandomGenerator によって生成される乱数は、疑似乱数で真の乱数ではない。
これら疑似乱数は、長周期で偏りの少ない数列を生成する数学的な関数によって作られる。
つまり、何度も乱数を取得していれば、いつかは同じ値の繰り返しになる。
真の乱数があるとすれば、次に出る数は不明で、出る数はその時ごとに全ての数が等確率になるが、疑似乱数は次に出る数は決まっており、何度も値を得れば出る数の確率が出来るだけ均等になるように考えられている。
少し乱暴になるが、疑似乱数は様々な値の入った配列を最初から順に見ていき、最後までいくとまた最初から見ていくのと同じような動作となる。
疑似乱数で必要になる要素には以下のようなものがある。
1. 出る数は偏りが少ないようになっている。
2. 同じ数の並びが頻繁に繰り返し出ないように、ある程度長い周期を持っている。
3. 生成される数値の幅がある程度広くなっている。
1.は、たとえばサイコロで1と2ばかり出るようでは困る。
そのような動作をしていると不具合だと思われることもあるだろう。
2.は、1,2,3,1,2,3,1,2,3…と同じ順で繰り返し出ていれば次に何が出るか丸わかりだし、ゲームとして成立しない場合もあるので、一見繰り返しがわからないくらい長い周期が必要。
出来るのなら、全く繰り返していない方が望ましい。
また、1と関連するが奇数ばかり出たり、奇数、偶数、奇数と繰り返されたりするなど、規則性があるように見えて困る場合もある。
3.は、たとえば1～10のいずれかの値が欲しいのに、6までしか出ないと、7～10の値が全くでなくて困る。
6が10になるようにスケーリングして10までの数値が出るようにもできるが、歯抜けになってしまい、出ない数字が出来てしまう。
疑似乱数では必要とする値の幅以上の乱数が生成されないと不都合がある。
吉里吉里2の Math.random は bcc の _lrand が使用されており、_lrand は乗算合同法を使っていると書かれている。
ソースコードを見ると線形合同法と同じように見える。
乗算合同法や線形合同法は、乱数を生成するアルゴリズムの名前。
吉里吉里Z の場合、vc の rand が使用されている。
実装は不明だが、0 ～ 32767 の値を返すと書かれている。
線形合同法で実装されていると思われるが、実際にどういう実装かは不明。
線形合同法は、下位ビットを使用すると偏りが大きかったり、奇数/偶数の偏りが見られるなどの問題が知られている。
また、二次元座標などペアで使うと規則的に並ぶ下図のような問題もある。
これらの問題は、下位ビットは使わず、上位ビットを使うことで回避できる。
bcc の実装はそのようになっており、この問題は発生しない。
vc でもこの問題は発生しないため、同じような実装になっているものと思われる。
つまり、吉里吉里2 も Z もこれらの問題は関係ない。
そもそも Math.random は 0 ～ 1 の数値で返す形になっているので、下位ビットよりも上位ビットの方が影響が大きくなり、この問題はあったとしても影響しない(意図的にやらないと下位ビットのみを取り出せない)。
実際に上図のように Math.random を使って点をプロットして見ると以下のようになる。
Math.RandomGenerator でも同じようになる。
xorshift を使うと以下。
だいたい同じようになる。
これを見る限りそこまで大きな偏りがあるようには感じない。
ただ、局所的な偏りが発生しているかどうかはわからない。
続く
投稿者 Takenori : 2015年03月17日 01:23
comments powered by Disqus