I spiludvikling er det ofte nødvendigt at binde noget til tilfældigheder: i Unity har de deres egen Random, men der findes også System.Random. Engang på et projekt fik jeg indtrykket af, at de to kunne arbejde forskelligt (selvom de burde have en ensartet fordeling).
Vi gik ikke i dybden dengang — det var nok at vi fjernede problemerne ved at skifte til System.Random. Nu har vi besluttet at undersøge det nærmere og lave en lille undersøgelse: hvor "partiske" eller forudsigelige er tilfældighedsgeneratorer, og hvilken skal man vælge. Desuden har jeg hørt modstridende meninger om deres "retfærdighed" — lad os finde ud af, hvordan de faktiske resultater forholder sig til de angivne.
Kort introduktion eller Hvad er GRT virkelig?
Hvis du allerede kender til tilfældighedsgeneratorer, kan du gå direkte til sektionen "Testning".
Tilfældige tal (ST) er en sekvens af tal, der genereres ved hjælp af en eller anden tilfældig (kaotisk) proces, en kilde til entropi. Det vil sige, at det er en sekvens, hvis elementer ikke er relateret til hinanden gennem nogen matematisk regel — de mangler en årsags- og virkningsforbindelse.
Det, der skaber ST, kaldes en tilfældighedsgenerator (GR). Det virker måske simpelt, men når man går fra teori til praksis, er det faktisk ikke så let at implementere en softwarealgoritme til at generere en sådan sekvens.
Årsagen ligger i manglen på den samme kaotiskhed i moderne forbrugerelektronik. Uden den stopper tilfældige tal med at være tilfældige, og deres generator bliver blot en almindelig funktion af givet bestemte argumenter. For mange specialiteter inden for IT er dette et alvorligt problem (for eksempel inden for kryptografi), mens der for de andre findes fuldt acceptable løsninger.
Det er nødvendigt at skrive en algoritme, der vil returnere, selvom det ikke er ægte tilfældige tal, så tæt på dem som muligt — de såkaldte pseudotilfældige tal (PST). Algoritmen kaldes i dette tilfælde en generator af pseudotilfældige tal (GPT).
Der er flere metoder til at skabe GPT, men for alle vil følgende være relevant:
- Behovet for forudgående initialisering.
En random generator er uden en kilde til entropi, så før brug skal den angives en initial tilstand. Det angives som et tal (eller en vektor) og kaldes for frøet (seed, random seed). Ofte anvendes en tæller fra CPU'en eller det numeriske ækvivalent af systemtiden som seed.
- Reproducerbarheden af sekvensen.
En random generator er fuldstændig deterministisk, så frøet, der er angivet ved initialisering, bestemmer entydigt hele den fremtidige sekvens af tal. Det betyder, at en given random generator, der er initialiseret med det samme frø (på forskellige tidspunkter, i forskellige programmer, på forskellige enheder) vil generere den samme sekvens.
Man skal også vide, hvilken sandsynlighedsfordeling der karakteriserer random generatoren - hvilke tal den vil generere og med hvilken sandsynlighed. Ofte er dette enten en normalfordeling eller en uniform fordeling.
Normalfordeling (til venstre) og uniform fordeling (til højre)
Lad os sige, at vi har en ærlig terning med 24 ansigtter. Hvis vi kaster den, vil sandsynligheden for at få én være 1/24 (samme som sandsynligheden for at få et hvilket som helst andet tal). Hvis vi udfører mange kast og registrerer resultaterne, vil vi bemærke, at alle ansigtter kommer ud omtrent med den samme frekvens. I bund og grund kan denne terning betragtes som en tilfældig generator med en uniform fordeling.
Og hvad hvis vi kaster 10 sådanne terninger og tæller den samlede score? Vil der stadig være uniformitet? Nej. Ofte vil summen være tæt på 125 point, det vil sige et vis gennemsnitligt værdi. Og som følge heraf kan man allerede før kastet omtrent vurdere det fremtidige resultat.
Årsagen er, at der for at opnå den gennemsnitlige sum af point findes det største antal kombinationer. Jo længere væk fra den, jo færre kombinationer - og dermed, mindre sandsynlighed for at det sker. Hvis disse data visualiseres, vil de på en afstand minde om formen på en klokke. Derfor kan et system med 10 terninger med nogen retfærdighed kaldes en tilfældig generator med en normal fordeling.
Et andet eksempel, men nu i et plan - at sigte på en skive. Skytteren vil være en tilfældig generator, der genererer et par tal (x, y), som vises på en graf.
Enig, at venstre variant er mere tæt på virkeligheden — det er en PRNG med normal fordeling. Men hvis du skal sprede stjernerne på den mørke himmel, så passer den højre variant, opnået med en PRNG med ensartet fordeling, bedre. Generelt skal du vælge generator ud fra den opgave, du står overfor.
Lad os nu tale om entropien i sekvensen af PRNG. For eksempel er der en sekvens, der starter sådan her:
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, …
Hvor tilfældige ser disse tal ud ved første øjekast? Lad os starte med at tjekke fordelingen.
Ser ud til at være tæt på ensartet, men hvis vi læser sekvensen to tal ad gangen og fortolker dem som koordinater på et plan, får vi dette:
Mønstrene bliver tydeligt synlige. Og da dataene i sekvensen er ordnet på en bestemt måde (det vil sige har lav entropi), kan dette skabe den omtalte "bias". Som minimum er denne PRNG ikke særlig velegnet til at generere koordinater på et plan.
En anden 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 ser faktisk godt ud selv på planet:
Lad os se i 3D (læser tre tal ad gangen):
Og igen mønstre. At bygge en visualisering i fire dimensioner er allerede ikke muligt. Men mønstre kan eksistere i denne dimension og større.
I den samme kryptografi, hvor der stilles hårde krav til PRNG, er en sådan situation kategorisk uacceptabel. Derfor er der udviklet specielle algoritmer til at vurdere deres kvalitet, som vi ikke vil berøre nu. Emnet er omfattende og fortjener en egen artikel.
Testning
Hvordan håndterer man noget, vi ikke ved med sikkerhed? Skal man krydse vejen, hvis man ikke ved, hvilket trafiklys der tillader det? Konsekvenserne kan være forskellige.
Det samme gælder den berygtede tilfældighed i Unity. Det er godt, hvis dokumentationen afslører de nødvendige detaljer, men den historie, der er nævnt i starten af artiklen, skete netop på grund af mangel på den ønskede konkrethed.
Uden at vide, hvordan værktøjet fungerer, kan du ikke anvende det korrekt. Generelt er det tid til at teste og udføre eksperimentet for endelig at bekræfte, i det mindste hvad angår fordelingen.
Løsningen var simpel og effektiv – indsamle statistik, få objektive data og se på resultaterne.
Emnet for undersøgelsen
I Unity findes der flere metoder til at generere tilfældige tal – vi har testet fem.
- System.Random.Next(). Genererer heltal (integer) i et givet interval.
- System.Random.NextDouble(). Genererer dobbeltpræcisions tal (double) i intervallet [0; 1).
- UnityEngine.Random.Range(). Genererer enkeltpræcisions tal (float) i et givet interval.
- UnityEngine.Random.value. Genererer enkeltpræcisions tal (float) i intervallet [0; 1).
- Unity.Mathematics.Random.NextFloat(). En del af det nye bibliotek Unity.Mathematics. Genererer enkeltpræcisions tal (float) i et givet interval.
Næsten overalt i dokumentationen blev der angivet en ensartet fordeling, med undtagelse af UnityEngine.Random.value (hvor fordelingen ikke var angivet, men efter analogi med UnityEngine.Random.Range() forventedes også ensartet) og Unity.Mathematics.Random.NextFloat() (hvor algoritmen xorshift ligger til grund, så man må vente på en ensartet fordeling igen).
Som standard blev de forventede resultater taget fra dem, der er angivet i dokumentationen.
Metodologi
Vi har skrevet en lille applikation, der genererede sekvenser af tilfældige tal med hver af de præsenterede metoder og gemte resultaterne til videre behandling.
Længden af hver sekvens er 100.000 tal.
Intervallet for de tilfældige tal er [0, 100).
Dataene blev indsamlet fra flere målplatforme:
- Windows
— Unity v2018.3.14f1, Editor mode, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, Editor mode, Mono, .NET Standard 2.0
— Unity v5.6.4p4, Editor mode, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, bygning til enhed, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, bygning til enhed, il2cpp, .NET Standard 2.0
Implementering
Vi har flere forskellige måder at generere tilfældige tal på. For hver af dem vil vi skrive en separat wrapper-klasse, der skal give:
- Mulighed for at angive intervallet for værdier [min/max). Det vil blive angivet gennem konstruktøren.
- En metode, der returnerer tilfældige tal. Vi vælger at bruge float som datatype, da det er mere generelt.
- Navnet på metoden til at generere tal til mærkning af resultaterne. For brugervenlighed vil vi returnere det fulde navn på klassen + navnet på metoden, der bruges til at generere tilfældige tal.
Lad os først erklære en abstraktion, der vil blive repræsenteret af interfacet IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementering af System.Random.Next()
Denne metode giver mulighed for at definere et interval af værdier, men den returnerer heltal (integer), mens vi har brug for float. Man kan simpelthen fortolke integer som float, eller man kan udvide det numeriske interval i flere rækkefølger og kompensere for disse ved hver generation af tilfældige tal. Det vil blive noget, der ligner faste punkter med en specificeret præcision. Vi vil bruge denne mulighed, da den er tættere på det faktiske float-værdi.
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 af System.Random.NextDouble()
Her er det faste interval af værdier [0; 1). For at projicere det til det angivne i konstruktøren, bruger vi simpel 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 af UnityEngine.Random.Range()
Denne metode fra den statiske klasse UnityEngine.Random gør det muligt at definere et interval af værdier og returnerer tilfældige tal af typen float. Der er ikke behov for yderligere transformationer.
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 af UnityEngine.Random.value
Egenskaben value fra den statiske klasse UnityEngine.Random returnerer et tilfældigt tal af typen float fra det faste interval [0; 1). Vi projicerer det til det angivne interval på samme måde som ved implementeringen af 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;
}
}Implementering af Unity.Mathematics.Random.NextFloat()
Metoden NextFloat() i klassen Unity.Mathematics.Random returnerer en float-værdi og giver mulighed for at angive et værd interval. Det er vigtigt at bemærke, at hver instans af Unity.Mathematics.Random skal initialiseres med et bestemt seed - på den måde undgår vi at generere gentagne 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);
}
}Implementering af MainController
Flere implementeringer af IRandomGenerator er klar. Næste skridt er at generere sekvenser og gemme den resulterende datasæt til behandling. For dette formål opretter vi en scene i Unity og et lille script MainController, som vil håndtere alt det nødvendige arbejde og samtidig stå for interaktionen med UI.
Vi angiver størrelsen på datasættet og intervallet for float-værdierne samt tilføjer en metode, der returnerer et array af konfigurerede og klar-til-brug 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)
};
}
...
}
}Og nu danner vi datasættet. I dette tilfælde vil datagenereringen blive kombineret med skrivning af resultater til en tekststream (i csv-format). Hver IRandomGenerator får sin egen kolonne, og den første række indeholder generatorens navn.
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();
}
}
...
}
}Nu skal metoden GenerateCsvDataSet kaldes, og resultatet gemmes i en fil, eller dataene skal straks sendes over netværket fra den afsendende enhed til modtageren. 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();
}
}
...
}
}Kildemateriale til projektet ligger på .
Resultater
Der skete ikke noget mirakuløst. Hvad vi forventede, er hvad vi fik — i alle tilfælde en jævn fordeling uden antydninger af konspirationer. Jeg synes ikke, det giver mening at vedlægge separate grafer for platformene — de viser omtrent de samme resultater.
Realiteten er sådan:
Visualisering af sekvenser på planen fra alle fem genereringsmetoder:
Og visualisering i 3D. Jeg lader kun resultatet fra System.Random.Next() være tilbage for ikke at producere en masse identisk indhold.
Historien fortalt i indledningen om normalfordelingen af UnityEngine.Random gentog sig ikke: enten var den oprindeligt fejlagtig, eller også er der sket ændringer i motoren siden da. Men nu er vi sikre.
Kilde: habr.com
