BlessRNG または RNG の公平性のチェック

ゲーム開発では、何かをランダム性と結び付ける必要があることがよくあります。Unity にはこのための独自の Random があり、それと並行して System.Random があります。 かつて、あるプロジェクトで、両方が異なる動作をする可能性があるという印象を受けました (ただし、それらは均等に分散されているはずです)。

その後、彼らは詳細には立ち入りませんでした。System.Random への移行によってすべての問題が修正されただけで十分でした。 ここで、RNG がどの程度「偏っている」か、または予測可能か、そしてどれを選択すべきかについて、さらに詳細に調べて少し調査を行うことにしました。 さらに、私は彼らの「正直さ」について相反する意見を何度も聞いたことがあります。実際の結果が宣言された結果とどのように比較されるかを理解してみましょう。

簡単な教育プログラムまたは RNG は実際には RNG です

すでに乱数発生器に精通している場合は、すぐに「テスト」セクションに進んでください。

乱数 (RN) は、何らかのランダム (カオス) プロセスを使用して生成される一連の数値であり、エントロピーの源です。 つまり、これは要素が数学的法則によって相互接続されていないシーケンスであり、因果関係はありません。

乱数を生成するものを乱数発生器 (RNG) と呼びます。 すべてが初歩的なことのように思えますが、理論から実践に移行すると、実際には、そのようなシーケンスを生成するソフトウェア アルゴリズムを実装するのはそれほど簡単ではありません。

その理由は、現代の家庭用電化製品には同じような混乱が存在しないことにあります。 これがないと、乱数はランダムではなくなり、乱数のジェネレーターは、明らかに定義された引数の通常の関数に変わります。 IT 分野の多くの専門分野にとって、これは深刻な問題 (暗号化など) ですが、他の専門分野にとっては完全に許容できる解決策があります。

真の乱数ではないものの、できるだけ乱数に近い値、いわゆる擬似乱数 (PRN) を返すアルゴリズムを作成する必要があります。 この場合のアルゴリズムは擬似乱数生成器 (PRNG) と呼ばれます。

PRNG を作成するにはいくつかのオプションがありますが、以下はすべての人に関係します。

1. 予備的な初期化の必要性。

   PRNG にはエントロピーのソースがないため、使用する前に初期状態を与える必要があります。 これは数値 (またはベクトル) として指定され、シード (ランダム シード) と呼ばれます。 多くの場合、プロセッサ クロック カウンター、またはシステム時間に相当する数値がシードとして使用されます。

2. シーケンスの再現性。

   PRNG は完全に決定的であるため、初期化中に指定されたシードによって、将来の数値シーケンス全体が一意に決定されます。 これは、同じシードで初期化された別の PRNG (異なる時間、異なるプログラム、異なるデバイス上) が同じシーケンスを生成することを意味します。

また、PRNG を特徴付ける確率分布、つまり PRNG がどのような数値をどのような確率で生成するかを知る必要もあります。 ほとんどの場合、これは正規分布または一様分布のいずれかです。

正規分布（左）と一様分布（右）

24 面の公平なサイコロがあるとします。 それを投げた場合、1 が得られる確率は 24/XNUMX に等しくなります (他の数字が得られる確率と同じ)。 何度も投げて結果を記録すると、すべてのエッジがほぼ同じ頻度で脱落することがわかります。 基本的に、このダイは均一な分布を持つ RNG と考えることができます。

これらのサイコロを一度に 10 個投げて、合計点を数えたらどうなるでしょうか?均一性は保たれるのでしょうか？いいえ。ほとんどの場合、その量は 125 ポイント、つまり平均値に近くなります。その結果、投げる前でも、将来の結果を大まかに見積もることができます。

その理由は、平均スコアを取得するための組み合わせが最も多くなるからです。 そこから遠ざかるほど、組み合わせは少なくなり、それに応じて損失の可能性も低くなります。 このデータを視覚化すると、なんとなく鐘の形に似ています。 したがって、ある程度のストレッチをすれば、10 個のサイコロからなるシステムを正規分布の RNG と呼ぶことができます。

別の例ですが、今回は飛行機の中で、標的に向けて射撃します。 シューターは、グラフ上に表示される数値のペア (x、y) を生成する RNG になります。

左側のオプションが現実に近いことに同意します。これは正規分布の RNG です。 ただし、暗い空に星を散乱させる必要がある場合は、均一な分布を持つ RNG を使用して得られる適切なオプションの方が適しています。 一般に、当面のタスクに応じてジェネレータを選択します。

