BlessRNG eða athugaðu RNG fyrir sanngirni

Í leikjaþróun þarf oft að reiða sig á handahófskenndan hátt: Unity hefur sinn eigin Random fyrir þetta og System.Random er til samhliða því. Fyrir löngu síðan, í einu verkefni, fékk ég þá tilfinningu að þessi tvö forrit gætu virkað á ólíkan hátt (þó að þau ættu að hafa einsleita dreifingu).

Við fórum ekki í smáatriði þá — það var nóg til að skipta yfir í System.Random lagaði öll vandamálin. Nú höfum við ákveðið að skoða þetta betur og framkvæma litla rannsókn: hversu „hlutdræg“ eða fyrirsjáanleg eru tilsvörunartölur (RNG) og hvaða tölu á að velja. Þar að auki hef ég heyrt misvísandi skoðanir um „sanngirni“ þeirra oftar en einu sinni — við skulum reyna að átta okkur á því hvernig raunverulegar niðurstöður bera sig saman við fullyrðingarnar.

Stutt kynning á RNG eða er það í raun RNG?

Ef þú ert nú þegar kunnugur slembitöluframleiðendum geturðu farið beint í hlutann „Prófanir“.

Slembitölur (RN) eru talnaraðir sem myndast af tilviljunarkenndu (óreiðukenndu) ferli, uppspretta óreiða. Það er að segja, þær eru talnaraðir þar sem stökin tengjast ekki hvert öðru með neinum stærðfræðilegum lögmálum — þær hafa ekkert orsakatengsl.

Það sem býr til slembitölugjafann (e. slembitölugjafinn, RNG) kallast slembitölugjafi (e. slembitölugjafi). Þótt þetta virðist einfalt, þá leiðir það í ljós að það að beita kenningunni í framkvæmd er ekki svo einfalt að útfæra hugbúnaðarreiknirit til að búa til slíka röð.

Ástæðan liggur í fjarveru þessarar handahófskenndu reglu í nútíma neytendatækni. Án hennar hætta handahófskenndar tölur að vera handahófskenndar og myndunarbúnaður þeirra breytist í einfalda virkni fyrirfram ákveðinna inntaksþátta. Fyrir fjölda upplýsingatæknigreina (til dæmis dulritun) er þetta alvarlegt vandamál, en fyrir aðrar er fullkomlega ásættanleg lausn til.

