BlessRNG oder wir überprüfen den RNG auf Fairness.

In der Spieleentwicklung muss man oft etwas mit Zufall verknüpfen: Bei Unity gibt es dafür ein eigenes Random, und parallel dazu existiert System.Random. Vor langer Zeit hatte ich den Eindruck, dass beide unterschiedlich arbeiten können (obwohl sie dieselbe gleichmäßige Verteilung haben sollten).

Damals sind wir nicht ins Detail gegangen – es reichte, dass der Wechsel zu System.Random alle Probleme behoben hat. Jetzt haben wir beschlossen, das genauer zu untersuchen und eine kleine Studie durchzuführen: Wie „voreingenommen“ oder vorhersehbar sind Pseudozufallszahlengeneratoren und welchen sollte man wählen? Zumal ich immer wieder widersprüchliche Meinungen über ihre „Ehrlichkeit“ gehört habe – versuchen wir zu klären, wie die realen Ergebnisse mit den behaupteten übereinstimmen.

Eine kurze Einführung oder Was sind Pseudozufallszahlen?

Wenn Sie bereits mit Zufallszahlengeneratoren vertraut sind, können Sie direkt zum Abschnitt „Testen“ wechseln.

Zufallszahlen (Zahlen) sind eine Folge von Zahlen, die durch einen bestimmten zufälligen (chaotischen) Prozess oder eine Entropiequelle erzeugt werden. Das heißt, es handelt sich um eine solche Folge, deren Elemente nicht durch irgendein mathematisches Gesetz miteinander verbunden sind – sie haben keine ursächliche Beziehung.

Das, was Zufallszahlen erzeugt, wird als Zufallszahlengenerator (Zahlengenerator) bezeichnet. Es schien alles einfach zu sein, aber wenn man von der Theorie zur Praxis übergeht, ist es in der Tat nicht so einfach, einen Softwarealgorithmus zu implementieren, der eine solche Folge generiert.

Der Grund liegt im Fehlen der besagten Chaotizität in der modernen Verbraucherelektronik. Ohne sie hören Zufallszahlen auf, zufällig zu sein, und ihr Generator wird zu einer gewöhnlichen Funktion von vordefinierten Argumenten. Für eine ganze Reihe von Fachgebieten im IT-Bereich ist dies ein ernstes Problem (zum Beispiel in der Kryptographie), für die anderen hingegen gibt es durchaus akzeptable Lösungen.

Es muss ein Algorithmus geschrieben werden, der zwar keine wahrhaft zufälligen Zahlen zurückgibt, aber so nahe wie möglich daran kommt – sogenannte Pseudozufallszahlen. Der Algorithmus wird in diesem Fall als Pseudozufallszahlengenerator (Zahlengenerator) bezeichnet.

Es gibt mehrere Möglichkeiten zur Erstellung eines Pseudozufallszahlengenerators, aber für alle ist Folgendes relevant:

1. Die Notwendigkeit einer vorherigen Initialisierung.

   Der Pseudozufallszahlengenerator (GPGZ) hat keine Entropiequelle, daher muss ihm vor der Verwendung ein anfänglicher Zustand zugewiesen werden. Dieser wird in Form einer Zahl (oder eines Vektors) angegeben und als Samen (seed, Zufallswert) bezeichnet. Oftmals wird als seed ein Zähler des Prozessortakts oder der numerische Wert der Systemzeit verwendet.

2. Reproduzierbarkeit der Sequenz.

   Der Pseudozufallszahlengenerator ist vollständig deterministisch, weshalb der bei der Initialisierung angegebene seed die gesamte zukünftige Zahlenfolge eindeutig bestimmt. Das bedeutet, dass ein bestimmter GPGZ, der mit demselben seed (zu verschiedenen Zeiten, in verschiedenen Programmen, auf verschiedenen Geräten) initialisiert wurde, die gleiche Sequenz erzeugt.

Außerdem muss man die Wahrscheinlichkeitsverteilung des GPGZ kennen – welche Zahlen er generiert und mit welcher Wahrscheinlichkeit. Meistens handelt es sich um eine Normalverteilung oder eine Gleichverteilung.

Normalverteilung (links) und Gleichverteilung (rechts)