次に、PNG シーケンスのエントロピーについて話しましょう。 たとえば、次のように始まるシーケンスがあります。

89、93、33、32、82、21、4、42、11、8、60、95、53、30、42、19、34、35、62、23、44、38、74、36、52、 18、58、79、65、45、99、90、82、20、41、13、88、76、82、24、5、54、72、19、80、2、74、36、71、9、 ...

一見すると、これらの数字はどれほどランダムなのでしょうか?まずは分布を確認してみましょう。

均一に近いように見えますが、XNUMX つの数値のシーケンスを読み取り、それらを平面上の座標として解釈すると、次のようになります。

模様がはっきりと見えるようになります。 そして、シーケンス内のデータは特定の方法で順序付けされている (つまり、エントロピーが低い) ため、まさにその「バイアス」が生じる可能性があります。 少なくとも、このような PRNG は平面上の座標を生成するのにはあまり適していません。

別のシーケンス:

42、72、17、0、30、0、15、9、47、19、35、86、40、54、97、42、69、19、20、88、4、3、67、27、42、 56、17、14、20、40、80、97、1、31、69、13、88、89、76、9、4、85、17、88、70、10、42、98、96、53、 ...

ここでは飛行機の中でも何も問題ないようです。

ボリュームを見てみましょう (一度に XNUMX つの数字を読みます)。

そしてまたパターン。 XNUMX 次元でビジュアライゼーションを構築することはもはや不可能です。 しかし、パターンはこの次元にも、より大きな次元にも存在する可能性があります。

PRNG に最も厳しい要件が課される暗号化では、このような状況は絶対に受け入れられません。 したがって、その品質を評価するための特別なアルゴリズムが開発されましたが、ここでは触れません。 このトピックは広範囲にわたるため、別の記事にまとめる価値があります。

テスト

何か確かなことがわからない場合、どうやって対処すればよいでしょうか? どの信号で通行できるか分からない場合、道路を渡る価値はありますか? 結果は異なる場合があります。

Unity の悪名高いランダム性についても同様です。 ドキュメントで必要な詳細が明らかになっていれば良いのですが、記事の冒頭で述べたような話は、まさに望ましい詳細が欠けていたために起こりました。

また、ツールがどのように機能するかを知らなければ、正しく使用することはできません。 一般に、少なくとも分布について最終的に確認するために、検査と実験を実施する時期が来ています。

解決策はシンプルかつ効果的でした。統計を収集し、客観的なデータを取得し、結果を確認するというものでした。

研究テーマ

Unity で乱数を生成するにはいくつかの方法があります。私たちは XNUMX つの方法をテストしました。

1. System.Random.Next()。 指定された値の範囲内の整数を生成します。
2. System.Random.NextDouble()。 [0; からの範囲の倍精度数値を生成します。 1)。
3. UnityEngine.Random.Range()。 指定された値の範囲で単精度数値 (浮動小数点) を生成します。
4. UnityEngine.Random.value。 [0; からの範囲の単精度数値 (float) を生成します。 1)。
5. Unity.Mathematics.Random.NextFloat()。 新しい Unity.Mathematics ライブラリの一部です。 指定された値の範囲で単精度数値 (浮動小数点) を生成します。

UnityEngine.Random.value (分布が指定されていませんでしたが、UnityEngine.Random.Range() との類推により均一であることも期待されていました) と Unity.Mathematics.Random を除いて、ドキュメントのほぼすべての場所で均一分布が指定されていました。 .NextFloat() (基本は xorshift アルゴリズムです。これは、やはり一様な分布を待つ必要があることを意味します)。

デフォルトでは、期待される結果はドキュメントで指定されているとおりに取得されます。

方法論

私たちは、提示された各方法を使用して乱数のシーケンスを生成し、結果をさらなる処理のために保存する小さなアプリケーションを作成しました。

各シーケンスの長さは 100 個の数値です。
乱数の範囲は [0, 100) です。

データはいくつかのターゲット プラットフォームから収集されました。

• Windows
  — Unity v2018.3.14f1、エディター モード、モノラル、.NET Standard 2.0
• macOS
  — Unity v2018.3.14f1、エディター モード、モノラル、.NET Standard 2.0
  — Unity v5.6.4p4、エディター モード、モノラル、.NET Standard 2.0
