BlessRNG 또는 공정성을 위해 RNG 확인

게임 개발에서는 무언가를 무작위로 묶어야 하는 경우가 많습니다. Unity에는 이를 위한 자체 Random이 있고 이와 병행하여 System.Random이 있습니다. 옛날 옛적에 프로젝트 중 하나에서 둘 다 다르게 작동할 수 있다는 인상을 받았습니다(물론 균등하게 배포되어야 함).

그런 다음 세부 사항을 다루지 않았습니다. System.Random으로 전환하여 모든 문제를 수정하는 것만으로도 충분했습니다. 이제 우리는 이를 좀 더 자세히 살펴보고 RNG가 얼마나 "편향적"이거나 예측 가능한지, 어떤 것을 선택할 것인지에 대한 약간의 연구를 수행하기로 결정했습니다. 더욱이 나는 그들의 "정직성"에 대해 상충되는 의견을 한 번 이상 들었습니다. 실제 결과가 선언 된 결과와 어떻게 비교되는지 알아 보겠습니다.

간략한 교육 프로그램 또는 RNG는 실제로 RNG입니다.

난수 생성기에 이미 익숙하다면 즉시 "테스트" 섹션으로 건너뛸 수 있습니다.

난수(RN)는 엔트로피의 원인인 무작위(혼돈) 프로세스를 사용하여 생성된 일련의 숫자입니다. 즉, 이것은 요소가 수학적 법칙에 의해 상호 연결되지 않은 시퀀스이며 인과 관계가 없습니다.

난수를 생성하는 것을 난수 생성기(RNG)라고 합니다. 모든 것이 초보적인 것처럼 보이지만 이론에서 실습으로 이동하면 실제로 그러한 시퀀스를 생성하기 위한 소프트웨어 알고리즘을 구현하는 것이 그렇게 간단하지 않습니다.

그 이유는 현대 가전제품에 이와 같은 혼란이 없기 때문입니다. 그것이 없으면 난수는 더 이상 무작위가 아니며 생성기는 명확하게 정의된 인수의 일반 함수로 변합니다. IT 분야의 여러 전문 분야에서는 이것이 심각한 문제(예: 암호화)이지만 다른 분야에서는 완전히 수용 가능한 솔루션이 있습니다.

실제 난수는 아니지만 가능한 한 가까운 소위 의사 난수(PRN)를 반환하는 알고리즘을 작성해야 합니다. 이 경우의 알고리즘을 의사 난수 생성기(PRNG)라고 합니다.

PRNG를 생성하는 데는 여러 가지 옵션이 있지만 다음은 모든 사람에게 해당됩니다.

1. 예비 초기화가 필요합니다.

   PRNG에는 엔트로피 소스가 없으므로 사용하기 전에 초기 상태를 제공해야 합니다. 숫자(또는 벡터)로 지정하여 시드(Random Seed)라고 합니다. 종종 프로세서 클럭 카운터 또는 시스템 시간과 동등한 수치가 시드로 사용됩니다.

2. 서열 재현성.

   PRNG는 완전히 결정적이므로 초기화 중에 지정된 시드가 전체 미래 숫자 시퀀스를 고유하게 결정합니다. 이는 동일한 시드(다른 시간, 다른 프로그램, 다른 장치)로 초기화된 별도의 PRNG가 동일한 시퀀스를 생성한다는 것을 의미합니다.

또한 PRNG를 특징짓는 확률 분포, 즉 PRNG가 생성할 숫자와 확률을 알아야 합니다. 대부분 이는 정규 분포이거나 균일 분포입니다.

정규 분포(왼쪽) 및 균등 분포(오른쪽)

면이 24개인 공정한 주사위가 있다고 가정해 보겠습니다. 그것을 던지면 1이 나올 확률은 24/XNUMX(다른 숫자가 나올 확률과 동일)가 됩니다. 여러 번 던지고 결과를 기록하면 모든 가장자리가 거의 동일한 빈도로 떨어지는 것을 알 수 있습니다. 기본적으로 이 다이는 균일한 분포를 가진 RNG로 간주될 수 있습니다.

이 주사위 10개를 한번에 던져서 총점을 계산하면 어떻게 될까요? 통일성이 유지될 것인가? 아니요. 대부분의 경우 금액은 125포인트, 즉 평균값에 가깝습니다. 결과적으로 던지기 전에도 향후 결과를 대략적으로 추정할 수 있습니다.

그 이유는 평균점수를 얻기 위한 조합의 수가 가장 많기 때문이다. 멀어질수록 조합 수가 적어지고 그에 따라 손실 확률도 낮아집니다. 이 데이터를 시각화하면 종 모양과 어렴풋하게 닮게 됩니다. 따라서 약간의 확장을 통해 10개의 주사위로 구성된 시스템을 정규 분포를 갖는 RNG라고 부를 수 있습니다.

또 다른 예는 이번에는 비행기에서 표적을 쏘는 것입니다. 슈터는 그래프에 표시되는 숫자 쌍(x, y)을 생성하는 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, ...

얼핏 보면 이 숫자들이 얼마나 무작위적인가? 분포를 확인하는 것부터 시작하겠습니다.

