🥇祝福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, ...

乍一看这些数字有多随机？让我们首先检查分布。

它看起来接近统一，但如果您读取两个数字的序列并将它们解释为平面上的坐标，您会得到：

图案变得清晰可见。由于序列中的数据以某种方式排序（即，它具有低熵），因此这可能会引起这种“偏差”。至少，这样的 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, ...

即使在飞机上，一切似乎都很好：

让我们看看数量（一次读三个数字）：

再次是图案。不再可能构建四个维度的可视化。但模式可以存在于这个维度和更大的维度上。

在对 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()（其中的基础是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

履行

我们有几种不同的方法来生成随机数。对于它们中的每一个，我们将编写一个单独的包装类，它应该提供：

可以设置值的范围[最小/最大）。将通过构造函数设置。
返回 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 正态分布的故事并没有重复：要么最初是错误的，要么是引擎中发生了某些变化。但现在我们确定了。

来源： 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() 的实现

主控制器的实现

结果

添加评论 取消回复

添加评论取消回复