BlessRNG või RNG õigluse kontrollimine

Mänguarenduses tuleb sageli midagi juhuslikkusega siduda: Unityl on selleks oma Random ja sellega paralleelselt System.Random. Kunagi ammu ühe projekti puhul jäi mulje, et mõlemad võiksid toimida erinevalt (kuigi nende jaotus peaks olema ühtlane).

Siis nad detailidesse ei laskunud - piisas sellest, et üleminek süsteemile System.Random parandas kõik probleemid. Nüüd otsustasime seda üksikasjalikumalt uurida ja teha väikese uuringu: kui "kallutatud" või prognoositavad on RNG-d ja millist neist valida. Veelgi enam, olen korduvalt kuulnud vastakaid arvamusi nende "aususe" kohta - proovime välja mõelda, kuidas tegelikud tulemused võrreldavad deklareeritud tulemustega.

Lühiharidusprogramm ehk RNG on tegelikult RNG

Kui olete juhuslike numbrite generaatoritega juba tuttav, võite kohe minna jaotisse "Testimine".

Juhuslikud arvud (RN) on arvude jada, mis on genereeritud mõne juhusliku (kaootilise) protsessi abil, mis on entroopia allikas. See tähendab, et see on jada, mille elemendid ei ole omavahel seotud ühegi matemaatilise seadusega – neil pole põhjuse-tagajärje seost.

Juhusliku arvu loomist nimetatakse juhuslike arvude generaatoriks (RNG). Näib, et kõik on elementaarne, kuid kui liigume teooriast praktikasse, siis tegelikult pole sellise jada genereerimiseks tarkvaraalgoritmi rakendamine nii lihtne.

Põhjus peitub selles, et kaasaegses tarbeelektroonikas puudub sama kaos. Ilma selleta lakkavad juhuslikud arvud olemast juhuslikud ja nende generaator muutub ilmselgelt määratletud argumentide tavaliseks funktsiooniks. Mitmete IT-valdkonna erialade jaoks on see tõsine probleem (näiteks krüptograafia), kuid teiste jaoks on täiesti vastuvõetav lahendus.

On vaja kirjutada algoritm, mis tagastaks, ehkki mitte päris juhuslikud arvud, vaid neile võimalikult lähedased - nn pseudojuhuslikud numbrid (PRN). Sel juhul nimetatakse algoritmi pseudojuhuslike arvude generaatoriks (PRNG).

PRNG loomiseks on mitu võimalust, kuid järgmine on asjakohane kõigile:

1. Eelinitsialiseerimise vajadus.

   PRNG-l pole entroopia allikat, seega tuleb enne kasutamist anda sellele algseisund. See on määratud arvuna (või vektorina) ja seda nimetatakse seemneks (juhuslik seeme). Sageli kasutatakse seemnena protsessori kella loendurit või süsteemiaja numbrilist ekvivalenti.

2. Järjestuste reprodutseeritavus.

   PRNG on täielikult deterministlik, seega määrab lähtestamise käigus määratud seeme üheselt kogu tulevase numbrijada. See tähendab, et sama seemnega (eri aegadel, erinevates programmides, erinevates seadmetes) lähtestatud eraldi PRNG genereerib sama jada.

Samuti peate teadma PRNG-d iseloomustavat tõenäosusjaotust – milliseid numbreid see genereerib ja millise tõenäosusega. Enamasti on see kas normaaljaotus või ühtlane jaotus.

Normaaljaotus (vasakul) ja ühtlane jaotus (paremal)

Oletame, et meil on 24 küljega aus. Kui viskate selle ümber, on ühe saamise tõenäosus 1/24 (sama mis tõenäosusega saada mõni muu arv). Kui teete palju viskeid ja fikseerite tulemused, märkate, et kõik servad kukuvad välja ligikaudu sama sagedusega. Põhimõtteliselt võib seda stantsi pidada ühtlase jaotusega RNG-ks.

Mis siis, kui viskad 10 täringut korraga ja loeksid kokku punktid? Kas selle puhul säilib ühtsus? Ei. Kõige sagedamini on see summa 125 punkti lähedal, st mõnele keskmisele väärtusele. Ja tänu sellele saab juba enne viske sooritamist umbkaudu hinnata tulevast tulemust.

