BlessRNG vai RNG godīguma pārbaude

Spēļu izstrādē bieži vien ir jāpaļaujas uz nejaušību: Unity šim nolūkam ir sava Random funkcija, un līdzās tai pastāv arī System.Random. Sen atpakaļ, strādājot pie viena projekta, man radās iespaids, ka abi varētu darboties atšķirīgi (lai gan tiem vajadzētu būt vienmērīgam sadalījumam).

Toreiz mēs neiedziļinājāmies detaļās — pietika ar to, ka pāreja uz System.Random atrisināja visas problēmas. Tagad esam nolēmuši rūpīgāk aplūkot šo jautājumu un veikt nelielu pētījumu: cik "neobjektīvi" vai paredzami ir RNG un kuru izvēlēties. Turklāt esmu ne reizi vien dzirdējis pretrunīgus viedokļus par to "taisnīgumu" — mēģināsim noskaidrot, kā faktiskie rezultāti salīdzināmi ar apgalvojumiem.

Īss ievads RNG jeb vai tas tiešām ir RNG?

Ja jau esat iepazinies ar nejaušo skaitļu ģeneratoriem, varat pāriet uz sadaļu “Testēšana”.

Nejaušie skaitļi (RN) ir skaitļu virkne, kas ģenerēta kāda nejauša (haotiska) procesa rezultātā, entropijas avots. Tas ir, tā ir virkne, kuras elementi nav saistīti viens ar otru ne ar vienu matemātisku likumu — tiem nav cēloņsakarību.

Nejaušo skaitļu ģeneratora (RNG) izveides procesu sauc par nejaušo skaitļu ģeneratoru (RNG). Lai gan tas šķiet vienkārši, teorijas ieviešana praksē atklāj, ka programmatūras algoritma ieviešana šādas secības ģenerēšanai nav tik vienkārša.

Iemesls slēpjas tieši šīs nejaušības trūkumā mūsdienu plaša patēriņa elektronikā. Bez tās nejaušie skaitļi pārstāj būt nejauši, un to ģenerators pārvēršas par vienkāršu iepriekš noteiktu ievades datu funkciju. Vairākām IT profesijām (piemēram, kriptogrāfijai) tā ir nopietna problēma, bet citām ir pilnīgi pieņemams risinājums.

Mums jāuzraksta algoritms, kas atgriež skaitļus, kas nav patiesi nejauši, bet ir pēc iespējas tuvāki tiem — tā sauktos pseido-nejaušos skaitļus (PRNG). Šajā gadījumā algoritmu sauc par pseido-nejaušu skaitļu ģeneratoru (PRNG).

PRNG izveidei ir vairākas iespējas, taču visiem būs piemērotas šādas iespējas:

1. Nepieciešama iepriekšēja inicializācija.

   PRNG trūkst entropijas avota, tāpēc pirms lietošanas ir jānorāda sākotnējais stāvoklis. Šis sākotnējais stāvoklis tiek norādīts kā skaitlis (vai vektors) un tiek saukts par sēklu (nejaušu sēklu). Kā sākums bieži tiek izmantots procesora ciklu skaitītājs vai sistēmas laika skaitliskais ekvivalents.

2. Secības reproducējamība.

   PRNG ir pilnībā deterministisks, tāpēc inicializācijas laikā norādītā sākotnējā vērtība (sēkla) unikāli nosaka visu nākotnes skaitļu secību. Tas nozīmē, ka viens PRNG, kas inicializēts ar vienu un to pašu sākotnējo vērtību (dažādos laikos, dažādās programmās, dažādās ierīcēs), ģenerēs vienu un to pašu secību.

Jums jāzina arī PRNG raksturojošais varbūtības sadalījums — kādus skaitļus tas ģenerēs un ar kādu varbūtību. Visbiežāk tas ir vai nu normālsadalījums, vai vienmērīgs sadalījums.

Normālais sadalījums (pa kreisi) un vienmērīgais sadalījums (pa labi)

