BlessRNG 或檢查 RNG 的公平性

在遊戲開發中，你經常需要將某些東西與隨機性聯繫起來：Unity 有自己的 Random 函數來實現這一點，而 System.Random 與之並行存在。曾經在一個專案中，我感覺兩者的工作方式可能有所不同（儘管它們應該具有均勻分佈）。

當時我們並沒有深入探討細節──遷移到 System.Random 解決了所有問題就夠了。現在我們決定更深入地研究這個問題，並進行一項小型研究：RNG 的「偏差」或可預測性如何，以及應該選擇哪一個。此外，我不只一次聽到關於其「誠實度」的矛盾意見——讓我們試著比較一下實際結果與聲明結果的差異。

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

如果您已經熟悉隨機數產生器，則可以跳至「測試」部分。

隨機數 (RN) 是由某種隨機（混沌）過程產生的數字序列，該過程是熵的來源。也就是說，該序列的元素之間沒有任何數學定律的聯繫——它們之間沒有因果關係。

創建SN的程式稱為隨機數產生器（RNG）。一切看似簡單，但如果我們從理論到實踐，那麼實現一個產生此類序列的軟體演算法實際上並非易事。

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

有必要編寫一種演算法，使其即使不是真隨機數，也能傳回盡可能接近真隨機數的數值－即所謂的偽隨機數（PRNG）。這種演算法稱為偽隨機數產生器（PRNG）。

建立 PRNG 有多種選項，但以下內容適用於所有選項：

1. 需要預先初始化。

   PRNG 沒有熵源，因此在使用前需要指定初始狀態。此狀態可以指定為一個數字（或向量），稱為種子（隨機種子）。通常，處理器週期計數器或系統時間的數值等效值可用作種子。

2. 序列的可重複性。

   PRNG 是完全確定性的，因此在初始化期間指定的種子唯一地決定了整個未來的數字序列。這意味著，使用相同種子初始化的單一 PRNG（在不同時間、不同程式、不同裝置上）將產生相同的序列。

您還需要了解表徵PRNG的機率分佈——它將產生哪些數字以及機率是多少。通常，機率分佈是常態分佈或均勻分佈。

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

假設我們有一個公平的24面骰。如果我們擲它，擲出1的機率是24/XNUMX（擲出其他數字的機率也是XNUMX/XNUMX）。如果我們多次擲骰子並記錄結果，我們會發現所有面出現的機率大致相同。本質上，這個骰子可以被認為是一個均勻分佈的隨機數產生器（RNG）。

如果你一次擲10個這樣的骰子併計算總分，結果會保持一致嗎？不會。通常情況下，總分會接近125分，也就是某個平均值。因此，即使在擲骰子之前，你也能粗略地估計最終結果。

原因在於，為了獲得平均分數，組合數必須最大。距離平均分數越遠，組合數就越少，因此，出現偏差的機率就越低。如果將這些數據視覺化，它們會隱約呈現出鐘形。因此，略加延伸，10個骰子的系統可以稱為服從常態分佈的隨機數產生器 (RNG)。

另一個例子，已經在飛機上——射擊目標。射擊者將是一個隨機數產生器 (RNG)，產生一對數字 (x, y)，並將其顯示在圖表上。

我同意左邊的版本更接近現實生活——它是一個服從常態分佈的隨機數產生器 (RNG)。但如果你需要在黑暗的天空中散射星星，那麼右邊的版本（使用服從均勻分佈的隨機數產生器獲得）更適合。一般來說，要根據具體任務選擇生成器。

現在我們來討論一下隨機數序列的熵。例如，有一個序列以如下方式開始：

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、…

乍一看，這些數字有多隨機？我們先來檢查一下分佈。

它看起來接近均勻，但如果你一次讀取序列中的兩個數字並將它們解釋為平面上的座標，你會得到這樣的結果：

模式變得清晰可見。由於序列中的資料以某種方式排序（即熵值較低），這可能會產生這種「偏差」。至少，這樣的偽隨機數產生器不太適合產生平面座標。

另一個序列：

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、…

看起來這裡一切都很好，即使是在平坦的表面上：

我們來看看成交量（讀三個數字）：

再次強調，模式。現在我們已無法在四維空間中建構視覺化。但模式可以存在於四維空間以及更大的維度。

同樣，在對PRNG有最嚴格要求的密碼學中，這種情況是絕對不可接受的。因此，人們開發了專門的演算法來評估其質量，我們這裡就不贅述了。這個主題很廣泛，值得另寫一篇文章來探討。

測試

如果我們不確定某件事，我們該如何處理呢？如果我們不知道哪個交通號誌允許過馬路，我們該過馬路嗎？後果可能大相逕庭。

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

如果你不知道這個工具是如何運作的，你就無法正確使用它。通常情況下，你需要進行檢查並進行實驗，至少最終確定分佈情況。

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

研究主題

在 Unity 中有幾種方法可以產生隨機數 - 我們測試了其中五種。

1. System.Random.Next() 產生給定值範圍內的整數。
2. System.Random.NextDouble(). 產生 [0; 1) 範圍內的雙精度數。
3. UnityEngine.Random.Range() 在給定的值範圍內產生單精度數（浮點數）。
4. UnityEngine.Random.value 產生範圍在 [0; 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，編輯器模式，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

履行

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

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

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

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

        float Generate();
    }
}

System.Random.Next() 的實現

此方法可讓您設定一個值範圍，但它傳回的是整數，而浮點數是必要的。您可以簡單地將整數解釋為浮點數，也可以將值範圍擴大幾個數量級，並在每次產生 SC 時進行補償。您將得到類似於具有指定精度階的定點數。我們將使用此選項，因為它更接近真實的浮點值。

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 的這個方法允許指定一個值的範圍，並傳回一個浮點型隨機數。無需進行任何額外的轉換。

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 屬性傳回一個浮點型隨機數，範圍是固定的 [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() 方法傳回一個浮點型隨機數，並允許指定取值範圍。唯一需要注意的是，每個 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 的互動。

我們將設定資料集的大小和 SC 值的範圍，並取得傳回已配置且可立即使用的生成器陣列的方法。

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