Angenommen, wir haben einen fairen Würfel mit 24 Seiten. Wenn man ihn wirft, beträgt die Wahrscheinlichkeit, eine Eins zu würfeln, 1/24 (genauso wie die Wahrscheinlichkeit, eine andere Zahl zu würfeln). Wenn man viele Würfe macht und die Ergebnisse aufzeichnet, kann man beobachten, dass jede Seite etwa mit der gleichen Häufigkeit erscheint. In der Tat kann man diesen Würfel als GZ mit Gleichverteilung betrachten.

Und wenn man gleichzeitig 10 solcher Würfel wirft und die Gesamtpunktzahl zählt? Bleibt die Gleichverteilung dabei erhalten? Nein. Die Summe wird meistens nahe 125 Punkten liegen, also um einen bestimmten Mittelwert. Folglich kann man bereits vor dem Wurf den zukünftigen Ausgang grob abschätzen.

Der Grund dafür ist, dass es die höchste Anzahl von Kombinationen gibt, um die durchschnittliche Punktzahl zu erhalten. Je weiter man davon entfernt ist, desto weniger Kombinationen gibt es – und somit eine geringere Wahrscheinlichkeit, diese zu erreichen. Wenn man diese Daten visualisiert, erinnern sie entfernt an die Form einer Glocke. Daher kann man mit ein bisschen Wohlwollen das System aus 10 Würfeln als GZ mit Normalverteilung bezeichnen.

Ein weiteres Beispiel, aber diesmal im zweidimensionalen Raum – das Schießen auf eine Zielscheibe. Der Schütze wird der GZ sein, der ein Paar Zahlen (x, y) generiert, die auf dem Diagramm dargestellt werden.

Einverstanden, die linke Variante ist näher an der Realität – das ist ein Pseudozufallszahlengenerator mit einer Normalverteilung. Wenn jedoch Sterne am dunklen Himmel verteilt werden sollen, ist die rechte Variante, die mit einem gleichverteilten Pseudozufallszahlengenerator erstellt wurde, besser geeignet. Insgesamt wählen Sie den Generator je nach gestellter Aufgabe.

Nun sprechen wir über die Entropie der Sequenz von Pseudozufallszahlen. Zum Beispiel gibt es eine Sequenz, die so beginnt:

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

Wie zufällig erscheinen diese Zahlen auf den ersten Blick? Lassen Sie uns die Verteilung überprüfen.

Es sieht fast gleich verteilt aus, aber wenn man die Sequenz in Paaren liest und sie als Koordinaten in der Ebene interpretiert, entsteht dies:

Muster werden deutlich sichtbar. Und da die Daten in der Sequenz auf eine bestimmte Weise geordnet sind (das heißt, sie haben eine niedrige Entropie), kann dies die besagte "Voreingenommenheit" hervorrufen. Mindestens ist dieser Pseudozufallszahlengenerator nicht sehr gut geeignet, um Koordinaten in der Ebene zu generieren.

Eine andere Sequenz:

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

Hier scheint alles gut zu sein, sogar in der Ebene:

Schauen wir uns die dreidimensionale Darstellung an (wir lesen drei Zahlen):

Und wieder gibt es Muster. Eine Visualisierung in vier Dimensionen ist bereits nicht mehr möglich. Aber Muster können auch in dieser Dimension und in größeren existieren.

In der gleichen Kryptographie, wo an Pseudozufallszahlengeneratoren die strengsten Anforderungen gestellt werden, ist eine solche Situation kategorisch inakzeptabel. Daher wurden spezielle Algorithmen zur Bewertung ihrer Qualität entwickelt, auf die wir jetzt nicht näher eingehen werden. Das Thema ist umfangreich und würde einen eigenen Artikel erfordern.

Tests

Wenn wir etwas nicht sicher wissen, wie sollen wir damit umgehen? Sollten wir die Straße überqueren, wenn wir nicht wissen, welches Licht dies erlaubt? Die Konsequenzen können unterschiedlich sein.

Das gilt auch für das sprichwörtliche Random in Unity. Es ist gut, wenn die Dokumentation die notwendigen Details vermittelt, aber die zu Beginn des Artikels erwähnte Geschichte geschah gerade aufgrund des Fehlens der gewünschten Genauigkeit.

