JS 乱数

一.問題の背景

2 次元平面上に一群の NPC がおり、各ラウンドでランダムに上/下/左/右のいずれかの方向に 1 歩移動でき、ユニットの衝突体積があります（NPC の位置は重複できません）

ルールはこれだけですが、初期状態ではこれらの NPC は人工的に 2 次元平面上に均一に分布されており、N ラウンド実行后发现すべての NPC が左下角に集中していました。。なぜこうなるのでしょうか、ランダムと言っていたのに？

二.分析

既存の実装は以下の通りです：

1. NPC の現在の位置に基づいて移動可能な位置を判断し、結果を 1 次元配列 arr に格納します

P.S.上/下/左/右は最大 4 つの点（周囲が空いている）、最小 0 つの点（囲まれている）

2. [0, arr.length - 1] 内の乱数を生成し、ターゲット位置のインデックス値 index として使用します

    // 乱数を生成 [min, max]
    w.Util.rand = function(min, max) {
   
        return Math.round(Math.random() * (max - min) + min);
    }
   

3. 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 を引く……満足するまで）は汎用的であるためです