BlessRNG või kontrollime juhuslikkuse generaatori ausust

Mängude arenduses on sageli vajalik midagi juhuslikku: Unity'l on selle jaoks oma Random, kuid paralleelselt eksisteerib ka System.Random. Kaugelt muiste, ühel projektil, tekkis mul tunne, et need kaks võivad töötada erinevalt (kuigi nad peaksid omama ühtlast jaotust).

Siis ei süvenenud me detailidesse — piisavalt, et üleminek System.Random'ile lahendas kõik probleemid. Nüüd oleme otsustanud rohkem süveneda ja teha väike uurimus: kui "poolitatud" või ettearvatavad on juhuslikud numbrid ning millist valida. Eriti kuna olen kuulnud vastuolulisi arvamusi nende "aususe" kohta — püüame välja selgitada, kuidas reaalsed tulemused seonduvad deklareeritud tulemustega.

Lühike sissejuhatus või Juhuslikud arvud on tegelikult Pseudojuhuslikud arvud

Kui olete juba tuttav juhuslike numbrite generaatoritega, võite kohe minna "Testimise" osasse.

Juhuslikud numbrid (JN) on numbrite järjestus, mis genereeritakse mõne juhusliku (kaootilise) protsessi, entropia allika abil. See tähendab, et see on selline järjestus, mille elemendid ei ole omavahel mingisuguse matemaatilise seaduse kaudu seotud — neil puudub põhjuslik seos.

See, mis loob juhuslikke numbreid, on juhuslikke numbrite generaator (JNG). Tundub, et kõik on elementaarne, kuid kui minna teooriast praktikasse, pole tegelikult sellise järjestuse genereerimise programmeerimise algoritmi teostamine nii lihtne.

Põhjus peitub kaasaegse tarbeelektroonika puudulikes kaootilisuse tasemes. Ilma selleta kaotavad juhuslikud numbrid oma juhuslikkuse ning nende generaator muutub tavaliseks funktsiooniks etteantud argumentide põhjal. IT-ala teatud erialade jaoks on see tõsine probleem (näiteks krüptograafia jaoks), kuid teiste jaoks on täiesti vastuvõetav lahendus.

Peame kirjutama algoritmi, mis tagab, et kuigi need ei ole tõeliselt juhuslikud numbrid, oleksid nad võimalikult lähedased - nii nimetatud pseudojuhuslikud numbrid (PJN). Antud juhul nimetatakse algoritmi pseudojuhuslike numbrite generaatoriks (PJNG).

Pseudojuhuslike numbrite genereerimiseks on mitmeid variante, kuid kõigi jaoks kehtib järgmine:

1. Eeltingimusena on vajalik eelneva initsialiseerimise teostamine.

   GPSH on ilma entropiaallikat, seega tuleb enne kasutamist määrata algtingimused. Need esitatakse numbrina (või vektorina) ja neid nimetatakse seemneks (seed, random seed). Sageli kasutatakse seemnena protsessori taktisageduse loendajat või süsteemi aja numbrilist ekvivalenti.

2. Järje taastatavus.

   GPSH on täielikult deterministlik, seega määrab algatamisel antud seeme ühemõtteliselt kogu tulevase numbrite järjestuse. See tähendab, et ükski GPSH, mis on algatatud sama seemnega (erineval ajal, erinevates programmides, erinevates seadmetes), genereerib sama järjestuse.

Samuti tuleb teada, milline on GPSH iseloomustav tõenäosusjaotus — milliseid numbreid see genereerib ja millise tõenäosusega. Kõige sagedamini on see kas normaaljaotus (normal distribution) või ühtlane jaotus (uniform distribution).

Normaaljaotus (vasakul) ja ühtlane jaotus (paremal)

Oletame, et meil on keskmine mängukaart 24 küljega. Kui seda heita, siis ühe tulemise tõenäosus on 1/24 (nagu ka mis tahes muu numbri tõenäosus). Kui teha palju heiteid ja tulemusi kirja panna, võib märgata, et kõik küljed tulevad välja umbes sama sagedusega. Sisuliselt võib seda mängukaarti pidada ühtlase jaotusega RNG-ks.

Aga kui visata kohe 10 sellist kaarti ja arvestada saadud punktide kogusummat? Kas selle puhul jääb ühtsus alles? Ei. Kõige sagedamini on summa lähedal 125 punktile, st teatud keskmisele väärtusele. Seega võib enne heite tegemist tulevast tulemust umbes hinnata.

Põhjus on selles, et keskmise punktisumma saavutamiseks on kõige rohkem kombinatsioone. Mida kaugemal sellest, seda vähem on kombinatsioone — ja vastavalt ka väiksem tõenäosus tulemuste saamiseks. Kui neid andmeid visualiseerida, sarnaneksid need uduselt kellakujuga. Seetõttu võib mõningasel määral 10 kaardist koosnevat süsteemi nimetada normaaljaotusega RNG-ks.

