🥇BlessRNG או בדיקת ה-RNG לכנות

בפיתוח משחקים, לעתים קרובות צריך לקשור משהו לאקראיות: ל-Unity יש רנדום משלה בשביל זה, ובמקביל לזה יש System.Random. פעם, באחד הפרויקטים, התרשמתי ששניהם יכולים לעבוד אחרת (אם כי צריכה להיות להם חלוקה שווה).

אחר כך הם לא נכנסו לפרטים - מספיק שהמעבר ל-System.Random תיקן את כל הבעיות. כעת החלטנו לבדוק את זה ביתר פירוט ולערוך מחקר קטן: עד כמה RNGs הם "משוחדים" או צפויים, ובאיזה מהם לבחור. יתר על כן, לא פעם שמעתי דעות סותרות לגבי ה"כנות" שלהם - בואו ננסה להבין איך התוצאות האמיתיות משתוות לאלה המוצהרות.

תוכנית חינוכית קצרה או RNG היא למעשה RNG

אם אתה כבר מכיר מחוללי מספרים אקראיים, אתה יכול מיד לדלג לסעיף "בדיקות".

מספרים אקראיים (RN) הם רצף של מספרים שנוצר באמצעות תהליך אקראי (כאוטי) כלשהו, מקור לאנטרופיה. כלומר, מדובר ברצף שהאלמנטים שלו אינם קשורים זה בזה בשום חוק מתמטי - אין להם קשר של סיבה ותוצאה.

מה שיוצר את המספר האקראי נקרא מחולל מספרים אקראיים (RNG). נראה שהכל אלמנטרי, אבל אם נעבור מתאוריה לפרקטיקה, אז למעשה זה לא כל כך פשוט ליישם אלגוריתם תוכנה ליצירת רצף כזה.

הסיבה נעוצה בהיעדר אותו כאוס במוצרי אלקטרוניקה מודרנית. בלעדיו, מספרים אקראיים מפסיקים להיות אקראיים, והמחולל שלהם הופך לפונקציה רגילה של ארגומנטים מוגדרים בעליל. עבור מספר התמחויות בתחום ה-IT מדובר בבעיה רצינית (למשל קריפטוגרפיה), אך עבור אחרים יש פתרון מקובל לחלוטין.

יש צורך לכתוב אלגוריתם שיחזיר, אמנם לא מספרים אקראיים באמת, אבל כמה שיותר קרוב אליהם - מה שנקרא מספרים פסאודו-אקראיים (PRN). האלגוריתם במקרה זה נקרא מחולל מספרים פסאודו אקראיים (PRNG).

ישנן מספר אפשרויות ליצירת PRNG, אך הדברים הבאים יהיו רלוונטיים עבור כולם:

הצורך באתחול מקדים.
ל-PRNG אין מקור אנטרופיה, ולכן יש לתת לו מצב ראשוני לפני השימוש. הוא מצוין כמספר (או וקטור) ונקרא זרע (זרע אקראי). לעתים קרובות, מונה השעון של המעבד או המקבילה המספרית של זמן המערכת משמש כמקור.
יכולת שחזור של רצף.
ה-PRNG הוא דטרמיניסטי לחלוטין, כך שה-Seed שצוין במהלך האתחול קובע באופן ייחודי את כל רצף המספרים העתידי. משמעות הדבר היא ש-PRNG נפרד שאותחל עם אותו סיד (בזמנים שונים, בתוכניות שונות, במכשירים שונים) יפיק את אותו רצף.

צריך לדעת גם את התפלגות ההסתברות המאפיינת את ה-PRNG - אילו מספרים הוא יפיק ובאיזה הסתברות. לרוב זו התפלגות נורמלית או התפלגות אחידה.

התפלגות נורמלית (שמאל) והתפלגות אחידה (ימין)