Pieņemsim, ka mums ir vienāds 24-skaldņu kauliņš. Ja mēs to metīsim, varbūtība, ka tas uzkritīs uz 1, ir 1/24 (tāpat kā varbūtība, ka tas uzkritīs uz jebkura cita skaitļa). Ja veiksim daudz metienu un pierakstīsim rezultātus, mēs pamanīsim, ka visi 24-skaldņu kauliņi uzkritīs ar aptuveni vienādu biežumu. Būtībā šo kauliņu var uzskatīt par vienmērīgi sadalītu nejaušo skaitļu ģeneratoru.

Kas notiek, ja vienlaikus uzmet 10 šādus kauliņus un aprēķina kopējo rezultātu? Vai tas paliks vienāds? Nē. Visbiežāk rezultāts būs tuvu 125 punktiem, tas ir, kādai vidējai vērtībai. Rezultātā jūs varat aptuveni novērtēt nākotnes rezultātu vēl pirms metiena.

Iemesls ir tāds, ka pastāv vislielākais kombināciju skaits, kas ļauj sasniegt vidējo rezultātu. Jo tālāk tas atšķiras no vidējā, jo mazāk kombināciju ir — un līdz ar to jo mazāka ir metienā iegūtā kauliņa varbūtība. Ja šie dati tiktu vizualizēti, tie attāli atgādinātu zvaniņa formu. Tāpēc ar nelielu pielāgojumu 10 kauliņu sistēmu varētu saukt par normāli sadalītu RNG.

Vēl viens piemērs, šoreiz lidmašīnā, ir šaušana mērķī. Šāvējs ir nejaušo skaitļu ģenerators (RNG), kas ģenerē skaitļu pāri (x, y), kas tiek attēlots grafikā.

Jūs piekritīsiet, ka kreisās puses variants ir tuvāks reālajai dzīvei — tas ir nejaušo skaitļu ģenerators ar normālu sadalījumu. Bet, ja jums ir jāizkaisa zvaigznes pa tumšām debesīm, piemērotāks būtu labās puses variants, kas iegūts, izmantojot vienmērīgi sadalītu nejaušo skaitļu ģeneratoru. Īsāk sakot, izvēlieties ģeneratoru, pamatojoties uz veicamo uzdevumu.

Tagad parunāsim par nejaušu skaitļu virknes entropiju. Piemēram, ir virkne, kas sākas šādi:

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, …

Cik nejauši šie skaitļi šķiet no pirmā acu uzmetiena? Sāksim ar sadalījuma pārbaudi.

Tas izskatās gandrīz vienmērīgs, bet, ja izlasāt divu skaitļu secību un interpretējat tos kā koordinātas plaknē, iegūstat šo:

Raksti kļūst skaidri redzami. Un tā kā dati secībā ir sakārtoti noteiktā veidā (t. i., tiem ir zema entropija), tas var radīt tādu pašu "novirzi". Vismaz šāds PRNG nav īpaši piemērots koordinātu ģenerēšanai plaknē.

Vēl viena secība:

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, …

Šķiet, ka šeit viss ir kārtībā, pat uz līdzenas virsmas:

Apskatīsim apjomu (izlasiet trīs skaitļus):

Un atkal, modeļi. Vizualizācija četrās dimensijās vairs nav iespējama. Bet modeļi var pastāvēt šajā dimensijā un augstākās dimensijās.

Kriptogrāfijā, kur PRNG tiek izvirzītas visstingrākās prasības, šāda situācija ir absolūti nepieņemama. Tāpēc ir izstrādāti īpaši algoritmi to kvalitātes novērtēšanai, kurus mēs šeit neapspriedīsim. Tēma ir plaša un pelnījusi atsevišķu rakstu.

Testēšana

Ja mēs kaut ko nezinām droši, kā mēs varam ar to rīkoties? Vai mums vajadzētu šķērsot ceļu, ja nezinām, kurš luksofors to atļauj? Sekas var būt dažādas.