Ohne zu wissen, wie das Werkzeug funktioniert, kannst du es nicht korrekt anwenden. Es ist an der Zeit, einen Test durchzuführen und ein Experiment zu machen, um zumindest beim Thema Verteilung endgültig sicher zu sein.

Die Lösung war einfach und effektiv – Statistiken zu sammeln, objektive Daten zu erhalten und die Ergebnisse zu betrachten.

Gegenstand der Forschung

In Unity gibt es mehrere Möglichkeiten zur Generierung von Zufallszahlen – wir haben fünf getestet.

1. System.Random.Next(). Generiert ganze Zahlen (Integer) im angegebenen Wertebereich.
2. System.Random.NextDouble(). Generiert Fließkommazahlen (Double) im Bereich von [0; 1).
3. UnityEngine.Random.Range(). Generiert Fließkommazahlen (Float) im angegebenen Wertebereich.
4. UnityEngine.Random.value. Generiert Fließkommazahlen (Float) im Bereich von [0; 1).
5. Unity.Mathematics.Random.NextFloat(). Teil der neuen Unity.Mathematics-Bibliothek. Generiert Fließkommazahlen (Float) im angegebenen Wertebereich.

Fast überall in der Dokumentation wurde eine gleichmäßige Verteilung angegeben, mit Ausnahme von UnityEngine.Random.value (wo die Verteilung nicht angegeben ist, aber analog zu UnityEngine.Random.Range() ebenfalls eine gleichmäßige erwartet wurde) und Unity.Mathematics.Random.NextFloat() (wo der Algorithmus xorshift zugrunde liegt, und damit muss man erneut eine gleichmäßige Verteilung erwarten).

Standardmäßig wurden die erwarteten Ergebnisse anhand der in der Dokumentation angegebenen Werte festgelegt.

Methodik

Wir haben eine kleine Anwendung geschrieben, die mit jeder der vorgestellten Methoden Zufallszahlensequenzen generierte und die Ergebnisse zur weiteren Verarbeitung speicherte.

Die Länge jeder Sequenz beträgt 100.000 Zahlen.
Der Wertebereich der Zufallszahlen liegt bei [0, 100).

Die Daten wurden von mehreren Zielplattformen gesammelt:

• Windows
  – Unity v2018.3.14f1, Editor-Modus, Mono, .NET Standard 2.0
• macOS
  – Unity v2018.3.14f1, Editor-Modus, Mono, .NET Standard 2.0
  – Unity v5.6.4p4, Editor-Modus, Mono, .NET Standard 2.0
• Android
  – Unity v2018.3.14f1, Build für Geräte, Mono, .NET Standard 2.0
• iOS
  – Unity v2018.3.14f1, Build für Geräte, il2cpp, .NET Standard 2.0

Implementierung

Wir haben mehrere verschiedene Methoden zur Erzeugung von Zufallszahlen. Für jede von ihnen werden wir eine separate Wrapper-Klasse schreiben, die Folgendes bereitstellt:

1. Die Möglichkeit, den Wertebereich [min/max) festzulegen. Dies wird über den Konstruktor festgelegt.
2. Eine Methode, die Zufallszahlen zurückgibt. Wir wählen den Typ Float, da er allgemeiner ist.
3. Bezeichnung der Methode zur Generierung zur Kennzeichnung der Ergebnisse. Zur Vereinfachung geben wir als Wert den vollen Klassennamen + den Namen der verwendeten Methode zur Generierung der Zufallszahlen zurück.

Zuerst erklären wir die Abstraktion, die durch das Interface IRandomGenerator dargestellt wird:

namespace RandomDistribution
{
    public interface IRandomGenerator
    {
        string Name { get; }

        float Generate();
    }
}

Implementierung von System.Random.Next()

Diese Methode ermöglicht es, einen Wertebereich festzulegen, gibt jedoch ganze Zahlen (Integer) zurück, während wir Floats benötigen. Man kann einfach Integer als Float interpretieren oder den Wertebereich um mehrere Größenordnungen erweitern, indem man sie bei jeder Generierung von Zufallszahlen kompensiert. Das Ergebnis wäre etwas wie Fixed-Point mit einer bestimmten Präzision. Wir werden diese Variante verwenden, da sie näher am tatsächlichen Float-Wert liegt.

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