Põhjus on selles, et keskmise skoori saamiseks on kõige rohkem kombinatsioone. Mida kaugemal sellest, seda vähem kombinatsioone - ja vastavalt, seda väiksem on kaotuse tõenäosus. Kui need andmed visualiseerida, sarnanevad need ebamääraselt kella kujuga. Seetõttu võib teatud venitusega 10 täringust koosnevat süsteemi nimetada normaaljaotusega RNG-ks.

Veel üks näide, ainult seekord lennukis – sihtmärki laskmine. Tulistaja on RNG, mis genereerib arvude paari (x, y), mis kuvatakse graafikul.

Nõus, et vasakpoolne valik on tegelikule elule lähemal - see on normaaljaotusega RNG. Kuid kui teil on vaja tähti pimedas taevas hajutada, sobib paremini õige valik, mis on saadud ühtlase jaotusega RNG-ga. Üldiselt valige generaator sõltuvalt käsil olevast ülesandest.

Nüüd räägime PNG-jada entroopiast. Näiteks on jada, mis algab järgmiselt:

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 juhuslikud need numbrid esmapilgul on? Alustuseks kontrollime jaotust.

See näeb välja peaaegu ühtlane, kuid kui loete kahe numbri jada ja tõlgendate neid tasapinna koordinaatidena, saate järgmise:

Mustrid muutuvad selgelt nähtavaks. Ja kuna jadas olevad andmed on teatud viisil järjestatud (st neil on madal entroopia), võib see põhjustada just selle "kaldsuse". Vähemalt selline PRNG ei sobi tasapinnal 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 hästi olevat isegi lennukis:

Vaatame mahu järgi (loe kolme numbrit korraga):

Ja jälle mustrid. Neljamõõtmelist visualiseerimist pole enam võimalik konstrueerida. Kuid mustrid võivad eksisteerida nii sellel kui ka suurematel dimensioonidel.

Krüptograafias, kus PRNG-dele esitatakse kõige rangemad nõuded, on selline olukord kategooriliselt vastuvõetamatu. Seetõttu on nende kvaliteedi hindamiseks välja töötatud spetsiaalsed algoritmid, mida me nüüd ei puuduta. Teema on ulatuslik ja väärib eraldi artiklit.

Katsetamine

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

Sama kehtib Unity kurikuulsa juhuslikkuse kohta. Hea, kui dokumentatsioonist selgub vajalikud detailid, kuid artikli alguses mainitud lugu juhtus just soovitud spetsiifika puudumise tõttu.

Ja kui te ei tea, kuidas tööriist töötab, ei saa te seda õigesti kasutada. Üldiselt on kätte jõudnud aeg kontrollida ja läbi viia eksperiment, et lõpuks veenduda vähemalt levitamises.

Lahendus oli lihtne ja tõhus – koguge statistikat, hankige objektiivseid andmeid ja vaadake tulemusi.

Õppeaine

Juhuslike arvude genereerimiseks Unitys on mitu võimalust – testisime viit.

1. Süsteem.Juhuslik.Järgmine(). Genereerib täisarvud antud väärtusvahemikus.
2. System.Random.NextDouble(). Genereerib topelttäpsusega numbrid vahemikus [0; 1).
3. UnityEngine.Random.Range(). Genereerib üksikud täppisarvud (ujuvad) antud väärtusvahemikus.
4. UnityEngine.Random.value. Genereerib üksikud täppisarvud (ujuvad) vahemikus [0; 1).
5. Ühtsus.Matemaatika.Juhuslik.NextFloat(). Osa uuest Unity.Mathematics raamatukogust. Genereerib üksikud täppisarvud (ujuvad) antud väärtusvahemikus.

Peaaegu kõikjal dokumentatsioonis määrati ühtlane jaotus, välja arvatud UnityEngine.Random.value (kus jaotust ei täpsustatud, kuid analoogselt UnityEngine.Random.Range() ühtlust eeldati ka) ja Unity.Mathematics.Random .NextFloat() (kus aluseks on xorshift algoritm, mis tähendab, et jälle tuleb oodata ühtlast jaotust).

Vaikimisi võeti oodatavaid tulemusi dokumentatsioonis määratletutena.

Metoodika

Kirjutasime väikese rakenduse, mis genereeris iga esitatud meetodi abil juhuslike arvude jadad ja salvestas tulemused edasiseks töötlemiseks.

Iga jada pikkus on 100 000 numbrit.
Juhuslike arvude vahemik on [0, 100).

Andmeid koguti mitmelt sihtplatvormilt:

