🥇BlessRNG أو التحقق من صحة RNG

في تطوير اللعبة، غالبًا ما تحتاج إلى ربط شيء ما بالعشوائية: لدى Unity عشوائيتها الخاصة لهذا الغرض، وبالتوازي معها يوجد System.Random. ذات مرة، في أحد المشاريع، كان لدي انطباع بأن كلاهما يمكن أن يعملا بشكل مختلف (على الرغم من أنه يجب أن يكون لهما توزيع متساوٍ).

ثم لم يخوضوا في التفاصيل - كان يكفي أن يؤدي الانتقال إلى System.Random إلى تصحيح جميع المشكلات. قررنا الآن أن ننظر في الأمر بمزيد من التفصيل ونجري القليل من البحث: ما مدى "تحيز" RNGs أو إمكانية التنبؤ بها، وأي منها نختار. علاوة على ذلك، سمعت أكثر من مرة آراء متضاربة حول "صدقهم" - فلنحاول معرفة كيفية مقارنة النتائج الحقيقية بالنتائج المعلنة.

البرنامج التعليمي الموجز أو RNG هو في الواقع RNG

إذا كنت معتادًا بالفعل على مولدات الأرقام العشوائية، فيمكنك الانتقال فورًا إلى قسم "الاختبار".

الأرقام العشوائية (RN) هي سلسلة من الأرقام التي تم إنشاؤها باستخدام بعض العمليات العشوائية (الفوضوية)، وهي مصدر للإنتروبيا. أي أن هذا تسلسل لا ترتبط عناصره بأي قانون رياضي - وليس لديهم علاقة سبب ونتيجة.

ما ينشئ الرقم العشوائي يسمى مولد الأرقام العشوائية (RNG). يبدو أن كل شيء أساسي، ولكن إذا انتقلت من النظرية إلى الممارسة، ففي الواقع ليس من السهل تنفيذ خوارزمية برمجية لإنشاء مثل هذا التسلسل.

والسبب يكمن في غياب تلك الفوضى نفسها في الإلكترونيات الاستهلاكية الحديثة. بدونها، تتوقف الأرقام العشوائية عن أن تكون عشوائية، ويتحول مولدها إلى وظيفة عادية للوسائط المحددة بوضوح. بالنسبة لعدد من التخصصات في مجال تكنولوجيا المعلومات، تعد هذه مشكلة خطيرة (على سبيل المثال، التشفير)، ولكن بالنسبة للآخرين هناك حل مقبول تماما.

من الضروري كتابة خوارزمية من شأنها أن تعود، وإن لم تكن أرقامًا عشوائية حقًا، ولكنها أقرب ما يمكن إليها - ما يسمى بالأرقام العشوائية الزائفة (PRN). تسمى الخوارزمية في هذه الحالة بمولد الأرقام العشوائية الزائفة (PRNG).

هناك عدة خيارات لإنشاء PRNG، ولكن ما يلي سيكون مناسبًا للجميع:

الحاجة إلى التهيئة الأولية.
لا يوجد لدى PRNG أي مصدر للإنتروبيا، لذلك يجب إعطاؤه حالة أولية قبل الاستخدام. يتم تحديده كرقم (أو ناقل) ويسمى بذرة (بذرة عشوائية). في كثير من الأحيان، يتم استخدام عداد ساعة المعالج أو المعادل الرقمي لوقت النظام كبذرة.
استنساخ التسلسل.
إن PRNG حتمية تمامًا، لذا فإن البذرة المحددة أثناء التهيئة تحدد بشكل فريد التسلسل المستقبلي الكامل للأرقام. وهذا يعني أن 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، ...

يبدو أن كل شيء على ما يرام هنا حتى على متن الطائرة:

دعونا ننظر في الحجم (اقرأ ثلاثة أرقام في المرة الواحدة):

ومرة أخرى الأنماط. لم يعد من الممكن بناء تصور بأربعة أبعاد. لكن الأنماط يمكن أن توجد في هذا البعد وفي الأبعاد الأكبر.

