BlessRNG eller kontrollerar RNG:s ärlighet

Inom spelutveckling behöver man ofta ha något kopplat till slumpen: Unity har sin egen Random, men det finns även System.Random som alternativ. För länge sedan fick vi intrycket att de två kan fungera olika (även om de borde ha en jämn fördelning).

Vi fördjupade oss inte i detaljerna — det räckte med att övergången till System.Random löste alla problem. Nu har vi bestämt oss för att gå till botten med detta och genomföra en liten studie: hur "partiska" eller förutsägbara RNG:er är, och vilken man bör välja. Jag har hört motstridiga åsikter om deras "ärlighet" — låt oss ta reda på hur de verkliga resultaten förhåller sig till de påstådda.

En kort introduktion eller vad är RNG egentligen?

Om du redan är bekant med slumpgeneratorer kan du gå direkt till avsnittet "Testning".

Slumptal (ST) är en sekvens av siffror som genereras genom en viss slumpmässig (kaotisk) process, en entropikälla. Det vill säga, detta är en sekvens vars element inte hänger ihop med något matematiskt lag — de saknar ett orsakssamband.

Det som skapar ST kallas en slumptalsgenerator (RNG). Det verkar enkelt, men övergången från teori till praktik gör det faktiskt inte så lätt att implementera en algoritm för att generera en sådan sekvens.

Anledningen ligger i avsaknaden av den där kaotiska egenskapen i modern konsumelektronik. Utan den slutar slumptal att vara slumpmässiga och deras generator blir en vanlig funktion av kända argument. För en rad specialiteter inom IT-området är detta ett allvarligt problem (till exempel för kryptografi), medan det för andra finns fullt acceptabla lösningar.

Det behövs en algoritm som skulle returnera, om än inte verkligt slumpmässiga tal, så nära dem som möjligt — de så kallade pseudorandom-talen (PST). Algoritmen kallas i detta fall för en pseudorandom-talsgenerator (PRNG).

Det finns flera alternativ för att skapa en PRNG, men för alla är följande relevant:

1. Behovet av föregående initiering.

   En randomiseringskommitté (GPC) saknar en källa till entropi, så innan den används måste den ange ett initialt tillstånd. Detta anges som ett nummer (eller en vektor) och kallas för ett frö (seed, random seed). Ofta används en räknare för klockcykler eller det numeriska ekvivalenten för systemtiden som seed.

2. Återproducerbarheten av sekvensen.

   GPC är helt deterministisk, så det seed som anges vid initialisering entydigt bestämmer hela den framtida sekvensen av tal. Det betyder att en enskild GPC, initialiserad med samma seed (vid olika tidpunkter, i olika program, på olika enheter) kommer att generera samma sekvens.

Det är också viktigt att känna till den sannolikhetsfördelning som GPC representerar – vilka siffror den kommer att generera och med vilken sannolikhet. Oftast är det antingen en normalfördelning (normal distribution) eller en uniform fördelning (uniform distribution).

Normalfördelning (till vänster) och uniform fördelning (till höger)

Anta att vi har en rättvis tärning med 24 sidor. Om vi kastar den kommer sannolikheten att ettan kommer att rulla att vara 1/24 (på samma sätt är sannolikheten för varje annat nummer densamma). Om vi gör många kast och registrerar resultaten, kan vi se att alla sidor dyker upp med ungefär samma frekvens. I grund och botten kan denna tärning betraktas som en GPC med uniform fördelning.

Men vad händer om vi kastar 10 sådana tärningar och räknar den totala summan av poängen? Kommer den att behålla sin uniformitet? Nej. Oftast kommer summan att ligga nära 125 poäng, det vill säga nära ett visst medelvärde. Och som en följd kan vi, även innan kastet, ungefär uppskatta det framtida resultatet.

Anledningen är att det finns flest kombinationer för att få det genomsnittliga poängsumman. Ju längre bort från det, desto färre kombinationer – och därmed mindre sannolikhet för att det inträffar. Om dessa data visualiseras kan de på avstånd likna formen av en klocka. Därför kan man med viss överdrift kalla systemet av 10 tärningar för en GPC med normal fördelning.

