BlessRNG või kontrollime RNG ausust

Mängude arenduses on tihti vajalik seostada midagi juhuslikkusega: Unity'l on selleks oma Random, samas eksisteerib paralleelselt ka System.Random. Ajal, mil töötasin ühel projektil, tekkis mul mulje, et mõlemad võivad toimida erinevalt (kuigi nad peaksid omama ühtlast jaotust).

Siis ei süüvinud me detailidesse — piisav oli see, et üleminek System.Randomile lahendas kõik probleemid. Nüüd otsustasime süveneda ja teha väikese uurimuse: kui palju on RNG-d "eelistatud" või ettearvatavad ning millist valida. Eriti kuna olen korduvalt kuulnud vastuolulisi arvamusi nende "aususe" kohta — püüame välja selgitada, kuidas reaalsed tulemused seonduvad lubatutega.

Lühike sissejuhatus või RNG on tegelikult GPSC

Kui olete juba tuttav juhuslike arvude generaatoritega, võite kohe edasi liikuda jaotisse "Testimine".

Juhuslikud numbrid (JN) on numbrite jada, mis genereeritakse mõne juhusliku (kaootilise) protsessi, entropia allika abil. See tähendab, et tegemist on sellise jadaga, mille elemendid ei ole omavahel seotud mingisuguse matemaatilise seadusega – neil puudub põhjuslik seos.

Seda, mis loob JN, nimetatakse juhuslike numbrite generaatoriks (JNG). Näiliselt on kõik elementaarne, kuid kui teooriast praktikas liikuda, siis tegelikult ei ole sellise jada genereerimise programmialgoritmi rakendamine mitte nii lihtne.

Probleem peitub kaasaegse tarbielektroonika juhuslikkuse puudumises. Ilma selleta lõpetavad juhuslikud numbrid juhuslikkuse ja nende generaator muutub tavaliseks funktsiooniks eelnevalt määratletud argumentide suhtes. Teatud IT-erialade puhul on see tõsine probleem (näiteks krüptograafias), samas kui teiste jaoks on täiesti vastuvõetav lahendus.

Tuleb kirjutada algoritm, mis tagastaks ehk mitte tõeliselt juhuslikud numbrid, kuid maksimaalselt lähedased neile — nn pseudojuhuslikud numbrid (PJ). Sellist algoritmi nimetatakse pseudojuhuslike numbrite generaatoriks (PJG).

On olemas mitmeid võimalusi PJG loomiseks, kuid kõigile on oluline järgmine:

1. Eelneva initsialiseerimise vajadus.

   PJG-l puudub entropiaallikas, seega peab enne kasutamist sellele näitama algseisundi. See määratakse numbrina (või vektorina) ja seda nimetatakse seeme (seed, random seed). Sageli on seemena kasutusel protsessori taktsükli loendur või süsteemi aja numbriline ekvivalent.

2. Järjestuse reprodutseeritavus.

   PJG on täielikult määratud, seega määrab initsialiseerimise ajal antud seeme üheselt kogu tulevase numbriseeria. See tähendab, et eraldi võetud PJG, mis on initsialiseeritud sama seemnega (erinevatel aegadel, erinevates programmides, erinevates seadmetes), genereerib sama järjestuse.

Oluline on teada ka GSHD tõenäosuste jaotust — milliseid numbreid ta genereerib ja millise tõenäosusega. See on enamasti kas normaaljaotus (normal distribution) või ühtlane jaotus (uniform distribution).

Normaaljaotus (vasakul) ja ühtlane jaotus (paremal)

Oletame, et meil on aus mängukuubik, millel on 24 külge. Kui seda visata, siis ühe tulemuse tõenäosus on 1/24 (samuti iga teise numbri tõenäosus). Kui visata palju kordi ja tulemusi kirja panna, siis võib täheldada, et kõik külgedel on umbes sama sagedusega tulemusi. Sisuliselt võib seda mängukuubikut pidada GSHD-ks ühtlase jaotusega.

Kuidas siis, kui visata kohe 10 sellist kuubikut ja arvutada kokkupunktide summa? Kas see säilitab ühtsuse? Ei. Enamasti on summa lähedane 125 punktile, st mingile keskmisele väärtusele. Seega, juba enne viskamist saab tulevast tulemust umbkaudu hinnata.

Põhjus on see, et keskmise skoori saavutamiseks on kõige rohkem kombinatsioone. Mida kaugemal ollakse, seda vähem on kombinatsioone — ja seega ka väiksem tõenäosus esinemiseks. Kui neid andmeid visualiseerida, meenutavad need kaugel kujundit, mis sarnaneb kellakujule. Seetõttu võib natuke venitatuna 10 täringu süsteemi nimetada normaaljaotusega juhuslikuks arvuks.

