ProHoster > Blogs > interneta ziņas > BlessRNG vai RNG godīguma pārbaude

BlessRNG vai RNG godīguma pārbaude

BlessRNG vai RNG godīguma pārbaude

Spēļu izstrādē bieži kaut kas jāsaista ar nejauŔību: Unity Å”im nolÅ«kam ir savs Random, un paralēli tam ir System.Random. Kādreiz vienā no projektiem man radās iespaids, ka abi varētu darboties savādāk (lai gan vajadzētu vienmērÄ«gu sadalÄ«jumu).

Tad viņi neiedziļinājās detaļās - pietika ar pāreju uz System.Random visas problēmas. Tagad mēs nolēmām to izpētÄ«t sÄ«kāk un veikt nelielu izpēti: cik ā€œneobjektÄ«viā€ vai paredzami ir RNG un kuru izvēlēties. Turklāt vairāk nekā vienu reizi esmu dzirdējis pretrunÄ«gus viedokļus par viņu ā€œgodÄ«gumuā€ - mēģināsim izdomāt, kā Ä«stie rezultāti ir salÄ«dzināmi ar deklarētajiem.

ÄŖsa izglÄ«tÄ«bas programma jeb RNG patiesÄ«bā ir RNG

Ja esat jau iepazinies ar nejauÅ”o skaitļu Ä£eneratoriem, varat nekavējoties pāriet uz sadaļu ā€œPārbaudeā€.

NejauÅ”ie skaitļi (RN) ir skaitļu virkne, kas Ä£enerēta, izmantojot kādu nejauÅ”u (haotisku) procesu, kas ir entropijas avots. Tas ir, Ŕī ir secÄ«ba, kuras elementus savstarpēji nesaista neviens matemātisks likums ā€“ tiem nav cēloņsakarÄ«bas.

To, kas rada nejauÅ”o skaitļu, sauc par nejauÅ”o skaitļu Ä£eneratoru (RNG). Å Ä·iet, ka viss ir elementāri, bet, ja mēs pārejam no teorijas uz praksi, tad patiesÄ«bā nav tik vienkārÅ”i ieviest programmatÅ«ras algoritmu Ŕādas secÄ«bas Ä£enerÄ“Å”anai.

Iemesls ir tāda paÅ”a haosa neesamÄ«ba mÅ«sdienu plaÅ”a patēriņa elektronikā. Bez tā nejauÅ”ie skaitļi pārstāj bÅ«t nejauÅ”i, un to Ä£enerators pārvērÅ”as par parastu acÄ«mredzami definētu argumentu funkciju. Vairākām specialitātēm IT jomā tā ir nopietna problēma (piemēram, kriptogrāfija), bet citām ir pilnÄ«gi pieņemams risinājums.

Ir nepiecieÅ”ams uzrakstÄ«t algoritmu, kas atgrieztu, lai arÄ« ne Ä«sti nejauÅ”us skaitļus, bet pēc iespējas tuvāk tiem - tā sauktos pseidogadÄ«juma skaitļus (PRN). Algoritmu Å”ajā gadÄ«jumā sauc par pseidogadÄ«juma skaitļu Ä£eneratoru (PRNG).

PRNG izveidei ir vairākas iespējas, taču tālāk norādītais būs aktuāls ikvienam:

  1. NepiecieÅ”amÄ«ba pēc iepriekŔējas inicializācijas.

    PRNG nav entropijas avota, tāpēc pirms lietoÅ”anas tam ir jāpieŔķir sākotnējais stāvoklis. Tas ir norādÄ«ts kā skaitlis (vai vektors) un tiek saukts par sēklu (izlases sēkla). Bieži vien procesora pulksteņa skaitÄ«tājs vai sistēmas laika skaitliskais ekvivalents tiek izmantots kā sākums.

  2. Secības reproducējamība.

    PRNG ir pilnÄ«bā determinēta, tāpēc inicializācijas laikā norādÄ«tā sēkla unikāli nosaka visu turpmāko skaitļu secÄ«bu. Tas nozÄ«mē, ka atseviŔķs PRNG, kas inicializēts ar vienu un to paÅ”u sēklu (dažādos laikos, dažādās programmās, dažādās ierÄ«cēs), Ä£enerēs to paÅ”u secÄ«bu.

