BlessRNG ou RNG vérifier l'honnêteté

Dans gamedev, vous devez souvent attacher quelque chose sur une maison aléatoire: Unity a son propre Random pour cela, et System.Random existe en parallèle avec lui. Il était une fois un des projets, il semblait que les deux pouvaient fonctionner différemment (bien qu'ils devraient avoir une distribution uniforme).

Ensuite, ils ne sont pas entrés dans les détails - il suffisait que la transition vers System.Random ait résolu tous les problèmes. Maintenant, nous avons décidé de comprendre plus en détail et de mener une petite recherche: comment les RNG sont «biaisés» ou prévisibles, et lequel choisir. De plus, j’ai souvent entendu des opinions contradictoires sur leur «honnêteté» - essayons de comprendre comment les résultats réels se rapportent à ceux déclarés.

Un bref programme éducatif ou RNG est en fait un PRNG

Si vous connaissez déjà les générateurs de nombres aléatoires, vous pouvez immédiatement passer à la section "Test".

Les nombres aléatoires (MF) sont une séquence de nombres générés à l'aide d'un processus aléatoire (chaotique), une source d'entropie. Autrement dit, c'est une telle séquence, dont les éléments ne sont liés par aucune loi mathématique - ils n'ont pas de relation causale.

Ce qui crée un milieu de gamme s'appelle un générateur de nombres aléatoires (RNG). Il semblerait que tout soit élémentaire, mais si nous passons de la théorie à la pratique, la mise en œuvre d'un algorithme logiciel pour générer une telle séquence n'est pas si simple.

La raison réside en l'absence de l'aléatoire même dans l'électronique grand public moderne. Sans cela, les nombres aléatoires cessent d'être aléatoires et leur générateur se transforme en une fonction ordinaire d'arguments délibérément déterminés. Pour un certain nombre de spécialités dans le domaine informatique, il s'agit d'un problème sérieux (par exemple, pour la cryptographie), pour le reste, il existe une solution parfaitement acceptable.

Nous devons écrire un algorithme qui retournerait, même s'il ne s'agit pas vraiment de nombres aléatoires, mais aussi près que possible d'eux - les soi-disant nombres pseudo-aléatoires (PSN). Dans ce cas, l'algorithme est appelé générateur de nombres pseudo-aléatoires (PRNG).

Il existe plusieurs options pour créer un PRNG, mais pour tous, les éléments suivants seront pertinents:

1. La nécessité d'une pré-initialisation.
   
   Le PRNG est dépourvu de source d'entropie, par conséquent, avant utilisation, il doit indiquer l'état initial. Il est spécifié sous forme de nombre (ou vecteur) et est appelé une graine (graine, graine aléatoire). Souvent, un compteur d'horloge de processeur ou l'équivalent numérique du temps système est utilisé comme valeur de départ.
2. Reproductibilité de la séquence.
   
   Le PRNG est complètement déterministe, de sorte que la graine spécifiée lors de l'initialisation détermine de manière unique la future séquence entière de nombres. Cela signifie qu'un seul DSRP, initialisé avec la même graine (à différents moments, dans différents programmes, sur différents appareils) générera la même séquence.

Vous devez également connaître la distribution de probabilité caractérisant le PRNG - quels nombres il générera et avec quelle probabilité. Le plus souvent, il s'agit soit d'une distribution normale, soit d'une distribution uniforme.

Distribution normale (gauche) et distribution uniforme (droite)

Disons que nous avons un dé honnête avec 24 visages. Si vous le laissez tomber, la probabilité de chute d'une unité sera de 1/24 (ainsi que la probabilité de chute d'un autre nombre). Si vous faites beaucoup de lancers et enregistrez les résultats, vous remarquerez que tous les visages tombent à peu près à la même fréquence. En fait, ces dés peuvent être considérés comme un RNG avec une distribution uniforme.

Et si vous jetez immédiatement 10 de ces os et comptez le nombre total de points? L'uniformité sera-t-elle maintenue pour elle? Non. Le plus souvent, le montant sera proche de 125 points, soit une valeur moyenne. Et par conséquent - avant même de lancer, vous pouvez approximativement estimer le résultat futur.

La raison en est que pour obtenir le nombre moyen de points, il y a le plus grand nombre de combinaisons. Plus on s'en éloigne, moins il y a de combinaisons - et, par conséquent, moins de risques de perte. Si vous visualisez ces données, elles ressembleront à distance à la forme d'une cloche. Par conséquent, avec un peu d'étirement, un système de 10 os peut être appelé un RNG avec une distribution normale.

