Unityでスレッドから乱数を使いたくなった時に気になったこと

f:id:hirasho0:20190311125630j:plain

ここでは、UnityEngine.Randomを使えば99.9%解決するような話題について、 技術部平山が趣味で書いてみようと思います。 サンプルコードはgithubに置いてあります。

なお、マルチスレッドはあくまできっかけであり、本記事にスレッドの話はありません。 ただ、サンプルでは諸々の高速化のためにスレッドを使っております。

動機

少し前にAIを書いていた時、なにせ計算量が多いのでスレッドを使って並列化したいなと 思ったことがあります。 そうなると、使う乱数はマルチスレッドで呼べる奴じゃないとダメだなと。

しかし、UnityEngineの関数は他のスレッドから呼んではいけないという縛りがあります。 System.Randomを別個に持てばいいんですが、 System.Randomはずいぶん昔からある乱数です。 C言語のライブラリでは互換性のために標準の乱数が未だに昔のままで、 それを素直に使ってバグったゲームが売られたという話も聞きます。 C#でも同じことが起こったりはしないんでしょうか?

というわけで、調べてみることにしました。趣味です。

UnityEngine.Randomは使えないのか?

とりあえずUnityEngine.Randomが使えるならそれが一番いいでしょう。 中身が何なのかが気になったので ちょっと調べてみました。 本当かどうかはわかりませんが、XorShiftの128bit版だそうです。 21世紀に入ってから発明された手法で、よく見かけます。きっと良いに違いありません。 というわけで、本当に他のスレッドから呼んだらダメなのか、呼んでみましょう。

using UnityEngine;
using System.Threading;

public class Hoge : MonoBehaviour
{
    void Start()
    {
        int value = 0;
        var thread = new Thread(() =>
        {
            value = Random.Range(0, 100);
        });
        thread.Start();
        thread.Join();
        Debug.Log("Thread End! " + value);
    }
}

このコードから作ったスクリプトをテキトーなgameObjectに貼りつけて実行です。

f:id:hirasho0:20190311125633j:plain

やっぱりダメでした。他の手を考えましょう。

3つの手法

まあ仮にUnityEngine.Randomが使えたとしても、 staticで呼べるということは、中でスレッドセーフにするためのロックがあるはずで、きっとそれは遅いわけです。

ですので、真面目に使おうと思えばスレッドごとに別の乱数インスタンスを 持つべきだということになります。

そこで、ここでは3つの乱数について検証してみましょう。

乱数と言えばメルセンヌツイスタ な雰囲気なんですが、 数分で自作できるほど単純なものではなく、 ライブラリを入れないと使えないのがネックです。 乱数という奴は、どこか一箇所書き間違っても案外いい具合に動いて見えるので、 本当に正しく書けているのかわかりにくい特性があります。 ややこしい手法を自作するのは避けたいところです。

しかしライブラリを探すのも面倒くさいし、 もってきたライブラリがまともなのかを確かめるのも面倒なので、 まずは何も見ないで数行で書ける上の3つを候補としました。

System.Randomは単に呼ぶだけですので、下2つの実装をお見せします。

MWC(Multiply-with-carry)

class Mwc
{
    uint _x;
    public Mwc(int seed)
    {
        _x = 0xffff0000 | (uint)(seed & 0xffff);
    }
    int Next()
    {
        _x = ((_x & 0xffff) * 62904) + (_x >> 16);
        return (int)(_x & 0xffff);
    }
}

ミソはNext()の中で、実にシンプルです。 論理積、積、和、シフト、そして最後の論理積で5演算しかありません。いかにも速そうです。 32bitの状態変数を持ちますが、出力は16bitです。

なお、スレッドごとに別の系列を生成しないといけないので、乱数の種が設定できるように コンストラクタに引数を設けました。 ただ、MWCは状態変数が0になるとずっと0しか出てこなくなるので、 seedは下位16ビットだけを使い、上は全部1で埋めておきました (もし乱数インスタンスを6万個以上使いたい場合はこんなことをしてはまずいです)。 使う人が間違って0をつっこんでも事故らないようにしておくことは大切でしょう。

この乱数のいいところは、数学の専門家でなくても理屈がなんとなくわかることかなと感じます。 簡単に言えば「1を19で割ると0.052631578947368...となって桁が乱数っぽいよね」 的な話です。コードに割り算がないのに割り算をしたのと同じことになっている、 というところにも面白さがあります。 興味がおありの方は原論文をお読みください。

