ProHoster > Блог > интернет жаңалықтары > BlessRNG немесе RNG әділдігін тексеру

BlessRNG немесе RNG әділдігін тексеру

BlessRNG немесе RNG әділдігін тексеру

Ойын әзірлеуде жиі кездейсоқтықпен бірдеңені байланыстыру керек: Бірліктің бұл үшін өзінің Random жүйесі бар және онымен қатар System.Random бар. Бір кездері жобалардың бірінде мен екеуі де басқаша жұмыс істей алатындай әсер алдым (бірақ олар біркелкі үлестірілуі керек).

Содан кейін олар егжей-тегжейлі айтылмады - System.Random-қа көшу барлық мәселелерді түзетсе болды. Енді біз оны егжей-тегжейлі қарастырып, кішігірім зерттеу жүргізуді шештік: RNG қаншалықты «біржақты» немесе болжамды және қайсысын таңдау керек. Сонымен қатар, мен олардың «адалдығы» туралы қарама-қайшы пікірлерді бірнеше рет естідім - нақты нәтижелер жарияланған нәтижелермен қалай салыстырылатынын анықтауға тырысайық.

Қысқаша білім беру бағдарламасы немесе RNG шын мәнінде RNG болып табылады

Кездейсоқ сандар генераторларымен бұрыннан таныс болсаңыз, бірден «Тестілеу» бөліміне өтуге болады.

Кездейсоқ сандар (RN) - бұл кейбір кездейсоқ (хаотикалық) процесс, энтропия көзі арқылы құрылған сандар тізбегі. Яғни, бұл элементтер бір-бірімен ешбір математикалық заңмен байланыспаған тізбек – олардың себеп-салдар байланысы жоқ.

Кездейсоқ санды жасайтын нәрсе кездейсоқ сандар генераторы (RNG) деп аталады. Барлығы қарапайым болып көрінеді, бірақ егер теориядан практикаға көшетін болсақ, онда мұндай тізбекті құруға арналған бағдарламалық жасақтама алгоритмін жүзеге асыру оңай емес.

Мұның себебі қазіргі заманғы тұрмыстық электроникадағы бірдей хаостың болмауында. Онсыз кездейсоқ сандар кездейсоқ болуды тоқтатады және олардың генераторы анық анықталған аргументтердің қарапайым функциясына айналады. АТ саласындағы бірқатар мамандықтар үшін бұл күрделі мәселе (мысалы, криптография), бірақ басқалары үшін мүлдем қолайлы шешім бар.

Шынайы кездейсоқ сандар емес, бірақ оларға мүмкіндігінше жақын келетін - жалған кездейсоқ сандар (PRN) деп аталатын алгоритмді жазу керек. Бұл жағдайда алгоритм жалған кездейсоқ сандар генераторы (PRNG) деп аталады.

PRNG құрудың бірнеше нұсқасы бар, бірақ төмендегілер барлығына қатысты болады:

  1. Алдын ала инициализацияның қажеттілігі.

    PRNG-де энтропия көзі жоқ, сондықтан оны қолданар алдында бастапқы күйін беру керек. Ол сан (немесе вектор) ретінде көрсетіледі және тұқым (кездейсоқ тұқым) деп аталады. Көбінесе процессордың сағат санауышы немесе жүйелік уақыттың сандық эквиваленті тұқым ретінде пайдаланылады.

  2. Тізбектің қайталануы.

    PRNG толығымен детерминирленген, сондықтан инициализация кезінде көрсетілген тұқым барлық болашақ сандар тізбегін бірегей түрде анықтайды. Бұл бір тұқыммен (әртүрлі уақытта, әртүрлі бағдарламаларда, әртүрлі құрылғыларда) инициализацияланған бөлек PRNG бірдей реттілік жасайтынын білдіреді.

Сіз сондай-ақ PRNG-ді сипаттайтын ықтималдық үлестірімін білуіңіз керек - ол қандай сандарды және қандай ықтималдықпен жасайды. Көбінесе бұл қалыпты таралу немесе біркелкі таралу.
BlessRNG немесе RNG әділдігін тексеру
Қалыпты таралу (сол жақта) және біркелкі таралу (оң жақта)