נניח שיש לנו קובייה הוגנת עם 24 צדדים. אם תזרוק אותו, ההסתברות לקבל אחד תהיה שווה ל-1/24 (זהה להסתברות לקבל כל מספר אחר). אם תבצע זריקות רבות ותרשם את התוצאות, תבחין שכל הקצוות נושרים בערך באותה תדירות. בעיקרו של דבר, קובייה זו יכולה להיחשב כ-RNG עם חלוקה אחידה.

מה אם תזרוק 10 מהקוביות האלה בבת אחת ותספור את סך הנקודות? האם תישמר עבורו אחידות? לא. לרוב, הסכום יהיה קרוב ל-125 נקודות, כלומר לערך ממוצע כלשהו. וכתוצאה מכך, עוד לפני ביצוע זריקה, אתה יכול להעריך באופן גס את התוצאה העתידית.

הסיבה היא שיש את המספר הגדול ביותר של שילובים כדי להשיג את הציון הממוצע. ככל שמתרחקים ממנו, פחות צירופים - ובהתאם, ההסתברות להפסד נמוכה יותר. אם הנתונים האלה מוצגים, הם ידומים במעורפל לצורת פעמון. לכן, עם קצת מתיחה, מערכת של 10 קוביות יכולה להיקרא RNG עם התפלגות נורמלית.

דוגמה נוספת, רק הפעם במטוס - ירי לעבר מטרה. היורה יהיה RNG שיוצר זוג מספרים (x, y) המוצג על הגרף.

מסכים שהאופציה משמאל קרובה יותר לחיים האמיתיים - זהו 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, ...

עד כמה המספרים האלה אקראיים במבט ראשון? נתחיל בבדיקת התפלגות.

זה נראה קרוב לאחיד, אבל אם אתה קורא רצף של שני מספרים ומפרש אותם כקואורדינטות במישור, אתה מקבל את זה:

דפוסים הופכים גלויים בבירור. ומכיוון שהנתונים ברצף מסודרים בצורה מסוימת (כלומר, יש לו אנטרופיה נמוכה), זה יכול להוליד את אותה "הטיה". לכל הפחות, 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, ...

נראה שהכל בסדר כאן אפילו במטוס:

בואו נסתכל בנפח (קרא שלושה מספרים בכל פעם):

ושוב הדפוסים. לא ניתן עוד לבנות הדמיה בארבעה מימדים. אבל דפוסים יכולים להתקיים במימד הזה ובגדולים יותר.

בקריפטוגרפיה, שבה הדרישות המחמירות ביותר מוטלות על PRNGs, מצב כזה אינו מקובל באופן קטגורי. לכן פותחו אלגוריתמים מיוחדים להערכת איכותם, שלא ניגע בהם כעת. הנושא נרחב וראוי למאמר נפרד.

בדיקה

אם אנחנו לא יודעים משהו בוודאות, אז איך לעבוד איתו? האם כדאי לחצות את הכביש אם לא יודעים איזה רמזור מאפשר זאת? ההשלכות עשויות להיות שונות.

אותו דבר לגבי האקראיות הידועה לשמצה באחדות. זה טוב אם התיעוד חושף את הפרטים הדרושים, אבל הסיפור שהוזכר בתחילת המאמר קרה בדיוק בגלל היעדר הפרטים הרצויים.

ואם אתה לא יודע איך הכלי עובד, לא תוכל להשתמש בו נכון. באופן כללי, הגיע הזמן לבדוק ולערוך ניסוי כדי לוודא סופית לפחות לגבי ההתפלגות.

הפתרון היה פשוט ויעיל - איסוף נתונים סטטיסטיים, השגת נתונים אובייקטיביים והתבוננות בתוצאות.

נושא לימוד

ישנן מספר דרכים ליצור מספרים אקראיים ב-Unity - בדקנו חמש.