Veel üks näide, ainult et tasandil — sihtmärgi tulistamine. Kõ shooter on RNG, mis genereerib paari numbreid (x, y), mis kuvatakse graafikul.

Nõustuge, et vasakpoolne variant on tõelisema elu lähedal — see on normaaljaotusega juhuslik arvugeneraatoreis. But if you need to scatter stars on a dark sky, the right option, generated using a uniformly distributed RNG, is more suitable. Seega valige generaator vastavalt esitatud ülesandele.

Nüüd räägime PSČ järjestuseentsõt/üllatavust. Näiteks on olemas järjestus, mis algab nii:

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

Kui palju need numbrid esmapilgul juhuslikud on? Alustame jaotuse kontrollimisest.

Tundub, et see on peaaegu ühtlane, kuid kui lugeda järjestust kahe numbri kaupa ja tõlgendada neid koordinaatidena tasandil, siis see tundub selline:

Mustrid muutuvad selgelt nähtavaks. Kui andmed järjestuses on teatud viisil järjestatud (st neil on madal entropia), võib see tekitada nimelt "kallutatud" tulemusi. Vähemalt selline PSČ ei sobi hästi tasandi koordinaatide genereerimiseks.

Teine järjestus:

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

Siin tundub kõik isegi tasandil hea:

Vaadates kolmemõõtmeliselt (lugedes kolm numbrit korraga):

Ja jälle mustrid. Neljamõõtmelise visualiseerimise loomine ei ole enam võimalik. Kuid mustrid võivad eksisteerida ka selles mõõtmes ja suuremates.

Samas krüptograafias, kus RNG-dele esitatakse kõige rangemaid nõudeid, on selline olukord kategooriliselt vastuvõetamatu. Seetõttu on nende kvaliteedi hindamiseks välja töötatud spetsiaalsed algoritmid, millele me praegu ei keskendu. Teema on ulatuslik ja väärib eraldi artiklit.

Testimine

Kui me midagi kindlasti ei tea, siis kuidas sellega töötada? Kas tasub teed ületada, kui sa ei tea, milline valgusfoori signaal seda lubab? Tagajärjed võivad olla erinevad.

See kehtib ka kuulsate juhuslikkuse kohta Unitys. Hea, kui dokumentatsioon annab vajalikud detailid, kuid artikli alguses mainitud lugu juhtus just soovitud konkreetika puudumise tõttu.

Ilma et teada, kuidas tööriist töötab, ei saa seda õigesti rakendada. Üldiselt on aeg teha kontroll ja eksperiment, et lõpuks veenduda vähemalt jaotuse osas.

Lahendus oli lihtne ja tõhus - koguda statistikat, saada objektiivseid andmeid ja vaadata tulemusi.

Uuringu teema

Unitys on mitu viisi juhuslike arvude genereerimiseks - testisime viit.

1. System.Random.Next(). Genereerib täisarve (integer) määratud väärtuste vahemikus.
2. System.Random.NextDouble(). Genereerib kahefikaarse täpsusega arve (double) vahemikus [0; 1).
3. UnityEngine.Random.Range(). Genereerib üheselgelt täpsusega arve (float) määratud väärtuste vahemikus.
4. UnityEngine.Random.value. Genereerib üheselgelt täpsusega arve (float) vahemikus [0; 1).
5. Unity.Mathematics.Random.NextFloat(). Osa uuest raamatukogust Unity.Mathematics. Genereerib üheselgelt täpsusega arve (float) määratud väärtuste vahemikus.

Peaaegu igal pool dokumentatsioonis oli märgitud ühtlane jaotus, välja arvatud UnityEngine.Random.value (kus jaotust ei ole märgitud, kuid sarnaselt UnityEngine.Random.Range() oodati ka ühtlast) ja Unity.Mathematics.Random.NextFloat() (kuna alus põhineb algoritmil xorshift, tuleb jälle oodata ühtlast jaotust).

Oletati, et oodatavad tulemused on need, mis on esitatud dokumentatsioonis.

Metoodika

Kirjutasime väikese rakenduse, mis genereeris juhuslike arvsede järjendisid igal esitatud viisil ja salvestas tulemused edasise töötlemise jaoks.

Iga järjendi pikkus - 100 000 arvu.
Juhuslike arvude väärtuste vahemik - [0, 100).

Andmeid koguti mitmetelt sihtplatvormidelt:

• Windows
  — Unity v2018.3.14f1, toimetaja režiim, Mono, .NET Standard 2.0
