BlessRNG ou vérifier l'équité du RNG

En développement de jeux, on a souvent besoin de recourir à l'aléatoire : Unity propose sa propre fonction Random à cet effet, et System.Random existe en parallèle. Il y a longtemps, sur un projet, j'ai eu l'impression que les deux fonctionnaient différemment (bien qu'elles soient censées avoir une distribution uniforme).

Nous n'avions pas approfondi la question à l'époque ; il nous suffisait de constater que le passage à System.Random résolvait tous les problèmes. Nous avons maintenant décidé d'examiner la question de plus près et de mener une petite étude : dans quelle mesure les générateurs de nombres aléatoires sont-ils biaisés ou prévisibles, et lequel choisir ? Par ailleurs, j'ai entendu à plusieurs reprises des avis contradictoires quant à leur « équité » ; essayons donc de comparer les résultats obtenus aux affirmations.

Une brève introduction au générateur de nombres aléatoires (GNA), ou est-ce vraiment un GNA ?

Si vous êtes déjà familiarisé avec les générateurs de nombres aléatoires, vous pouvez passer directement à la section « Tests ».

Les nombres aléatoires (NA) sont une suite de nombres générés par un processus aléatoire (chaotique), source d'entropie. Autrement dit, il s'agit d'une suite dont les éléments ne sont liés entre eux par aucune loi mathématique ; il n'existe aucune relation de cause à effet.

Ce qui crée le générateur de nombres aléatoires (GNA) s'appelle un générateur de nombres aléatoires (GNA). Bien que cela paraisse simple, la mise en pratique de la théorie révèle que l'implémentation d'un algorithme logiciel pour générer une telle séquence est loin d'être aussi simple.

La raison tient à l'absence même d'aléatoire dans l'électronique grand public moderne. Sans lui, les nombres aléatoires cessent d'être aléatoires et leur générateur se réduit à une simple fonction d'entrées prédéterminées. Pour certains métiers de l'informatique (comme la cryptographie), cela pose un problème majeur, mais pour d'autres, une solution parfaitement acceptable existe.

Nous devons écrire un algorithme qui renvoie des nombres qui ne sont pas véritablement aléatoires, mais qui s'en approchent le plus possible : ce que l'on appelle des nombres pseudo-aléatoires (NPA). Cet algorithme est appelé générateur de nombres pseudo-aléatoires (NPA).

Il existe plusieurs options pour créer un générateur de nombres pseudo-aléatoires (PRNG), mais les suivantes seront pertinentes pour tous :

1. Nécessité d'une pré-initialisation.

   Un générateur de nombres pseudo-aléatoires (PRNG) ne possédant pas de source d'entropie, un état initial doit être spécifié avant utilisation. Cet état initial est défini par un nombre (ou un vecteur) et est appelé graine (graine aléatoire). Le compteur de cycles du processeur, ou l'équivalent numérique du temps système, est souvent utilisé comme graine.

2. Reproductibilité de la séquence.

   Le générateur de nombres pseudo-aléatoires (PRNG) est parfaitement déterministe ; la graine spécifiée lors de l’initialisation détermine donc de manière unique la séquence de nombres générée. Autrement dit, un même PRNG 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.

Il est également nécessaire de connaître la distribution de probabilité qui caractérise le générateur de nombres pseudo-aléatoires (PRNG) : quels nombres il génère et avec quelle probabilité. Le plus souvent, il s’agit d’une distribution normale ou d’une distribution uniforme.

Distribution normale (à gauche) et distribution uniforme (à droite)

Imaginons un dé équilibré à 24 faces. Si on le lance, la probabilité d'obtenir un 1 est de 1/24 (comme pour tout autre nombre). En répétant l'opération plusieurs fois et en notant les résultats, on constate que tous les dés à 24 faces donnent des résultats à peu près identiques. On peut donc considérer ce dé comme un générateur de nombres aléatoires à distribution uniforme.

