はじめに
疑似乱数生成関数に興味があって、調べたところ Xorshift って言う有名なアルゴリズムがあることを知りました。
Xorshift とは (Wikipediaより)
Xorshiftは疑似乱数列生成法の1つである。George Marsagliaが2003年に提案した。演算が排他的論理和とビットシフトのみであるため高速である などの特徴がある。
Xorshiftに限らず、疑似乱数関数ってのは「真の」ランダムではなく、あくまで数式で人間にはランダムに見える数のシリーズを作り出すものです。できの悪い数式だと「周期的なパターン」ができてしまったりするのですが、Xorshiftはそういうのが起こりにくく、しかも高速なので良いアルゴリズムなんだそうです。
Xorshiftの実装例【javascript】
なお、今回記事のためのサンプルを作成するにあたって、Xorshiftのコードはこちらを参考にさせていただきました。
なお、コメントでいただいたご指摘に従い、右ビットシフトを符号なしに変え、乱数結果としては絶対値を返すように修正しています。
【問題】シードを変えても同じパターン
それで早速自作ゲームに使ってみたんですが、一つ問題があることに気づきました。
よくあるtimestampを乱数シードに実装をしたのですが、序盤の展開がいつも同じ。ある程度時間を置くと、多少違った展開になりますが、さらに連続でプレイするとまたしばらく同じ展開がつづく。
つまり似たようなシードだと似たようなパターンが生成されてしまうことがわかりました（少なくとも最初の何回か）。
Xorshift固有の弱点ではない
他の乱数アルゴリズムでも、似たようなシードだと似たようなパターンが生成されることは、大なり小なりあるようです。
とはいえ本記事の改善策自体はアルゴリズムに依存しないので、参考になればと思います。
以下は、実際にシードをちょっとづつ変えて最初の8回の結果をRGB色で表示させたものです（セル内の数字が16進数で表したシードです）。
一見してわかるように、行方向も列方向もかなりの類似性が見られます。時々ちょっと大きく変わる場合があるのも、自作ゲームでの体感と一致しています。
【対策】
理想の乱数関数としては、シードがちょっとでも違ったら、一回目からガラッと変わってほしいものです。そこで改善を試みました。
１：シードの変化を増幅する
そもそも時刻のような、よく似た値が出やすいシードがよくない。
とはいえ時刻以外に手軽なシードもそうそうない。
じゃあ、加工してちょっとの差が大きな差になるようにビット差を増幅してみましょう！
こんな感じでビットシフトさせてXORしてみました。
n = n ^ (n>>>7) ^ (n<<7);
w = n;
結果・・・
まだまだよく似たパターンが多いけれど、まあ何もしないよりはマシですかね。
２：最初の数回消費する
そもそも、序盤に同じようなパターンが出やすいのはXorshiftの根源的な問題である気がします。
これが次の乱数を生成するコードですが、
this.rnd = function() {
const t = x ^ (x << 11);
x = y; y = z; z = w;
w = (w^(w>>>19))^(t^(t>>>8)); // 符号なしシフト
return w >>>=0; // 負の値を正の値に変える
}
x →加工→ t, y → x, z → y, w → z, t →加工→ w
のように循環しており、w はシードそのものですが、x,y,z は初期値が定数値になっているため、シードの違いがx,y,zすべてに伝播しきるまで数回かかることがわかります。
wの値が大きく違っていても、初回の計算では25％しか影響を及ぼしません。ましてや時刻のようによく似た値のシード同士だと、ほとんど同じパターンになっても不思議はなさそうです。
シードに応じてx,y,zも加工したらいいんじゃないの？
シードの伝播を早めるという意味では効果はあると思います。
（※当初、x,y,zは良い乱数列を作るため調整された特別な値のセットであり、あまり触らない方がよいと考えてましたが、コメントでご指摘を受けて自分の勘違いと判明したので、記事を訂正しました。）
では、時刻などの似通った値になりがちなシードを元にx,y,zをどのように加工するべきか？
結局、時刻をごにょごにょして乱数っぽい物作るなら、後述する乱数消費するのとあまり変わらない気がします。「同じシードからは同じ乱数列が得られる」という条件はマストとして、何かもっとスマートな解決法があればアドバイス頂けますと幸いです。
改善案として、シード設定関数の中であらかじめ数回乱数を消費してしまうようにしてみました。
さらに消費回数は固定ではなく、シードに応じて1～18回（たぶん？）に変化するようにして、乱数の「用途をずらす」ことでパターンが目立たなくなるよう工夫してみました。
let u = this.rnd();
let cnt = 1;
[11,7,5].forEach((n, i) => {
let j = u % n;
i++;
while(j > 0) {
this.rnd();
cnt++;
j -= i;
};
});
結果はこちら
いかがでしょう。ほとんどのセルで隣接セルが似通ったパターンではなくなったように思います。
１と２の合わせ技
とはいえ、たまたまスキップ回数が一致してしまうと、よく似たパターンになるのは避けられません。
なので、１と２を両方適用してしまいましょう。
いかがでしょうか？ざっと見渡した感じ類似パターンはほぼ解消できてるように思います。
まとめ
乱数アルゴリズムXorshiftには、「似たシードは似たパターンになりやすい」「たとえシードが大きく違っていても、最初の数回は似たパターンになりやすい」問題があるようです。
しかし「シードの変化を増幅する」、「シードに応じて最初の数回を消費する」対策をすることで、その問題を解消できました。
ご参考までに、以下に実際に動かせるコードを這っておきます。
See the Pen XorShift random seed disparsion by ShinodaNaoki (@shinodanaoki) on CodePen.
参考リンク