Geekly articles weekly

BlessRNG或RNG检查是否诚实



在gamedev中，您经常需要在随机的房子上绑一些东西：Unity为此具有自己的Random，而System.Random与之并行存在。 从前，在一个项目中似乎两个项目的工作方式可能有所不同（尽管它们应该具有统一的分布）。

然后他们没有详细介绍-过渡到System.Random就足以解决所有问题。 现在，我们决定更详细地理解并进行一些研究：RNG的“偏向”或可预测性如何，以及选择哪种。 此外，我经常听到关于他们的“诚实”的相互矛盾的看法-让我们尝试找出实际结果与陈述结果之间的关系。

简短的教育计划或RNG实际上是PRNG


如果您已经熟悉随机数生成器，则可以立即进入“测试”部分。

随机数（MF）是使用某种随机（混沌）过程（熵的来源）生成的数字序列。 也就是说，这是一个序列，其元素不受任何数学法则连接-它们没有因果关系。

产生中音的原因称为随机数生成器（RNG）。 似乎一切都是基本的，但是如果我们从理论上转到实践上，那么实际上实现生成这种序列的软件算法并不是那么简单。

原因在于现代消费电子产品缺乏随机性。 没有它，随机数就不再是随机的，它们的生成器变成了故意确定参数的普通函数。 对于IT领域的许多专业而言，这是一个严重的问题（例如，对于密码学而言），而对于其他领域，则存在一个完全可以接受的解决方案。

我们需要编写一种算法，即使它不是真正的随机数，但也要返回尽可能近的算法-所谓的伪随机数（PSN）。 这种情况下的算法称为伪随机数生成器（PRNG）。

有多种创建PRNG的选项，但对于所有这些而言，以下都是相关的：

  1. 需要预先初始化。

    PRNG没有熵源，因此，在使用它之前，有必要指出初始状态。 它被指定为数字（或向量），并称为种子（种子，随机种子）。 通常，将处理器时钟计数器或系统时间的数值等效项用作种子。
  2. 序列的可重复性。

    PRNG是完全确定性的，因此在初始化过程中指定的种子将唯一确定整个将来的数字序列。 这意味着使用相同种子（在不同时间，在不同程序中，在不同设备上）初始化的单个PRSP将生成相同序列。

您还需要知道PRNG的概率分布-它将生成什么数字以及以何种概率生成。 通常，这是正态分布或均匀分布。

正态分布（左）和均匀分布（右）

假设我们有一个24张面孔的诚实骰子。 如果您将其删除，则单位掉出的概率为1/24（以及其他任何数字掉出的概率）。 如果您进行大量投掷并记录结果，您会发现所有面孔的掉落频率大致相同。 实际上，该骰子可以被认为是具有均匀分布的RNG。

如果您立即扔出10根这样的骨头并计算总点数？ 会为她保持统一性吗？ 不行 通常，金额接近125点，即某个平均值。 结果-即使在抛出之前，您也可以粗略估计未来的结果。

原因是要获得平均点数，组合的数量最多。 离它越远，组合越少-因此损失的机会也就越少。 如果您可视化此数据，它将在远程上类似于钟形。 因此，在一定程度上可以将具有10个骨骼的系统称为具有正态分布的RNG。

另一个例子，只有已经在飞机上的目标射击。 射击者将是生成一对数字（x，y）的RNG，该数字将显示在图形上。

同意左侧的选项更接近现实生活-这是具有正态分布的RNG。 但是，如果您需要在黑暗的天空中散布星星，那么在具有均匀分布的RNG的帮助下，正确的选择会更好。 通常，根据任务选择一个生成器。

现在让我们谈谈PSP序列的熵。 例如，有一个序列是这样开始的：

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，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,000个数字。
随机数的范围是[0，100）。

数据是从几个目标平台收集的：

  • 窗户
    -Unity v2018.3.14f1，编辑器模式，Mono，.NET Standard 2.0
  • 操作系统
    -Unity v2018.3.14f1，编辑器模式，Mono，.NET Standard 2.0
    -Unity v5.6.4p4，编辑器模式，Mono，.NET Standard 2.0
  • 安卓系统
    -Unity v2018.3.14f1，在设备上组装，Mono，.NET Standard 2.0
  • 的iOS
    -Unity v2018.3.14f1，构建到设备，il2cpp，.NET Standard 2.0

实作


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

  1. 能够设置值的范围[最小/最大）。 将通过构造函数进行设置。
  2. 方法返回中端。 我们将选择float作为类型，作为更通用的类型。
  3. 用于标记结果的生成方法的名称。 为了方便起见，我们将返回完整的类名+用于生成中间值的方法的名称作为值。

首先，声明一个抽象，它将由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属性从固定值范围[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交互。

我们设置了数据集的大小和中值的范围，并且还获得了一种方法，该方法返回已调优且随时可用的生成器数组。

 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最初是错误的，或者此后引擎发生了变化。 但是现在我们可以确定了。

Source: https://habr.com/ru/post/zh-CN473880/

More articles:


All Articles