Бізде 24 қырлы әділ өлексе бар делік. Егер сіз оны лақтырып тастасаңыз, біреуді алу ықтималдығы 1/24 тең болады (кез келген басқа санды алу ықтималдығымен бірдей). Егер сіз көп лақтырсаңыз және нәтижелерді жазсаңыз, барлық жиектер шамамен бірдей жиілікте құлап кеткенін байқайсыз. Негізінде, бұл матрицаны біркелкі таралуы бар RNG деп санауға болады.

Осы сүйектердің 10-ын бірден лақтырып, жалпы ұпайларды санасаңыз ше? Ол үшін біркелкілік сақталады ма? Жоқ. Көбінесе сома 125 ұпайға жақын болады, яғни орташа мәнге жетеді. Нәтижесінде, лақтыруды жасамас бұрын, сіз болашақ нәтижені шамамен бағалай аласыз.

Себебі, орташа балл алу үшін комбинациялардың ең көп саны бар. Одан неғұрлым алыс болса, соғұрлым аз комбинациялар - және, тиісінше, жоғалту ықтималдығы төмен болады. Егер бұл деректер визуалды түрде көрсетілсе, ол қоңыраудың пішініне анық емес ұқсайды. Сондықтан, біраз созылғанда, 10 сүйектен тұратын жүйені қалыпты таралумен RNG деп атауға болады.

Тағы бір мысал, тек осы жолы ұшақта - нысанаға ату. Атқыш графикте көрсетілген жұп сандарды (x, y) генерациялайтын RNG болады.
BlessRNG немесе RNG әділдігін тексеру
Сол жақтағы опция нақты өмірге жақынырақ екеніне келісіңіз - бұл қалыпты таралу бар RNG. Бірақ егер сізге жұлдыздарды қараңғы аспанда шашырату қажет болса, онда біркелкі таралумен RNG көмегімен алынған дұрыс нұсқа жақсырақ. Жалпы алғанда, генераторды тапсырмаға байланысты таңдаңыз.

Енді PNG тізбегінің энтропиясы туралы сөйлесейік. Мысалы, келесідей басталатын реттілік бар:

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

Бұл сандар бір қарағанда қаншалықты кездейсоқ? Бөлуді тексеруден бастайық.
BlessRNG немесе RNG әділдігін тексеру
Бұл біркелкі болып көрінеді, бірақ егер сіз екі санның тізбегін оқып, оларды жазықтықтағы координаттар ретінде түсінсеңіз, мынаны аласыз:
BlessRNG немесе RNG әділдігін тексеру
Үлгілер анық көрінеді. Ал реттіліктегі деректер белгілі бір ретпен реттелгендіктен (яғни оның энтропиясы төмен), бұл дәл сол «қиғаштықты» тудыруы мүмкін. Кем дегенде, мұндай PRNG жазықтықта координаттарды құру үшін өте қолайлы емес.

Басқа реттілік:

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

Мұнда тіпті ұшақта бәрі жақсы сияқты:
BlessRNG немесе RNG әділдігін тексеру
Көлемді қарайық (бір уақытта үш санды оқыңыз):
BlessRNG немесе RNG әділдігін тексеру
Және тағы да үлгілер. Енді төрт өлшемде визуализацияны құру мүмкін емес. Бірақ үлгілер осы өлшемде және үлкенірек өлшемдерде болуы мүмкін.

PRNG-ге ең қатаң талаптар қойылған криптографияда мұндай жағдайға мүлдем жол берілмейді. Сондықтан олардың сапасын бағалау үшін арнайы алгоритмдер әзірленді, біз қазір оған тоқталмаймыз. Тақырып ауқымды және жеке мақалаға лайық.

Тестілеу

Егер біз бір нәрсені нақты білмесек, онымен қалай жұмыс істеуге болады? Қай бағдаршам рұқсат беретінін білмесеңіз, жолды кесіп өту керек пе? Салдары әртүрлі болуы мүмкін.