Que se passe-t-il si vous lancez 10 dés de ce type simultanément et calculez le score total ? Sera-t-il uniforme ? Non. Le plus souvent, le score sera proche de 125 points, soit une valeur moyenne. Par conséquent, vous pouvez estimer approximativement le résultat futur avant même de lancer les dés.

La raison est simple : il existe un maximum de combinaisons pour atteindre le score moyen. Plus on s'éloigne de la moyenne, moins il y a de combinaisons, et par conséquent, plus la probabilité d'obtenir un résultat positif est faible. Si ces données étaient visualisées, elles ressembleraient vaguement à une courbe en cloche. Ainsi, en forçant un peu les choses, un système de 10 dés pourrait être qualifié de générateur de nombres aléatoires à distribution normale.

Un autre exemple, cette fois-ci dans un avion, consiste à tirer sur une cible. Le tireur est un générateur de nombres aléatoires (GNA), qui génère une paire de nombres (x, y), lesquels sont affichés sur un graphique.

Vous conviendrez que la variante de gauche est plus proche de la réalité : il s’agit d’un générateur de nombres aléatoires suivant une loi normale. Mais si vous devez disperser des étoiles dans un ciel sombre, la variante de droite, obtenue à l’aide d’un générateur de nombres aléatoires suivant une loi uniforme, sera plus appropriée. En résumé, choisissez un générateur en fonction de la tâche à accomplir.

Parlons maintenant de l'entropie d'une suite de nombres aléatoires. Par exemple, voici une suite qui commence ainsi :

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

À première vue, ces nombres semblent-ils aléatoires ? Commençons par examiner leur distribution.

Cela semble presque uniforme, mais si vous lisez la séquence de deux nombres et les interprétez comme des coordonnées dans un plan, vous obtenez ceci :

Des schémas apparaissent clairement. Et comme 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 générer le même « biais ». À tout le moins, un tel générateur de nombres pseudo-aléatoires n'est pas très adapté à la génération de coordonnées dans 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 à plat :

Examinons le volume (lisez trois chiffres) :

Et encore une fois, des motifs. La visualisation en quatre dimensions n'est plus possible. Mais des motifs peuvent exister dans cette dimension et dans des dimensions supérieures.

En cryptographie, où les exigences imposées aux générateurs de nombres pseudo-aléatoires sont extrêmement strictes, une telle situation est absolument inacceptable. C'est pourquoi des algorithmes spécifiques ont été développés pour évaluer leur qualité, mais nous n'aborderons pas ce sujet ici. Il est vaste et mériterait un article à part entière.

Test

Si nous ignorons quelque chose avec certitude, comment pouvons-nous réagir ? Devons-nous traverser la rue sans savoir quel feu de circulation l'autorise ? Les conséquences peuvent varier.

Il en va de même pour le caractère aléatoire notoire d'Unity. C'est formidable lorsque la documentation fournit les détails nécessaires, mais l'incident mentionné au début de l'article est survenu précisément en raison de ce manque de précision.

Et sans comprendre le fonctionnement de l'outil, impossible de l'utiliser correctement. Il est donc temps de le tester et de mener une expérience pour en être enfin certain, du moins en ce qui concerne la distribution.

La solution était simple et efficace : collecter des statistiques, obtenir des données objectives et analyser 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 compris dans une plage de valeurs donnée.
2. System.Random.NextDouble(). Génère des nombres à double précision dans la plage [0; 1).
3. UnityEngine.Random.Range(). Génère des nombres à simple précision (flottants) dans une plage de valeurs donnée.
4. UnityEngine.Random.value. Génère des nombres à simple précision (float) dans la plage [0; 1).
5. Unity.Mathematics.Random.NextFloat(). Fait partie de la nouvelle bibliothèque Unity.Mathematics. Génère des nombres flottants simple précision dans une plage donnée.

Presque partout dans la documentation, une distribution uniforme était spécifiée, à l'exception de UnityEngine.Random.value (où la distribution n'est pas spécifiée, mais par analogie avec UnityEngine.Random.Range(), une distribution uniforme était également attendue) et Unity.Mathematics.Random.NextFloat() (qui est basé sur l'algorithme xorshift, ce qui signifie qu'une distribution uniforme devrait également être attendue).