Ett annat exempel, men denna gång i plan – skytte mot en måltavla. Skyttarens GPC kommer att generera ett par nummer (x, y), som representeras på grafen.

Håller du med om att alternativet till vänster är mer nära verkligheten — det är en slumptalsgenerator med normalfördelning. Men om du behöver sprida stjärnor på den mörka himlen, passar det högra alternativet, som erhållits med hjälp av en slumptalsgenerator med uniform fördelning, bättre. I allmänhet, välj generator beroende på den uppgift som ska lösas.

Nu ska vi prata om entropin i sekvensen av slumptal. Till exempel, det finns en sekvens som börjar så här:

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

Hur slumpmässiga är dessa siffror vid första ögonkastet? Låt oss börja med att kontrollera fördelningen.

Det ser nästan ut som en jämn fördelning, men om man läser sekvensen i par av två siffror och tolkar dem som koordinater på ett plan, får man detta:

Mönstren blir tydligt synliga. Eftersom datan i sekvensen är ordnad på ett visst sätt (det vill säga har låg entropi) kan detta skapa den så kallade "partiskheten". Åtminstone passar en sådan slumptalsgenerator inte bra för att generera koordinater på ett plan.

En annan sekvens:

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

Det verkar som att allt är bra här även på planet:

Låt oss titta på volymen (läser tre siffror):

Och återigen mönster. Det går inte att skapa en visualisering i fyra dimensioner. Men mönster kan existera även i denna dimension och större.

I samma kryptografi, där hårda krav ställs på slumptalsgeneratorer, är en sådan situation kategoriskt oacceptabel. Därför har speciella algoritmer utvecklats för att bedöma deras kvalitet, som vi inte kommer att beröra just nu. Ämnet är omfattande och skulle kunna fylla en egen artikel.

Testning

Om vi inte vet något med säkerhet, hur ska vi då hantera det? Ska vi korsa vägen om vi inte vet vilket trafikljus som tillåter det? Konsekvenserna kan vara olika.

Samma gäller den ökända slumpen i Unity. Det är bra om dokumentationen avslöjar nödvändiga detaljer, men historien som nämndes i början av artikeln inträffade just på grund av bristen på önskad specifik information.

Utan att veta hur verktyget fungerar kan du inte tillämpa det korrekt. Det är dags att kontrollera och göra ett experiment för att slutgiltigt försäkra dig om åtminstone fördelningen.

Lösningen var enkel och effektiv — samla statistik, få objektiva data och titta på resultaten.

Forskningens ämne

I Unity finns det flera sätt att generera slumpmässiga tal — vi testade fem.

1. System.Random.Next(). Genererar heltal (integer) inom ett angivet värdeintervall.
2. System.Random.NextDouble(). Genererar dubbeld precision (double) inom intervallet [0; 1).
3. UnityEngine.Random.Range(). Genererar enkel precision (float) inom ett angivet värdeintervall.
4. UnityEngine.Random.value. Genererar enkel precision (float) inom intervallet [0; 1).
5. Unity.Mathematics.Random.NextFloat(). Del av det nya biblioteket Unity.Mathematics. Genererar enkel precision (float) inom ett angivet värdeintervall.

Nästan överallt i dokumentationen angavs en jämn fördelning, förutom UnityEngine.Random.value (där distributionen inte angavs, men i enlighet med UnityEngine.Random.Range() förväntades en jämn fördelning) och Unity.Mathematics.Random.NextFloat() (där grunden är xorshift-algoritmen, så vi behöver återigen vänta på en jämn fördelning).

Som förväntade resultat togs de som angavs i dokumentationen.

Metodologi

Vi skrev en liten applikation som genererade sekvenser av slumpmässiga tal med varje av de presenterade metoderna och sparade resultaten för vidare bearbetning.

Längden på varje sekvens är 100 000 tal.
Värdeintervall för de slumpmässiga talen — [0, 100).

Data samlades in från flera målplattformar:

• Windows
  — Unity v2018.3.14f1, Editor-läge, Mono, .NET Standard 2.0
• macOS
  — Unity v2018.3.14f1, Editor-läge, Mono, .NET Standard 2.0
  — Unity v5.6.4p4, Editor-läge, Mono, .NET Standard 2.0
