🥇祝福RNG或檢查RNG是否誠實| 專業主機

在遊戲開發中，您經常需要將某些東西與隨機性聯繫起來：Unity 為此有自己的 Random，與之並行的是 System.Random。曾幾何時，在其中一個項目中，我的印像是兩者可以以不同的方式工作（儘管它們應該具有均勻的分佈）。

然後他們沒有詳細說明 - 過渡到 System.Random 糾正了所有問題就足夠了。現在我們決定更詳細地研究它並進行一些研究：RNG 的「偏見」或可預測性如何，以及選擇哪一個。此外，我不只一次聽到關於他們的「誠實」的相互矛盾的意見——讓我們試著弄清楚真實的結果與宣稱的結果相比如何。

簡短的教育計劃或RNG實際上是RNG

如果您已經熟悉隨機數產生器，那麼您可以立即跳到「測試」部分。

隨機數 (RN) 是使用某種隨機（混沌）過程（熵的來源）產生的數字序列。也就是說，這是一個序列，其元素不通過任何數學定律互連——它們沒有因果關係。

創建隨機數的設備稱為隨機數產生器 (RNG)。看起來一切都很簡單，但如果我們從理論轉向實踐，那麼實際上實現產生這樣一個序列的軟體演算法並不是那麼簡單。

原因在於現代消費性電子產品中沒有同樣的混亂。沒有它，隨機數就不再是隨機的，它們的生成器就會變成一個由明顯定義的參數組成的普通函數。對於 IT 領域的許多專業來說，這是一個嚴重的問題（例如密碼學），但對於其他專業來說，有一個完全可以接受的解決方案。

有必要編寫一種演算法，雖然傳回的不是真正的隨機數，但盡可能接近它們，即所謂的偽隨機數 (PRN)。這種情況下的演算法稱為偽隨機數產生器 (PRNG)。

創建 PRNG 有多種選項，但以下內容與每個人都相關：

需要進行初步初始化。
PRNG沒有熵源，因此在使用前必須給定一個初始狀態。它被指定為一個數字（或向量），稱為種子（隨機種子）。通常，處理器時鐘計數器或系統時間的數值等效物被用作種子。
序列重現性。
PRNG 是完全確定性的，因此在初始化期間指定的種子唯一地確定了整個未來的數字序列。這意味著使用相同種子初始化的單獨 PRNG（在不同時間、在不同程式中、在不同裝置上）將產生相同的序列。

您還需要知道表徵 PRNG 的機率分佈 - 它將產生什麼數字以及以什麼機率產生。大多數情況下，這是常態分佈或均勻分佈。

常態分佈（左）和均勻分佈（右）

假設我們有一個 24 面的公平骰。如果你扔它，得到 1 的機率將等於 24/XNUMX（與得到任何其他數字的機率相同）。如果您進行多次拋出並記錄結果，您會注意到所有邊緣以大致相同的頻率掉落。本質上，該骰子可以被視為具有均勻分佈的 RNG。

如果您一次扔 10 個這樣的骰子併計算總點數會怎麼樣？會保持統一嗎？不。大多數情況下，該金額會接近 125 點，即某個平均值。因此，即使在投擲之前，您也可以粗略地估計未來的結果。

原因是獲得平均分數的組合數量最多。離它越遠，組合就越少，相應地，損失的可能性就越低。如果將這些數據視覺化，它會隱約類似於鐘的形狀。因此，經過一定的延伸，10 個骰子的系統可以稱為常態分佈的 RNG。

另一個例子，只是這次是在飛機上——射擊目標。射手將是一個 RNG，產生一對顯示在圖表上的數字 (x, y)。

同意左邊的選項更接近現實生活 - 這是一個常態分佈的 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, XNUMX, XNUMX, XNUMX, XNUMX, XNUMX, 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, XNUMX, XNUMX, XNUMX, XNUMX, XNUMX, …

即使在飛機上，一切似乎都很好：

讓我們看看數量（一次讀三個數字）：

再次是圖案。不再可能建構四個維度的可視化。但模式可以存在於這個維度和更大的維度上。

在對 PRNG 提出最嚴格要求的密碼學中，這種情況是絕對不可接受的。因此，已經開發了特殊的演算法來評估它們的質量，我們現在不會觸及。這個主題很廣泛，值得單獨寫一篇文章。

測試

如果我們不確定某件事，那麼該如何處理它呢？如果您不知道哪個紅綠燈允許過馬路，是否值得過馬路？後果可能會有所不同。