• Android
  — Unity v2018.3.14f1、デバイスごとのビルド、Mono、.NET Standard 2.0
• iOS
  — Unity v2018.3.14f1、デバイスごとのビルド、il2cpp、.NET Standard 2.0

具現化

乱数を生成するにはいくつかの異なる方法があります。 それぞれに対して、次のものを提供する個別のラッパー クラスを作成します。

1. 値の範囲を設定する可能性[最小/最大)。 コンストラクター経由で設定されます。
2. MFを返すメソッド。 より一般的なので、型として float を選択しましょう。
3. 結果をマークするための生成方法の名前。 便宜上、クラスの完全名 + MF の生成に使用されたメソッドの名前を値として返します。

まず、IRandomGenerator インターフェイスによって表される抽象化を宣言しましょう。

namespace RandomDistribution
{
    public interface IRandomGenerator
    {
        string Name { get; }

        float Generate();
    }
}

System.Random.Next() の実装

このメソッドでは値の範囲を設定できますが、整数が返されますが、浮動小数点数が必要です。 単純に整数を浮動小数点として解釈することも、値の範囲を数桁拡大して、ミッドレンジの各世代で補正することもできます。 結果は、一定の精度の固定小数点のようなものになります。 このオプションは実際の float 値に近いため、このオプションを使用します。

using System;

namespace RandomDistribution
{
    public class SystemIntegerRandomGenerator : IRandomGenerator
    {
        private const int DefaultFactor = 100000;
        
        private readonly Random _generator = new Random();
        private readonly int _min;
        private readonly int _max;
        private readonly int _factor;


        public string Name => "System.Random.Next()";


        public SystemIntegerRandomGenerator(float min, float max, int factor = DefaultFactor)
        {
            _min = (int)min * factor;
            _max = (int)max * factor;
            _factor = factor;
        }


        public float Generate() => (float)_generator.Next(_min, _max) / _factor;
    }
}

System.Random.NextDouble() の実装

ここでは、値の固定範囲[0; 1)。 それをコンストラクターで指定されたものに投影するには、単純な算術 X * (最大値 − 最小値) + 最小値を使用します。

using System;

namespace RandomDistribution
{
    public class SystemDoubleRandomGenerator : IRandomGenerator
    {
        private readonly Random _generator = new Random();
        private readonly double _factor;
        private readonly float _min;


        public string Name => "System.Random.NextDouble()";


        public SystemDoubleRandomGenerator(float min, float max)
        {
            _factor = max - min;
            _min = min;
        }


        public float Generate() => (float)(_generator.NextDouble() * _factor) + _min;
    }
}

UnityEngine.Random.Range() の実装

UnityEngine.Random 静的クラスのこのメソッドを使用すると、値の範囲を設定し、float 型を返すことができます。 追加の変換を行う必要はありません。

using UnityEngine;

namespace RandomDistribution
{
    public class UnityRandomRangeGenerator : IRandomGenerator
    {
        private readonly float _min;
        private readonly float _max;


        public string Name => "UnityEngine.Random.Range()";


        public UnityRandomRangeGenerator(float min, float max)
        {
            _min = min;
            _max = max;
        }


        public float Generate() => Random.Range(_min, _max);
    }
}

UnityEngine.Random.value の実装

静的クラス UnityEngine.Random の value プロパティは、値の固定範囲から float 型を返します [0; 1)。 System.Random.NextDouble() を実装したときと同じように、指定された範囲に射影してみましょう。

using UnityEngine;

namespace RandomDistribution
{
    public class UnityRandomValueGenerator : IRandomGenerator
    {
        private readonly float _factor;
        private readonly float _min;


        public string Name => "UnityEngine.Random.value";


        public UnityRandomValueGenerator(float min, float max)
        {
            _factor = max - min;
            _min = min;
        }


        public float Generate() => (float)(Random.value * _factor) + _min;
    }
}

Unity.Mathematics.Random.NextFloat() の実装

Unity.Mathematics.Random クラスの NextFloat() メソッドは float 型の浮動小数点を返し、値の範囲を指定できます。 唯一のニュアンスは、Unity.Mathematics.Random の各インスタンスを何らかのシードで初期化する必要があることです。これにより、繰り返しシーケンスの生成が回避されます。

using Unity.Mathematics;

namespace RandomDistribution
{
    public class UnityMathematicsRandomValueGenerator : IRandomGenerator
    {
        private Random _generator;
        private readonly float _min;
        private readonly float _max;