Implementierung von System.Random.NextDouble()

Hier ist der feste Wertebereich [0; 1). Um ihn auf den im Konstruktor angegebenen Bereich zu projizieren, verwenden wir einfache Arithmetik: 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;
    }
}

Implementierung von UnityEngine.Random.Range()

Diese Methode der statischen Klasse UnityEngine.Random ermöglicht es, einen Wertebereich festzulegen und gibt Zufallszahlen vom Typ Float zurück. Es sind keine zusätzlichen Umwandlungen erforderlich.

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

Implementierung von UnityEngine.Random.value

Die Eigenschaft value der statischen Klasse UnityEngine.Random gibt eine Zufallszahl vom Typ Float aus einem festen Wertebereich [0; 1) zurück. Wir projizieren sie auf den angegebenen Bereich auf die gleiche Weise wie bei der Implementierung von 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;
    }
}

Implementierung von Unity.Mathematics.Random.NextFloat()

Die NextFloat()-Methode der Klasse Unity.Mathematics.Random gibt einen float-Zufallswert zurück und ermöglicht die Festlegung eines Wertebereichs. Der einzige Punkt ist, dass jede Instanz von Unity.Mathematics.Random mit einem bestimmten Seed initialisiert werden muss — so vermeiden wir die Generierung wiederholter Sequenzen.

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

Implementierung von MainController

Einige Implementierungen von IRandomGenerator sind bereits vorhanden. Als nächstes müssen wir Sequenzen generieren und den resultierenden Datensatz zur Verarbeitung speichern. Dazu erstellen wir eine Szene in Unity und ein kleines Skript MainController, das die gesamte erforderliche Arbeit ausführt und gleichzeitig für die Interaktion mit der UI verantwortlich ist.

Wir legen die Größe des Datensatzes und den Wertebereich für die Zufallszahlen fest und stellen eine Methode bereit, die ein Array von konfigurierten und einsatzbereiten Generatoren zurückgibt.

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

        ...
    }
}

Jetzt erstellen wir den Datensatz. In diesem Fall wird die Datengenerierung mit der Protokollierung der Ergebnisse in einen Textstream (im CSV-Format) kombiniert. Für die Speicherung der Werte jedes IRandomGenerators wird eine eigene Spalte vorgesehen, und die erste Zeile enthält den Namen des Generators.

namespace RandomDistribution
{
    public class MainController : MonoBehaviour
    {
        ...
		
        private void GenerateCsvDataSet(TextWriter writer, int dataSetSize, params IRandomGenerator[] generators)
        {
            const char separator = ',';
            int lastIdx = generators.Length - 1;

            // Kopfzeile schreiben
            for (int j = 0; j <= lastIdx; j++)
            {
                writer.Write(generators[j].Name);
                if (j != lastIdx)
                    writer.Write(separator);
            }
            writer.WriteLine();

            // Daten schreiben
            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();
            }
        }

        ...
    }
}

Es bleibt, die Methode GenerateCsvDataSet aufzurufen und das Ergebnis in einer Datei zu speichern oder die Daten sofort über das Netzwerk vom Endgerät an den Empfänger zu übertragen. Server.

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

        ...
    }
}

Die Quellcodes des Projekts liegen auf GitLab.

Ergebnisse

Wunder ist kein geschehen. Was man erwartet hat, hat man auch erhalten - in allen Fällen eine gleichmäßige Verteilung ohne jeglichen Anzeichen von Verschwörungen. Einzelne Grafiken pro Plattform zu liefern macht meines Erachtens keinen Sinn - sie zeigen alle ungefähr die gleichen Ergebnisse.

Die Realität ist folgende:


Visualisierung der Sequenzen auf der Fläche aus allen fünf Generierungsmethoden:


Und die Visualisierung in 3D. Ich lasse nur das Ergebnis von System.Random.Next() übrig, um keinen Haufen identischer Inhalte zu produzieren.


Die im Einführungsgeschichte über die Normalverteilung von UnityEngine.Random erzählte, hat sich nicht wiederholt: entweder war sie von Anfang an fehlerhaft, oder seitdem hat sich etwas in der Engine geändert. Aber jetzt sind wir sicher.

Quelle: habr.com