乱数のつくり方

コンピューターは本当の意味でランダムな数を作れません。アプリが使っている「疑似乱数」の仕組み (xorshift32 と mulberry32) と、シード・再現性・ハッシュによる振り分けを、ビット演算のレベルから説明します。

#疑似乱数 — 決まった手順で、ランダムに見える数を作る

コンピューターは決まった手順しか実行できないので、サイコロのような本物の偶然は作れません。そこで「前の数から次の数を計算する」決まった式で、ランダムに 見える 数の列を作ります。これを 疑似乱数 と呼びます。

最初の値 $s_0$ を シード (種) と呼びます。同じシードからは、いつも同じ列が出てきます。これは欠点ではなく、結果を再現できる という長所です。

#xorshift32 — 3 行の乱数

Zig のモンテカルロは xorshift32 という方法を使っています。

fn nextRand() f32 {
    // xorshift32: 速くて十分ランダム (暗号用途ではない)
    rng ^= rng << 13;
    rng ^= rng >> 17;
    rng ^= rng << 5;
    return @as(f32, @floatFromInt(rng >> 8)) / 16777216.0;
}

rng は 32 ビットの符号なし整数です。3 行はすべて「自分を何ビットかずらしたものと、自分の 排他的論理和 (XOR, ^) をとる」操作です。

左シフトで上位のビットに、右シフトで下位のビットに情報が混ざり、それを 3 回くり返すことで、32 ビット全体がよくかき混ぜられます。13, 17, 5 という数は、考案者 George Marsaglia が「周期が最大になる組み合わせ」として探し出したものの 1 つです。

#なぜ周期が $2^{32} - 1$ なのか

xorshift の 1 ステップは、32 ビットを 32 次元のベクトル (各成分は 0 か 1) とみなすと、行列の掛け算 で書けます。XOR は「1+1=0 となる足し算」(2 を法とする足し算) なので、

($L$, $R$ はシフトを表す行列、$I$ は単位行列)。適切なシフト量を選ぶと $M$ は、0 以外のすべての 32 ビット値 ($2^{32} - 1$ 個) を 1 周してから元に戻る、という性質を持ちます。

rng = if (seed == 0) 0x9E3779B9 else seed;

#整数を 0〜1 の小数に変える

rng >> 8 で上位 24 ビットを取り出すと、$0$ 〜 $2^{24} - 1$ の整数になります。これを $2^{24} = 16777216$ で割ると

となり、0 以上 1 未満 の値が $2^{24}$ 通り、等間隔で同じ確率で出ます。

なぜ 32 ビット全部ではなく 24 ビットなのでしょうか。結果を入れる f32 (32 ビットの浮動小数点数) は、仮数部 (有効数字) が 24 ビット (保存される 23 ビット + 暗黙の 1 ビット) しかありません。32 ビットの整数をそのまま $2^{32}$ で割ると、丸めによって ちょうど 1.0 が出てしまうことがあります。24 ビットに揃えれば、すべての値が誤差なしに表せて、1.0 は絶対に出ません。

#シードを固定する意味

レース予想画面の勝率シミュレーションは、毎回同じシードで計算しています。

z.simulate(list.length, 100000, state.mcPace, 20261109);

シードが固定なので、同じ出馬表・同じペースなら、何度画面を開いても同じ勝率が表示されます。表示が毎回少しずつ変わると、利用者は「何か変わったのか」と混乱するからです。

一方、3D シミュレーションは毎回違う展開にしたいので、シードを毎回変えています。

const seed = (Math.random() * 2 ** 31) | 0;

「リプレイ」では、同じシードで計算した結果 (scores) をそのまま使うので、まったく同じレースが再現されます。

#mulberry32 — JavaScript 側の乱数

JavaScript の Math.random() にはシードを指定できません。シードが必要な場面 (Zig を読み込めなかったときの代わり、「名馬でおまかせ」の抽選) では、mulberry32 という別の方法を使っています。

export const seeded = seed => () => {
  seed = (seed + 0x6D2B79F5) | 0;
  let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
  return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};

状態に定数を足していく部分 (seed + 0x6D2B79F5) は単純なカウンターで、その値を掛け算と XOR でかき混ぜて出力します。Math.imul は「32 ビット整数として掛けて、はみ出た分を捨てる」掛け算です (普通の * は小数になってしまうため)。

#ハッシュで「くじ引き」する — 脚質の初期値

名鑑の馬には脚質のデータがないので、得意距離が分からない馬は 名前から 脚質を決めています。

let hsh = 0;
for (const ch of v.horse.title) hsh = (hsh * 31 + ch.charCodeAt(0)) | 0;
const x = Math.abs(hsh) % 100;
return x < 12 ? 0 : x < 52 ? 1 : x < 85 ? 2 : 3;

名前の文字コード $c_1, c_2, \dots, c_n$ から

を計算します (| 0 が 32 ビットで切り捨てる操作)。これは Java の String.hashCode() と同じ式です。$|h| \bmod 100$ がほぼ一様に 0〜99 に散らばるとみなすと、

乱数ではなくハッシュを使うのは、同じ馬はいつも同じ脚質 にするためです。毎回変わると、同じ馬を追加し直しただけで展開が変わってしまいます。