In game development, there's often a need to tie something to randomness: Unity has its own Random for this, while System.Random exists alongside it. Long ago, in one of the projects, it was thought that both could behave differently (even though they should have a uniform distribution).
At that time, we didn't delve into the details ā it was sufficient that switching to System.Random fixed all the problems. Now we've decided to investigate further and conduct a small study: how 'biased' or predictable are random number generators, and which one to choose. Moreover, I've heard conflicting opinions about their 'fairness' ā let's try to understand how real results relate to those claimed.
A brief introduction or what random number generators really are.
If you are already familiar with random number generators, you can directly go to the 'Testing' section.
Random numbers (RNs) are a sequence of numbers generated by some random (chaotic) process, an entropy source. This means it's a sequence where the elements are not connected by any mathematical law ā they lack a causal relationship.
What creates random numbers is called a random number generator (RNG). It seems straightforward, but when transitioning from theory to practice, implementing a software algorithm to generate such a sequence is not that simple.
The reason lies in the lack of true chaos in modern consumer electronics. Without it, random numbers cease to be random, and their generator turns into a mere function of predetermined arguments. For a range of IT fields, this poses a significant problem (for instance, in cryptography), while for others, there are acceptable solutions.
An algorithm needs to be written that returns numbers that may not be truly random but are as close to them as possible ā the so-called pseudorandom numbers (PRNs). In this case, the algorithm is referred to as a pseudorandom number generator (PRNG).
There are several options for creating PRNGs, but the following will be relevant for all of them:
- The need for preliminary initialization.
Een pseudo-random number generator (PRNG) mist een entropiebron, dus voordat deze kan worden gebruikt, moet een initiƫle toestand worden opgegeven. Dit gebeurt in de vorm van een getal (of een vector) en wordt een zaadje (seed, random seed) genoemd. Vaak wordt een klokcyclus of het numerieke equivalent van de systeemtijd als zaadje gebruikt.
- Reproduceerbaarheid van de reeks.
Een PRNG is volledig deterministisch, wat betekent dat het opgegeven zaadje bij initiatie de gehele toekomstige reeks getallen uniek bepaalt. Dit betekent dat een afzonderlijke PRNG die met hetzelfde zaadje (op verschillende tijden, in verschillende programma's, op verschillende apparaten) is geĆÆnitialiseerd, altijd dezelfde reeks getallen zal genereren.
Daarnaast moet men weten welk waarschijnlijkheidsverdeling de PRNG heeft ā welke getallen het zal genereren en met welke waarschijnlijkheid. Meestal is dit of een normale verdeling (normal distribution) of een uniforme verdeling (uniform distribution).
Normale verdeling (links) en uniforme verdeling (rechts)
Stel dat we een eerlijke dobbelsteen met 24 vlakken hebben. Als we deze gooien, is de kans op het krijgen van een Ć©Ć©n gelijk aan 1/24 (net als de kans op het krijgen van elk ander getal). Als we veel gooien en de resultaten bijhouden, zien we dat alle vlakken ongeveer met dezelfde frequentie verschijnen. In feite kan deze dobbelsteen worden beschouwd als een PRNG met een uniforme verdeling.
En wat als we meteen 10 van zulke dobbelstenen gooien en de totale score tellen? Blijft de uniformiteit dan behouden? Nee. Meestal zal de som dichtbij de 125 punten zijn, dat wil zeggen, een gemiddeld waarde. En als gevolg hiervan kan men de toekomstige uitkomst zelfs vĆ³Ć³r de worp ruwweg inschatten.
De reden hiervoor is dat er voor het verkrijgen van de gemiddelde score het grootste aantal combinaties bestaat. Hoe verder men van deze gemiddelde score afwijkt, hoe minder combinaties er zijn - en dus minder kans op die uitkomst. Als men deze gegevens visualiseert, zal deze een belvormige curve benaderen. Daarom kan het systeem van 10 dobbelstenen met enige moeite worden aangeduid als een PRNG met een normale verdeling.
Een ander voorbeeld, alleen nu in een vlak ā schieten op een doel. De schutter zou een PRNG zijn die een paar getallen (x, y) genereert, die op een grafiek worden weergegeven.
We kunnen het erover eens zijn dat de linkse optie dichter bij de werkelijkheid komt - dit is RNG met een normale verdeling. Maar als je sterren op een donkere hemel wilt verspreiden, is de rechter optie, verkregen met behulp van RNG met een uniforme verdeling, beter. Kies dus een generator afhankelijk van de taak die voor je ligt.
Laten we nu praten over de entropie van de reeks van de RNG. Bijvoorbeeld, er is een reeks die begint met:
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, ā¦
Hoe willekeurig lijken deze getallen in eerste instantie? Laten we beginnen met het controleren van de verdeling.
Het lijkt dichtbij uniform, maar als we de reeks in paren van twee lezen en deze interpreteren als coƶrdinaten op een vlak, krijg je dit:
Patronen worden duidelijk zichtbaar. Aangezien de gegevens in de reeks op een bepaalde manier zijn geordend (dat wil zeggen, ze hebben lage entropie), kan dit de bedoelde "vooringenomenheid" veroorzaken. Een dergelijke PRNG is in ieder geval niet erg geschikt voor het genereren van coƶrdinaten op een vlak.
Een andere reeks:
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, ā¦
Het lijkt erop dat hier alles goed is, zelfs op het vlak:
Laten we in de ruimte kijken (lezen we in groepen van drie getallen):
En opnieuw patronen. Een visualisatie in vier dimensies maken is al niet mogelijk. Maar patronen kunnen ook in deze dimensie en in grotere dimensies bestaan.
In de cryptografie, waar de strengste eisen aan PRNG's worden gesteld, is een dergelijke situatie categorisch onaanvaardbaar. Daarom zijn er speciale algoritmen ontwikkeld om hun kwaliteit te beoordelen, maar daar zullen we het nu niet over hebben. Dit is een uitgebreid onderwerp dat om een apart artikel vraagt.
Testen
Als we iets niet zeker weten, hoe werken we daar dan mee? Moet je de weg oversteken als je niet weet welk verkeerslicht dat toestaat? De gevolgen kunnen variƫren.
Hetzelfde geldt voor de beruchte random functie in Unity. Het is fijn als de documentatie de nodige details onthult, maar het verhaal dat in het begin van het artikel werd genoemd, gebeurde juist vanwege het ontbreken van die specifieke details.
Als je niet weet hoe het instrument werkt, kun je het niet correct toepassen. Het is tijd om een test uit te voeren en te experimenteren, om eindelijk zekerheid te krijgen over de verdeling.
De oplossing was eenvoudig en effectief: verzamel statistieken, verkrijg objectieve gegevens en bekijk de resultaten.
Onderzoeksobject
In Unity zijn er verschillende manieren om willekeurige getallen te genereren - we hebben er vijf getest.
- System.Random.Next(). Genereert gehele getallen (integer) binnen een opgegeven bereik.
- System.Random.NextDouble(). Genereert double-precisie getallen (double) in het bereik van [0; 1).
- UnityEngine.Random.Range(). Genereert enkelvoudige precisie getallen (float) binnen een opgegeven bereik.
- UnityEngine.Random.value. Genereert enkelvoudige precisie getallen (float) in het bereik van [0; 1).
- Unity.Mathematics.Random.NextFloat(). Deel van de nieuwe bibliotheek Unity.Mathematics. Genereert enkelvoudige precisie getallen (float) binnen een opgegeven bereik.
Bijna overal in de documentatie werd een uniforme verdeling vermeld, met uitzondering van UnityEngine.Random.value (waar de verdeling niet is vermeld, maar op basis van UnityEngine.Random.Range() ook een uniforme verdeling werd verwacht) en Unity.Mathematics.Random.NextFloat() (waar de xorshift-algoritme aan ten grondslag ligt, wat betekent dat we opnieuw moeten wachten op een uniforme verdeling).
Als verwachte resultaten werden die genomen welke in de documentatie zijn vermeld.
Methodiek
We hebben een kleine applicatie geschreven die reeksen willekeurige getallen genereerde met elk van de gepresenteerde methoden en de resultaten opsloeg voor verdere verwerking.
De lengte van elke reeks is 100.000 getallen.
Het bereik van willekeurige getallen is [0, 100).
De gegevens werden verzameld vanaf verschillende doelplatformen:
- 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 voor apparaat, Mono, .NET Standard 2.0 - iOS
ā Unity v2018.3.14f1, build voor apparaat, il2cpp, .NET Standard 2.0
Implementatie
We hebben verschillende manieren om willekeurige getallen te genereren. Voor elk van deze zullen we een aparte wrapperklasse schrijven, die moet bieden:
- De mogelijkheid om een bereik van waarden [min/max) in te stellen. Dit zal via de constructor worden ingesteld.
- Een methode die de RNG retourneert. We kiezen float als type, omdat het algemener is.
- De naam van de generatie methode voor het labelen van resultaten. Voor de duidelijkheid zullen we als waarde de volledige naam van de klasse + de naam van de methode die wordt gebruikt voor het genereren van de RNG retourneren.
Laten we een abstractie definiƫren die wordt weergegeven door het interface IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementatie van System.Random.Next()
Deze methode laat een bereik van waarden toe, maar retourneert gehele getallen (integer), terwijl we float nodig hebben. We kunnen integer eenvoudig als float interpreteren, of het bereik van waarden uitbreiden met enkele ordes, door ze bij elke generering van de willekeurige getallen te compenseren. Het wordt iets als fixed-point met een opgegeven nauwkeurigheid. We zullen deze variant gebruiken, omdat deze dichter bij de werkelijke float-waarde ligt.
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;
}
}Implementatie van System.Random.NextDouble()
Hier is er een vast bereik van waarden [0; 1). Om dit te projecteren naar het gespecificeerde bereik in de constructor, gebruiken we eenvoudige rekenkunde: 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;
}
}Implementatie van UnityEngine.Random.Range()
Deze methode van de statische klasse UnityEngine.Random laat een bereik van waarden toe en retourneert willekeurige getallen van het type float. Er zijn geen extra conversies nodig.
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);
}
}Implementatie van UnityEngine.Random.value
De property value van de statische klasse UnityEngine.Random retourneert een willekeurig getal van het type float uit een vast bereik van waarden [0; 1). We zullen het naar het gespecificeerde bereik projecteren op dezelfde manier als bij de implementatie van 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;
}
}Implementatie van Unity.Mathematics.Random.NextFloat()
De NextFloat() methode van de Unity.Mathematics.Random klasse retourneert een float-waarde en maakt het mogelijk om een bereik van waarden op te geven. Het enige probleem is dat elke instantie van Unity.Mathematics.Random met een bepaalde seed moet worden geĆÆnitialiseerd ā op deze manier vermijden we het genereren van herhalende reeksen.
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);
}
}Implementatie van MainController
Er zijn verschillende implementaties van IRandomGenerator klaar. Laten we eerst reeksen genereren en de resulterende dataset opslaan voor verdere verwerking. Hiervoor maken we een scĆØne in Unity en een klein script MainController dat al het benodigde werk zal uitvoeren en tevens verantwoordelijk zal zijn voor de interactie met de UI.
Laten we de grootte van de dataset en het bereik van de willekeurige getallen definiƫren, en ook een methode toevoegen die een array van geconfigureerde en operationele generatoren retourneert.
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)
};
}
...
}
}En nu vormen we de dataset. In dit geval zullen de gegevensgeneratie en het opslaan van resultaten in een tekststream (in csv-formaat) worden gecombineerd. Voor het opslaan van de waarden van elke IRandomGenerator is er een aparte kolom, en de eerste rij bevat de naam van de generator.
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();
}
}
...
}
}Het is nog nodig om de methode GenerateCsvDataSet aan te roepen en het resultaat op te slaan in een bestand, of om de gegevens direct via het netwerk van het eindapparaat naar de ontvanger te verzenden. 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();
}
}
...
}
}De projectbronnen bevinden zich op .
Resultaten
Er is geen wonder gebeurd. Wat werd verwacht, is wat we kregen - in alle gevallen een uniforme verdeling zonder enige aanwijzing voor samenzweringen. Het heeft geen zin om aparte grafieken voor de platforms bij te voegen - ze tonen allemaal ongeveer dezelfde resultaten.
De werkelijkheid is als volgt:
Visualisering van de reeksen op het vlak uit alle vijf generatiemethoden:
En de visualisering in 3D. Ik laat alleen het resultaat van System.Random.Next() zien om niet een hoop identieke inhoud te creƫren.
Het verhaal dat in de inleiding over de normale verdeling van UnityEngine.Random werd verteld, herhaalde zich niet: of het was vanaf het begin verkeerd, of er is sindsdien iets veranderd in de engine. Maar nu zijn we er zeker van.
Bron: habr.com