Við þurfum að skrifa reiknirit sem skilar tölum sem eru ekki sannarlega tilviljunarkenndar, heldur eins nálægt þeim og mögulegt er — svokallaðar sýndarslembitölur (e. pseudorandom numbers (e. PRNGs). Reikniritið í þessu tilfelli kallast sýndarslembitölugjafi (e. pseudorandom number generator, PRNG).

Það eru nokkrir möguleikar á að búa til PRNG, en eftirfarandi mun eiga við um alla:

1. Þörf fyrir foruppsetningar.

   PRNG skortir óreiða, þannig að upphafsástand verður að vera tilgreint áður en það er notað. Þetta upphafsástand er tilgreint sem tala (eða vigur) og kallast fræ (handahófskennt fræ). Hringrásarteljari örgjörvans eða tölulegt jafngildi kerfistíma er oft notaður sem fræ.

2. Endurtekningarhæfni raðar.

   PRNG er algerlega ákvarðandi, þannig að sá fræ sem tilgreindur er við frumstillingu ákvarðar einstakt alla framtíðar talnaröðina. Þetta þýðir að einn PRNG sem er frumstilltur með sama fræi (á mismunandi tímum, í mismunandi forritum, á mismunandi tækjum) mun mynda sömu röðina.

Þú þarft einnig að vita líkindadreifinguna sem einkennir PRNG - hvaða tölur hún mun mynda og með hvaða líkum. Oftast er þetta annað hvort normaldreifing eða einsleit dreifing.

Normaldreifing (vinstri) og einsleit dreifing (hægri)

Segjum sem svo að við höfum sanngjarnan 24-hliða tening. Ef við köstum honum eru líkurnar á að lenda á 1 1/24 (alveg eins og líkurnar á að lenda á hvaða annarri tölu sem er). Ef við köstum mörgum teningum og skráum niðurstöðurnar munum við taka eftir því að allir 24-hliða teningarnir lenda með nokkurn veginn sömu tíðni. Í meginatriðum má líta á þennan tening sem jafndreifðan slembitalnagjafa.

Hvað ef þú kastar 10 slíkum teningum í einu og reiknar út heildarskorið? Mun það helst jafnt? Nei. Oftast verður skorið nálægt 125 stigum, það er einhvers konar meðaltal. Þess vegna geturðu gróflega áætlað framtíðarniðurstöðuna jafnvel áður en þú kastar.

Ástæðan er sú að flestir samsetningar eru til til að ná meðalskorinu. Því lengra frá meðaltalinu, því færri samsetningar eru til — og þar af leiðandi því minni eru líkurnar á kasti. Ef þessum gögnum væri sýnt myndu þau líkjast óljóst bjöllulaga. Þess vegna, með nokkurri teygju, mætti ​​kalla kerfi með 10 teningum normaldreifðan tilfellatölu (RNG).

Annað dæmi, að þessu sinni í flugvél, er að skjóta á skotmark. Skotmaðurinn er slembitölugjafi (RNG) sem býr til par af tölum (x, y) sem birtist á grafi.

Þú munt samþykkja að vinstri útgáfan er nær raunveruleikanum — það er slembitölugjafi með normaldreifingu. En ef þú þarft að dreifa stjörnum yfir dimman himin, þá væri hægri útgáfan, sem fæst með jafndreifðum slembitölugjafi, hentugri. Í stuttu máli, veldu rafal út frá verkefninu sem fyrir liggur.

Nú skulum við ræða um óreiða handahófskenndrar talnaröð. Til dæmis er til röð sem byrjar svona:

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

Hversu tilviljanakenndar eru þessar tölur við fyrstu sýn? Byrjum á að athuga dreifinguna.

Þetta lítur út fyrir að vera einsleitt, en ef þú lest rað tveggja talna og túlkar þær sem hnit á plani, þá færðu þetta:

Mynstur verða greinilega sýnileg. Og þar sem gögnin í röðinni eru raðað á ákveðinn hátt (þ.e. hafa lága óreiða), getur þetta skapað sömu „skekkju“. Að minnsta kosti er slík PRNG ekki mjög hentug til að búa til hnit á plani.

Önnur röð:

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

Það virðist allt vera í lagi hér, jafnvel á sléttu yfirborði:

Skoðum rúmmálið (lesum þrjár tölur):

Og aftur, mynstur. Það er ekki lengur mögulegt að sjá fyrir sér í fjórum víddum. En mynstur geta verið til í þessari vídd og í hærri víddum.

Í dulritunarfræði, þar sem ströngustu kröfur eru gerðar til PRNG-gagna, er slík staða algjörlega óásættanleg. Þess vegna hafa sérstakir reiknirit verið þróaðir til að meta gæði þeirra, sem við munum ekki ræða hér. Efnið er umfangsmikið og réttlætir sérstaka grein.

Prófun

Ef við vitum ekki eitthvað fyrir víst, hvernig getum við þá brugðist við því? Ættum við að fara yfir götuna ef við vitum ekki hvaða umferðarljós leyfa það? Afleiðingarnar geta verið mismunandi.

Það sama á við um hina alræmdu handahófskenndu reglu í Unity. Það er frábært þegar skjölunin veitir nauðsynlegar upplýsingar, en atvikið sem minnst var á í upphafi greinarinnar kom upp einmitt vegna skorts á æskilegri sérstöðu.

Og án þess að vita hvernig tólið virkar er ekki hægt að nota það rétt. Það er því kominn tími til að prófa það og framkvæma tilraun til að vera loksins viss, að minnsta kosti varðandi dreifinguna.

Lausnin var einföld og áhrifarík: safna tölfræði, afla hlutlægra gagna og skoða niðurstöðurnar.

Rannsóknarefni

Það eru nokkrar leiðir til að búa til handahófstölur í Unity — við prófuðum fimm.

1. System.Random.Next(). Býr til heiltölur innan gefins gildabils.
2. System.Random.NextDouble(). Býr til tölur með tvöfaldri nákvæmni á bilinu [0; 1).
3. UnityEngine.Random.Range(). Býr til tölur með einni nákvæmni (fljótandi tölur) innan gefins gildabils.
4. UnityEngine.Random.value. Býr til tölur með einni nákvæmni (float) á bilinu [0; 1).
5. Unity.Mathematics.Random.NextFloat(). Hluti af nýja Unity.Mathematics bókasafninu. Býr til eins nákvæmra fleytitölur innan tiltekins bils.

Næstum alls staðar í skjöluninni var tilgreind einsleit dreifing, fyrir utan UnityEngine.Random.value (þar sem dreifingin er ekki tilgreind, en á hliðstæðu við UnityEngine.Random.Range() var einnig búist við einsleitri dreifingu) og Unity.Mathematics.Random.NextFloat() (sem byggir á xorshift reikniritinu, sem þýðir að aftur ætti að búast við einsleitri dreifingu).

Sjálfgefið er að væntanlegar niðurstöður séu þær sem tilgreindar eru í skjölunum.

Aðferðafræði

Við skrifuðum lítið forrit sem bjó til raðir af handahófskenndum tölum með því að nota hverja af þeim aðferðum sem kynntar voru og geymdi niðurstöðurnar til frekari vinnslu.

Lengd hverrar raðar er 100.000 tölur.
Sviðið fyrir slembitölur er [0, 100].

Gögnum var safnað frá nokkrum markhópum:

• Windows
  — Unity v2018.3.14f1, Ritstjórnarstilling, Mono, .NET Standard 2.0
• MacOS
  — Unity v2018.3.14f1, Ritstjórnarstilling, Mono, .NET Standard 2.0
  — Unity v5.6.4p4, Ritstjórnarstilling, Mono, .NET Standard 2.0
• Android
  — Unity v2018.3.14f1, tækjasmíði, Mono, .NET staðall 2.0
• IOS
  — Unity v2018.3.14f1, tækjasmíði, il2cpp, .NET staðall 2.0

Framkvæmd

Við höfum nokkrar mismunandi leiðir til að búa til slembitölur. Fyrir hverja þeirra munum við skrifa sérstakan umbúðaklasa sem ætti að veita:

1. Möguleiki á að tilgreina gildissvið [lágmark/hámark]. Verður stillt með smiðnum.
2. Aðferð sem skilar tölu. Við veljum float sem gerðina, þar sem hún er almennari.
3. Heiti aðferðarinnar sem notuð er til að merkja niðurstöður. Til þæginda munum við skila fullu klasanafni + nafni aðferðarinnar sem notuð var til að búa til SC sem gildi.

Fyrst skulum við lýsa yfir abstrakt sem verður táknað með IRandomGenerator viðmótinu:

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

        float Generate();
    }
}