Par défaut, les résultats attendus étaient ceux spécifiés dans la documentation.

Méthodologie

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

Chaque séquence comporte 100 000 nombres.
La plage de valeurs numériques 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, version pour appareil, Mono, .NET Standard 2.0
• iOS
  — Unity v2018.3.14f1, version pour appareil, il2cpp, .NET Standard 2.0

exécution

Nous disposons de plusieurs méthodes pour générer des nombres aléatoires. Pour chacune d'elles, nous écrirons une classe wrapper distincte qui devra fournir :

1. Possibilité de spécifier une plage de valeurs (min/max). Sera définie via le constructeur.
2. Une méthode qui renvoie un nombre. Nous choisirons le type float, car il est plus général.
3. Nom de la méthode de génération des résultats d'étiquetage. Par commodité, nous renverrons le nom complet de la classe suivi du nom de la méthode utilisée pour générer le SC.

Commençons par déclarer 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 permet de spécifier une plage de valeurs, mais elle renvoie des entiers, alors que des nombres à virgule flottante sont requis. Vous pouvez simplement interpréter l'entier comme un nombre à virgule flottante, ou étendre la plage de valeurs sur plusieurs ordres de grandeur, en compensant à chaque génération de la fréquence. On obtient ainsi un résultat proche d'un nombre à virgule fixe avec un ordre de précision spécifié. Nous utiliserons cette option, car elle se rapproche davantage d'une véritable valeur à virgule flottante.

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()

Ici, la plage de valeurs fixe est [0; 1). Pour la projeter sur celle spécifiée 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;
    }
}

Implémentation de UnityEngine.Random.Range()

Cette méthode de la classe statique UnityEngine.Random permet de spécifier une plage de valeurs et renvoie un nombre aléatoire de type float. Aucune conversion supplémentaire n'est requise.

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 nombre aléatoire de type float à partir d'une plage de valeurs fixe [0; 1). Nous le projetons sur la 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 nombre aléatoire de type float et permet de spécifier une plage de valeurs. Seule condition : chaque instance de Unity.Mathematics.Random doit être initialisée avec une graine afin d’éviter la génération de séquences identiques.

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 du MainController

Plusieurs implémentations d'IRandomGenerator sont prêtes. Il nous faut maintenant générer des séquences et enregistrer les données résultantes pour traitement. Pour ce faire, nous allons créer une scène dans Unity et un petit script MainController qui effectuera toutes les opérations nécessaires et gérera l'interaction avec l'interface utilisateur.

Nous définirons la taille de l'ensemble de données et la plage de valeurs de fréquence, et nous créerons également une méthode qui renvoie un tableau de générateurs configuré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)
            };
        }

        ...
    }
}

Nous allons maintenant créer l'ensemble de données. Dans ce cas, la génération des données sera combinée à l'écriture des résultats dans un flux de texte (au format CSV). Chaque générateur IRandomGenerator aura sa propre colonne, et la première ligne contiendra 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 ne reste plus qu'à 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 du périphérique final vers le périphérique de réception. serveur.

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 situées à gitlab ce.

résultats

Il n'y a pas eu de miracle. Nous avons obtenu ce que nous attendions : une distribution uniforme dans tous les cas, sans la moindre trace de complot. Je ne vois pas l'intérêt de joindre des graphiques distincts pour chaque plateforme ; ils présentent tous des résultats sensiblement identiques.

La réalité est la suivante :


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


Et la visualisation 3D. Je ne conserverai que le résultat de System.Random.Next() afin d'éviter de générer une multitude de contenus identiques.


L'histoire racontée en introduction concernant la distribution normale de UnityEngine.Random ne s'est pas reproduite : soit elle était erronée dès le départ, soit quelque chose a changé dans le moteur depuis. Mais maintenant, nous sommes confiants.

Source: habr.com