Бірліктегі атышулы кездейсоқтық туралы да солай. Құжаттама қажетті мәліметтерді ашса жақсы, бірақ мақаланың басында айтылған оқиға қалаған ерекшеліктің болмауына байланысты болды.

Ал құралдың қалай жұмыс істейтінін білмесеңіз, оны дұрыс пайдалана алмайсыз. Тұтастай алғанда, ең болмағанда тарату туралы сенімді болу үшін экспериментті тексеріп, жүргізу уақыты келді.

Шешім қарапайым және тиімді болды - статистиканы жинау, объективті деректерді алу және нәтижелерді қарау.

Зерттеу пәні

Unity бағдарламасында кездейсоқ сандарды құрудың бірнеше жолы бар - біз бесеуін сынадық.

  1. System.Random.Next(). Берілген мәндер ауқымында бүтін сандарды жасайды.
  2. System.Random.NextDouble(). [0-ден бастап диапазондағы қос дәлдікті сандарды жасайды; 1).
  3. UnityEngine.Random.Range(). Мәндердің берілген ауқымында бір дәлдік сандарды (қалқымалы мәндерді) жасайды.
  4. UnityEngine.Random.value. [0-ден бастап диапазондағы жалғыз дәлдік сандарды (қалқымалы) жасайды; 1).
  5. Unity.Mathematics.Random.NextFloat(). Жаңа Unity.Mathematics кітапханасының бөлігі. Мәндердің берілген ауқымында бір дәлдік сандарды (қалқымалы мәндерді) жасайды.

Құжаттаманың барлық жерінде дерлік UnityEngine.Random.value (тарату көрсетілмеген, бірақ UnityEngine.Random.Range() ұқсастығы бойынша біркелкі күтілген) және Unity.Mathematics.Random қоспағанда, біркелкі бөлу көрсетілген. .NextFloat() (мұндағы The негізі - xorshift алгоритмі, бұл қайтадан біркелкі үлестіруді күту керек дегенді білдіреді).

Әдепкі бойынша күтілетін нәтижелер құжаттамада көрсетілгендей алынды.

Әдістеме

Біз ұсынылған әдістердің әрқайсысын қолдана отырып, кездейсоқ сандар тізбегін құрайтын және одан әрі өңдеу үшін нәтижелерді сақтаған шағын қосымшаны жаздық.

Әрбір тізбектің ұзындығы 100 000 сан.
Кездейсоқ сандар диапазоны [0, 100).

Деректер бірнеше мақсатты платформалардан жиналды:

  • Windows
    — Unity v2018.3.14f1, редактор режимі, моно, .NET Standard 2.0
  • MacOS
    — Unity v2018.3.14f1, редактор режимі, моно, .NET Standard 2.0
    — Unity v5.6.4p4, Редактор режимі, Mono, .NET Standard 2.0
  • Android
    — Unity v2018.3.14f1, әр құрылғыға құрастыру, Mono, .NET Standard 2.0
  • IOS
    — Unity v2018.3.14f1, әр құрылғыға құрастыру, il2cpp, .NET Standard 2.0

Реализация

Бізде кездейсоқ сандарды құрудың бірнеше түрлі әдістері бар. Олардың әрқайсысы үшін біз бөлек орауыш класын жазамыз, ол мыналарды қамтамасыз етуі керек:

  1. Мәндер ауқымын орнату мүмкіндігі [min/max). Конструктор арқылы орнатылады.
  2. MF қайтару әдісі. Түр ретінде қалқымалыны таңдайық, себебі ол жалпылама.
  3. Нәтижелерді белгілеуге арналған генерация әдісінің атауы. Ыңғайлы болу үшін біз мән ретінде сыныптың толық атауын + MF құру үшін қолданылатын әдістің атауын қайтарамыз.

Алдымен, IRandomGenerator интерфейсімен ұсынылатын абстракцияны жариялайық:

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

        float Generate();
    }
}

System.Random.Next() іске асыру