System.Random.Next(). יוצר מספרים שלמים בטווח נתון של ערכים.
System.Random.NextDouble(). יוצר מספרי דיוק כפולים בטווח של [0; 1).
UnityEngine.Random.Range(). יוצר מספרי דיוק בודדים (צפים) בטווח נתון של ערכים.
UnityEngine.Random.value. יוצר מספרי דיוק בודדים (צפים) בטווח של [0; 1).
Unity.Mathematics.Random.NextFloat(). חלק מספריית Unity.Mathematics החדשה. יוצר מספרי דיוק בודדים (צפים) בטווח נתון של ערכים.

כמעט בכל מקום בתיעוד צוינה התפלגות אחידה, למעט UnityEngine.Random.value (שם ההתפלגות לא צוינה, אבל באנלוגיה למדים של UnityEngine.Random.Range() צפויה גם Unity.Mathematics.Random) .NextFloat() (כאשר בבסיס הוא אלגוריתם xorshift, מה שאומר ששוב צריך לחכות להתפלגות אחידה).

כברירת מחדל, התוצאות הצפויות נלקחו כפי שצוינו בתיעוד.

מתודולוגיה

כתבנו אפליקציה קטנה שיצרה רצפים של מספרים אקראיים בכל אחת מהשיטות שהוצגו ושמרנו את התוצאות לעיבוד נוסף.

אורכו של כל רצף הוא 100 מספרים.
טווח המספרים האקראיים הוא [0, 100).

הנתונים נאספו ממספר פלטפורמות יעד:

Windows
— Unity v2018.3.14f1, מצב עורך, מונו, .NET Standard 2.0
MacOS
— Unity v2018.3.14f1, מצב עורך, מונו, .NET Standard 2.0
— Unity v5.6.4p4, מצב עורך, מונו, .NET Standard 2.0
אנדרואיד
— Unity v2018.3.14f1, בנייה לכל מכשיר, מונו, .NET Standard 2.0
iOS
— Unity v2018.3.14f1, בנייה לכל מכשיר, il2cpp, .NET Standard 2.0

Реализация

יש לנו כמה דרכים שונות ליצור מספרים אקראיים. עבור כל אחד מהם, נכתוב כיתת עטיפה נפרדת, שאמורה לספק:

אפשרות להגדיר את טווח הערכים [min/max). יוגדר באמצעות הקונסטרוקטור.
שיטה מחזירה MF. בואו נבחר לצוף כסוג, מכיוון שהוא כללי יותר.
שם שיטת הדור לסימון התוצאות. מטעמי נוחות, נחזיר כערך את השם המלא של המחלקה + שם השיטה המשמשת ליצירת ה-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 * (מקסימום - דקה) + דקות.

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

שיטת NextFloat() של המחלקה Unity.Mathematics.Random מחזירה נקודה צפה מסוג 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 מוכנים. לאחר מכן, עליך ליצור רצפים ולשמור את מערך הנתונים המתקבל לעיבוד. לשם כך ניצור סצנה וסקריפט MainController קטן ב-Unity, שיבצע את כל העבודה הנדרשת ובמקביל יהיה אחראי על האינטראקציה עם ה-UI.

בואו נגדיר את גודל מערך הנתונים ואת טווח ערכי ה-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.

ממצאים

שום נס לא קרה. מה שהם ציפו זה מה שהם קיבלו - בכל המקרים, הפצה שווה בלי שמץ של קונספירציות. אני לא רואה טעם לשים גרפים נפרדים לפלטפורמות - כולם מציגים בערך את אותן תוצאות.

המציאות היא:

הדמיה של רצפים במישור מכל חמש שיטות הדור:

והדמיה בתלת מימד. אשאיר רק את התוצאה של System.Random.Next() כדי לא לייצר חבורה של תוכן זהה.

הסיפור שסופר בהקדמה על ההתפלגות הנורמלית של UnityEngine.Random לא חזר על עצמו: או שהוא היה שגוי בהתחלה, או שמשהו השתנה מאז במנוע. אבל עכשיו אנחנו בטוחים.

מקור: www.habr.com

BlessRNG או בדיקת ה-RNG להגינות