• Android
  — Unity v2018.3.14f1, byggd för enhet, Mono, .NET Standard 2.0
• iOS
  — Unity v2018.3.14f1, byggd för enhet, il2cpp, .NET Standard 2.0

Implementering

Vi har flera olika sätt att generera slumpmässiga tal. För var och en av dem kommer vi att skriva en separat wrapper-klass som ska tillhandahålla:

1. Möjlighet att ange värdeintervall [min/max). Det kommer att anges genom konstruktorn.
2. Metod som returnerar RNG. Vi väljer float som typ, eftersom det är mer allmänt.
3. Genereringsmetoden för att märka resultat. För bekvämlighetens skull kommer vi att returnera det fullständiga klassnamnet + metodenamnet som används för att generera SČ.

Vi börjar med att deklarera en abstraktion som representeras av gränssnittet IRandomGenerator:

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

        float Generate();
    }
}

Implementering av System.Random.Next()

Denna metod tillåter att ange ett värdeintervall, men den returnerar heltal (integer), medan vi behöver float. Vi kan helt enkelt tolka integer som float, eller så kan vi utöka värdeintervallet med flera ordningar, vilket kompenserar för dem vid varje SČ-generering. Det kommer att bli något som liknar fixed-point med angiven ordning av noggrannhet. Vi kommer att använda denna variant, eftersom den är närmare det verkliga float-värdet.

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

Implementering av System.Random.NextDouble()

Här är det ett fast värdeintervall [0; 1). För att projicera det på det angivna i konstruktorn använder vi enkel aritmetik: 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;
    }
}

Implementering av UnityEngine.Random.Range()

Denna metod i den statiska klassen UnityEngine.Random tillåter att ange ett värdeintervall och returnerar SČ av typen float. Inga ytterligare konverteringar behöver göras.

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

Implementering av UnityEngine.Random.value

Egenskapen value av den statiska klassen UnityEngine.Random returnerar ett slumpmässigt tal av typen float från ett fast intervall av värden [0; 1). Vi projicerar det på det angivna intervallet på samma sätt som vid implementeringen av 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;
    }
}

Implementation av Unity.Mathematics.Random.NextFloat()

Metoden NextFloat() i klassen Unity.Mathematics.Random returnerar ett slumpmässigt tal av typen float och tillåter att ange ett intervall av värden. Det viktiga är att varje instans av Unity.Mathematics.Random måste initieras med ett seed — så undviker vi att generera upprepade sekvenser.

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

Implementation av MainController

Flera implementationer av IRandomGenerator är klara. Nästa steg är att generera sekvenser och spara den resulterande datasetet för bearbetning. För detta skapar vi en scen i Unity och ett litet skript MainController som kommer att utföra allt nödvändigt arbete och också ansvara för interaktionen med UI.

Vi definierar storleken på datasetet och intervallet av slumpmässiga tal, samt skaffar en metod som returnerar en array av inställda och klara generatorer.

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

        ...
    }
}

Nu skapar vi datasetet. I det här fallet kommer datagenereringen att kombineras med att skriva resultaten till en textström (i csv-format). För lagring av värdena för varje IRandomGenerator avsätts en egen kolumn, och den första raden innehåller generatorns namn.

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

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

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

        ...
    }
}

Det återstår att kalla på metoden GenerateCsvDataSet och spara resultatet i en fil, eller direkt överföra data från den slutliga enheten till mottagaren. 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();
            }
        }

        ...
    }
}

Projektets källfiler finns på GitLab.

Resultat

Det blev inget mirakel. Vad vi förväntade oss, det fick vi — i alla fall en jämn fördelning utan antydan till sammansvärjningar. Jag ser ingen mening med att bifoga individuella grafer från plattformarna — de visar alla ungefär samma resultat.

Verkligheten är denna:


Visualisering av sekvenser på planet från alla fem metoder för generering:


Och visualisering i 3D. Jag lämnar bara resultatet från System.Random.Next(), för att inte skapa en massa identiskt innehåll.


Berättelsen i inledningen om normalfördelningen från UnityEngine.Random upprepades inte: antingen var den ursprungligen felaktig, eller så har något förändrats i motorn sedan dess. Men nu är vi helt övertygade.

Källa: habr.com