Ir 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 normāls sadalÄ«jums vai vienmērÄ«gs sadalÄ«jums.
BlessRNG vai RNG godīguma pārbaude
Normāls sadalījums (pa kreisi) un vienmērīgs sadalījums (pa labi)

Pieņemsim, ka mums ir godÄ«gs kauliņŔ ar 24 malām. Ja jÅ«s to izmetat, varbÅ«tÄ«ba iegÅ«t vienu bÅ«s vienāda ar 1/24 (tāda pati kā varbÅ«tÄ«ba iegÅ«t jebkuru citu skaitli). Izdarot daudz metienu un piefiksējot rezultātus, pamanÄ«sit, ka visas malas izkrÄ«t aptuveni vienādi. BÅ«tÄ«bā Å”o matricu var uzskatÄ«t par RNG ar vienmērÄ«gu sadalÄ«jumu.

Ko darÄ«t, ja jÅ«s uzreiz izmetat 10 no Å”iem kauliņiem un saskaitāt kopējos punktus? Vai tam tiks saglabāta vienveidÄ«ba? Nē. Visbiežāk summa bÅ«s tuvu 125 punktiem, tas ir, kādai vidējai vērtÄ«bai. Un rezultātā jau pirms metiena veikÅ”anas var aptuveni novērtēt nākotnes rezultātu.

Iemesls ir tāds, ka ir vislielākais kombināciju skaits, lai iegÅ«tu vidējo punktu skaitu. Jo tālāk no tā, jo mazāk kombināciju - un attiecÄ«gi mazāka ir zaudējuma iespējamÄ«ba. Ja Å”ie dati ir vizualizēti, tie neskaidri atgādinās zvana formu. Tāpēc ar zināmu stiepÅ”anos 10 kauliņu sistēmu var saukt par RNG ar normālu sadalÄ«jumu.

Vēl viens piemērs, tikai Å”oreiz lidmaŔīnā ā€“ Å”auÅ”ana mērÄ·Ä«. Šāvējs bÅ«s RNG, kas Ä£enerē skaitļu pāri (x, y), kas tiek parādÄ«ts diagrammā.
BlessRNG vai RNG godīguma pārbaude
PiekrÄ«tiet, ka opcija kreisajā pusē ir tuvāk reālajai dzÄ«vei - tas ir RNG ar normālu sadalÄ«jumu. Bet, ja jums ir nepiecieÅ”ams izkaisÄ«t zvaigznes tumŔās debesÄ«s, tad pareizākais variants, kas iegÅ«ts, izmantojot RNG ar vienmērÄ«gu sadalÄ«jumu, ir labāk piemērots. Parasti izvēlieties Ä£eneratoru atkarÄ«bā no veicamā uzdevuma.

Tagad parunāsim par PNG secÄ«bas entropiju. Piemēram, ir secÄ«ba, 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 ir Ŕie skaitļi no pirmā acu uzmetiena? Sāksim ar sadalījuma pārbaudi.
BlessRNG vai RNG godīguma pārbaude
Tas izskatās gandrÄ«z viendabÄ«gs, bet, ja lasāt divu skaitļu secÄ«bu un interpretējat tos kā koordinātas plaknē, jÅ«s iegÅ«stat Å”o:
BlessRNG vai RNG godīguma pārbaude
Raksti kļūst skaidri redzami. Un tā kā secÄ«bā esoÅ”ie dati ir sakārtoti noteiktā veidā (tas ir, tiem ir zema entropija), tas var izraisÄ«t Å”o ā€œneobjektivitātiā€. 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 lidmaŔīnā:
BlessRNG vai RNG godīguma pārbaude
Apskatīsim apjomu (lasīt trīs ciparus vienlaikus):
BlessRNG vai RNG godīguma pārbaude
Un atkal modeļi. Vairs nav iespējams izveidot vizualizāciju četrās dimensijās. Taču modeļi var pastāvēt gan Å”ajā dimensijā, gan lielākās.

