Ve světě herního vývoje je často potřeba něco navázat na náhodu: pro Unity existuje jeho vlastní Random, a vedle něj ponecháváme System.Random. Před nějakou dobou, na jednom z projektů, vznikl dojem, že oba mohou fungovat odlišně (i když by měly mít rovnoměrné rozdělení).
Tehdy jsme se do detailů nezabývali — stačilo, že přechod na System.Random vyřešil všechny problémy. Nyní jsme se rozhodli podívat se na to podrobněji a provést malý výzkum: jak moc jsou „předpojaté“ nebo předvídatelné generátory náhodných čísel, a který z nich zvolit. Navíc jsem několikrát slyšel protichůdné názory na jejich „poctivost“ — pokusíme se zjistit, jak se skutečné výsledky vztahují k proklamovaným.
Stručný přehled nebo Generátory náhodných čísel jsou ve skutečnosti Generátory pseudonáhodných čísel.
Pokud už znají generátory náhodných čísel, můžete přejít rovnou do části „Testování“.
Náhodná čísla (NC) jsou sekvence čísel generovaných pomocí nějakého náhodného (chaotického) procesu, zdroje entropie. To znamená, že se jedná o takovou sekvenci, jejíž prvky nejsou navzájem spojeny žádným matematickým zákonem — chybí jim příčinná vazba.
To, co vytváří náhodná čísla, se nazývá generátor náhodných čísel (GNČ). Na první pohled se to zdá jednoduché, ale pokud přejdeme od teorie k praxi, skutečně realizovat softwarový algoritmus generování takové sekvence není tak snadné.
Důvodem je absence oné chaotičnosti v moderní spotřební elektronice. Bez ní náhodná čísla přestávají být náhodná, a jejich generátor se mění na obyčejnou funkci se známými argumenty. Pro celou řadu specializací v oblasti IT je to vážný problém (například pro kryptografii), pro ostatní však existuje zcela přijatelně řešení.
Je potřeba napsat algoritmus, který by vracel, i když ne skutečně náhodná čísla, alespoň maximálně přibližná — tzv. pseudonáhodná čísla (PNČ). Algoritmus se v tomto případě nazývá generátor pseudonáhodných čísel (GPČ).
Existuje několik možností pro vytvoření GPČ, ale pro všechny bude důležité následující:
- Potřeba předběžné inicializace.
Generátor pseudonáhodných čísel (GŠČ) nemá zdroj entropie, a proto je před jeho použitím nutné specifikovat počáteční stav. Ten se nastavuje jako číslo (nebo vektor) a nazývá se semeno (seed, random seed). Často se jako semeno používá počitadlo taktů procesoru nebo číselný ekvivalent systémového času.
- Reprodukovatelnost sekvence.
GŠČ je zcela deterministický, takže zadané semeno při inicializaci jednoznačně určuje celou budoucí sekvenci čísel. To znamená, že jednotlivý GŠČ inicializovaný stejným semenem (v různých časových okamžicích, v různých programech, na různých zařízeních) bude generovat stejnou sekvenci.
Dále je třeba znát charakteristické rozdělení pravděpodobnosti GŠČ – jaká čísla bude generovat a s jakou pravděpodobností. Častěji to bývá buď normální rozdělení (normal distribution), nebo rovnoměrné rozdělení (uniform distribution).
Normální rozdělení (vlevo) a rovnoměrné rozdělení (vpravo)
Představme si, že máme férovou kostku se 24 stranami. Pokud ji hodíme, pravděpodobnost, že padne jedna, bude 1/24 (stejně jako pravděpodobnost, že padne jakékoli jiné číslo). Pokud provedeme mnoho hodů a zapíšeme výsledky, můžeme si všimnout, že všechny strany padnou přibližně stejnou frekvencí. V podstatě můžeme tuto kostku považovat za GŠČ s rovnoměrným rozdělením.
A co když hodíme najednou 10 takových kostek a spočítáme celkový součet bodů? Bude pro něj zachována rovnoměrnost? Ne. Častěji bude součet blízko 125 bodům, tedy k určitému průměrnému hodnotě. A jako důsledek – ještě před provedením hodu lze přibližně odhadnout budoucí výsledek.
Důvodem je, že pro získání průměrného součtu bodů existuje největší množství kombinací. Čím dále od ní, tím méně kombinací – a tím pádem menší pravděpodobnost výskytu. Pokud tato data vizualizujeme, budou vzdáleně připomínat tvar zvonu. Proto lze s jistou nadsázkou systém 10 kostek nazvat GŠČ s normálním rozdělením.
Další příklad, ale tentokrát v rovině – střelba na terč. Střelcem bude GŠČ, generující pár čísel (x, y), která se zobrazuje na grafu.
Souhlasíte, že varianta vlevo je blíže skutečnosti – to je generátor náhodných čísel s normálním rozdělením. Ale pokud je třeba rozptýlit hvězdy na temné obloze, lépe poslouží pravá varianta, získaná pomocí generátoru náhodných čísel s rovnoměrným rozdělením. Obecně si vyberte generátor podle zadaného úkolu.
Teď se podíváme na entropii sekvence náhodných čísel. Například existuje sekvence, která začíná takto:
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, …
Jak moc jsou tato čísla náhodná na první pohled? Začněme kontrolou rozdělení.
Vypadá to jako blízké k rovnoměrnému, ale pokud čteme sekvenci po dvou číslech a interpretujeme je jako souřadnice na rovině, dostaneme toto:
Jasně se objevují vzory. A protože jsou data v sekvenci uspořádána určitým způsobem (tedy mají nízkou entropii), může to vést k oné "předpojatosti". Minimálně takový generátor náhodných čísel není příliš vhodný pro generaci souřadnic na rovině.
Další sekvence:
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, …
Na rovině to vypadá docela dobře:
Podíváme se ve 3D (čteme po třech číslech):
A opět vzory. Vytvořit vizualizaci ve čtyřech dimenzích už nebude možné. Ale vzory mohou existovat i v této dimenzi a ve větších.
Ve stejném oboru kryptografie, kde jsou na generátory náhodných čísel kladeny nejpřísnější požadavky, je taková situace kategoricky nepřijatelná. Proto byly vyvinuty speciální algoritmy pro hodnocení jejich kvality, kterých se teď dotýkat nebudeme. Téma je rozsáhlé a zaslouží si samostatný článek.
Testování
Pokud něco nevíme jistě, jak s tím pracovat? Má smysl přejít silnici, pokud nevíte, který signál semaforu to povoluje? Následky mohou být různé.
To samé platí pro proslulý random v Unity. Je dobré, pokud dokumentace odhaluje nezbytné podrobnosti, ale zmíněná historie na začátku článku vznikla právě kvůli nedostatku očekávané konkretizace.
Bez znalosti, jak nástroj funguje, ho nebudeš moci správně použít. Obecně je čas prověřit a provést experiment, abychom se aspoň ujistili ohledně rozdělení.
Řešení bylo jednoduché a efektivní — shromáždit statistiky, získat objektivní data a podívat se na výsledky.
Předmět výzkumu
V Unity existuje několik způsobů generování náhodných čísel — otestovali jsme pět.
- System.Random.Next(). Generuje celá čísla (integer) v daném rozsahu hodnot.
- System.Random.NextDouble(). Generuje čísla s dvojitou přesností (double) v rozsahu od [0; 1).
- UnityEngine.Random.Range(). Generuje čísla s jednoduchou přesností (float) v daném rozsahu hodnot.
- UnityEngine.Random.value. Generuje čísla s jednoduchou přesností (float) v rozsahu od [0; 1).
- Unity.Mathematics.Random.NextFloat(). Součást nové knihovny Unity.Mathematics. Generuje čísla s jednoduchou přesností (float) v daném rozsahu hodnot.
V prakticky celé dokumentaci bylo uvedeno rovnoměrné rozdělení, kromě UnityEngine.Random.value (kde není rozdělení uvedeno, ale analogicky s UnityEngine.Random.Range() se také očekávalo rovnoměrné) a Unity.Mathematics.Random.NextFloat() (kde je základem algoritmus xorshift, což znamená, že opět musíme čekat na rovnoměrné rozdělení).
Za očekávané výsledky jsme brali ty, které jsou uvedeny v dokumentaci.
Metodika
Napsali jsme malou aplikaci, která generovala sekvence náhodných čísel každým z uvedených způsobů a ukládala výsledky pro další zpracování.
Délka každé sekvence — 100 000 čísel.
Rozsah hodnot náhodných čísel — [0, 100).
Data jsme shromažďovali z několika cílových platforem:
- Windows
— Unity v2018.3.14f1, režim Editor, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, režim Editor, Mono, .NET Standard 2.0
— Unity v5.6.4p4, režim Editor, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, sestavení pro zařízení, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, sestavení pro zařízení, il2cpp, .NET Standard 2.0
Implementace
Máme několik různých způsobů generování náhodných čísel. Pro každý z nich napíšeme samostatnou obalovou třídu, která by měla poskytnout:
- Možnost nastavit rozsah hodnot [min/max). Bude nastavena přes konstruktor.
- Metodu, která vrací náhodné číslo. Jako typ zvolíme float, jako obecnější.
- Název způsobu generování pro označení výsledků. Pro pohodlí bude jako hodnota vracet úplný název třídy + název metody, která se používá k generování náhodného čísla.
Nejprve vyhlásíme abstrakci, která bude představena rozhraním IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementace System.Random.Next()
Tato metoda umožňuje nastavit rozsah hodnot, ale vrací celá čísla (integer), zatímco potřebujeme float. Můžeme jednoduše interpretovat integer jako float, nebo můžeme rozšířit rozsah hodnot o několik řádů a kompenzovat je při každé generaci náhodného čísla. Výsledkem bude něco jako pevná desetinná čárka s danou přesností. Použijeme tuto variantu, protože je bližší skutečné hodnotě float.
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;
}
}Implementace System.Random.NextDouble()
Zde je pevný rozsah hodnot [0; 1). Abychom ho mohli promítnout na zadaný v konstruktoru, použijeme jednoduchou aritmetiku: 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;
}
}Implementace UnityEngine.Random.Range()
Tato metoda statické třídy UnityEngine.Random umožňuje nastavit rozsah hodnot a vrací náhodné číslo typu float. Není potřeba provádět žádné další převody.
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);
}
}Implementace UnityEngine.Random.value
Vlastnost value statické třídy UnityEngine.Random vrací náhodné číslo typu float z pevného rozsahu hodnot [0; 1). Promítneme ho na zadaný rozsah stejným způsobem, jakým jsme to udělali při implementaci 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;
}
}Implementace Unity.Mathematics.Random.NextFloat()
Metoda NextFloat() třídy Unity.Mathematics.Random vrací číslo typu float a umožňuje nastavit rozsah hodnot. Zásadní je, že každý instance Unity.Mathematics.Random musí být inicializována nějakým seedem — tím předejdeme generaci opakujících se sekvencí.
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);
}
}Implementace MainController
Několik implementací IRandomGenerator je připraveno. Nyní je třeba vygenerovat sekvence a uložit výsledný dataset pro zpracování. K tomu vytvoříme ve Unity scénu a malý skript MainController, který provede veškerou potřebnou práci a zároveň se postará o interakci s UI.
Nastavíme velikost datasetu a rozsah hodnot, a také budeme mít metodu, která vrátí pole nakonfigurovaných a funkčních generátorů.
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)
};
}
...
}
}A nyní formujeme dataset. V tomto případě bude generování dat spojeno se zapisováním výsledků do textového proudu (ve formátu csv). Pro ukládání hodnot každého IRandomGenerator je vyhrazena samostatná kolona, a první řádek obsahuje jméno generátoru.
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();
}
}
...
}
}Je třeba zavolat metodu GenerateCsvDataSet a uložit výstup do souboru, nebo data okamžitě odeslat přes síť z koncového zařízení na přijímající. 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();
}
}
...
}
}Zdroje projektu jsou umístěny na .
Výsledky
Zázraky se nekonaly. To, co jsme očekávali, se přesně splnilo — ve všech případech rovnoměrné rozdělení bez náznaku spiknutí. Nepřikládám jednotlivé grafy dle platforem, protože ukazují zhruba stejné výsledky.
Skutečnost je následující:
Vizualizace sekvencí na rovině podle všech pěti způsobů generování:
A vizualizace ve 3D. Zůstane mi pouze výsledek System.Random.Next(), abych neplodil hromadu stejného obsahu.
Příběh zmíněný v úvodu o normálním rozdělení UnityEngine.Random se neopakoval: buď byl původně chybný, nebo se od té doby v engine něco změnilo. Nicméně nyní jsme si jisti.
Zdroj: habr.com