• macOS
  — Unity v2018.3.14f1, toimetaja režiim, Mono, .NET Standard 2.0
  — Unity v5.6.4p4, toimetaja režiim, Mono, .NET Standard 2.0
• Android
  — Unity v2018.3.14f1, seade jaoks koostamine, Mono, .NET Standard 2.0
• iOS
  — Unity v2018.3.14f1, seade jaoks koostamine, il2cpp, .NET Standard 2.0

Rakendamine

Meil on mitu erinevat viisi juhuslike arvude genereerimiseks. Igaühe jaoks kirjutame eraldi wrapper-klassi, mis peab pakkuma:

1. Võimalust määrata väärtuste vahemik [min/max). See määratakse konstruktoris.
2. Meetod, mis tagastab RND. Tüübina valime float, kuna see on üldisem.
3. Genereerimisviisi nimetus tulemuste märgistamiseks. Mugavuse huvides tagastame väärtuse täieliku klassi nime + meetodi nime, mida RND genereerimiseks kasutatakse.

Alustame abstraktsiooni kuulutamisega, mis esindatakse IRandomGenerator liidese kaudu:

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

        float Generate();
    }
}

Teostus System.Random.Next()

See meetod võimaldab seada väärtuste vahemiku, kuid tagastab täisarve (integer), kuid vajame float. Saame lihtsalt tõlgendada integerit floatiks või laiendada väärtuste vahemikku mõne järgu võrra, kompenseerides neid igal juhuslike arvude genereerimisel. Tulemuseks on midagi sarnast fixed-point'iga antud täpsusega. Kasutame seda varianti, kuna see on lähemal tõelisele float väärtusele.

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

Teostus System.Random.NextDouble()

Siin on fikseeritud väärtuste vahemik [0; 1). Selle projitseerimiseks antud konstruktoris kasutame lihtsat aritmeetikat: 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;
    }
}

Teostus UnityEngine.Random.Range()

See staatilise klassi UnityEngine.Random meetod võimaldab seada väärtuste vahemiku ja tagastab float tüüpi juhuslikud arvud. Täiendavateks teisendusteks ei ole vaja.

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

Teostus UnityEngine.Random.value

Staatilise klassi UnityEngine.Random property value tagastab float tüüpi juhusliku arvu fikseeritud väärtuste vahemikust [0; 1). Projitseerime selle antud vahemikku sama viisi kasutades, nagu teostuses System.Random.NextDouble().

kasutades 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() rakendamine

NextFloat() meetod klassis Unity.Mathematics.Random tagastab float tüüpi juhusliku arvu ning võimaldab määrata väärtuste vahemikku. Oluline on, et iga Unity.Mathematics.Random eksemplar tuleb initsialiseerida teatud seed'iga — nii vältime korduvate järjestuste genereerimist.

kasutades 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 rakendamine

Mitmed IRandomGenerator rakendused on valmis. Järgmine samm on genereerida järjestused ja salvestada saadud andmestik töötlemiseks. Selleks loome Unitys stseeni ja väikese MainController skripti, mis täidab kogu vajaliku töö ning vastutab UI-ga suhtlemise eest.

Määrame andmestiku suuruse ja juhuslike arvude vahemiku, samuti loome meetodi, mis tagastab seadistatud ja tööks valmis generaatorite massiivi.

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

        ...
    }
}

Nüüd loome andmestiku. Antud juhul toimub andmete genereerimine koos tulemuste salvestamisega tekstivoogu (csv formaadis). Iga IRandomGenerator väärtuste jaoks määratakse eraldi veerg, samas kui esimene rida sisaldab generaatori nime.

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

        ...
    }
}

On jäänud kutsuda GenerateCsvDataSet meetod ja salvestada tulemus faili või saata andmed otse võrgus lõpuseadmest vastuvõtjale. 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();
            }
        }

        ...
    }
}

Projekti lähtekoodid asuvad GitLab.

tulemused näitasid ainult nelja ebaolulise koodibloki kattuvust, mis olid tingitud POSIX ja ANSI C nõuetest.

Imesid ei juhtunud. Saime seda, mida ootasime — igas olukorras ühtlane jaotus ilma igasuguste vandenõudeta. Eraldi graafikute lisamine platvormide kaupa ei tundu mõttekas — need kõik näitavad enam-vähem samu tulemusi.

Tegelik olukord on järgmine:


Seeriate visualiseerimine tasandil kõikidest viiest genereerimisviisist:


Ja 3D visualiseerimine. Jätsin alles ainult System.Random.Next() tulemuse, et mitte toota hulk sama sisu.


Eelnevas sissejuhatuses jutustatud lugu UnityEngine.Random normaalsest jaotusest ei kordunud: kas see oli algusest peale vale või on midagi mootoris muutunud. Kuid nüüd oleme kindlad.

Allikas: habr.com