Kriptogrāfijā, kur PRNG tiek izvirzÄ«tas visstingrākās prasÄ«bas, Ŕāda situācija ir kategoriski nepieņemama. Tāpēc to kvalitātes novērtÄ“Å”anai ir izstrādāti Ä«paÅ”i algoritmi, kurus mēs tagad neskarsim. Tēma ir plaÅ”a un ir pelnÄ«jusi atseviŔķu rakstu.

TestēŔana

Ja mēs kaut ko nezinām droÅ”i, tad kā ar to strādāt? Vai ir vērts Ŕķērsot ceļu, ja nezināt, kurÅ” luksofors to atļauj? Sekas var bÅ«t dažādas.

Tas pats attiecas uz bēdÄ«gi slaveno nejauŔību VienotÄ«bā. Ir labi, ja dokumentācija atklāj nepiecieÅ”amās detaļas, bet raksta sākumā minētais stāsts noticis tieÅ”i vēlamās specifikas trÅ«kuma dēļ.

Un, ja jÅ«s nezināt, kā rÄ«ks darbojas, jÅ«s nevarēsit to pareizi izmantot. Kopumā ir pienācis laiks pārbaudÄ«t un veikt eksperimentu, lai beidzot pārliecinātos vismaz par izplatÄ«Å”anu.

Risinājums bija vienkārÅ”s un efektÄ«vs ā€“ vāc statistiku, iegÅ«sti objektÄ«vus datus un apskati rezultātus.

Studiju priekŔmets

Ir vairāki veidi, kā Ä£enerēt nejauÅ”us skaitļus Unity ā€” 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ē dubultas precizitātes skaitļus diapazonā no [0; 1).
  3. UnityEngine.Random.Range(). Ä¢enerē atseviŔķus precizitātes skaitļus (peld) noteiktā vērtÄ«bu diapazonā.
  4. UnityEngine.Random.value. Ä¢enerē atseviŔķus precizitātes skaitļus (peld) diapazonā no [0; 1).
  5. VienotÄ«ba.Matemātika.Random.NextFloat(). Daļa no jaunās VienotÄ«bas.Matemātikas bibliotēkas. Ä¢enerē atseviŔķus precizitātes skaitļus (peld) noteiktā vērtÄ«bu diapazonā.

Gandrīz visur dokumentācijā tika norādīts vienmērīgs sadalījums, izņemot UnityEngine.Random.value (kur sadalījums nebija norādīts, bet pēc analoģijas ar UnityEngine.Random.Range() uniformu arī bija paredzēts) un Unity.Mathematics.Random. .NextFloat() (kur pamats ir xorshift algoritms, kas nozīmē, ka atkal jāgaida vienmērīgs sadalījums).

Pēc noklusējuma gaidāmie rezultāti tika uzskatīti par tādiem, kas norādīti dokumentācijā.

Metodoloģija

Mēs uzrakstÄ«jām nelielu lietojumprogrammu, kas Ä£enerēja nejauÅ”u skaitļu secÄ«bas, izmantojot katru no piedāvātajām metodēm, un saglabāja rezultātus turpmākai apstrādei.

Katras secības garums ir 100 000 skaitļu.
NejauŔo skaitļu diapazons ir [0, 100).

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

  • Windows
    ā€” Unity v2018.3.14f1, redaktora režīms, mono, .NET standarts 2.0
  • macOS
    ā€” Unity v2018.3.14f1, redaktora režīms, mono, .NET standarts 2.0
    ā€” Unity v5.6.4p4, redaktora režīms, mono, .NET standarts 2.0
  • android
    ā€” Unity v2018.3.14f1, bÅ«vējums katrai ierÄ«cei, Mono, .NET standarts 2.0
  • iOS
    ā€” Unity v2018.3.14f1, bÅ«vējums katrai ierÄ«cei, il2cpp, .NET standarts 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 iesaiņojuma klasi, kurā bÅ«tu jānorāda:

  1. Iespēja iestatīt vērtību diapazonu [min/max). Tiks iestatīts caur konstruktoru.
  2. MF atgrieÅ”anas metode. Kā veidu izvēlēsimies pludiņu, jo tas ir vispārÄ«gāks.
  3. Rezultātu atzÄ«mÄ“Å”anas Ä£enerÄ“Å”anas metodes nosaukums. ĒrtÄ«bas labad mēs kā vērtÄ«bu atgriezÄ«sim pilnu klases nosaukumu + MF Ä£enerÄ“Å”anai izmantotās metodes nosaukumu.