なお、どんな乱数でも言えることですが、レイトレをするとかかで億以上の回数で乱数を使う場合は、 状態変数が32bitの手法だと乱数を使い果たしてしまいます。 _xが同じ値に戻ってきたら、そこからはまた繰り返しですから、 どんなにがんばっても2の32乗回呼ぶまでに戻ってきてしまうのです。 状態変数が64bitくらいある手法が欲しいところです。

XorShift

class XorShift
{
    uint _x;
    public XorShift(int seed)
    {
        _x = 0xffff0000 | (uint)(seed & 0xffff);
    }
    public int Next()
    {
        _x ^= _x << 13;
        _x ^= _x >> 17;
        _x ^= _x << 5;
        return (int)(_x & 0xffff);
    }
}

これもまたシンプルです。xorとシフトで6演算しかありません。 なんでこれで乱数になるんでしょうね? 最後にandして下16bitを取っているのはMWCに合わせたからで、 本来は32bit全域を使えます。 ただし、32bit全域を使うと「続けて同じ値が出ることはない」「絶対0が出ない」 といった乱数らしからぬ性質を持ってしまうので、状態変数の半分使うくらいで丁度良いでしょう。

さて、この乱数の理屈なんですが、私にもよくわかりません。 論文を見た感じ、どうも行列ベクトル積になってるみたいです。 「232-1乗して単位行列になるような行列を、32ビットから成るベクトルに乗算すると周期232-1の乱数ができる」 という説明を聞いて、「おお、なるほど」と思った方はこんなものを読んでいる場合ではないと思います。 原論文をお読みください。

なお、出力に32bit欲しい場合や、億以上の回数で呼ぶ場合は、64bit版のXorShiftを使うのが良いかと思います。 その場合3回のシフト量は上の例とは違う値になります(例えば順に21,35,4)。 Numerical Recipes をご参照ください。手元に置いておくと便利です。私は年に何回か使います。

計測

さて、これら2つにSystem.Randomを加え、 さらにUnityEngine.Randomの中身であるらしいXorShiftの128bit版(以下XorShift128)も加えて 速度を測ってみましょう。1億回ほど呼んでみます。

const int N = 1000 * 1000 * 100; // 1億
var t0 = Time.realtimeSinceStartup;
int sum = 0; // 結果を何かに使わないと最適化で消されそうなので用意
for (int i = 0; i < N; i++)
{
    sum += rand.Next();
}
var t1 = Time.realtimeSinceStartup;
Debug.Log((t1 - t0) + " sum:" + sum);

こんな感じです。randはMWCだったりXorShiftだったりします (サンプルコード ではIRandomというインターフェイスで抽象化しています)。 結果はこうなりました。

Mwc XorShift System.Random XorShift128
Editor 2.13 2.49 5.38 3.36
Standalone 0.312 0.682 0.876 0.303
WebGL 1.57 1.67 5.01 1.96

単位は秒です。 macbook pro mid2014(i7 3GHz)上で、エディタ、Standaloneビルド、WebGLビルド(chrome)にて計測しました。 プラットフォームごとに得意不得意があって、特にStandaloneの結果がいろいろ謎なのですが、 一番遅いものでも1億回呼んで6秒未満なので、 60FPSのゲームでCPUの1%を使えば3000回呼べる計算になります。 他にいくらでも遅い処理がありますし、気にするまでもないでしょう (ただし、WebGLは64bit整数演算が遅いですし、2羃でない整数除算は泣くほど遅いです。Javascriptだから仕方ないですね)。

さて、速度に大した差がないことを確認したところで、今度は質です。 こいつらは本当に乱数になっているのでしょうか。

乱数の品質を調べる

とはいえ、「乱数が乱数になっているか?」を完全に確認することはできません。 なぜなら、本当に乱数であればどんなことだって起こり得るからです。 100回連続サイコロで1が出ることだって、6の100乗回繰り返せば起こるかもしれません (たぶん宇宙が終わっても起こらないでしょうけど)。

残念ながら「乱数が乱数らしいか」というのは結構難しいテーマで、素人には手に余るところがあります。 概して確率とか統計とかは直感に反することが正しいことが多く、ちょっとかじった程度だと あっさり罠にはまります。

とはいえ、乱数がまともに動いているのか全く確かめない、というのもマズいでしょう。 例えばくじ引きが正しく実装できているか、は何らかの形でテストしないといけません。 乱数そのものに問題がなくても、使い方を間違えばダメになります。 必ず、お客さんにとって意味のある最終結果が望む確率分布になっているか、を確認したいところです。 くじ引きやアイテムドロップの類については、一回くらいはカイ二乗検定 をしておいた方がいいのではないでしょうか。

ですがここではそこまでは深入りせず、 「あからさまにダメ」な場合をはじくことに主眼を置いてみます。 なんでもパッと見でわかる形に可視化すると楽ですので、 まずはランダム具合を画像化してみることにしましょう。

