JS 난수

一.문제 배경

2 차원 평면에 한 무리의 NPC 가 있으며, 각 라운드에서 랜덤하게 상/하/좌/우 중任一방향으로 1 보 이동할 수 있고, 유닛의 충돌 부피가 있습니다 (NPC 위치는 중복될 수 없음)

규칙은 이뿐이지만, 초기 상태에서 이 NPC 들은 인위적으로 2 차원 평면에 균일하게 분포되어 있으며, N 라운드 실행 후 모든 NPC 가 좌하각에 집중되어 있었습니다..왜 이럴까요, 랜덤하다고 했잖아요?

二.분석

기존 구현은 다음과 같습니다:

NPC 의 현재 위치에 따라 이동 가능한 위치를 판단하고, 결과를 1 차원 배열 arr 에 저장합니다

P.S.상/하/좌/우는 최대 4 개의 점 (주변이 비어 있음), 최소 0 개의 점 (囲まれている)

[0, arr.length - 1] 내의 난수를 생성하여 타겟 위치의 인덱스 값 index 로 사용합니다

 // 난수 생성 [min, max]
 w.Util.rand = function(min, max) {

     return Math.round(Math.random() * (max - min) + min);
 }

NPC 를 arr[index] 위치로 이동시킵니다

로직에는 문제가 없어야 하는데, 왜 실행 결과는 NPC 가 모두 좌하각에 모여 회의를 하고 있는 걸까요? 잠깐, 왜 좌하각이고 다른 모서리가 아닐까요?

1 단계 구현이 상->하->좌->우 순서로 판단하고 있기 때문에, 마지막에 모두 좌하각으로 갔다는 것은 상과 우의 확률이 너무 작다는 것을 나타냅니다 (난수 생성 함수 rand 는 문제없으며, 확실히 [min, max] 의 숫자를 얻을 수 있습니다)

문제의 근원은 Math.random() 이役に立たずで、[0, 1) 사이의 소수를 생성하며, 0 이나 1 에 가까운 값을 얻을 확률이 매우 낮기 때문에, rand() 함수가 생성하는 난수가 min 이나 max 를 얻을 확률도 매우 낮고, 상/우로 이동할 가능성도 작아집니다

三.해결책

min 과 max 를 얻을 확률이 매우 낮고, 중간 확률이 비교적 균일하다면, 간단합니다. 이 2 개의 값을 잘라내면 됩니다. 구체적인 구현은 다음과 같습니다:

function randEx(min, max) {

    var num;
    var maxEx = max + 2; // 범위를 [min, max + 2] 로 확대하고, 2 개의 여분 값을 도입하여 min/max 를 대체
    
    do{
    
        num = Math.round(Math.random() * (maxEx - min) + min);
        num--;
    } while (num < min || num > max);   // 범위가 올바르지 않으면, 루프 계속
    
    return num;
}

특기할 만한 것은, 위의2 를 더하고 1 을 빼는것이 교묘하며, min 과 max 를 정확히 제외할 수 있다는 것입니다

四.실행 결과

JS 에서 Math.random() 반환값의 확률 차이는 상상보다 클 수 있으며, 실제 응용에서는 받아들일 수 없습니다

테스트 코드는 다음과 같습니다:

// 난수 생성 [min, max]
w.Util.rand = function(min, max) {

    return Math.round(Math.random() * (max - min) + min);
}

// 더 랜덤한 난수 생성 [min, max]
function randEx(min, max) {

    var num;
    var maxEx = max + 2; // 범위를 [min, max + 2] 로 확대하고, 2 개의 여분 값을 도입하여 min/max 를 대체
    
    do{
    
        num = Math.round(Math.random() * (maxEx - min) + min);
        num--;
    } while (num < min || num > max);   // 범위가 올바르지 않으면, 루프 계속
    
    return num;
}

function testRand(times, fun) {

    var arr = [1, 2, 3, 4];
    var count = [];
    var randVal;
    for (var i = 0; i < times; i++) {

        // [0, 3] 의 난수 획득
        randVal = fun(0, arr.length - 1);
        // 횟수 기록
        if (typeof count[randVal] !== "number") {
        
            count[randVal] = 0;
        }
        count[randVal]++;
    }
    
    console.log(count);
}

console.log("100 times");
testRand(100, w.Util.rand); // 이전 구현
testRand(100, randEx);      // 개선한 구현

console.log("1000 times");
testRand(1000, w.Util.rand); // 이전 구현
testRand(1000, randEx);      // 개선한 구현

console.log("10000 times");
testRand(10000, w.Util.rand); // 이전 구현
testRand(10000, randEx);      // 개선한 구현

console.log("100000 times");
testRand(100000, w.Util.rand); // 이전 구현
testRand(100000, randEx);      // 개선한 구현

실행 결과는 다음과 같습니다:

보시다시피, 효과는 매우 좋습니다

###후일담

이론적으로 Java 의 Math.random(), C#의 next 도 이 문제가 존재할 수 있지만, 여기서는 검증할 필요가 없습니다. randEx 함수의 사상 (2 를 더하고 1 을 빼고, 효과가 좋지 않으면 4 를 더하고 2 를 빼고, 6 을 더하고 3 을 빼고……만족할 때까지) 은 보편적이기 때문입니다

一.문제 배경

二.분석

三.해결책

四.실행 결과

댓글

댓글 작성