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

Dans le développement de jeux, il est souvent nécessaire de baser certaines choses sur le hasard : Unity dispose de son propre Random, tandis que System.Random existe également. Il y a longtemps, lors d'un projet, j'ai eu l'impression que les deux pouvaient agir différemment (bien qu'ils devraient avoir une distribution uniforme).

À l'époque, nous ne nous sommes pas attardés sur les détails — il suffisait de constater que le passage à System.Random avait corrigé tous les problèmes. Maintenant, nous avons décidé d'explorer cela plus en profondeur et de mener une petite investigation : à quel point les générateurs de nombres aléatoires sont-ils « biaisés » ou prévisibles, et lequel choisir. D'autant plus que j'ai entendu plusieurs avis contradictoires sur leur « honnêteté » — essayons de comprendre comment les résultats réels se comparent à ceux annoncés.

Cours bref ou en réalité, un générateur de nombres aléatoires (GNA) est un générateur de pseudo-nombres aléatoires.

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

Les nombres aléatoires (NA) sont une séquence de nombres générée par un processus aléatoire (chaotique) ou une source d'entropie. En d'autres termes, il s'agit d'une séquence dont les éléments ne sont pas liés les uns aux autres par une loi mathématique — ils n'ont pas de lien de cause à effet.

Ce qui génère des NA s'appelle un générateur de nombres aléatoires (GNA). Cela semble élémentaire, mais en passant de la théorie à la pratique, il n'est en réalité pas si simple de réaliser un algorithme de génération de cette séquence.

La raison réside dans l'absence de cette chaos dans l'électronique grand public moderne. Sans cela, les nombres aléatoires cessent d'être aléatoires, et leur générateur devient une simple fonction de paramètres déterminés à l'avance. Pour un certain nombre de spécialités dans le domaine de l'informatique, c'est un véritable problème (par exemple pour la cryptographie), tandis que pour les autres, il existe des solutions acceptables.

Il est nécessaire d'écrire un algorithme qui renvoie, même si ce n'est pas réellement des nombres aléatoires, des valeurs aussi proches que possible — les soi-disant nombres pseudo-aléatoires (NPA). Dans ce cas, l'algorithme s'appelle générateur de nombres pseudo-aléatoires (GNPA).

Il existe plusieurs façons de créer un GNPA, mais pour tous, le point suivant est pertinent :

1. La nécessité d'une initialisation préalable.

   Le générateur de nombres pseudo-aléatoires est dépourvu de source d'entropie, il est donc nécessaire de lui indiquer un état initial avant utilisation. Cet état est défini comme un nombre (ou un vecteur) et est appelé graine (seed). Souvent, un compteur de cycles du processeur ou un équivalent numérique de l'heure système est utilisé comme graine.

2. Reproductibilité de la séquence.

   Le générateur de nombres pseudo-aléatoires est entièrement déterministe, donc la graine spécifiée lors de l'initialisation détermine sans ambiguïté toute la séquence de nombres futurs. Cela signifie qu'un générateur de nombres pseudo-aléatoires, initialisé avec la même graine (à des moments différents, dans différents programmes, sur différents appareils) va générer la même séquence.

Il est également nécessaire de connaître la distribution de probabilités caractéristique du générateur de nombres pseudo-aléatoires — quels nombres il va générer 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)

Supposons que nous avons un dé à 24 faces équitable. Si nous le lançons, la probabilité d'obtenir un un sera de 1/24 (tout comme la probabilité d'obtenir n'importe quel autre nombre). Si nous effectuons de nombreux lancés et enregistrons les résultats, nous pouvons remarquer que toutes les faces sortent à peu près avec la même fréquence. En essence, ce dé peut être considéré comme un générateur de nombres pseudo-aléatoires avec une distribution uniforme.

Que se passe-t-il si nous lançons 10 de ces dés en même temps et que nous comptons la somme totale ? La uniformité sera-t-elle conservée ? Non. Le plus souvent, la somme sera proche de 125 points, donc à une certaine valeur moyenne. Et en conséquence, même avant de lancer, nous pouvons estimer approximativement le résultat futur.

La raison en est qu'il y a le plus grand nombre de combinaisons possibles pour obtenir la somme moyenne des points. Plus nous nous éloignons de celle-ci, moins il y a de combinaisons - et donc, moins la probabilité d'obtenir ce résultat. Si ces données sont visualisées, elles ressembleront vaguement à la forme d'une cloche. Ainsi, avec un certain effort, le système de 10 dés peut être qualifié de générateur de nombres pseudo-aléatoires avec une distribution normale.

Un autre exemple, mais cette fois dans un plan - tir sur une cible. Le tireur sera un générateur de nombres pseudo-aléatoires, générant une paire de nombres (x, y) qui est représentée sur un graphique.

Vous conviendrez que l'option de gauche reflète mieux la réalité : c'est un GCS avec une distribution normale. Mais si vous devez disperser des étoiles dans un ciel noir, alors l'option de droite, obtenue avec un GCS à distribution uniforme, convient mieux. En général, choisissez le générateur en fonction de la tâche à accomplir.

Parlons maintenant de l'entropie de la séquence des GCS. Par exemple, il y a une séquence 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, …

À quel point ces chiffres semblent aléatoires à première vue ? Commençons par vérifier la distribution.

Cela semble proche de l'uniformité, mais si nous lisons la séquence deux chiffres à la fois et que nous les interprétons comme des coordonnées sur un plan, cela donne ceci :