في التشفير، حيث يتم فرض المتطلبات الأكثر صرامة على PRNG، فإن مثل هذا الموقف غير مقبول على الإطلاق. ولذلك تم تطوير خوارزميات خاصة لتقييم جودتها، وهو ما لن نتطرق إليه الآن. الموضوع واسع ويستحق مقالة منفصلة.

تجريب

إذا لم نكن نعرف شيئًا ما على وجه اليقين، فكيف نتعامل معه؟ هل يستحق عبور الطريق إذا كنت لا تعرف أي إشارة مرور تسمح بذلك؟ قد تكون العواقب مختلفة.

الأمر نفسه ينطبق على العشوائية سيئة السمعة في الوحدة. من الجيد أن تكشف الوثائق التفاصيل الضرورية، لكن القصة المذكورة في بداية المقال حدثت على وجه التحديد بسبب عدم وجود التفاصيل المطلوبة.

وإذا كنت لا تعرف كيفية عمل الأداة، فلن تتمكن من استخدامها بشكل صحيح. بشكل عام، لقد حان الوقت للتحقق وإجراء تجربة للتأكد أخيرا من التوزيع على الأقل.

كان الحل بسيطًا وفعالًا - جمع الإحصائيات والحصول على بيانات موضوعية وإلقاء نظرة على النتائج.

موضوع الدراسة

هناك عدة طرق لتوليد أرقام عشوائية في 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، وضع المحرر، Mono، .NET Standard 2.0
ماك
— Unity v2018.3.14f1، وضع المحرر، Mono، .NET Standard 2.0
— Unity v5.6.4p4، وضع المحرر، Mono، .NET Standard 2.0
أندرويد
— Unity v2018.3.14f1، مصمم لكل جهاز، Mono، .NET Standard 2.0
آيفون
— Unity v2018.3.14f1، مصمم لكل جهاز، il2cpp، .NET Standard 2.0

تطبيق

لدينا عدة طرق مختلفة لتوليد أرقام عشوائية. لكل واحد منهم، سنكتب فئة مجمعة منفصلة، والتي ينبغي أن توفر:

إمكانية ضبط نطاق القيم [الحد الأدنى/الحد الأقصى). سيتم تعيينه عبر المنشئ.
طريقة إرجاع MF. لنختار النوع float، لأنه أكثر عمومية.
اسم طريقة الإنشاء لوضع علامات على النتائج. للراحة، سنعيد كقيمة الاسم الكامل للفئة + اسم الطريقة المستخدمة لإنشاء 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()

تقوم طريقة 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);
    }
}

تنفيذ وحدة التحكم الرئيسية

العديد من تطبيقات IRandomGenerator جاهزة. بعد ذلك، تحتاج إلى إنشاء تسلسلات وحفظ مجموعة البيانات الناتجة للمعالجة. للقيام بذلك، سنقوم بإنشاء مشهد وبرنامج نصي صغير لـ MainController في Unity، والذي سيقوم بكل العمل اللازم وفي نفس الوقت يكون مسؤولاً عن التفاعل مع واجهة المستخدم.

لنقم بتعيين حجم مجموعة البيانات ونطاق قيم 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.

النتائج

لم تحدث معجزة. ما توقعوه هو ما حصلوا عليه، وفي كل الأحوال، توزيع متساوٍ دون أي إشارة إلى وجود مؤامرات. لا أرى فائدة من وضع رسوم بيانية منفصلة للمنصات - فكلها تظهر نفس النتائج تقريبًا.

الحقيقة هي:

تصور التسلسلات على المستوى من جميع طرق التوليد الخمسة:

والتصور في 3D. سأترك فقط نتيجة System.Random.Next() حتى لا يتم إنتاج مجموعة من المحتوى المتطابق.

القصة التي رويت في المقدمة عن التوزيع الطبيعي لـ UnityEngine. لم تكرر Random نفسها: إما أنها كانت خاطئة في البداية، أو تغير شيء ما في المحرك منذ ذلك الحين. لكننا الآن متأكدون.

المصدر: www.habr.com

BlessRNG أو التحقق من RNG للتأكد من عدالته