        public string Name => "Unity.Mathematics.Random.NextFloat()";


        public UnityMathematicsRandomValueGenerator(float min, float max)
        {
            _min = min;
            _max = max;
            _generator = new Random();
            _generator.InitState(unchecked((uint)System.DateTime.Now.Ticks));
        }


        public float Generate() => _generator.NextFloat(_min, _max);
    }
}

MainControllerの実装

IRandomGenerator の実装がいくつか用意されています。 次に、シーケンスを生成し、結果のデータセットを処理用に保存する必要があります。 これを行うには、Unity でシーンと小さな MainController スクリプトを作成します。これは、必要な作業をすべて実行すると同時に、UI との対話を担当します。

データセットのサイズと MF 値の範囲を設定し、構成されて動作する準備ができているジェネレーターの配列を返すメソッドも取得しましょう。

namespace RandomDistribution
{
    public class MainController : MonoBehaviour
    {
        private const int DefaultDatasetSize = 100000;

        public float MinValue = 0f;
        public float MaxValue = 100f;

        ...

        private IRandomGenerator[] CreateRandomGenerators()
        {
            return new IRandomGenerator[]
            {
                new SystemIntegerRandomGenerator(MinValue, MaxValue),
                new SystemDoubleRandomGenerator(MinValue, MaxValue),
                new UnityRandomRangeGenerator(MinValue, MaxValue),
                new UnityRandomValueGenerator(MinValue, MaxValue),
                new UnityMathematicsRandomValueGenerator(MinValue, MaxValue)
            };
        }

        ...
    }
}

それでは、データセットを作成しましょう。 この場合、データ生成は、結果をテキスト ストリーム (csv 形式) に記録することと組み合わされます。 各 IRandomGenerator の値を格納するために、独自の個別の列が割り当てられ、最初の行にはジェネレーターの名前が含まれます。

namespace RandomDistribution
{
    public class MainController : MonoBehaviour
    {
        ...
		
        private void GenerateCsvDataSet(TextWriter writer, int dataSetSize, params IRandomGenerator[] generators)
        {
            const char separator = ',';
            int lastIdx = generators.Length - 1;

            // write header
            for (int j = 0; j <= lastIdx; j++)
            {
                writer.Write(generators[j].Name);
                if (j != lastIdx)
                    writer.Write(separator);
            }
            writer.WriteLine();

            // write data
            for (int i = 0; i <= dataSetSize; i++)
            {
                for (int j = 0; j <= lastIdx; j++)
                {
                    writer.Write(generators[j].Generate());
                    if (j != lastIdx)
                        writer.Write(separator);
                }

                if (i != dataSetSize)
                    writer.WriteLine();
            }
        }

        ...
    }
}

残っているのは、GenerateCsvDataSet メソッドを呼び出して結果をファイルに保存するか、ネットワークを介してエンド デバイスから受信サーバーにデータを即座に転送することだけです。

namespace RandomDistribution
{
    public class MainController : MonoBehaviour
    {
        ...
		
        public void GenerateCsvDataSet(string path, int dataSetSize, params IRandomGenerator[] generators)
        {
            using (var writer = File.CreateText(path))
            {
                GenerateCsvDataSet(writer, dataSetSize, generators);
            }
        }


        public string GenerateCsvDataSet(int dataSetSize, params IRandomGenerator[] generators)
        {
            using (StringWriter writer = new StringWriter(CultureInfo.InvariantCulture))
            {
                GenerateCsvDataSet(writer, dataSetSize, generators);
                return writer.ToString();
            }
        }

        ...
    }
}

プロジェクトのソースは次のとおりです。 GitLab.

結果

奇跡は起こりませんでした。 彼らが期待していたものは、彼らが得たものです - いずれの場合も、陰謀の気配のない均等な分配でした。 プラットフォームごとに別々のグラフを作成する意味がわかりません。すべてのグラフがほぼ同じ結果を示しています。

現実は次のとおりです。


XNUMX つの生成方法すべてからのシーケンスを平面上で視覚化:


そして3Dでの視覚化。 同じ内容が大量に生成されないように、System.Random.Next() の結果のみを残します。


UnityEngine.Random の正規分布についての導入部で語られた話は繰り返されませんでした。最初に誤りがあったのか、その後エンジン内で何かが変更されたかのどちらかです。 しかし今、私たちは確信しています。

出所： habr.com