Útfærsla á System.Random.Next()

Þessi aðferð gerir þér kleift að tilgreina gildissvið, en hún skilar heiltölum, en fleytitölur eru nauðsynlegar. Þú getur einfaldlega túlkað heiltöluna sem fleytitölu, eða þú getur stækkað gildissviðið um nokkrar stærðargráður og bætt upp fyrir þau í hvert skipti sem tíðnin er mynduð. Þetta mun leiða til einhvers eins og fasts punkts með tiltekinni nákvæmni. Við munum nota þennan valkost, þar sem hann er nær raunverulegu fleytitölu.

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

Útfærsla á System.Random.NextDouble()

Hér er fasta gildissviðið [0; 1). Til að varpa því á það gildi sem tilgreint er í smiðnum notum við einfalda reikningsaðferð: 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;
    }
}

Útfærsla á UnityEngine.Random.Range()

Þessi aðferð í kyrrstæða UnityEngine.Random klasanum gerir þér kleift að tilgreina gildabil og skilar slembitölu af fljótandi gerð. Engin frekari umbreyting er nauðsynleg.

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

Útfærsla á UnityEngine.Random.value

Eiginleikinn `value` í kyrrstöðuklasanum UnityEngine.Random skilar slembitölu af fljótandi gerð úr föstu bili gilda [0; 1]. Við varpum henni á gefið bil á sama hátt og þegar System.Random.NextDouble() er útfært.

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

Útfærsla á Unity.Mathematics.Random.NextFloat()

Aðferðin NextFloat() í Unity.Mathematics.Random klasanum skilar slembitölu af floti og gerir þér kleift að tilgreina gildabil. Eini fyrirvarinn er að hvert tilvik af Unity.Mathematics.Random verður að vera frumstillt með fræi — þetta kemur í veg fyrir að tvíteknar raðir séu myndaðar.

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 útfærsla

Nokkrar útfærslur af IRandomGenerator eru tilbúnar. Næst þurfum við að búa til raðir og vista gagnasafnið til vinnslu. Til að gera þetta munum við búa til sviðsmynd í Unity og lítið MainController forskrift sem mun framkvæma allt nauðsynlegt verk og sjá um samskipti við notendaviðmótið.

Við munum skilgreina stærð gagnasafnsins og tíðnibilið og einnig búa til aðferð sem skilar fylki af stilltum og tilbúnum til notkunar raföllum.

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ú ætlum við að búa til gagnasafn. Í þessu tilfelli verður gagnaöflun sameinuð við að skrifa niðurstöðurnar í textastraum (á CSV sniði). Hver IRandomGenerator mun hafa sinn eigin dálk og fyrsta röðin inniheldur nafn rafallsins.

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

        ...
    }
}

Það eina sem eftir er er að kalla á GenerateCsvDataSet aðferðina og vista niðurstöðuna í skrá, eða flytja gögnin strax yfir netið frá endatækinu til móttökuþjónsins.

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

        ...
    }
}

Heimildir verkefnisins eru staðsettar á GitLab.

Niðurstöður

Það var ekkert kraftaverk. Við fengum það sem við bjuggumst við — einsleita dreifingu í öllum tilvikum, án nokkurrar samsæriskenningar. Ég sé ekki tilganginn í að hengja við aðskilin töflur — þau sýna öll nokkurn veginn sömu niðurstöður.

Raunveruleikinn er þessi:


Sjónræn framsetning raða á plani með öllum fimm kynslóðaraðferðum:


Og þrívíddarsýnileiki. Ég læt aðeins niðurstöðuna úr System.Random.Next() eftir til að forðast að búa til fullt af eins efni.


Sagan sem sögð var í innganginum um normaldreifingu UnityEngine.Random endurtók sig ekki: annað hvort var hún gölluð frá upphafi eða eitthvað í vélinni hefur breyst síðan þá. En nú erum við bjartsýn.

Heimild: www.habr.com