Unity 中臭名昭著的隨機性也是如此。如果文件揭示了必要的細節，那就太好了，但文章開頭提到的故事正是因為缺乏所需的細節而發生的。

如果您不知道該工具是如何運作的，您將無法正確使用它。一般來說，是時候檢查和進行實驗以最終至少確定分佈了。

解決方案簡單而有效——收集統計數據、獲取客觀數據並查看結果。

研究課題

在 Unity 中產生隨機數的方法有多種 - 我們測試了五種。

System.Random.Next()。產生給定值範圍內的整數。
System.Random.NextDouble()。產生 [0; 範圍內的雙精度數字] 1).
UnityEngine.Random.Range()。產生給定值範圍內的單精度數字（浮點數）。
UnityEngine.Random.value。產生 [0; 範圍內的單精度數字（浮點數）] 1).
Unity.Mathematics.Random.NextFloat()。新 Unity.Mathematics 庫的一部分。產生給定值範圍內的單精度數字（浮點數）。

文件中幾乎所有地方都指定了均勻分佈，但 UnityEngine.Random.value 除外（未指定分佈，但透過與 UnityEngine.Random.Range() 類比，也期望均勻分佈）和 Unity.Mathematics.Random .NextFloat() （其中的基礎是異或移位演算法，這意味著再次需要等待均勻分佈）。

預設情況下，預期結果會採用文件中指定的結果。

技術

我們編寫了一個小型應用程序，使用所提供的每種方法生成隨機數序列，並保存結果以進行進一步處理。

每個序列的長度是 100 個數字。
隨機數的範圍是[0, 100)。

數據是從幾個目標平台收集的：

Windows
— Unity v2018.3.14f1，編輯器模式，Mono，.NET Standard 2.0
MacOS
— Unity v2018.3.14f1，編輯器模式，Mono，.NET Standard 2.0
— Unity v5.6.4p4，編輯器模式，Mono，.NET Standard 2.0
Android
— Unity v2018.3.14f1，按設備構建，Mono，.NET Standard 2.0
iOS
— Unity v2018.3.14f1，按設備構建，il2cpp，.NET Standard 2.0

履行

我們有幾種不同的方法來產生隨機數。對於它們中的每一個，我們將編寫一個單獨的包裝類，它應該提供：

可以設定值的範圍[最小/最大）。將透過構造函數設定。
傳回 MF 的方法。我們選擇 float 作為類型，因為它更通用。
用於標記結果的生成方法的名稱。為了方便起見，我們將傳回類別的全名 + 用於產生 MF 的方法名稱作為值。

首先，讓我們聲明一個由 IRandomGenerator 介面表示的抽象：

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

        float Generate();
    }
}

System.Random.Next() 的實現

此方法允許您設定一個值範圍，但它會傳回整數，但需要浮點數。您可以簡單地將整數解釋為浮點數，也可以將數值的範圍擴大幾個數量級，並用每一代中位數來補償它們。結果將類似於具有給定精度等級的定點。我們將使用此選項，因為它更接近真實的浮點值。

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 * (max − min) + min。

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);
    }
}

主控制器的實現

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.

Результаты

奇蹟沒有發生。他們所期望的就是他們得到的東西——在所有情況下，都是均勻分配，沒有任何陰謀的跡象。我不認為為平台放置單獨的圖表有什麼意義——它們都顯示了大致相同的結果。

現實是這樣的：

所有五種生成方法的平面序列視覺化：

以及 3D 視覺化。我將只保留 System.Random.Next() 的結果，以免產生一堆相同的內容。

簡介中講述的有關 UnityEngine.Random 常態分佈的故事並沒有重複：要么最初是錯誤的，要么是引擎中發生了某些變化。但現在我們確定了。

來源： www.habr.com

BlessRNG 或檢查 RNG 的公平性

簡短的教育計劃或RNG實際上是RNG

測試

研究課題

技術

履行

System.Random.Next() 的實現

System.Random.NextDouble() 的實現

UnityEngine.Random.Range() 的實現

UnityEngine.Random.value 的實現

Unity.Mathematics.Random.NextFloat() 的實現

主控制器的實現

Результаты

添加評論取消回复

BlessRNG 或檢查 RNG 的公平性

簡短的教育計劃或RNG實際上是RNG

測試

研究課題

技術

履行

System.Random.Next() 的實現

System.Random.NextDouble() 的實現

UnityEngine.Random.Range() 的實現

UnityEngine.Random.value 的實現

Unity.Mathematics.Random.NextFloat() 的實現

主控制器的實現

Результаты

添加評論 取消回复

添加評論取消回复