UnityEngine.Random の実装と性質

はじめに

Unity では、組み込みの擬似乱数生成器として UnityEngine.Random が用意されています。この記事では、その実装や特徴について追っていきます。

※本記事の内容は Unity 2020.1.3f1 の Windows Editor にて確認したものです。

内部実装

UnityEngine.Random の遷移関数は Xorshift アルゴリズムで実装されています。 Xorshift には変種が色々ありますが、一番メジャーな実装 (Wikipedia の xor128 と同じもの) を使用しています。

// uint[] State = new uint[4] { ... };

public uint Next()
{
    uint t = State[0] ^ State[0] << 11;
    State[0] = State[1];
    State[1] = State[2];
    State[2] = State[3];
    return State[3] = State[3] ^ State[3] >> 19 ^ t ^ t >> 8;
}

内部状態

内部状態は UnityEngine.Random.State 構造体として保持されており、 state プロパティ経由で取得・設定できます。

この構造体の中身は { int s0, s1, s2, s3; } のようになっています。各メンバーはパブリックではないので直接編集するにはリフレクションを使う必要があります。加えて、 uint ではないため注意が必要です。

内部状態を uint[] で取得・設定するメソッドは以下のようになります。(雑)

public uint[] GetBuiltinState()
{
    var stateObject = UnityEngine.Random.state;

    return stateObject.GetType().GetFields(BindingFlags.NonPublic | BindingFlags.Instance)
        .OrderBy(field => field.Name)
        .Select(field => (uint)(int)field.GetValue(stateObject))
        .ToArray();
}

public void SetBuiltinState(uint[] state)
{
    var stateObject = new UnityEngine.Random.State();

    stateObject.GetType().GetFields(BindingFlags.NonPublic | BindingFlags.Instance)
        .OrderBy(field => field.Name)
        .Select((field, i) => { field.SetValue(stateObject, (int)state[i]); return 0; })
        .ToArray();

    UnityEngine.Random.state = stateObject;
}

初期化

明示的に初期化するときに使う InitState メソッドの実装を調べてみましょう。試しに公式サンプルにあった InitState(42) を呼び出すと、以下の内部状態が得られました。

0x0000002A, 0xB93C8A93, 0x49105700, 0xF3015301

[0] はそのまま引数の値 (42) のようです。後続はランダムなようですが、最下位ビットが 0, 1, 0, 1 となっており、なんとなく線形合同法の雰囲気があります。実際にパラメータの逆算を試してみると、同じ数列を生成する線形合同法のパラメータを得ることができました。 *1 再現コードを以下に示します。

// uint State[4] として
public void InitState(uint seed)
{
    for (int i = 0; i < 4; i++)
    {
        State[i] = seed;
        seed = seed * 1812433253 + 1;
    }
}

なお、ビルドしたアプリの起動時・エディタ起動時の初期状態は、InitState() 以外の方法で計算されているようです。初期状態から 1000000 回前の状態まで遡ってみましたが *2 、どれも線形合同法の関係式を満たしませんでした。

ちなみにエディタ上では、内部状態はプレイをまたいで保持されていそうでした。プレイ → InitState() → プレイ終了 → プレイ、とすると、前回設定したシード近辺の値が得られました。*3 エディタをいったん終了して再起動すると何らかの初期値が設定されます。もちろんビルドしたアプリでは、何らかの方法できちんと毎回違うシードが設定されているようです。

出力

一様乱数を求める Random.value と Random.Range の実装を調べてみます。出力を調べたところ、概ね以下の値を返すことが分かりました。

// public uint Next() がある前提で

// returns [0, 1]
public float value => (Next() & 0x7fffffu) / 8388607.0f;

// returns [min, max)
public int Range(int min, int max) => min + (int)(Next() % (uint)(max - min));

// returns [min, max]. note: 近似値を返します
public float Range(float min, float max)
{
    float t = value;        // [0, 1]
    return t * min + (1 - t) * max;
}

概ね、としたのは float Range の出力について、計算誤差？で微妙に最下位桁付近が合わない場合があるためです。上に挙げた式では正解率 70% 程度でした。もし正しい式をご存知の方がいらっしゃいましたら教えていただけると嬉しいです…

value の定数はどちらも値としては同じ 8388607 、言い換えれば $2^ {23} - 1$ です。したがって、value の出力は概ね 23bit 精度で行われていることになります。

注記すべき点としては、value 及び float Range の出力は max を含みます。他の言語やシステムで一般的な max を含まない出力を受け付ける前提のアルゴリズムをそのまま使用した場合 (例えば Math.Log(1 - Random.value) など)、-∞ などの予期しない値を返す可能性があるため注意が必要です。 $1 / 2^ {32}$ と低確率ではありますが…

また面白い点として、int Range では Next() が大きくなるほど出力が大きくなるのに対し、 float Range では Next() が大きくなるほど出力が小さくなるようになっています。 t と 1 - t は交換しても分布が変わらないためでしょうか…？