Des motifs deviennent clairement visibles. Étant donné que les données de la séquence sont organisées d'une certaine manière (c'est-à-dire qu'elles ont une faible entropie), cela peut engendrer ce qu'on appelle le "biais". Au minimum, un tel GCS n'est pas vraiment adapté 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 bien ici, même sur le plan :

Examinons en trois dimensions (en lisant trois chiffres à la fois) :

Et encore des motifs. Il ne sera déjà plus possible de construire une visualisation en quatre dimensions. Mais des motifs peuvent exister dans cette dimension et dans des dimensions supérieures.

Dans la cryptographie, où les exigences envers les GCS sont les plus strictes, une telle situation est catégoriquement inacceptable. C'est pourquoi des algorithmes spéciaux ont été développés pour évaluer leur qualité, dont nous ne parlerons pas ici. Le sujet est vaste et mériterait un article à part entière.

Test

Que faire si nous ne savons pas quelque chose avec certitude ? Est-il judicieux de traverser la route si vous ne savez pas quel feu de signalisation permet de le faire ? Les conséquences peuvent être variées.

Il en va de même pour le fameux random dans Unity. C'est bien si la documentation révèle les détails nécessaires, mais l'histoire mentionnée au début de l'article est survenue justement à cause de l'absence de la précision souhaitée.

Sans comprendre comment fonctionne l'outil, vous ne pourrez pas l'appliquer correctement. Il est temps de vérifier et de mener une expérience pour s'assurer au moins en ce qui concerne la distribution.

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

Objet de l'étude

Dans Unity, il existe plusieurs méthodes pour générer des nombres aléatoires — nous en avons testé cinq.

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

Pratiquement 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 une distribution uniforme était également attendue par analogie avec UnityEngine.Random.Range()) et Unity.Mathematics.Random.NextFloat() (où repose un algorithme xorshift, donc il faut également s'attendre à une distribution uniforme).

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

Méthodologie

Nous avons écrit une petite application qui générait des séquences de nombres aléatoires par chacun des moyens présentés et sauvegardait les résultats pour un traitement ultérieur.

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

Les données ont été collectées à partir de plusieurs plates-formes 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

Mise en œuvre

Nous avons plusieurs façons différentes de générer des nombres aléatoires. Pour chacune d'elles, nous rédigerons une classe d'encapsulation distincte qui devra fournir :

1. La possibilité de définir une plage de valeurs [min/max). Cela sera défini par le constructeur.
2. Une méthode retournant un nombre flottant. Choisissons le type float, étant le plus général.
3. Le nom de la méthode de génération pour étiqueter les résultats. Pour la commodité, nous retournerons le nom complet de la classe + le nom de la méthode utilisée pour générer le nombre flottant.

D'abord, nous allons 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 définir une plage de valeurs, mais elle retourne des entiers (integer), alors que nous avons besoin de float. On peut simplement interpréter les entiers comme des float, ou élargir la plage de valeurs de plusieurs ordres, en les compensant lors de chaque génération de nombre aléatoire. Cela donnera quelque chose comme un point fixe avec une précision d'ordre spécifiée. Nous allons utiliser cette option, car elle est plus proche de la valeur float 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;
    }
}

Implémentation de System.Random.NextDouble()

Ici, la plage de valeurs est fixe [0; 1). Pour la projeter sur celle spécifiée dans le constructeur, nous utilisons une simple arithmétique : 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 définir une plage de valeurs et retourne un nombre de type float. Aucune transformation supplémentaire ne sera 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 retourne un nombre de type float d'une plage fixe de valeurs [0; 1). Nous allons le projeter sur la plage spécifiée de la même manière que pour 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 définir une plage de valeurs. La nuance est que chaque instance de Unity.Mathematics.Random doit être initialisée avec une valeur de départ (seed) — cela nous permet d'éviter la génération de séquences répétitives.

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 de IRandomGenerator sont prêtes. Ensuite, il faut générer des séquences et enregistrer le jeu de données résultant pour traitement. Pour cela, créons une scène dans Unity et un petit script MainController, qui effectuera tout le travail nécessaire tout en gérant l'interaction avec l'interface utilisateur.

Définissons la taille du jeu de données et la plage de valeurs des nombres aléatoires, et équipons-nous d'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)
            };
        }

        ...
    }
}

Et maintenant, formons le jeu de données. Dans ce cas, la génération de données sera combinée avec l'enregistrement des résultats dans un flux de texte (au format csv). Chaque 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;

            // écrire l'en-tête
            for (int j = 0; j <= lastIdx; j++)
            {
                writer.Write(generators[j].Name);
                if (j != lastIdx)
                    writer.Write(separator);
            }
            writer.WriteLine();

            // écrire les données
            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 à sauvegarder le résultat dans un fichier, ou à transmettre directement les données sur le réseau depuis l'appareil final vers le récepteur. 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 se trouvent sur GitLab.

Résultats

Le miracle n'a pas eu lieu. Ce qu'on attendait est exactement ce qu'on a eu : dans tous les cas une distribution uniforme sans aucune allusion à des conspirations. Je ne vois pas l'intérêt d'annexer des graphiques séparés par plateformes - ils montrent tous des résultats à peu près identiques.

La réalité est la suivante :


Visualisation des séquences à plat par toutes les cinq méthodes de génération :


Et une visualisation en 3D. Je ne mettrai que le résultat de System.Random.Next(), pour ne pas créer un tas de contenu identique.


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

Source : habr.com