まずテキトーなテクスチャを用意します。

_texture = new Texture2D(Width, Height, TextureFormat.RGBA32, false);
_image.texture = _texture;

可視化するためにテスチャを貼りつけるためのRawImageを_imageとして用意し、 そこにテクスチャをつっこみます。

あとは、テキトーにColor32の配列を用意して、乱数を使って詰めます。

for (int i = 0; i < PixelsPerUnit; i++)
{
    var x = _random.Next() % Width;
    var y = _random.Next() % Height;
    var color = _random.Next();
    var r = ((color >> 10) & 0x1f) << 3; // 5ビット取り出して8倍すると0から248になる
    var g = ((color >> 5) & 0x1f) << 3;
    var b = ((color >> 0) & 0x1f) << 3;
    var offset = ((y * Width) + x);
    pixels[offset].r = (byte)r;
    pixels[offset].g = (byte)g;
    pixels[offset].b = (byte)b;
}

pixelsはColor32のWidth*Heightの配列で、 PixelsPerUnitは「1回に何ピクセル塗るか」です。 ランダムにx,yを決め、色もランダムで決めます。サンプルでは1万にしています。 ここでは出てきた乱数から5ビットづつ取り出してRGBを決めていますが、趣味です。 RGBそれぞれに乱数を使ってもいいでしょう。

これを、Texture2D.SetPixels32() で詰めます。 サンプルでは、テクスチャを縦に分割して、それぞれを別のスレッドで処理していますが、 品質の検査には関係ありません。

さて、それで出てきたのが以下のような画像です。

f:id:hirasho0:20190311125622j:plainf:id:hirasho0:20190311125630j:plain
f:id:hirasho0:20190311125627j:plainf:id:hirasho0:20190311125618j:plain

3つは見た感じランダムですね。 一方、右下はどう見てもランダムではない絵になっています。

これはダメな例を示すために用意した線形合同法 によるものです。ランダムさが足りないために全部の点が塗れません。奇数と偶数が交互に出るというひどい有様です。 2000年くらいまではこんな乱数を工夫しながら使っていたようですが、 MWCなりXorShiftなりメルセンヌツイスタなりが発明された今となっては、そんな必要はないでしょう。 興味がおありの方はサンプルコード をご覧ください。とりあえず実行している所を見たい方はWebGLビルドをどうぞ。

さて、残念ながらこのテストでは、MWCもXorShiftもSystem.Randomも、 「十分ランダム」に見えます。 しかし「System.Randomはランダムさが足りなくてダメだ」と言っている人もいるわけで、 何をやるとダメなのかは知っておきたいところです。 それがはっきりしていれば、逆に「そこまでやる気ないからこれでいいよ」と言えます。

ゴリラテスト

何か楽に差が出るテストはないかなあと調べていたところ、 こんな論文 を見つけました。「このテストを通る奴は、以前からあるテストは大抵通る」 という話で、本当なら魅力的な話です。MWCやXorShiftを発明した人の論文で、 なんとなく信用できそう、というのも良いですね。 中でも「ゴリラテスト」という奴は理屈が簡単で、実装も簡単そうです。ちょっと試してみましょう。

原理は簡単です。今、サルがテキトーにaからzまであるキーボードを打ちまくったとします。 例えば26回叩いたとしましょう。 何回かは同じ文字を叩くこともあるでしょうから、その分出てこない文字もあるでしょう。 もし本当にランダムなら、平均的に何個の文字が出てくるか、というのは計算できます。 ある文字が出てこない確率は、(25/26)で、26回やっても出てこないのですから26乗して、(25/26)26です。 出てくる確率は1から引くので、1-(25/26)26となります。 これを26倍すれば、「平均して何文字現れるか」がわかります。だいたい16.6文字です。

次に、文字1個でなく2個をセットにして、その単語で考えます。aiとかgoとかですね。 26*26で676通りあります。そこで、676回キーを叩いてできた文章の中から、 1文字づつずらしながら2文字の単語を拾って、出てきた単語を数えることができます。 abcdeの5文字から成る文章であれば、ab、bc、cd、de、が出てきます。 これに関しても同じような計算ができて、2文字の単語676種類のうち平均して何個出てくるか、 は前もってわかります。

さて実際にはアルファベットである必要はないので、01の2進法でやりましょう。 この論文では26ビットの文字列をどれくらい網羅しているかを計測して、 それが理屈上の平均値からどれくらい離れているかで判定しています。 26ビットの01文字列は226=6700万通りほどあり、 6700万回乱数を作って、テキトーなビットを取ってきてつなげます。 理屈上はだいたい4200万種類くらい出るはずです。