Un autre exemple, seulement déjà dans l'avion - tir à la cible. Le tireur sera le RNG générant une paire de nombres (x, y), qui est affiché sur le graphique.

Convenez que l'option de gauche est plus proche de la vie réelle - il s'agit d'un RNG avec une distribution normale. Mais si vous avez besoin de disperser des étoiles dans un ciel sombre, la bonne option, obtenue à l'aide d'un RNG avec une distribution uniforme, est meilleure. En général, choisissez un générateur en fonction de la tâche.

Parlons maintenant de l'entropie de la séquence PSP. Par exemple, il existe une séquence qui commence comme ceci:

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, ...

Dans quelle mesure ces chiffres sont-ils aléatoires à première vue? Commençons par vérifier la distribution.

Cela ressemble à de l'uniforme, mais si vous lisez la séquence de deux nombres et les interprétez comme des coordonnées dans le plan, vous obtenez ceci:

Les motifs sont clairement visibles. Et puisque les données de la séquence sont ordonnées d'une certaine manière (c'est-à-dire qu'elles ont une faible entropie), cela peut conduire au «biais» même. Au minimum, un tel PRNG n'est pas très approprié pour générer des coordonnées sur un plan.

Une autre séquence:

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, ...

Tout semble aller bien ici même dans l'avion:

Voyons en volume (nous lisons trois chiffres chacun):

Et encore une fois les motifs. La visualisation de la construction en quatre dimensions ne fonctionnera pas. Mais des motifs peuvent exister à la fois sur cette dimension et sur les grands.

Dans la même cryptographie, où les exigences les plus strictes sont imposées au PRNG, une telle situation est catégoriquement inacceptable. Par conséquent, pour évaluer leur qualité, des algorithmes spéciaux ont été développés, que nous n'aborderons pas maintenant. Le sujet est vaste et s'inspire d'un article distinct.

Test

Si nous ne savons pas quelque chose avec certitude, alors comment travailler avec cela? Vaut-il la peine de traverser la route si vous ne savez pas quel feu il autorise? Les conséquences peuvent être différentes.

Il en va de même pour l'aléatoire notoire dans Unity. Eh bien, si la documentation révèle les détails nécessaires, mais l'histoire mentionnée au début de l'article s'est produite juste en raison du manque de détails souhaités.

Et sans savoir comment l'outil fonctionne, vous ne pouvez pas l'appliquer correctement. En général, le moment est venu de vérifier et de mener une expérience pour enfin s'assurer au moins au détriment de la distribution.

La solution était simple et efficace: collecter des statistiques, obtenir des données objectives et consulter les résultats.

Sujet de recherche

Il existe plusieurs façons de générer des nombres aléatoires dans Unity - nous en avons testé cinq.

1. System.Random.Next (). Génère des entiers dans une plage de valeurs donnée.
2. System.Random.NextDouble (). Génère des nombres à double précision (double) dans la plage de [0; 1).
3. UnityEngine.Random.Range (). Génère des nombres à simple précision (float) dans une plage de valeurs donnée.
4. UnityEngine.Random.value. Génère des nombres à simple précision (float) dans la plage de [0; 1).
5. Unity.Mathematics.Random.NextFloat (). Fait partie de la nouvelle bibliothèque Unity.Mathematics. Génère des nombres à simple précision (float) dans une plage de valeurs donnée.