Tas pats attiecas uz bēdīgi slaveno nejaušību Unity. Ir lieliski, ja dokumentācijā ir sniegta nepieciešamā informācija, taču raksta sākumā minētais incidents radās tieši vēlamās specifikas trūkuma dēļ.

Un, nezinot, kā rīks darbojas, to nevar pareizi izmantot. Tāpēc ir pienācis laiks to pārbaudīt un veikt eksperimentu, lai beidzot pārliecinātos vismaz par izplatību.

Risinājums bija vienkāršs un efektīvs: apkopot statistiku, iegūt objektīvus datus un aplūkot rezultātus.

Pētījuma priekšmets

Unity ir vairāki veidi, kā ģenerēt nejaušus skaitļus — mēs pārbaudījām piecus.

1. System.Random.Next(). Ģenerē veselus skaitļus noteiktā vērtību diapazonā.
2. System.Random.NextDouble(). Ģenerē dubultprecizitātes skaitļus diapazonā [0; 1).
3. UnityEngine.Random.Range(). Ģenerē skaitļus ar vienu precizitāti (peldošās skaitļus) noteiktā vērtību diapazonā.
4. UnityEngine.Random.value. Ģenerē skaitļus ar vienu precizitāti (peldošo skaitli) diapazonā [0; 1].
5. Unity.Mathematics.Random.NextFloat(). Jaunās Unity.Mathematics bibliotēkas daļa. Ģenerē vienas precizitātes peldošos skaitļus noteiktā diapazonā.

Gandrīz visur dokumentācijā bija norādīts vienmērīgs sadalījums, izņemot UnityEngine.Random.value (kur sadalījums nav norādīts, bet pēc analoģijas ar UnityEngine.Random.Range() arī tika gaidīts vienmērīgs sadalījums) un Unity.Mathematics.Random.NextFloat() (kas ir balstīts uz xorshift algoritmu, kas nozīmē, ka atkal ir sagaidāms vienmērīgs sadalījums).

Pēc noklusējuma sagaidāmie rezultāti bija tie, kas norādīti dokumentācijā.

Metodoloģija

Mēs uzrakstījām nelielu lietojumprogrammu, kas, izmantojot katru no piedāvātajām metodēm, ģenerēja nejaušu skaitļu secības un saglabāja rezultātus tālākai apstrādei.

Katras secības garums ir 100 000 skaitļu.
Nejaušo skaitļu vērtību diapazons ir [0, 100].

Dati tika apkopoti no vairākām mērķa platformām:

• Windows
  — Unity v2018.3.14f1, redaktora režīms, Mono, .NET Standard 2.0
• macOS
  — Unity v2018.3.14f1, redaktora režīms, Mono, .NET Standard 2.0
  — Unity v5.6.4p4, redaktora režīms, Mono, .NET Standard 2.0
• Android
  — Unity v2018.3.14f1, ierīces būvējums, Mono, .NET Standard 2.0
• iOS
  — Unity v2018.3.14f1, ierīces būvējums, il2cpp, .NET Standard 2.0

Ieviešana

Mums ir vairāki dažādi veidi, kā ģenerēt nejaušus skaitļus. Katram no tiem mēs uzrakstīsim atsevišķu apvalka klasi, kurai jānodrošina:

1. Iespēja norādīt vērtību diapazonu [min/max]. Tiks iestatīts, izmantojot konstruktoru.
2. Metode, kas atgriež skaitli. Kā tipu izvēlēsimies float, jo tas ir vispārīgāks.
3. Rezultātu marķēšanas ģenerēšanas metodes nosaukums. Ērtības labad mēs atgriezīsim pilnu klases nosaukumu + SC ģenerēšanai izmantotās metodes nosaukumu.

Vispirms deklarēsim abstrakciju, ko attēlos IRandomGenerator saskarne:

namespace RandomDistribution
{
    public interface IRandomGenerator
    {
        string Name { get; }

        float Generate();
    }
}

System.Random.Next() ieviešana