Veel üks näide, kuid juba tasapinnal — sihtmärkide tulistamine. Sihtmärgi laskuriks on juhuslik arv, mis genereerib paari numbreid (x, y), mis kuvatakse graafikul.

Kokkuleppel, et vasakpoolne variant on rohkem lähedane reaalsusele — see on normaaljaotusega juhuslik arv. Kuid kui on vaja tähti pimedas taevas hajutada, sobib parempoolne variant, mis on saadud ühtlaselt jaotatud juhusliku arvu abil. Üldiselt valige generaator vastavalt ülesandele.

Nüüd räägime PSE jada entropiast. Näiteks on olemas jada, 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, …

Kuidas need numbrid esmapilgul näivad? Alustame jaotuse kontrollimisega.

Need näivad peaaegu ühtlased, kuid kui lugeda järjestust kahte numbrit korraga ja tõlgendada neid koordinaatidena tasandil, siis tuleb välja selline pilt:

Mustrid hakkavad selgelt välja paistma. Kuna andmed järjestuses on teatud viisil korraldatud (st neil on madal entropia), võib see tekitada just seda "ebamugavust". Igatahes ei sobi selline GPСJ koordinaatide genereerimiseks tasandil väga hästi.

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

Taas tundub, et siin on kõik korras isegi tasandil:

Vaadakem ruumis (loeme kolme numbrit korraga):

Ja jälle mustrid. Neli mõõtmetes visualiseerimine ei toimi. Kuid mustrid võivad eksisteerida ka selle mõõtme ja suuremate puhul.

Samal krüptograafial, kus PRNG-dele esitatavad nõuded on kõige rangemad, on selline olukord kategooriliselt vastuvõetamatu. Seetõttu on nende kvaliteedi hindamiseks välja töötatud spetsiaalsed algoritmid, mille kohta me praegu ei räägi. Teema on ulatuslik ja väärib eraldi artiklit.

Testimine

Kui me ei tea midagi kindlalt, kuidas sellega siis ümber käia? Kas on mõtet teed ületada, kui sa ei tea, milline valgusfoori signaal seda lubab? Tagajärjed võivad olla erinevad.

Sama kehtib ka kurikuulsa juhuslikkuse kohta Unitys. Hea on, kui dokumentatsioon toob esile vajalikud üksikasjad, kuid artikli alguses mainitud lugu juhtus just selle puudumise tõttu.

Ilma teadmata, kuidas tööriist töötab, ei saa sa seda õigesti rakendada. Ühesõnaga, on aeg kontrollida ja katsetada, et lõpuks veenduda vähemalt jaotuses.

Lahendus oli lihtne ja efektiivne — koguda statistikat, saada objektiivseid andmeid ja vaadata tulemusi.

Uuringu teema

Unitys on mitmeid viise juhuslike numbrite genereerimiseks — testisime viit.

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

Peaaegu igal pool dokumentatsioonis on märgitud ühtlane jaotumine, välja arvatud UnityEngine.Random.value (kus jaotumist ei ole mainitud, kuid sarnaselt UnityEngine.Random.Range() oodati samuti ühtlast jaotumist) ja Unity.Mathematics.Random.NextFloat() (kus põhineb algoritmil xorshift, seega tuleb jälle oodata ühtlast jaotumist).

Vaikimisi võeti oodatud tulemused, mis on dokumentatsioonis märgitud.

Metoodika

Kirasime väikese rakenduse, mis genereeris juhuslike arvude järjestusi iga esindatud meetodi abil ja salvestas tulemused edasiseks töötlemiseks.

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

Andmed koguti mitmelt sihtplatvormilt:

• Windows
  — Unity v2018.3.14f1, redigeerimise režiim, Mono, .NET Standard 2.0
• macOS
  — Unity v2018.3.14f1, redigeerimise režiim, Mono, .NET Standard 2.0
  — Unity v5.6.4p4, redigeerimise režiim, Mono, .NET Standard 2.0
• Android
  — Unity v2018.3.14f1, seadmele versioon, Mono, .NET Standard 2.0
• iOS
  — Unity v2018.3.14f1, seadmele versioon, il2cpp, .NET Standard 2.0

Rakendus

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

1. Võimalust määrata väärtuste vahemik [min/max). See määratakse konstruktoris.
2. Meetod, mis tagastab juhusliku arvu. Tüübiks valime float, kuna see on üldisema iseloomuga.
3. Generatsiooni meetodi nimetus tulemuste märgistamiseks. Mugavuse huvides tagastame väärtusena klassi täisnime + meetodi nime, mida juhusliku arvu genereerimiseks kasutatakse.