ここでは、16bitの出力のそれぞれで別々に文字列を作り、 ビットごとに偏りがないかどうかを調べてみました。 結果は色で表してあります。 各ビットについて、理論上の平均値よりあんまり多ければ赤、あんまり少なければ緑、 だいたい同じなら灰色っぽい感じ、としています(標準偏差の4倍ズレると色が飽和します)。

f:id:hirasho0:20190311125553p:plainf:id:hirasho0:20190311125608p:plain
f:id:hirasho0:20190311125603p:plainf:id:hirasho0:20190311125612p:plain

簡単に言えば、色が灰色っぽければ良くて、キツい赤やキツい緑ならダメ、という感じです。 これで言うと、XorShiftはヤバイですね。完全に緑です。 つまり、思ったより単語が出てきてない、イコール、同じ単語が何回も出ている、 ということですから、乱数のバリエーションが少ないのでは?という疑いがあります。 MWCも緑ですが、XorShiftよりはマシな印象です。 一方図にStandardとあるSystem.Randomもだいぶ灰色な感じに見えますが、 左下はだいぶ赤いです。 そして最後にXorShift128ですが、この中では一番鈍い感じの色になりました。 全部赤っぽいとか、全部緑っぽい、とかだとヤバい感じがしますが、そうでもないようです。

これくらい厳しいテストをすると差が出てくるわけですね。 6700万回乱数を叩いて、それぞれのビットごとにバラバラにする、 というようなことをして初めてわかる偏り、が問題になるかどうかは用途次第です。

ところで、なぜ「ゴリラ」なんでしょうか。 実は「サルがテキトーにキーを叩いた的なテスト」として モンキーテストというものが昔からありまして、 「今回はそれをすごい回数でやるから、モンキーよりも強い。そう、ゴリラだ!!」 という感じでゴリラなようです。

メモリ量比較

参考までにそれぞれの手法の消費メモリ量も表にしておきます。 MWCやXorShiftは上で紹介した32ビットバージョンです。

Mwc XorShift System.Random XorShift128
4 4 288 16

単位はバイトです。 System.Randomはnewしてプロファイラで何バイト取ったかを見た数値なので、 アルゴリズム上の正味のサイズは数十バイト小さいと思われます。 System.RandomのアルゴリズムはKnuth先生によるものらしく、 もしそのままであれば32bit変数を55個使うので、220バイトくらいなのではないでしょうか。 「そんなに使う割に別に性能がいいわけでもない」と言えなくもないですが、 気にするレベルではないと思います。なにせ、標準ですから。 標準から外れるのは勇気がいります。長いものに巻かれて困らないなら巻かれればいいのです。

まとめ

マルチスレッドしないなら、UnityEngine.Randomでいいと思います。 XorShift128は上に示した通り、相当厳しいテストをしてもそんなに偏りません。 本当にXorShift128なのか?パラメータも同じなのか? といったことはわかりませんが、まさかそんなところに問題があることはないでしょう。 なにせ標準ですから。

そして、もしマルチスレッドするならSystem.Randomでいいと思います。 今回見た範囲では優れている所はありませんでしたが、なにせ標準でみんな使っています。 下手に自分で手法を選んで罠に落ちる危険を冒すよりもいいでしょう。

とはいえ、テトリスで次にどれが落ちてくるか決める、とか、 ゲーム中20/256の確率で宝箱を落とす、とかいうような程度なら 32ビットのMWCでも全く問題ないと思います。

ところで、最近はスマホでもCPUの演算器が64bitになってきました。 64bitということは、32bitの数に32bitの数を乗算できるということですので、 変数をulongにして、

_x = ((_x & 0xffffffff) * 4294957665) + (_x >> 32);

とすれば簡単に32bit出力のMWCが得られます。 ゴリラテストでもXorShift128以上に灰色になりました。

f:id:hirasho0:20190311125557p:plain

状態変数は64bitで、2の60乗回くらい呼ばないと元の状態には戻ってこないので、実質無限です。 2の60乗はだいたい10の18乗くらいですから、 1秒間に1億回(10の8乗)使うのを、1万台のマシン(10の4乗)で、10年間(だいたい100万秒で10の6乗) 続けてやっと使い切るかな?というくらいなので、我々ゲーム屋にとっては十分無限でしょう。 計算速度も今回試したmacでは32bitとほとんど同じでした。むしろ速いくらいです。

でもまあ、何か罠があった時に私は責任を取れないので、 「標準でいいんじゃないでしょうか」と言うことでお話を締めたいと思います。 長いものに巻かれましょう。