Presque partout dans la documentation, une distribution uniforme a été indiquée, à l'exception de UnityEngine.Random.value (où la distribution n'est pas spécifiée, mais de manière similaire à UnityEngine.Random.Range (), elle devait également être uniforme) et Unity.Mathematics.Random.NextFloat () (où dans la base est l'algorithme xorshift, ce qui signifie que vous devez à nouveau attendre une distribution uniforme).

Par défaut, ceux attendus dans la documentation ont été pris pour les résultats attendus.

Méthodologie

Nous avons écrit une petite application qui a généré des séquences de nombres aléatoires dans chacune des méthodes présentées et enregistré les résultats pour un traitement ultérieur.

La longueur de chaque séquence est de 100 000 numéros.
La plage de nombres aléatoires est [0, 100).

Les données ont été collectées à partir de plusieurs plateformes cibles:

• Windows
  - Unity v2018.3.14f1, mode Éditeur, Mono, .NET Standard 2.0
• macOS
  - Unity v2018.3.14f1, mode Éditeur, Mono, .NET Standard 2.0
  - Unity v5.6.4p4, mode Éditeur, Mono, .NET Standard 2.0
• Android
  - Unity v2018.3.14f1, assemblage sur l'appareil, Mono, .NET Standard 2.0
• iOS
  - Unity v2018.3.14f1, build to device, il2cpp, .NET Standard 2.0

Implémentation

Nous avons plusieurs façons de générer des nombres aléatoires. Pour chacun d'eux, nous allons écrire une classe wrapper distincte, qui devrait fournir:

1. Possibilité de définir la plage de valeurs [min / max). Il sera défini par le constructeur.
2. Méthode de retour de milieu de gamme. Nous choisirons float comme type, comme type plus général.
3. Nom de la méthode de génération pour marquer les résultats. Pour plus de commodité, nous retournerons le nom complet de la classe + le nom de la méthode utilisée pour générer le milieu de gamme comme valeur.

Tout d'abord, déclarez une abstraction, qui sera représentée par l'interface IRandomGenerator:

namespace RandomDistribution { public interface IRandomGenerator { string Name { get; } float Generate(); } } 

Implémentation de System.Random.Next ()

Cette méthode vous permet de spécifier une plage de valeurs, mais elle renvoie des entiers et un flottant est nécessaire. Vous pouvez simplement interpréter l'entier comme un flottant, ou vous pouvez étendre la plage de valeurs de plusieurs ordres de grandeur, en les compensant chaque fois que le milieu de gamme est généré. Il se révélera quelque chose comme virgule fixe avec la précision spécifiée. Nous utiliserons cette option, car elle est plus proche de la valeur flottante réelle.

 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; } } l' 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; } } du 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; } } 

Implémentation de System.Random.NextDouble ()

Voici une plage fixe de valeurs [0; 1). Pour le projeter sur celui spécifié dans le constructeur, nous utilisons une arithmétique simple: 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; } } l' 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; } } du 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; } } 

Implémentation de UnityEngine.Random.Range ()

Cette méthode de la classe statique UnityEngine.Random vous permet de spécifier une plage de valeurs et renvoie un milieu de gamme de type float. Aucune transformation supplémentaire n'est nécessaire.

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

Implémentation de UnityEngine.Random.value

La propriété value de la classe statique UnityEngine.Random renvoie un milieu de gamme de type float à partir d'une plage fixe de valeurs [0; 1). Nous le projetons sur une plage donnée de la même manière que lors de l'implémentation de 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; } } 

Implémentation de Unity.Mathematics.Random.NextFloat ()

La méthode NextFloat () de la classe Unity.Mathematics.Random renvoie un milieu de gamme de type float et vous permet de spécifier une plage de valeurs. La seule nuance est que chaque instance de Unity.Mathematics.Random devra être initialisée avec une graine - de cette façon, nous éviterons de générer des séquences répétées.

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

Implémentation de MainController

Plusieurs implémentations IRandomGenerator sont prêtes. Ensuite, vous devez générer des séquences et enregistrer l'ensemble de données résultant pour le traitement. Pour ce faire, créez une scène dans Unity et un petit script MainController, qui effectuera tout le travail nécessaire et sera simultanément responsable de l'interaction avec l'interface utilisateur.

Nous définissons la taille de l'ensemble de données et la plage de valeurs de milieu de gamme, et obtenons également une méthode qui renvoie un tableau de générateurs optimisés et prêts à l'emploi.

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

Et maintenant, nous formons un ensemble de données. Dans ce cas, la génération des données sera combinée avec l'enregistrement des résultats dans un flux de texte (au format csv). Pour stocker les valeurs de chaque IRandomGenerator, une colonne distincte est allouée et la première ligne contient le nom du générateur.

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

Il reste à appeler la méthode GenerateCsvDataSet et à enregistrer le résultat dans un fichier, ou à transférer immédiatement les données sur le réseau de l'appareil final vers le serveur de réception.

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

Les sources du projet sont sur GitLab .

Résultats

Aucun miracle ne s'est produit. Ce à quoi ils s'attendaient, ils l'ont compris - dans tous les cas, une distribution uniforme sans la moindre trace de complot. Je ne vois pas l’intérêt d’appliquer des graphiques séparés sur les plates-formes - ils affichent tous approximativement les mêmes résultats.

La réalité est:


Visualisation de séquences sur un plan à partir des cinq méthodes de génération:


Et la visualisation en 3D. Je ne laisserai que le résultat de System.Random.Next (), afin de ne pas produire un tas du même contenu.


L'histoire racontée dans l'introduction sur la distribution normale d'UnityEngine.Random ne s'est pas répétée: soit elle était initialement erronée, soit quelque chose a changé dans le moteur depuis. Mais maintenant, nous en sommes sûrs.