균일해 보이지만 일련의 두 숫자를 읽고 이를 평면의 좌표로 해석하면 다음과 같은 결과를 얻습니다.

패턴이 선명하게 보입니다. 그리고 시퀀스의 데이터는 특정 방식으로 정렬되기 때문에(즉, 엔트로피가 낮음) 바로 그 "편향"이 발생할 수 있습니다. 최소한 이러한 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, ...

비행기 안에서도 모든 것이 괜찮은 것 같습니다.

볼륨을 살펴보겠습니다(한 번에 세 개의 숫자를 읽음).

그리고 다시 패턴. 더 이상 4차원 시각화를 구성하는 것이 불가능합니다. 그러나 패턴은 이 차원과 더 큰 차원에 존재할 수 있습니다.

PRNG에 가장 엄격한 요구 사항이 적용되는 암호화에서는 이러한 상황이 용납될 수 없습니다. 따라서 품질을 평가하기 위해 특수 알고리즘이 개발되었지만 지금은 다루지 않겠습니다. 주제는 광범위하며 별도의 기사가 필요합니다.

테스트

우리가 확실히 모르는 것이 있다면 어떻게 작업해야 할까요? 어떤 신호등이 허용하는지 모른다면 길을 건너는 것이 가치가 있습니까? 결과는 다를 수 있습니다.

Unity의 악명 높은 무작위성도 마찬가지입니다. 문서에 필요한 세부 사항이 밝혀지면 좋지만 기사 시작 부분에 언급된 이야기는 원하는 세부 사항이 부족했기 때문에 발생했습니다.

그리고 도구의 작동 방식을 모르면 도구를 올바르게 사용할 수 없습니다. 일반적으로 최소한의 분포 정도를 확인하기 위해 실험을 확인하고 수행해야 할 때가 왔습니다.

해결책은 간단하고 효과적이었습니다. 통계를 수집하고, 객관적인 데이터를 얻고, 결과를 살펴보는 것이었습니다.

연구 주제

Unity에서 난수를 생성하는 방법에는 여러 가지가 있습니다. 우리는 5가지를 테스트했습니다.

1. 시스템.랜덤.다음(). 주어진 값 범위에서 정수를 생성합니다.
2. 시스템.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() (여기서 기본은 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
• Android
  — Unity v2018.3.14f1, 장치별 빌드, Mono, .NET Standard 2.0
• iOS
  — Unity v2018.3.14f1, 장치별 빌드, il2cpp, .NET Standard 2.0

Реализация

난수를 생성하는 방법에는 여러 가지가 있습니다. 각각에 대해 다음을 제공하는 별도의 래퍼 클래스를 작성합니다.

1. 값 범위 [최소/최대) 설정 가능. 생성자를 통해 설정됩니다.
2. MF를 반환하는 메서드입니다. 더 일반적이므로 유형으로 float를 선택하겠습니다.
3. 결과를 표시하기 위한 생성 방법의 이름입니다. 편의상 클래스 전체 이름 + MF 생성에 사용된 메서드 이름을 값으로 반환하겠습니다.

먼저 IRandomGenerator 인터페이스로 표현될 추상화를 선언해 보겠습니다.

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

        float Generate();
    }
}

System.Random.Next() 구현

이 메서드를 사용하면 값 범위를 설정할 수 있지만 정수를 반환하지만 부동 소수점이 필요합니다. 단순히 정수를 부동소수점으로 해석할 수도 있고, 값의 범위를 몇 배로 확장하여 중간 범위의 각 세대에 따라 보상할 수도 있습니다. 결과는 주어진 정확도의 고정 소수점과 같습니다. 실제 float 값에 더 가깝기 때문에 이 옵션을 사용하겠습니다.

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의 value 속성은 고정된 값 범위에서 부동 소수점 유형을 반환합니다. [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에서 장면과 작은 MainController 스크립트를 생성합니다. 이 스크립트는 필요한 모든 작업을 수행하는 동시에 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();
            }
        }

        ...
    }
}

남은 것은 생성CsvDataSet 메서드를 호출하고 결과를 파일에 저장하거나 네트워크를 통해 최종 장치에서 수신 서버로 즉시 데이터를 전송하는 것입니다.

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.

조사 결과

기적은 일어나지 않았습니다. 그들이 기대했던 것은 그들이 얻은 것입니다. 모든 경우에 음모의 힌트 없이 균등한 분포가 이루어졌습니다. 플랫폼에 대해 별도의 그래프를 작성하는 것이 의미가 없다고 생각합니다. 모두 거의 동일한 결과를 보여줍니다.

현실은 다음과 같습니다


5가지 생성 방법 모두에서 평면의 시퀀스 시각화:


그리고 3D로 시각화합니다. 동일한 내용이 많이 생성되지 않도록 System.Random.Next()의 결과만 남겨 두겠습니다.


UnityEngine.Random의 정규 분포에 대한 소개 부분에서 이야기한 이야기는 반복되지 않았습니다. 처음에는 오류가 있었거나 나중에 엔진에서 뭔가가 변경되었습니다. 하지만 이제 우리는 확신합니다.

출처 : habr.com