Бұл әдіс мәндер ауқымын орнатуға мүмкіндік береді, бірақ ол бүтін сандарды қайтарады, бірақ қалқымалы мәндер қажет. Сіз жай ғана бүтін санды қалқымалы мән ретінде түсіндіре аласыз немесе мәндер ауқымын ортаңғы диапазонның әрбір буынымен өтей отырып, бірнеше шама ретімен кеңейте аласыз. Нәтиже берілген дәлдік реті бар тұрақты нүкте сияқты нәрсе болады. Біз бұл опцияны қолданамыз, себебі ол нақты қалқымалы мәнге жақынырақ.

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() іске асыру

Мұнда мәндердің бекітілген диапазоны [0; 1). Оны конструкторда көрсетілгенге проекциялау үшін қарапайым арифметиканы қолданамыз: 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() іске асыру

UnityEngine.Random статикалық класының бұл әдісі мәндер ауқымын орнатуға мүмкіндік береді және қалқымалы түрді қайтарады. Сізге қосымша түрлендірулер жасаудың қажеті жоқ.

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 іске асыру

UnityEngine.Random статикалық класының мән қасиеті бекітілген мәндер ауқымынан қалқымалы түрді қайтарады [0; 1). Оны 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() іске асыру

Unity.Mathematics.Random класының NextFloat() әдісі float түріндегі өзгермелі нүктені қайтарады және мәндер ауқымын көрсетуге мүмкіндік береді. Жалғыз нюанс мынада, Unity.Mathematics.Random бағдарламасының әрбір данасы кейбір тұқыммен инициализациялануы керек - осылайша біз қайталанатын тізбектерді генерациялаудан аулақ боламыз.

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 іске асыру

IRandomGenerator бірнеше іске асыру дайын. Әрі қарай, реттіліктерді жасап, алынған деректер жинағын өңдеу үшін сақтау керек. Мұны істеу үшін біз Unity бағдарламасында барлық қажетті жұмыстарды орындайтын және сонымен бірге UI-мен өзара әрекеттесу үшін жауапты болатын көрініс пен шағын MainController сценарийін жасаймыз.

Деректер жинағының өлшемін және MF мәндерінің ауқымын орнатайық, сонымен қатар конфигурацияланған және жұмысқа дайын генераторлар массивін қайтаратын әдісті алайық.

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

        ...
    }
}

Енді деректер жиынтығын жасайық. Бұл жағдайда деректерді генерациялау нәтижелерді мәтін ағынына (csv пішімінде) жазумен біріктіріледі. Әрбір IRandomGenerator мәндерін сақтау үшін оның жеке бағанасы бөлінеді және бірінші жолда генератордың аты бар.

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

        ...
    }
}

Тек GenerateCsvDataSet әдісін шақыру және нәтижені файлға сақтау немесе деректерді желі арқылы соңғы құрылғыдан қабылдау серверіне дереу тасымалдау ғана қалады.

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

        ...
    }
}

Жобаның дереккөздері мына жерде GitLab.

нәтижелері

Ешқандай керемет болған жоқ. Олар күткен нәрсе - олар барлық жағдайда, ешқандай қастандықсыз біркелкі бөлу. Мен платформалар үшін бөлек графиктерді қоюдың мәнін көрмеймін - олардың барлығы шамамен бірдей нәтижелерді көрсетеді.

Шындық мынау:
BlessRNG немесе RNG әділдігін тексеру

Барлық бес генерация әдісінен жазықтықта тізбектерді визуализациялау:
BlessRNG немесе RNG әділдігін тексеру

Және 3D форматындағы визуализация. Бірдей мазмұнды шығармау үшін тек System.Random.Next() нәтижесін қалдырамын.
BlessRNG немесе RNG әділдігін тексеру

UnityEngine.Random-тың қалыпты таралуы туралы кіріспеде айтылған оқиға қайталанбады: не ол бастапқыда қате болды, не қозғалтқышта бірдеңе өзгерді. Бірақ қазір біз сенімдіміз.

Ақпарат көзі: www.habr.com

пікір қалдыру