Šī metode ļauj norādīt vērtību diapazonu, bet tā atgriež veselus skaitļus, savukārt peldošās vērtības ir obligātas. Veselo skaitli var vienkārši interpretēt kā peldošo vērtību vai arī paplašināt vērtību diapazonu par vairākām lieluma pakāpēm, kompensējot tās katru reizi, kad tiek ģenerēta frekvence. Tas radīs kaut ko līdzīgu fiksētam punktam ar noteiktu precizitātes pakāpi. Mēs izmantosim šo opciju, jo tā ir tuvāka patiesai peldošās vērtības vērtībai.

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;
    }
}

System.Random.NextDouble() ieviešana

Šeit fiksētais vērtību diapazons ir [0; 1]. Lai to projicētu uz konstruktorā norādīto, izmantojam vienkāršu aritmētiku: 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;
    }
}

UnityEngine.Random.Range() ieviešana

Šī statiskās UnityEngine.Random klases metode ļauj norādīt vērtību diapazonu un atgriež nejaušu skaitli ar peldošu skaitli. Papildu konvertēšana nav nepieciešama.

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);
    }
}

UnityEngine.Random.value ieviešana

Statiskās klases UnityEngine.Random vērtības īpašība atgriež peldoša tipa nejaušu skaitli no fiksēta vērtību diapazona [0; 1]. Mēs to projicējam uz doto diapazonu tāpat kā ieviešot 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;
    }
}

Unity.Mathematics.Random.NextFloat() ieviešana

Unity.Mathematics.Random klases NextFloat() metode atgriež peldošu nejaušu skaitli un ļauj norādīt vērtību diapazonu. Vienīgais brīdinājums ir tāds, ka katrs Unity.Mathematics.Random eksemplārs ir jāinicializē ar sākotnējo vērtību (seed) — tas novērš dublētu secību ģenerēšanu.

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);
    }
}

MainController ieviešana

Vairākas IRandomGenerator implementācijas ir gatavas. Tālāk mums ir jāģenerē secības un jāsaglabā iegūtais datu kopums apstrādei. Lai to izdarītu, mēs izveidosim ainu Unity vidē un nelielu MainController skriptu, kas veiks visu nepieciešamo darbu un apstrādās lietotāja saskarni.

Mēs definēsim datu kopas lielumu un frekvences vērtību diapazonu, kā arī izveidosim metodi, kas atgriež konfigurētu un lietošanai gatavu ģeneratoru masīvu.

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)
            };
        }

        ...
    }
}

Tagad mēs izveidosim datu kopu. Šajā gadījumā datu ģenerēšana tiks apvienota ar rezultātu ierakstīšanu teksta plūsmā (CSV formātā). Katram IRandomGenerator būs sava kolonna, un pirmajā rindā ir ģeneratora nosaukums.

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();
            }
        }

        ...
    }
}

Atliek tikai izsaukt metodi GenerateCsvDataSet un saglabāt rezultātu failā vai nekavējoties pārsūtīt datus tīklā no gala ierīces uz saņēmēju. serveri.

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();
            }
        }

        ...
    }
}

Projekta avoti atrodas šeit: GitLab.

rezultātus

Nekāds brīnums nenotika. Mēs saņēmām to, ko gaidījām — vienmērīgu sadalījumu visos gadījumos, bez jebkādām sazvērestības pazīmēm. Es neredzu jēgu pievienot atsevišķas platformu diagrammas — tās visas rāda aptuveni vienādus rezultātus.

Realitāte ir šāda:


Secību vizualizācija plaknē, izmantojot visas piecas ģenerēšanas metodes:


Un 3D vizualizācija. Es atstāšu tikai System.Random.Next() rezultātu, lai izvairītos no identiska satura kaudzes ģenerēšanas.


Ievadā aprakstītais stāsts par UnityEngine.Random normālo sadalījumu neatkārtojās: vai nu tas bija kļūdains jau no paša sākuma, vai arī kaut kas dzinējā kopš tā laika ir mainījies. Bet tagad mēs esam pārliecināti.

Avots: www.habr.com