Alustame abstraktsiooni väljakuulutamisest, mille esindab IRandomGenerator liides:

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

        float Generate();
    }
}

Realiseerimine System.Random.Next()

See meetod võimaldab määrata väärtuste vahemikku, kuid tagastab täisarvud (integer), samas kui vajalikud on ujukomaarvud (float). Üks võimalus on tõlgendada täisarve kui ujukomaarve, teine võimalus on laiendada väärtuste vahemikku mitme järjekorra võrra, kompenseerides neid iga kord juhuslikku arvu genereerimisel. Saame midagi sarnast fikseeritud punktiga, millel on määratud täpsus. Kasutame seda varianti, kuna see on lähemal tõelise ujukomaarvulise väärtuse mõistele.

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

Siin on fikseeritud väärtuste vahemik [0; 1). Et projitseerida see konstruktoris määratud vahemikule, kasutame lihtsat aritmeetikat: X * (max − min) + min.

kasutades System;

nimeserver RandomDistribution
{
    avalik klass SystemDoubleRandomGenerator : IRandomGenerator
    {
        privaatne lõplik Random _generator = uus Random();
        privaatne lõplik double _factor;
        privaatne lõplik float _min;


        avalik string Nimi => "System.Random.NextDouble()";


        public SystemDoubleRandomGenerator(float min, float max)
        {
            _factor = max - min;
            _min = min;
        }


        avalik float Generate() => (float)(_generator.NextDouble() * _factor) + _min;
    }
}

UnityEngine.Random.Range() rakendamine

See staatilise klassi UnityEngine.Random meetod võimaldab määrata väärtuste vahemiku ja tagastab float tüüpi arvu. Täiendavaid teisendusi tegema ei pea.

kasutades UnityEngine;

nimeserver RandomDistribution
{
    avalik klass UnityRandomRangeGenerator : IRandomGenerator
    {
        privaatne lõplik float _min;
        privaatne lõplik float _max;


        avalik string Nimi => "UnityEngine.Random.Range()";


        public UnityRandomRangeGenerator(float min, float max)
        {
            _min = min;
            _max = max;
        }


        avalik float Generate() => Random.Range(_min, _max);
    }
}

UnityEngine.Random.value rakendamine

Staatilise klassi UnityEngine.Random omadus value tagastab float tüüpi arvu fikseeritud väärtuste vahemikust [0; 1). Projekteerime selle antud vahemikku samamoodi nagu System.Random.NextDouble() rakendamisel.

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() rakendus

Unity.Mathematics.Random.NextFloat() meetod tagastab float tüüpi juhusliku arvu ja võimaldab määrata väärtuste vahemiku. Ainus nüanss on see, et iga Unity.Mathematics.Random eksemplar tuleb initsialiseerida mõne seed'iga — nii saame vältida korduvate jadade genereerimist.

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 rakendus

Mitmed IRandomGenerator'i rakendused on valmis. Edasi tuleks genereerida järjestusi ja salvestada tulemuste andmestik töötlemiseks. Selle jaoks loome Unity's stseeni ja väikese skripti MainController, mis teostab kogu vajaliku töö ja vastutab samal ajal UI-ga suhtlemise eest.

Määrame andmestiku suuruse ja juhuslike arvude väärtuste vahemiku ning loome meetodi, mis tagastab töötamiseks seadistatud ja 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 koosneb andmete genereerimine tulemuste kirjutamisest tekstivoolu (csv-formaadis). Iga IRandomGenerator'i väärtuste salvestamiseks on ettenähtud oma 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();
            }
        }

        ...
    }
}

Peab ainult kutsuda välja meetod GenerateCsvDataSet ja salvestada tulemus faili või edastada andmed otse võrgus lõppseadmest 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 on saadaval aadressil GitLab.

Tulemused

Ihme ei juhtunud. Ootused ja saadud tulemused olid samad — kõigis juhtumites ühtlane jaotus ilma mingite vandenõude märkideta. Eraldi graafikute lisamine platvormide kaupa ei tundu mõistlik, kuna need näitavad kõik enam-vähem samu tulemusi.

Tõde on selline:


Seeriate visualiseerimine tasapinnal kõigi viie genereerimise viisi puhul:


Ja visualiseerimine 3D-s. Jätan alles ainult System.Random.Next() tulemuse, et mitte toota liiga palju sarnast sisu.


Sissejuhatuses räägitud normaaljaotuse lugu UnityEngine.Random kohta ei kordunud: kas see oli algselt vale või on mootoris sellest ajast midagi muutunud. Kuid nüüd oleme kindlad.

Allikas: habr.com