W branży gier często trzeba coś związać z przypadkowością: w Unity jest do tego swój Random, a równolegle istnieje System.Random. Kiedyś, na jednym z projektów, odniosłem wrażenie, że obydwa mogą działać inaczej (choć powinny mieć równomierny rozkład).
Nie zagłębialiśmy się w szczegóły — wystarczyło, że przejście na System.Random naprawiło wszystkie problemy. Teraz postanowiliśmy dokładniej zbadać: na ile „stronnicze” lub przewidywalne są generatory liczb losowych i który wybrać. Ponadto nie raz słyszałem sprzeczne opinie na temat ich „uczciwości” — spróbujemy zrozumieć, jak rzeczywiste wyniki odnoszą się do zadeklarowanych.
Krótki wprowadzenie lub co to takiego generator liczb losowych
Jeśli już znasz generatory liczb losowych, możesz od razu przejść do sekcji „Testowanie”.
Liczby losowe (LL) to sekwencja liczb generowana za pomocą pewnego losowego (chaotycznego) procesu, źródła entropii. Oznacza to, że to taka sekwencja, której elementy nie są ze sobą powiązane żadnym prawem matematycznym — nie mają przyczynowo-skutkowego związku.
To, co tworzy LL nazywa się generatorem liczb losowych (GLR). Wydawałoby się, że to wszystko elementarne, ale jeśli przejść od teorii do praktyki, to w rzeczywistości wykorzystanie algorytmu do generowania takiej sekwencji nie jest takie proste.
Przyczyna leży w braku tej chaotyczności w nowoczesnej elektronice konsumenckiej. Bez niej liczby losowe przestają być losowe, a ich generator zamienia się w zwykłą funkcję od z góry określonych argumentów. Dla wielu specjalności w dziedzinie IT to poważny problem (np. dla kryptografii), dla innych jednak jest całkiem akceptowalne rozwiązanie.
Należy napisać algorytm, który zwracałby choć nie prawdziwie losowe liczby, to maksymalnie do nich zbliżone — tak zwane liczby pseudolosowe (LPL). Algorytm w tym przypadku nazywa się generatorem liczb pseudolosowych (GPL).
Jest kilka sposobów stworzenia GPL, ale dla wszystkich będą aktualne następujące kwestie:
- Potrzeba wcześniejszej inicjalizacji.
Generator liczb losowych (GPL) nie ma źródła entropii, dlatego przed użyciem musi określić stan początkowy. Ustala się go w postaci liczby (lub wektora) i nazywa się ziarnem (seed, random seed). Często jako seed wykorzystuje się licznik taktów procesora lub numeryczny ekwiwalent czasu systemowego.
- Reprodukowalność sekwencji.
Główny Generator Liczb Losowych (GPL) jest całkowicie deterministyczny, dlatego podany podczas inicjalizacji seed jednoznacznie określa całą przyszłą sekwencję liczb. Oznacza to, że pojedynczy GPL, zainicjowany tym samym ziarnem (w różnym czasie, w różnych programach, na różnych urządzeniach) będzie generował tę samą sekwencję.
Musimy również znać charakterystyczne dla GPL rozkład prawdopodobieństwa — jakie liczby będzie generował i z jakim prawdopodobieństwem. Najczęściej jest to albo rozkład normalny (normal distribution), albo rozkład jednorodny (uniform distribution).
Rozkład normalny (po lewej) i rozkład jednorodny (po prawej)
Załóżmy, że mamy uczciwą kostkę do gry z 24 ściankami. Jeśli ją rzucimy, prawdopodobieństwo wypadnięcia jednostki będzie równe 1/24 (podobnie jak prawdopodobieństwo wypadnięcia innej liczby). Jeśli wykonamy wiele rzutów i zapiszemy wyniki, możemy zauważyć, że wszystkie ścianki wypadają mniej więcej z taką samą częstotliwością. W zasadzie tę kostkę można uznać za generator liczb losowych z rozkładem jednorodnym.
A co, jeśli jednocześnie rzucać 10 takimi kostkami i liczyć łączną sumę punktów? Czy dla niej zachowa się jednorodność? Nie. Najczęściej suma będzie bliska 125 punktów, czyli pewnej wartości średniej. I w konsekwencji — nawet przed wykonaniem rzutu można w przybliżeniu oszacować przyszły wynik.
Powód jest taki, że dla uzyskania średniej sumy punktów istnieje największa liczba kombinacji. Im dalej od niej, tym mniej kombinacji — a co za tym idzie, mniejsze prawdopodobieństwo wystąpienia. Jeśli te dane zwizualizować, będą one odlegle przypominały kształt dzwonu. Dlatego z pewnym przymusem system 10 kostek można nazwać generatorem liczb losowych z rozkładem normalnym.
Inny przykład, ale już w płaszczyźnie — strzelanie do celu. Strzelcem będzie generator liczb losowych, generujący parę liczb (x, y), która jest przedstawiana na wykresie.
Zgadzam się, że lewa opcja jest bliższa rzeczywistości — to generator liczb losowych z rozkładem normalnym. Ale jeśli trzeba rozrzucić gwiazdy na ciemnym niebie, to lepiej sprawdzi się prawa opcja, uzyskana za pomocą generatora liczb losowych z rozkładem jednorodnym. Ogólnie, wybieraj generator w zależności od postawionego zadania.
Teraz porozmawiajmy o entropii ciągu liczb losowych. Na przykład mamy ciąg, który zaczyna się tak:
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 bardzo te liczby wydają się losowe na pierwszy rzut oka? Zacznijmy od sprawdzenia rozkładu.
Wygląda na bliskie jednorodnemu, ale jeśli odczytasz ciąg w parach i zinterpretujesz je jako współrzędne na płaszczyźnie, to otrzymasz to:
Widzimy wyraźnie układy. A ponieważ dane w ciągu są uporządkowane w określony sposób (to znaczy mają niską entropię), może to prowadzić do wspomnianej „stronniczości”. Przynajmniej taki generator nie bardzo nadaje się do generacji współrzędnych na płaszczyźnie.
Inny ciąg:
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 płaszczyźnie wydaje się wszystko w porządku:
Spójrzmy w objętości (odczytując po trzy liczby):
I znów układy. Nie da się zbudować wizualizacji w czterech wymiarach. Ale układy mogą istnieć także w tej wymiarze i na wyższych.
W tej samej kryptografii, gdzie do generatorów liczb losowych stawia się najsurowsze wymagania, podobna sytuacja jest kategorycznie niedopuszczalna. Dlatego opracowano specjalne algorytmy do oceny ich jakości, o których teraz nie będziemy mówić. Temat jest rozległy i zasługuje na osobny artykuł.
Testowanie
Jeśli czegoś nie wiemy na pewno, to jak z tym pracować? Czy warto przejść przez ulicę, jeśli nie wiesz, który sygnał świetlny to zezwala? Konsekwencje mogą być różne.
To samo dotyczy wspomnianego losowego w Unity. Dobrze, jeśli dokumentacja ujawnia niezbędne szczegóły, ale wspomniana na początku artykułu historia wydarzyła się właśnie z powodu braku pożądanej konkretności.
Nie wiedząc, jak działa narzędzie, nie będziesz mógł go prawidłowo zastosować. W każdym razie nadszedł czas, aby sprawdzić i przeprowadzić eksperyment, aby ostatecznie upewnić się przynajmniej co do rozkładu.
Rozwiązanie było proste i skuteczne - zebrać statystyki, uzyskać obiektywne dane i spojrzeć na wyniki.
Przedmiot badania
W Unity istnieje kilka sposobów generowania liczb losowych - przetestowaliśmy pięć z nich.
- System.Random.Next(). Generuje liczby całkowite (integer) w określonym zakresie wartości.
- System.Random.NextDouble(). Generuje liczby podwójnej precyzji (double) w zakresie od [0; 1).
- UnityEngine.Random.Range(). Generuje liczby pojedynczej precyzji (float) w określonym zakresie wartości.
- UnityEngine.Random.value. Generuje liczby pojedynczej precyzji (float) w zakresie od [0; 1).
- Unity.Mathematics.Random.NextFloat(). Część nowej biblioteki Unity.Mathematics. Generuje liczby pojedynczej precyzji (float) w określonym zakresie wartości.
Praktycznie wszędzie w dokumentacji wskazane było równomierne rozkład, z wyjątkiem UnityEngine.Random.value (gdzie rozkład nie został określony, ale analogicznie do UnityEngine.Random.Range() również oczekiwano rozkładu równomiernego) i Unity.Mathematics.Random.NextFloat() (gdzie podstawą jest algorytm xorshift, więc znów musimy oczekiwać równomiernego rozkładu).
Domyślnie za oczekiwane wyniki uznano te, które są podane w dokumentacji.
Metodyka
Napisaliśmy niewielką aplikację, która generowała sekwencje liczb losowych w każdy z zaprezentowanych sposobów i zapisywała wyniki do dalszej obróbki.
Długość każdej sekwencji to 100 000 liczb.
Zakres wartości liczb losowych to [0, 100).
Dane zbierano z kilku docelowych platform:
- Windows
— Unity v2018.3.14f1, tryb edytora, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, tryb edytora, Mono, .NET Standard 2.0
— Unity v5.6.4p4, tryb edytora, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, kompilacja na urządzenie, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, kompilacja na urządzenie, il2cpp, .NET Standard 2.0
Realizacja
Mamy kilka różnych sposobów generowania liczb losowych. Dla każdego z nich napiszemy osobną klasę-owijkę, która powinna zapewnić:
- Możliwość ustalenia zakresu wartości [min/max). Będzie ustalana przez konstruktor.
- Metodę, która zwraca RNG. Jako typ wybierzemy float, jako bardziej ogólny.
- Nazwa metody generowania do etykietowania wyników. Dla wygody jako wartość zwrócimy pełną nazwę klasy + nazwę metody używanej do generowania liczby losowej.
Najpierw zadeklarujemy abstrakcję, która będzie przedstawiona przez interfejs IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementacja System.Random.Next()
Ta metoda umożliwia określenie zakresu wartości, ale zwraca liczby całkowite (integer), a potrzebujemy float. Można po prostu zinterpretować integer jako float, lub można rozszerzyć zakres wartości o kilka rzędów, kompensując je przy każdej generacji liczby losowej. Uzyskamy coś w rodzaju fixed-point z określoną precyzją. Będziemy używać tej opcji, ponieważ jest ona bliższa rzeczywistym wartościom 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;
}
}Implementacja System.Random.NextDouble()
Tutaj mamy ustalony zakres wartości [0; 1). Aby odwzorować go na podany w konstruktorze, używamy prostej arytmetyki: 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;
}
}Implementacja UnityEngine.Random.Range()
Ta metoda statycznej klasy UnityEngine.Random pozwala określić zakres wartości i zwraca liczbę losową typu float. Żadne dodatkowe przekształcenia nie będą potrzebne.
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);
}
}Implementacja UnityEngine.Random.value
Właściwość value statycznej klasy UnityEngine.Random zwraca liczbę typu float z ustalonego zakresu wartości [0; 1). Projkujemy ją na zadany zakres w ten sam sposób, jak przy implementacji 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;
}
}Implementacja Unity.Mathematics.Random.NextFloat()
Metoda NextFloat() klasy Unity.Mathematics.Random zwraca liczbę typu float i pozwala na określenie zakresu wartości. Istnieje jednak jeden niuans: każdy egzemplarz Unity.Mathematics.Random musi być zainicjowany pewnym seed — dzięki temu unikniemy generacji powtarzających się sekwencji.
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);
}
}Implementacja MainController
Kilka implementacji IRandomGenerator jest gotowych. Następnie trzeba wygenerować sekwencje i zapisać wynikowy zbiór danych do przetworzenia. W tym celu stwórzmy w Unity scenę i mały skrypt MainController, który będzie realizował wszystkie niezbędne działania i jednocześnie zajmował się interakcją z UI.
Określimy rozmiar zbioru danych i zakres wartości, a także przygotujemy metodę, która zwraca tablicę skonfigurowanych generatorów gotowych do pracy.
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 teraz formujemy zbiór danych. W tym przypadku generacja danych będzie połączona z zapisem wyników do strumienia tekstowego (w formacie csv). Każdemu IRandomGenerator zostanie przypisana osobna kolumna, a pierwszy wiersz będzie zawierał nazwę generatora.
namespace RandomDistribution
{
public class MainController : MonoBehaviour
{
...
private void GenerateCsvDataSet(TextWriter writer, int dataSetSize, params IRandomGenerator[] generators)
{
const char separator = ',';
int lastIdx = generators.Length - 1;
// napisz nagłówek
for (int j = 0; j <= lastIdx; j++)
{
writer.Write(generators[j].Name);
if (j != lastIdx)
writer.Write(separator);
}
writer.WriteLine();
// napisz dane
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();
}
}
...
}
}Teraz należy wywołać metodę GenerateCsvDataSet i zapisać wynik w pliku, lub od razu przesłać dane przez sieć z urządzenia końcowego do odbiorcy. serwer.
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();
}
}
...
}
}Pliki źródłowe projektu znajdują się na .
Wyniki
Cudów nie było. To, czego się spodziewaliśmy, to i otrzymaliśmy — we wszystkich przypadkach równomierne rozkład bez śladów spisków. Nie widzę sensu w dołączaniu indywidualnych wykresów dla platform — wszystkie pokazują mniej więcej te same wyniki.
Rzeczywistość jest taka:
Wizualizacja sekwencji na płaszczyźnie z wszystkich pięciu sposobów generacji:
A wizualizacja w 3D. Zostawię tylko wynik System.Random.Next(), aby nie mnożyć identycznej treści.
Opowiedziana w wprowadzeniu historia o normalnym rozkładzie UnityEngine.Random się nie powtórzyła: albo pierwotnie była błędna, albo coś od tego czasu zmieniło się w silniku. Ale teraz jesteśmy pewni.
Źródło: habr.com