Vispirms deklarēsim abstrakciju, ko attēlo IRandomGenerator interfeiss:

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

        float Generate();
    }
}

System.Random.Next() ievieŔana

Å Ä« metode ļauj iestatÄ«t vērtÄ«bu diapazonu, taču tā atgriež veselus skaitļus, taču ir nepiecieÅ”ami pludiņi. JÅ«s varat vienkārÅ”i interpretēt veselu skaitli kā pludiņu vai arÄ« paplaÅ”ināt vērtÄ«bu diapazonu par vairākām kārtām, kompensējot tos ar katru vidējā diapazona paaudzi. Rezultāts bÅ«s kaut kas lÄ«dzÄ«gs fiksētam punktam ar noteiktu precizitātes secÄ«bu. Mēs izmantosim Å”o opciju, jo tā ir tuvāk reālajai peldoÅ”ajai 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ēts vērtÄ«bu diapazons [0; 1). Lai to projicētu uz konstruktorā norādÄ«to, mēs 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

Šī UnityEngine.Random statiskās klases metode ļauj iestatīt vērtību diapazonu un atgriež pludiņa veidu. Jums nav jāveic nekādas papildu transformācijas.

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 vērtÄ«bas rekvizÄ«ts.Random atgriež peldoÅ”o tipu no fiksēta vērtÄ«bu diapazona [0; 1). Projicēsim to noteiktā diapazonā tādā paŔā veidā 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

Klases Unity.Mathematics.Random metode NextFloat() atgriež peldoŔā komata tipa peldoÅ”o punktu un ļauj norādÄ«t vērtÄ«bu diapazonu. VienÄ«gā nianse ir tā, ka katrs Unity.Mathematics.Random gadÄ«jums bÅ«s jāinicializē ar kādu sēklu - tādā veidā mēs izvairÄ«simies no atkārtotu secÄ«bu Ä£enerÄ“Å”anas.

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

Ir gatavas vairākas IRandomGenerator implementācijas. Pēc tam jums ir jāģenerē secÄ«bas un jāsaglabā iegÅ«tā datu kopa apstrādei. Lai to izdarÄ«tu, Unity izveidosim ainu un nelielu MainController skriptu, kas veiks visu nepiecieÅ”amo darbu un vienlaikus bÅ«s atbildÄ«gs par mijiedarbÄ«bu ar UI.

Iestatīsim datu kopas lielumu un MF vērtību diapazonu, kā arī iegūsim metodi, kas atgriež konfigurētu un darbam 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 izveidosim datu kopu. Å ajā gadÄ«jumā datu Ä£enerÄ“Å”ana tiks apvienota ar rezultātu ierakstÄ«Å”anu teksta straumē (csv formātā). Lai saglabātu katra IRandomGenerator vērtÄ«bas, tiek pieŔķirta atseviŔķa 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 GenerateCsvDataSet metodi un saglabāt rezultātu failā vai nekavējoties pārsūtīt datus pa tīklu 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 plkst GitLab.

rezultātus

Nekāds brÄ«nums nenotika. Viņi gaidÄ«ja to, ko viņi ieguva - visos gadÄ«jumos vienmērÄ«gu izplatÄ«Å”anu bez sazvērestÄ«bas mājiena. Es neredzu jēgu platformām ievietot atseviŔķus grafikus - tie visi parāda aptuveni vienādus rezultātus.

Realitāte ir Ŕāda:
BlessRNG vai RNG godīguma pārbaude

Sekvenču vizualizācija plaknē no visām piecām Ä£enerÄ“Å”anas metodēm:
BlessRNG vai RNG godīguma pārbaude

Un vizualizācija 3D formātā. Es atstāŔu tikai System.Random.Next() rezultātu, lai neradītu identisku saturu.
BlessRNG vai RNG godīguma pārbaude

Ievadā izstāstītais stāsts par UnityEngine.Random normālu sadalījumu neatkārtojās: vai nu tas sākotnēji bija kļūdains, vai arī pēc tam dzinējā kaut kas ir mainījies. Bet tagad mēs esam pārliecināti.

Avots: www.habr.com

Pievieno komentāru