float Range の実装が、よりシンプルである min + value * (max - min) ではない理由としては、計算誤差が上記の実装よりも大きくなるから、と推測しています。この辺りは英語版 Wikipedia の「線形補完」の記事に情報があります。

ちなみに、ColorHSV など一部のメソッドの実装は、UnityCsReference から確認できます。

遊んでみる

さて、内部実装が分かれば、性質を利用していろいろと遊ぶことができます。

すべて 0 の state を入れて `Random` を壊す

Random.state = new Random.State(); とすることで、以降 Next() から出力される乱数はすべて 0 になります。私の環境では、それぞれ以下の数値だけを出力するようになりました。

value = 0
insideUnitCircle = (1, 0)
insideUnitSphere = (0, 0, 0)
onUnitSphere = (0, 0, 1)
rotation = (0.5, 0.5, 0.5, 0.5) (-> euler 0, 90, 90)
rotationUniform = (0, 0, 0, 0) (-> euler 0, 0, 0)
ColorHSV() = (0, 0, 0, 1) (-> Black)
Range(2, 12) = 2
Range(2f, 12f) = 12f

なお、前述したように内部状態はエディタを閉じるまで維持されるため、プレイを終了してもこの状態は残ります。大変邪悪ですのでよいこは真似しないでください。解除したい場合は InitState() を適当な数値で呼び出してください。

出力から内部状態を復元する

いわゆる乱数調整というやつです。全ての内部状態が計算できれば、将来（あるいは過去）の乱数列を予測・取得することができます。

ベースは Xorshift ですから、出力から生のビット (内部状態がそのまま露出しているビット) が得られれば行列計算で内部状態復元が可能です。行列計算については汎用的なものなので詳細は別の記事に譲るとして、Unity の出力関数から生のビットを得る方法について検討します。

`value` 経由

$2^ {n}$ ではない数で割っているので、直接ビットを抽出することはできません。とはいえ 8388607.0 を掛ければほとんどの上位ビットは復元できるはずです。 23 bit のうち上位 16 bit だけを使って 8 個の出力を観測する、のが無難でしょうか。

// value の出力から State[3] & 0x007fff80 の情報を得ます
public static uint ReverseValue(float value) =>
    ((uint)(value * 8388607.0) & 0x7fff80);

不安定な下位ビットも取得したい場合は、& の定数を 0x7fffff としてください。

最も、乱数は大抵 [0, 1] のままではなく特定の範囲に加工して使うので、プレイヤーが value の値を直接観測できるかというと難しいとは思いますが…

`int Range()` 経由

max - min が偶数ならビットを抽出できます。 $2^ {n}$ なら n ビット全部使えるのでなおよいです。実用上は最も観測しやすいものかと思います。

// Range(int min, int max) の出力から State[3] の下位 n bit の情報を得ます。
// n == tzcnt(max - min)
public static uint ReverseIntRange(int value, int min, int max)
    => (uint)(value - min) & ((1u << tzcnt((uint)(max - min))) - 1);

ややこしいことをしているように見えますが、要するに max - min の下位ビットが 0 になっているところだけ取り出すイメージです。例えば min = 0, max = pow(2, n) なら単に n ビットを取り出せばよいです。

なお、tzcnt は最下位から連続する 0 ビットの個数を返す関数とします。 System.Numerics.BitOperations.TrailingZeroCount() と等価です（が、このメソッドは Unity から簡単に参照できないようです…）。

`float Range()` 経由

基本的には value と同様ですが、ただでさえ近似値のところに計算を重ねるため、誤差が大きくなりそうです。値域を [min, max] から [0, 1] に変換したうえで、value と同じ逆算を行う例を示します。

// Range(float min, float max) の出力から State[3] & 0x007fff80 の情報を得ます
// ReverseValue は上述
public static uint ReverseFloatRange(float value, float min, float max)
    => ReverseValue((max - value) / (max - min));

ランダムな min, max に対してこのメソッドを試した限りでは、上位 16 bit を得ようとした場合の正解率は 1 回あたり 99 % 程度でした。完全復元には 128 bit 分の情報量、つまり連続 8 回の成功が必要となるので、全体としての成功率は概ね 92 % 程度でしょうか。計算誤差の大きさに依存するので、max と value がほぼ等しい場合などでは成功率が落ちそうではあります。

おわりに

この記事では、 Unity 組み込みの擬似乱数生成器 UnityEngine.Random の実装と性質について調べました。好きに書いた結果散らかってしまいましたが、思っていた以上に発見があり楽しかったです。

誤り・追加情報等あればご指摘いただけると助かります。

*1:計算方法については別の記事に書ければと思います

*2:Xorshift は状態を過去の方向に進めることも可能です。こちらの記事に理論と文献リンクがあります

*3:終了時の状態から 1-3 個程度進んでいる場合があります。