Nel game development è spesso necessario legare qualcosa al random: per Unity esiste il suo Random, mentre parallelamente c'è System.Random. Una volta, in un progetto, ho avuto l'impressione che entrambi potessero comportarsi in modo diverso (anche se dovrebbero avere una distribuzione uniforme).
Allora non ci siamo approfonditi troppo — bastava sapere che il passaggio a System.Random ha risolto tutti i problemi. Ora abbiamo deciso di esaminare più a fondo e condurre una piccola ricerca: quanto sono "prevenuti" o prevedibili i generatori di numeri casuali e quale scegliere. Inoltre, ho sentito opinioni contrastanti sulla loro "onestà" — cerchiamo di capire come i risultati reali si confrontano con quelli dichiarati.
Breve lezione introduttiva o cos'è realmente un generatore di numeri casuali
Se sei già familiare con i generatori di numeri casuali, puoi passare direttamente alla sezione "Test".
I numeri casuali (NC) sono una sequenza di numeri generata attraverso un processo casuale (caotico) o una fonte di entropia. In altre parole, si tratta di una sequenza i cui elementi non sono collegati da alcuna legge matematica — non esiste un rapporto di causa ed effetto tra di essi.
Ciò che crea i NC è chiamato generatore di numeri casuali (GNC). Potrebbe sembrare tutto semplice, ma passare dalla teoria alla pratica rende in realtà difficile l’implementazione di un algoritmo software per generare tale sequenza.
La ragione risiede nell'assenza di quella stessa caoticità nell'elettronica di consumo moderna. Senza di essa, i numeri casuali cessano di essere tali e il loro generatore si trasforma in una semplice funzione di argomenti predefiniti. Per alcune specializzazioni nel campo IT, questo rappresenta un serio problema (ad esempio, per la crittografia), mentre per altri rappresenta una soluzione accettabile.
È necessario scrivere un algoritmo che restituisca, sebbene non numeri veramente casuali, quelli che vi si avvicinano il più possibile: i cosiddetti numeri pseudocasuali (PSZ). In questo caso, l'algoritmo è chiamato generatore di numeri pseudocasuali (GNPZ).
Esistono diverse modalità per creare un GNPZ, ma per tutti sarà rilevante quanto segue:
- La necessità di un'inizializzazione preliminare.
Il GNPZ è privo di una sorgente di entropia, quindi prima di essere utilizzato è necessario specificare uno stato iniziale. Questo è definito come un numero (o un vettore) e viene chiamato seme (seed, random seed). Spesso si utilizza un contatore di cicli del processore o l'equivalente numerico del tempo di sistema come seed.
- Riproducibilità della sequenza.
Il GNPZ è completamente deterministico, quindi il seed fornito durante l'inizializzazione determina univocamente l'intera futura sequenza di numeri. Ciò significa che uno specifico GNPZ, inizializzato con lo stesso seed (in tempi diversi, in programmi diversi, su dispositivi diversi) genererà la stessa sequenza.
È importante conoscere la distribuzione delle probabilità associate ai numeri generati da un generatore di numeri casuali (GPC). Di solito, si tratta di una distribuzione normale oppure di una distribuzione uniforme.
Distribuzione normale (a sinistra) e distribuzione uniforme (a destra)
Immaginiamo di avere un dado regolare a 24 facce. Se lo lanciamo, la probabilità di ottenere un uno è di 1/24 (così come per ogni altro numero). Se eseguiamo molti lanci e registriamo i risultati, noteremo che tutte le facce escono con una frequenza simile. In sostanza, questo dado può essere considerato un GPC con distribuzione uniforme.
E se lanciassimo subito 10 dadi e sommassimo i punteggi? La distribuzione rimarrebbe uniforme? No. Di solito, la somma si avvicina a 125 punti, cioè a un certo valore medio. Di conseguenza, è possibile stimare il risultato futuro anche prima di effettuare il lancio.
La ragione è che per ottenere la somma media dei punti esiste il numero maggiore di combinazioni. Più ci allontaniamo, meno combinazioni ci sono, e di conseguenza, minore è la probabilità di ottenere quel risultato. Se queste informazioni vengono visualizzate, assomiglieranno vagamente alla forma di un campana. Pertanto, con un certo sforzo, si può definire il sistema di 10 dadi come un generatore casuale con distribuzione normale.
Un altro esempio, ma questa volta in piano — il tiro al bersaglio. Il generatore casuale sarà colui che genera una coppia di numeri (x, y), che viene poi visualizzata su un grafico.
Concordate che la versione a sinistra è più vicina alla vita reale — si tratta di un generatore casuale con distribuzione normale. Ma se è necessario spargere stelle nel cielo scuro, allora la versione a destra, ottenuta tramite generatore casuale con distribuzione uniforme, sarà la più adatta. In generale, scegliete il generatore in base al compito da svolgere.
Ora parliamo dell'entropia della sequenza dei numeri casuali. Ad esempio, c'è una sequenza che inizia così:
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, …
Quanto sono casuali questi numeri a prima vista? Iniziamo a controllare la distribuzione.
Sembra quasi uniforme, ma se leggiamo la sequenza due numeri alla volta e li interpretiamo come coordinate in un piano, otteniamo questo:
Diventano chiaramente visibili dei patterns. E poiché i dati nella sequenza sono ordinati in un certo modo (cioè hanno bassa entropia), questo può generare quel tipo di "bias". Almeno, un tale RNG non è molto adatto per generare coordinate in un piano.
Un'altra sequenza:
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, …
Sembra che qui tutto vada bene anche nel piano:
Esaminiamo in volume (leggiamo tre numeri alla volta):
E ancora patterns. Costruire una visualizzazione in quattro dimensioni non sarà possibile. Ma i patterns possono esistere anche in questa dimensione e in dimensioni maggiori.
Nella stessa crittografia in cui vengono posti i requisiti più rigorosi ai PRNG, una tale situazione è categoricamente inaccettabile. Pertanto, sono stati sviluppati algoritmi speciali per valutarne la qualità, di cui non discuteremo ora. L'argomento è ampio e merita un articolo a sé.
Test
Se non sappiamo qualcosa con certezza, come possiamo lavorarci? Ha senso attraversare la strada se non conosci il segnale del semaforo che lo permette? Le conseguenze possono essere diverse.
Lo stesso vale per il famigerato random in Unity. È positivo se la documentazione rivela i dettagli necessari, ma la storia menzionata all'inizio dell'articolo è accaduta proprio a causa della mancanza di concretezza auspicata.
E non conoscendo come funziona lo strumento, non sarà possibile applicarlo correttamente. In generale, è tempo di verificare e condurre un esperimento per assicurarsi, almeno riguardo alla distribuzione.
La soluzione è stata semplice ed efficace: raccogliere statistiche, ottenere dati oggettivi e osservare i risultati.
Oggetto di studio
In Unity ci sono diversi modi per generare numeri casuali: ne abbiamo testati cinque.
- System.Random.Next(). Genera numeri interi (integer) nell'intervallo specificato di valori.
- System.Random.NextDouble(). Genera numeri a precisione doppia (double) nell'intervallo da [0; 1).
- UnityEngine.Random.Range(). Genera numeri a precisione singola (float) nell'intervallo specificato di valori.
- UnityEngine.Random.value. Genera numeri a precisione singola (float) nell'intervallo da [0; 1).
- Unity.Mathematics.Random.NextFloat(). Parte della nuova libreria Unity.Mathematics. Genera numeri a precisione singola (float) nell'intervallo specificato di valori.
Praticamente ovunque nella documentazione è stato indicato che si tratta di una distribuzione uniforme, ad eccezione di UnityEngine.Random.value (dove la distribuzione non è specificata, ma per analogia con UnityEngine.Random.Range() ci si aspettava comunque una distribuzione uniforme) e Unity.Mathematics.Random.NextFloat() (dove si basa su un algoritmo xorshift, e quindi si deve nuovamente attendere una distribuzione uniforme).
Come risultati attesi sono stati presi in considerazione quelli specificati nella documentazione.
Metodologia
Abbiamo scritto una piccola applicazione che generava sequenze di numeri casuali usando ciascuno dei metodi presentati e salvava i risultati per ulteriori elaborazioni.
La lunghezza di ciascuna sequenza è di 100.000 numeri.
L'intervallo di valori dei numeri casuali è [0, 100).
I dati sono stati raccolti da diverse piattaforme di destinazione:
- Windows
— Unity v2018.3.14f1, modalità Editor, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, modalità Editor, Mono, .NET Standard 2.0
— Unity v5.6.4p4, modalità Editor, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, build su dispositivo, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, build su dispositivo, il2cpp, .NET Standard 2.0
Implementazione
Abbiamo diversi metodi per generare numeri casuali. Per ognuno di essi scriveremo una classe wrapper separata, che dovrà fornire:
- La possibilità di impostare un intervallo di valori [min/max). Sarà definito tramite il costruttore.
- Un metodo che restituisce un numero casuale. Sceglieremo float come tipo, essendo più generico.
- Il nome del metodo di generazione per etichettare i risultati. Per comodità, restituiremo il nome completo della classe + il nome del metodo utilizzato per generare il numero casuale.
Iniziamo a dichiarare un’astrazione, che sarà rappresentata dall’interfaccia IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementazione di System.Random.Next()
Questo metodo consente di definire un intervallo di valori, ma restituisce numeri interi (integer) quando servirebbero float. È possibile interpretare semplicemente integer come float, oppure ampliare l'intervallo di valori di alcuni ordini di grandezza, compensandoli ad ogni generazione di numeri casuali. Otterremo qualcosa di simile a un fixed-point con una precisione stabilita. Utilizzeremo questa opzione, poiché è più vicino al valore float reale.
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;
}
}Implementazione di System.Random.NextDouble()
Qui c'è un intervallo fisso di valori [0; 1). Per proiettarlo sull'intervallo specificato nel costruttore, utilizziamo una semplice aritmetica: 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;
}
}Implementazione di UnityEngine.Random.Range()
Questo metodo della classe statica UnityEngine.Random consente di definire un intervallo di valori e restituisce un numero casuale di tipo float. Non è necessario effettuare ulteriori conversioni.
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);
}
}Implementazione di UnityEngine.Random.value
La proprietà value della classe statica UnityEngine.Random restituisce un numero casuale di tipo float da un intervallo fisso di valori [0; 1). Proiettiamolo nell'intervallo specificato nello stesso modo in cui abbiamo implementato 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;
}
}Implementazione di Unity.Mathematics.Random.NextFloat()
Il metodo NextFloat() della classe Unity.Mathematics.Random restituisce un valore float e consente di impostare un intervallo di valori. L'unico accorgimento è che ogni istanza di Unity.Mathematics.Random deve essere inizializzata con un seme, in modo da evitare la generazione di sequenze ripetute.
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);
}
}Implementazione di MainController
Diverse implementazioni di IRandomGenerator sono pronte. Ora dobbiamo generare sequenze e salvare il dataset risultante per l'elaborazione. A tal fine, creeremo una scena in Unity e un piccolo script MainController, che si occuperà di tutta la necessaria operazione e gestirà anche l'interazione con l'UI.
Imposteremo la dimensione del dataset e l'intervallo dei valori casuali, e ci doteremo di un metodo che restituisce un array di generatori configurati e pronti all'uso.
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)
};
}
...
}
}Ora formiamo il dataset. In questo caso, la generazione dei dati sarà combinata con la registrazione dei risultati in un flusso di testo (in formato csv). Per memorizzare i valori di ciascun IRandomGenerator viene riservata una colonna separata, mentre la prima riga contiene il nome del generatore.
namespace RandomDistribution
{
public class MainController : MonoBehaviour
{
...
private void GenerateCsvDataSet(TextWriter writer, int dataSetSize, params IRandomGenerator[] generators)
{
const char separator = ',';
int lastIdx = generators.Length - 1;
// scrivere intestazione
for (int j = 0; j <= lastIdx; j++)
{
writer.Write(generators[j].Name);
if (j != lastIdx)
writer.Write(separator);
}
writer.WriteLine();
// scrivere dati
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();
}
}
...
}
}È rimasto da chiamare il metodo GenerateCsvDataSet e salvare il risultato in un file, oppure trasferire i dati direttamente attraverso la rete dal dispositivo finale a quello ricevente. un 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();
}
}
...
}
}I sorgenti del progetto si trovano su .
Risultati
Non è successo nulla di straordinario. Abbiamo ottenuto esattamente ciò che ci aspettavamo: in tutti i casi una distribuzione uniforme senza alcun accenno di cospirazione. Non ha senso allegare grafici specifici per piattaforme: mostrano tutti risultati simili.
La realtà è questa:
Visualizzazione delle sequenze su un piano da tutti e cinque i metodi di generazione:
E visualizzazione in 3D. Mostrerò solo il risultato di System.Random.Next() per evitare di creare contenuti ripetitivi.
La storia raccontata nell'introduzione riguardo la distribuzione normale di UnityEngine.Random non si è ripetuta: o era errata fin dall'inizio, oppure qualcosa è cambiato da allora nel motore. Tuttavia, ora siamo certi.
Fonte: habr.com