• Windows
  — Unity v2018.3.14f1, redigeerimisrežiim, mono, .NET standard 2.0
• macOS
  — Unity v2018.3.14f1, redigeerimisrežiim, mono, .NET standard 2.0
  — Unity v5.6.4p4, redaktorirežiim, mono, .NET standard 2.0
• Android
  — Unity v2018.3.14f1, ehitamine seadme kohta, Mono, .NET standard 2.0
• iOS
  — Unity v2018.3.14f1, järg seadme kohta, il2cpp, .NET standard 2.0

Реализация

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

1. Võimalus määrata väärtuste vahemik [min/max). Seadistab konstruktori kaudu.
2. MF-i tagastamise meetod. Valime tüübiks ujuki, kuna see on üldisem.
3. Tulemuste märgistamise genereerimismeetodi nimetus. Mugavuse huvides tagastame väärtusena klassi täisnime + MF genereerimiseks kasutatud meetodi nime.

Esiteks deklareerime abstraktsiooni, mida esindab IRandomGeneratori liides:

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

        float Generate();
    }
}

System.Random.Next() juurutamine

See meetod võimaldab teil määrata väärtuste vahemiku, kuid see tagastab täisarvud, kuid ujukid on vajalikud. Täisarvu saate lihtsalt tõlgendada ujuvana või väärtuste vahemikku mitme suurusjärgu võrra laiendada, kompenseerides neid keskvahemiku iga põlvkonnaga. Tulemuseks on midagi kindla täpsusega fikseeritud punkti sarnast. Kasutame seda valikut, kuna see on tegelikule ujuvväärtusele lähemal.

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

Süsteemi System.Random.NextDouble() rakendamine

Siin on fikseeritud väärtuste vahemik [0; 1). Selle projekteerimiseks konstruktoris määratletule 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;
    }
}

UnityEngine.Random.Range() rakendamine

See UnityEngine.Random staatilise klassi meetod võimaldab teil määrata väärtuste vahemikku ja tagastab ujukitüübi. Te ei pea tegema täiendavaid teisendusi.

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 rakendamine

Staatilise klassi UnityEngine.Random väärtusomadus tagastab ujuktüübi fikseeritud väärtusvahemikust [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() rakendamine

Klassi Unity.Mathematics.Random meetod NextFloat() tagastab ujukoma tüüpi ujukoma ja võimaldab määrata väärtusvahemiku. Ainus nüanss on see, et iga Unity.Mathematics.Random eksemplar tuleb lähtestada mõne seemnega – nii väldime 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);
    }
}

MainControlleri juurutamine

Valmis on mitu IRandomGeneratori rakendust. Järgmiseks peate genereerima järjestused ja salvestama saadud andmekogumi töötlemiseks. Selleks loome Unitys stseeni ja väikese MainControlleri skripti, mis teeb ära kogu vajaliku töö ja vastutab samal ajal kasutajaliidese interaktsiooni eest.

Määrame andmestiku suuruse ja MF väärtuste vahemiku ning saame ka meetodi, mis tagastab konfigureeritud ja töö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. Sel juhul kombineeritakse andmete genereerimine tulemuste salvestamisega tekstivoogu (csv-vormingus). Iga IRandomGeneratori väärtuste salvestamiseks eraldatakse oma eraldi veerg ja 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();
            }
        }

        ...
    }
}

Jääb vaid välja kutsuda meetod GenerateCsvDataSet ja tulemus faili salvestada või andmed kohe üle võrgu lõppseadmest vastuvõtvasse serverisse üle kanda.

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 allikad on aadressil GitLab.

Järeldused

Ime ei juhtunud. Nad ootasid seda, mida nad said – kõigil juhtudel ühtlase jaotuse ilma vandenõu vihjeta. Ma ei näe mõtet platvormide jaoks eraldi graafikuid panna – need kõik näitavad ligikaudu samu tulemusi.

Tegelikkus on järgmine:


Jadade visualiseerimine tasapinnal kõigi viie genereerimismeetodi järgi:


Ja visualiseerimine 3D-s. Jätan ainult System.Random.Next() tulemuse, et mitte tekitada hunnikut identset sisu.


Sissejuhatuses jutustatud lugu UnityEngine’i normaaljaotusest. Random ei kordunud: kas see oli alguses vigane või on vahepeal midagi mootoris muutunud. Aga nüüd oleme kindlad.

Allikas: www.habr.com