JDK 17 における擬似乱数生成と LXM ファミリについて

はじめに

2021/09/14 に GA となった JDK 17 では、擬似乱数生成まわりの強化が行われました。

更新点を見ると、 LXM という新しい擬似乱数生成器が実装されているようです。
しかし、このアルゴリズムについて聞いたことがなかったため (実装当時) 、調べてみました。

ついでに、このアルゴリズムが導入されるきっかけとなった JEP 356: Enhanced Pseudo-Random Number Generators についてもある程度解説しようと思います。

本記事では、特に注釈がなければ下記環境を使用して検証しています。

openjdk 17.0.6 2023-01-17
OpenJDK Runtime Environment Temurin-17.0.6+10 (build 17.0.6+10)
OpenJDK 64-Bit Server VM Temurin-17.0.6+10 (build 17.0.6+10, mixed mode, sharing)

はじめに
JEP 356 の要約
インタフェースの追加
LXM アルゴリズムについて
その他の改善点
アルゴリズムの選び方
均等分布性について
- exactly equidistributed とは
- k-equidistributed とは
おわりに

JEP 356 の要約

そもそもどういった提案で何が追加されたのか、のざっくりとしたお話です。
原文は JEP 356 を参照してください。

旧 API では、擬似乱数生成器ごとの互換性が微妙だったり (SplittableRandom は Random を継承していないので代入できないなど) 、各生成器で nextDouble() などをそれぞれが独自に (コピペで) 実装していてよろしくなかったり、といった問題がありました。

また、 SplittableRandom には "弱点" が見つかっており、新しい別のアルゴリズムを導入して問題を回避したいニーズがありました。
JEP 内ではこの弱点について具体的に触れられていませんが、おそらくこちらの文献 *1 を指しているものと思います。
問題点の説明の部分を要約します。 SplittableRandom は内部に gamma という定数を持っており、 split() で新しいインスタンスを生成した際に自身と異なる gamma を設定することで別々の乱数列を得る仕組みになっています。この gamma は乱数の品質に深くかかわっており、 "弱い" gamma を設定すると品質が下がってしまいます。 Java では弱い gamma を弾くアルゴリズムが入っているのですが、それでも処理しきれない値 ( $2 ^ {64} / k$ や $2 ^ {s} m + 1$ など) が存在しており、それが選ばれた場合に乱数の品質が下がってしまう、という問題がありました。

問題への対応だけではなく、ポジティブな面もあります。
擬似乱数生成器によっては split() や jump() といった異なる乱数列を得る仕組みを持つものがあり、並列実行において便利に扱うことができます。前者は SplittableRandom 、後者は xoroshiro128+ アルゴリズムなどが該当します。
この機能を統一的に扱うことができる API を用意したい、というニーズがありました。

インタフェースの追加

以下のインタフェースが提供されます。箇条書きは実装関係を示しています。

RandomGenerator
- StreamableGenerator
  - SplittableGenerator
  - JumpableGenerator
    - LeapableGenerator
      - ArbitrarilyJumpableGenerator

これらについて、ざっくりと解説をしていきます。 (網羅しているわけではないので、詳細はそれぞれリンク先の API ドキュメントから確認してください。)

`RandomGenerator`

擬似乱数生成器としての基底のインタフェースです。基本的に nextLong() を実装すれば nextDouble() などはデフォルト実装で生やしてくれます。

これのおかげで、擬似乱数生成器を独自実装する際に Random を継承する必要がなくなりました。不要な内部状態などがついてこなくなります。

`StreamableGenerator`

異なる乱数列を出力するインスタンスを無限に生成する rngs() をサポートします。

rngs() は Stream<RandomGenerator> 、つまり擬似乱数生成器のインスタンスが得られるストリームを返します。何に使うのかというと、 (特にマルチスレッドにおける) 並列実行です。

本質的に乱数生成は内部状態の変更を伴います。したがって、スレッド間でインスタンスを共有してしまうと、内部状態が正しく更新されず出力が崩壊したり、ロックで時間と手間がかかったりと良いことがありません。
(ちなみに Random はロックをかけるほうの手法を採用しており、代償としてオーバーヘッドがかなり大きかったのです。)
そこで、各スレッドで別々のインスタンスを利用することによって、速度と品質を同時に得ることができる、というわけです。従来の ThreadLocalRandom に近い雰囲気です。

ただ、各スレッド用の個別インスタンスを作る際、単純にクローンを作ったり適当なシードを与えて初期化したりした場合、運が悪いと出力される乱数列が重複してしまい、ランダムではなくなってしまう (相関が生まれる) 可能性があります。
これを回避するアプローチは 2 つあり、それらが SplittableGenerator, JumpableGenerator にあたります。

`SplittableGenerator`

従来 SplittableRandom で使えた機能の一般化である split() をサポートします。
(実際に SplittableRandom もこのインタフェースを実装するようになりました。)

内部状態とは別にある種の定数を持ち、この定数をインスタンスごとに変えることで乱数列自体を別々にするしくみを持ちます。
定数が異なれば、初期の内部状態 (≒シード) が完全一致していてもそれぞれ異なる乱数列が出力されるため、乱数の重複を回避できます。

ちなみに、現在 SplittableGenerator を実装している擬似乱数生成器が split() で定数をどうやって決めているのかというと、 nextLong() ベースでランダムに決定しているようです。
つまり奇跡が起こって親子で定数が一致する可能性も 0 ではありませんが、そこは楽観的に決定しているようです。
もっとも、そうなる確率は天文学的に低く、もしそうなっても内部状態が離れていれば実用上重複しないので、心配する必要はありません。
具体例を挙げると、 L64X128MixRandom で同じ乱数列に入る確率は $2 ^ {-63}$ 、かつ親との距離が $\pm 2 ^ {64}$ 以内になる確率は約 $2 ^ {-190}$ ですので、 GUID の衝突よりもはるかに低確率です。

`JumpableGenerator`

固定長ジャンプを高速に行う jump() をサポートします。

jump() は、 nextLong() を大量に ( $2 ^ {64}$ や $2 ^ {128}$ といったオーダーで) 呼び出したのと同じ状態遷移を高速に得られる機能です。
これによって、そのジャンプ距離と同じ回数 nextLong() などを呼び出さない限りは乱数列が重複しない保証を得る (そんな回数は現実的に呼び出せないので事実上独立した乱数列を得る) ことができます。

通常の乱数列を 1 本の長いテープに例えると、 SplittableGenerator は「異なるテープを何本も用意する」、 JumpableGenerator は「1 本のテープを等間隔に分割して使う」といったイメージです。
こう書くと JumpableGenerator のほうは 1 本あたりの長さ (≒周期; 使える量) が減ってしまって良くないように思えるかもしれませんが、切ったとしてもそれぞれ $2 ^ {64}$ 個分の長さはあって現実的に使いきれる量ではないので、心配は無用です。
また SplittableGenerator に比べると品質のばらつきが比較的少ない利点もあります。前述した「 SplittableRandom で gamma 値によっては品質が下がってしまう問題」のようなことが起こりにくいです。

`LeapableGenerator` / `ArbitrarilyJumpableGenerator`

JumpableGenerator の拡張として、 LeapableGenerator と ArbitrarilyJumpableGenerator も存在します。

LeapableGenerator は、 jump() よりも長距離の固定長ジャンプを行う leap() もサポートします。
ArbitrarilyJumpableGenerator は、さらに任意長のジャンプを行える jump(distance) もサポートします。

これらの見分けが難しいかもしれませんが、基本的にはジャンプ距離の違いと、距離を指定できるかどうかです。

JumpableGenerator : 中距離の固定長ジャンプ (例: $2 ^ {64}$ )
LeapableGenerator : ＋長距離の固定長ジャンプ (例: $2 ^ {128}$ )
ArbitrarilyJumpableGenerator : ＋任意長ジャンプ

LeapableGenerator の存在意義は、擬似乱数生成器の分割自体を並列化することにあります。
jumps() で n 個のインスタンスを生成するとき、 jump() を n 回連続で呼ぶ必要があり、 $O(n)$ で時間がかかることになります。この時、最初に leap() でいくつかの子インスタンスを作り、そこから jump() で孫インスタンスを切り出すようにすれば処理時間が (n / leap() で作ったインスタンスの数) となり、最善を尽くせば $O(\sqrt{n})$ に短縮することができます。先のテープのたとえで言えば、最初にテープを何本かに切り分けて、それらを重ねてまとめて切っていくイメージです。

ちなみに、固定長のジャンプ距離については厳密な指定はなく、周期を $p$ として jump() が $2 ^ {64}$ または $\sqrt{p}$ ぐらい、 leap() が $2 ^ {128}$ ぐらい、といった目安が参考として記載されています。実用上は特に気にする必要はありませんが、もし擬似乱数生成器を実装する側になった場合は参考にしてください。

なお、 2023/03/17 時点では ArbitrarilyJumpableGenerator を実装している擬似乱数生成器はありません。

`JumpableGenerator` シリーズの注意点

注意点として、 JumpableGenerator において rngs() や jumps() で作成したインスタンスからさらに rngs() などで孫を作ってはいけないことが挙げられます。
jumps() は、内部的には

自身のコピーを作る
自身を jump() させる
コピーを返す

といったことを繰り返しています。
ここで、子でも rngs() してしまうと最初の親と子の jump() 呼び出し回数 (距離) が一致し、擬似乱数生成器の内部状態がかなり近い (最悪一致する) 状態となり、結果として親子でほぼ同一の乱数列を永遠に出力し続けるようになってしまいます。
jumps() の戻り値が Stream<JumpableGenerator> ではなく Stream<RandomGenerator> になっているのはそのためで、孫の作成を自然と防止するようにできています。

孫が欲しい場合 (例えば、単一スレッドで複数の乱数列が必要なものをさらにマルチスレッド処理する場合など) は LeapableGenerator の leaps() を使いましょう。大本 → leaps() → 子供 → jumps() → 孫、といった感じで生成できます。もちろん、 leaps() を繰り返して子孫を作ると同じ問題が発生します。 leaps() と jumps() を使い分けるのがポイントです。

なお、 SplittableGenerator の splits() では子孫で衝突する問題は事実上発生しません。一つの乱数列を共有している JumpableGenerator とは異なり、乱数列自体がインスタンスごとに異なるためです。

実装例

インタフェースが分かったところで、自分でアルゴリズムを実装する際の例を紹介します。
今回は Seiran128 アルゴリズムを実装してみました。
このアルゴリズムは LeapableGenerator の要件を満たしているので、それでざっくり実装してみます。

package Java17Test.src;  

import java.nio.ByteBuffer;  
import java.security.SecureRandom;  
import java.util.concurrent.atomic.AtomicLong;  
import java.util.random.RandomGenerator.LeapableGenerator;  

public class Seiran128 implements LeapableGenerator {  

    private long state0, state1;  

    private static final AtomicLong SEEDER = new AtomicLong(ByteBuffer.wrap(SecureRandom.getSeed(8)).getLong());  

    public Seiran128() {  
        this(SEEDER.getAndAdd(0x9e3779b97f4a7c15L));  
    }  

    public Seiran128(long seed) {  
        state0 = seed = seed * 6364136223846793005L + 1442695040888963407L;  
        state1 = seed = seed * 6364136223846793005L + 1442695040888963407L;  
    }  

    public Seiran128(long s0, long s1) {  
        if (s0 == 0 && s1 == 0) {  
            long seed = SEEDER.getAndAdd(0x9e3779b97f4a7c15L);  
            s0 = seed = seed * 6364136223846793005L + 1442695040888963407L;  
            s1 = seed = seed * 6364136223846793005L + 1442695040888963407L;  
        }  

        state0 = s0;  
        state1 = s1;  
    }  

    @Override  
    public void jump() {  
        internalJump(new long[] { 0xF4DF34E424CA5C56L, 0x2FE2DE5C2E12F601L });  
    }  

    @Override  
    public double jumpDistance() {  
        return 0x1p64;  
    }  

    @Override  
    public long nextLong() {  
        long s0 = state0, s1 = state1;  
        long result = Long.rotateLeft((s0 + s1) * 9, 29) + s0;  

        state0 = s0 ^ Long.rotateLeft(s1, 29);  
        state1 = s0 ^ s1 << 9;  

        return result;  
    }  

    @Override  
    public LeapableGenerator copy() {  
        return new Seiran128(state0, state1);  
    }  

    @Override  
    public void leap() {  
        internalJump(new long[] { 0x185F4DF8B7634607L, 0x95A98C7025F908B2L });  
    }  

    @Override  
    public double leapDistance() {  
        return 0x1p96;  
    }  

    private void internalJump(long[] jumpTable) {  
        long t0 = 0, t1 = 0;  

        for (int i = 0; i < 2; i++) {  
            for (int b = 0; b < 64; b++) {  
                if ((jumpTable[i] & (1L << b)) != 0) {  
                    t0 ^= state0;  
                    t1 ^= state1;  
                }  
                nextLong();  
            }  
        }  

        state0 = t0;  
        state1 = t1;  
    }  
}

nextDouble() などは RandomGenerator のデフォルト実装としてついてくるので基本的には nextLong() だけ、 LeapableGenerator を実装する場合は対応する jump() ・ leap() などを実装すればよいです。

ただ、 RandomGenerator.of("Seiran128") でインスタンス化できるか試してみましたが、どうもうまくいきませんでした。
内部実装を見た限りでは internal なアノテーションを設定する必要がありそうで、今のところ外部からの追加は難しそうです。
(もしうまくやる方法をご存じの方がいらっしゃればぜひ…)

LXM アルゴリズムについて

さて、いよいよ本題に入ります。
JDK 17 では以下の擬似乱数生成器 (アルゴリズム) が追加されています。ソースコードはこちらを参照してください。

Xoroshiro128PlusPlus
Xoshiro256PlusPlus
L32X64MixRandom
L64X128MixRandom
L64X128StarStarRandom
L64X256MixRandom
L64X1024MixRandom
L128X128MixRandom
L128X256MixRandom
L128X1024MixRandom

RandomGenerator.of("Xoshiro256PlusPlus") といった形でアルゴリズム名を指定することでインスタンスを生成することができます。

xoroshiro128++ と xoshiro256++ については作者のサイトでの説明や論文 *2 が存在しますが、 LXM ファミリは初出当時は jdk リポジトリや API ドキュメント以外では記述のないアルゴリズムでした。 2023 年現在は論文 *3 が発表されており、詳細を知ることができます。

以降は、 java.util.random パッケージの "The LXM Family of Random Number Generator Algorithms" の項をベースに紹介していきます。

LXM は、

L : LCG → Linear Congruential Generator; 線形合同法
X : XBG → Xor-Based Generator; xoshiro/xoroshiro アルゴリズム
M : Mixer → 上の 2 つを混ぜること (いわゆる出力関数)

という略語です。
名前の通り、内部に線形合同法と xo(ro)shiro の 2 つのアルゴリズムを独立して持ち、出力の際にそれらを "mix" することによって高品質な乱数出力を実現する設計となっています。

「あの悪名高い線形合同法？怪しい…」と思われた方もいらっしゃるかもしれませんが、線形合同法も使い方を工夫したりこのように他の擬似乱数生成器と組み合わせたりすることで高品質な乱数を生成することができます。使い方を工夫した例でいえば PCG が有名です。

L64X128MixRandom という暗号めいた名前は、それぞれどんなアルゴリズムを組み合わせているかを示しています。

name	LCG (bits)	XBG (algorithm)	Mixer (algorithm)
L32X64MixRandom	32	xoroshiro64 (32-bit)	mixLea32(s+x0)
L64X128MixRandom	64	xoroshiro128	mixLea64(s+x0)
L64X128StarStarRandom	64	xoroshiro128	starstar(s+x0)
L64X256MixRandom	64	xoshiro256	mixLea64(s+x0)
L64X1024MixRandom	64	xoroshiro1024	mixLea64(s+x0)
L128X128MixRandom	128	xoroshiro128	mixLea64(sh+x0)
L128X256MixRandom	128	xoshiro256	mixLea64(sh+x0)
L128X1024MixRandom	128	xoroshiro1024	mixLea64(sh+x0)

2021/09/12 当時は Package Summary の表 "LXM Multipliers" には概ね mixLea32 が使われていると書かれていますが、これは誤りでした。 32 bit ベースの L32X64MixRandom だけが本当に mixLea32 で、それ以外の mixLea32 の行は実際は mixLea64 を使用しています。 2023/03/17 現在のドキュメントでは修正されています。

ちなみに、 LXM の xoroshiro128 のパラメータ (遷移関数のシフト/ローテート定数) は (24, 16, 37) であり、 Xoroshiro128PlusPlus の (49, 21, 28) とは異なります。
LXM のパラメータは公式実装における xoroshiro128** 、 Xoroshiro128PlusPlus のは xoroshiro128++ に基づいているようです。 (ちなみに xoroshiro128++ のほうが新型です。)
解析を行う場合に混同するとおかしくなるので注意が必要です。

L64X128MixRandom の必要最小限の実装は以下のようになります。なお、異常系や付加機能 (split() など) は省いています。

package Java17Test.src;  

import java.util.random.RandomGenerator;  

public class L64X128MixRandomClone implements RandomGenerator {  

    private final long lcgAdditive;  
    private long lcgState, xbgState0, xbgState1;  

    public L64X128MixRandomClone(  
        long lcgAdditive, long lcgState, long xbgState0, long xbgState1) {  
        this.lcgAdditive = lcgAdditive | 1;  
        this.lcgState = lcgState;  
        this.xbgState0 = xbgState0;  
        this.xbgState1 = xbgState1;  
    }  

    @Override  
    public long nextLong() {  

        // Mix  
        long r = lcgState + xbgState0;  
        r = (r ^ r >>> 32) * 0xdaba0b6eb09322e3L;  
        r = (r ^ r >>> 32) * 0xdaba0b6eb09322e3L;  
        r = (r ^ r >>> 32);  

        // LCG  
        lcgState = lcgState * 0xd1342543de82ef95L + lcgAdditive;  

        // XBG (xoroshiro)  
        long s0 = xbgState0, s1 = xbgState1;  
        s1 ^= s0;  
        s0 = Long.rotateLeft(s0, 24) ^ s1 ^ s1 << 16;  
        s1 = Long.rotateLeft(s1, 37);  
        xbgState0 = s0;  
        xbgState1 = s1;  

        return r;  
    }  
}

LCG パートでは、加算する定数 (lcgAdditive) をインスタンスごとに可変にすることで、 PCG と同様に異なる乱数列の生成 (split()) を可能にしています。
この部分での周期は $2 ^ {l}$ ( $l$ は lcgState のビット数) です。

ちなみに、 L128 のバリアントでは 128 bit 乗算を行っている…　わけではなく、工夫によって 64 bit 乗算と 64 bit x 64 bit → 128 bit の乗算のみで計算できるようになっています。
まず、乗算する定数 0x1d605bbb58c8abbfd は 65 bit 、つまり上位 64 bit が 0x1 になっています。これによって、乗算結果の下位 64 ビット (lo) は lo * 0xd605bbb58c8abbfdL 、上位 64 bit (hi) は Math.unsignedMultiplyHigh(lo, 0xd605bbb58c8abbfdL) + hi * 0xd605bbb58c8abbfdL + lo として計算することができます。 64 bit ごとに区切った筆算をイメージすると分かりやすいです。

XBG パートは、既存の xo(ro)shiro 系アルゴリズムから出力関数 (+, **, ++) を除いた状態になっています。この部分での周期は $2 ^ {x} - 1$ ( $x$ は xbgState の合計ビット数) です。
-1 されているのは、 xbgState がすべて 0 の場合は何回遷移しても 0 のままになるので除外しているためです。実際のコンストラクタではすべて 0 で初期化されないように補正処理が行われています。

そして、全体としての周期は $2 ^ {l} \cdot (2 ^ {x} - 1) = 2 ^ {l + x} - 2 ^ {l}$ となります。具体的には、 L64X128MixRandom では $2 ^ {192} - 2 ^ {64}$ です。各パートの周期が互いに素なため、単に掛け合わせたぶんだけ周期になります。

Mix パートが出力関数です。これを状態更新前にやっているのは、内部状態の更新と並列に計算できるようにして高速化を狙っているためです。
この mixLea64 実装は SplittableRandom の出力関数に似ていますが、定数が異なっています。
シフトを 32 bit 単位に揃えたり乗算の定数を同じにすることでより高速化を図っているようです。
定数設定はソースコードのコメントを見た限りでは Doug Lea 氏 (SplitMix の論文の共著者) によるものらしいです。詳しくは LXM の論文を参照して下さい。

ところで、現状の JDK 17 では LXM ファミリは SplittableGenerator だけ実装してありますが、 LeapableGenerator も実装することもできます。
例えば、 L64X128MixRandom における jump() と leap() はこのように実装できます。

    @Override  
    public void jump() {  
        internalJump(new long[] { 0x2bd7a6a6e99c2ddcL, 0x0992ccaf6a6fca05L });  
    }  

    @Override  
    public double jumpDistance() {  
        return 0x1p64;  
    }  

    @Override  
    public LeapableGenerator copy() {  
        return new L64X128MixRandomClone(lcgAdditive, lcgState, xbgState0, xbgState1);  
    }  

    @Override  
    public void leap() {  
        internalJump(new long[] { 0x360fd5f2cf8d5d99L, 0x9c6e6877736c46e3L });  
    }  

    @Override  
    public double leapDistance() {  
        return 0x1p96;  
    }  

    private void internalJump(long[] jumpTable) {  
        long x0 = 0, x1 = 0, s = lcgState;  

        for (int i = 0; i < 2; i++) {  
            for (long b = 1; b != 0; b <<= 1) {  
                if ((jumpTable[i] & b) != 0) {  
                    x0 ^= xbgState0;  
                    x1 ^= xbgState1;  
                }  
                nextLong();  
            }  
        }  

        lcgState = s;  
        xbgState0 = x0;  
        xbgState1 = x1;  
    }

基本的には xo(ro)shiro のジャンプ関数実装を使うだけです。
LCG パートに変更がないのは、ジャンプ距離が $2 ^ {64}$ や $2 ^ {96}$ と LCG の周期 ( $2 ^ {64}$ ) の倍数になっており、 n 周して元の位置に戻ってきているためです。
理論上は任意長ジャンプの ArbitrarilyJumpableGenerator を実装することも可能ですが、そこそこ手間がかかるので割愛します。

これは完全に余談ですが、 L128X1024MixRandom のコンストラクタがあまりにもいかついので笑ってしまいました。

新しいアルゴリズム、コンストラクタの圧がすごいです https://t.co/tLwBXgOiNM pic.twitter.com/3c6swi6kUK
— Andante (@andanteyk) 2021年9月8日

LXM ファミリの品質について

JEP 356 によれば、 LXM ファミリは TestU01 や PractRand といった著名な乱数性テストに合格するとのことです。
ただ、具体的にどう合格しているのか (TestU01 なら p-value の許容範囲はどこまでか・何個のシード値で試したか、 PractRand ならどのモードで何 TB まで確認したか) は書かれていませんでした。

そこで論文を見ると、TestU01 は BigCrush (最も多くのテストを行うモード) において、現行の L64X128MixRandom 相当の実装では複数の初期化方法について各 84 回ものテストを行い問題ないことを確認した、とあるようです。
また、 PractRand では 4 TB までテストにパスすることを確認した、ともありました。

ただ、確認したとされている PractRand のバージョンは 0.90 とのことで、現行の最新版 (0.94 及び pre-0.95) より前のものになっています。 v0.94 でいくつかのテストが追加されており、それで FAIL した擬似乱数生成器もそこそこあったので、懸念材料となります。

最も、単体でもほとんどの (線形性テストを除く) テストを突破しうる xo(ro)shiro に LCG を組み合わせたうえで mix までかけているので、大丈夫ではあるだろう、とは推測できます。
参考までに、 SplittableRandom は雑に言えば state += gamma; という足し算だけのシーケンスを mix を通して出力するだけのものです。それでも PractRand にパスしているので、それより内部が複雑な LXM でも通るだろう、というのが理由です。

実際に確認してみましょう。 LXM ファミリの中で最も内部状態が小さい (つまり、問題が顕在化しやすいと思われる) L32X64MixRandom について、 PractRand v0.94 でテストを行いました。引数は -multithreaded -te 1 -tf 2 -tlmaxonly と、最も多くのテストをかけられるモードを指定しています。

RNG_test using PractRand version 0.94
RNG = L32X64MixRandomJava64, seed = 0x19aa8a23
test set = expanded, folding = extra

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 512 megabytes (2^29 bytes), time= 2.9 seconds
  no anomalies in 1220 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 1 gigabyte (2^30 bytes), time= 7.7 seconds
  no anomalies in 1293 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 2 gigabytes (2^31 bytes), time= 15.4 seconds
  no anomalies in 1368 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 4 gigabytes (2^32 bytes), time= 29.2 seconds
  no anomalies in 1448 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 8 gigabytes (2^33 bytes), time= 60.3 seconds
  no anomalies in 1542 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 16 gigabytes (2^34 bytes), time= 117 seconds
  no anomalies in 1636 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 32 gigabytes (2^35 bytes), time= 213 seconds
  no anomalies in 1716 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 64 gigabytes (2^36 bytes), time= 455 seconds
  no anomalies in 1807 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 128 gigabytes (2^37 bytes), time= 914 seconds
  no anomalies in 1902 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 256 gigabytes (2^38 bytes), time= 1667 seconds
  no anomalies in 1983 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 512 gigabytes (2^39 bytes), time= 3541 seconds
  no anomalies in 2058 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 1 terabyte (2^40 bytes), time= 7137 seconds
  no anomalies in 2132 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 2 terabytes (2^41 bytes), time= 14111 seconds
  no anomalies in 2194 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 4 terabytes (2^42 bytes), time= 29294 seconds
  no anomalies in 2255 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 8 terabytes (2^43 bytes), time= 59262 seconds
  no anomalies in 2313 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 16 terabytes (2^44 bytes), time= 119867 seconds
  no anomalies in 2366 test result(s)

時間の都合上 16 TB までの範囲ではありますが、異常は検出されませんでした。
(本来は 32 TB まで検定します。)
私の実験は完全ではありませんが、この範囲では少なくとも大丈夫だと言えそうです。

他の L64X128MixRandom などについては L32X64MixRandom よりも内部状態が大きくなっているので、それ以上の品質を確保できていると推測できます。

要約すれば、現時点では問題は検出されない、高品質な擬似乱数生成器である、ということです。

速度について

LCG と xo(ro)shiro を組み合わせて mix している関係上、それぞれ単体の xo(ro)shiro や SplittableRandom より遅くなっているのではないか、と推測できます。

実際に測ってみましょう。 1 GB (nextLong() $2 ^ {27}$ 回分) の乱数を生成するのにかかった時間 (実測値, ms) と、そこから計算した速度 (GB/s) を速い順に示します。環境は以下の通りです。

12th Gen Intel(R) Core(TM) i7-12700F

openjdk 17.0.6 2023-01-17
OpenJDK Runtime Environment Temurin-17.0.6+10 (build 17.0.6+10)
OpenJDK 64-Bit Server VM Temurin-17.0.6+10 (build 17.0.6+10, mixed mode, sharing)

Algorithm	ms	GB/s
SplittableRandom	226.00	4.42
Xoroshiro128PlusPlus	240.75	4.15
Xoshiro256PlusPlus	260.68	3.84
L64X128StarStarRandom	291.99	3.42
L64X128MixRandom	313.23	3.19
L64X256MixRandom	340.49	2.94
L64X1024MixRandom	362.83	2.76
L32X64MixRandom	386.71	2.59
L128X256MixRandom	575.84	1.74
L128X128MixRandom	578.84	1.73
L128X1024MixRandom	922.06	1.08
Random	2189.57	0.46
SecureRandom	75161.27	0.01

実測値のため環境や試行によってぶれる可能性がありますが、この結果を見ると、

ざっくりした傾向としては SplittableRandom > Xo(ro)shiro > LXM (L64 > L32 > L128) >> Random >>(越えられない壁)>> SecureRandom といった感じです。
- 品質を犠牲にしてでも速度第一にする場合は SplittableRandom 、品質も大事な場合は Xoroshiro128PlusPlus がよさそうです。
LXM シリーズは、 L が小さい > X が小さい順に速い傾向がみられます。
- 長い乗算が必要になるとさすがに遅くなるようです。
L32X64MixRandom は 32 bit ベースのため nextLong() 1 回あたり 2 回の遷移が必要になって結果として遅くなりそう、と予想していましたが、思っていたよりも速いようです。
新しいアルゴリズムは、遅いものでも Random の 2.3 倍、速いものでは 9.0 倍ほど速くなっています。
- Random が遅いのは、マルチスレッド対応のため都度ロックをかけているせいと推測しています。
(当然ながら) SecureRandom は非常に低速なため、必要な用途にだけ使用すべきでしょう。

といった感じです。

余談ですが、 C# に移植したバージョンで BenchmarkDotNet を使って nextLong() を測定してみると、以下のようになりました。

BenchmarkDotNet=v0.13.2, OS=Windows 11 (10.0.22000.1574/21H2)
12th Gen Intel Core i7-12700F, 1 CPU, 20 logical and 12 physical cores
.NET SDK=7.0.200
  [Host]     : .NET 7.0.3 (7.0.323.6910), X64 RyuJIT AVX2
  DefaultJob : .NET 7.0.3 (7.0.323.6910), X64 RyuJIT AVX2

Method	Mean	Error	StdDev	Ratio	RatioSD
Xoroshiro128PlusPlus	0.5713 ns	0.0114 ns	0.0107 ns	0.22	0.01
Shioi	0.5972 ns	0.0127 ns	0.0113 ns	0.23	0.00
L64X128StarStar	0.6012 ns	0.0145 ns	0.0136 ns	0.23	0.01
SplitMix	0.6013 ns	0.0168 ns	0.0157 ns	0.23	0.01
Seiran	0.6019 ns	0.0206 ns	0.0183 ns	0.23	0.01
Xoshiro256PlusPlus	0.7908 ns	0.0123 ns	0.0103 ns	0.30	0.00
L64X256Mix	0.8066 ns	0.0126 ns	0.0118 ns	0.31	0.00
L64X128Mix	0.8069 ns	0.0160 ns	0.0150 ns	0.31	0.01
L64X1024Mix	1.3266 ns	0.0239 ns	0.0212 ns	0.51	0.01
L128X128Mix	1.9699 ns	0.0253 ns	0.0225 ns	0.76	0.01
L128X256Mix	2.0528 ns	0.0215 ns	0.0202 ns	0.79	0.01
SystemRandomUnseeded	2.5940 ns	0.0259 ns	0.0242 ns	1.00	0.00
L32X64Mix	2.7956 ns	0.0280 ns	0.0262 ns	1.08	0.02
L128X1024Mix	4.5566 ns	0.0337 ns	0.0299 ns	1.76	0.03
SystemRandomSeeded	50.8033 ns	0.2700 ns	0.2525 ns	19.59	0.19

補足すると、 SplitMix は SplittableRandom 相当、 SystemRandom(Un)Seeded は .NET の System.Random にシードを与えた/与えなかったもの (それぞれ内部アルゴリズムが変化します) 、 Shioi と Seiran はいつもの私の自作アルゴリズムです。

微妙に結果は異なりますが、全体の印象としては同じ雰囲気です。

内部状態復元攻撃

これだけで記事 1 本文の分量になりそうだったので、後日別の記事に…できれば…いいな…。
L32 ・ L64 シリーズについては攻撃の目処が立っています。

その他の改善点

全体の話に戻します。

乱数を加工して使いやすくするメソッドもいくつか追加・改善されています。

`nextDouble(double bound)` / `nextDouble(double origin, double bound)`

nextDouble(double bound) と nextDouble(double origin, double bound) が追加され、一定範囲への変換が楽になりました。 nextFloat() も同様です。
今まではストリームを返すほう doubles() でだけ使えていたのが nextDouble() でも使えるようになった形になります。
「そんなの nextDouble() * (bound - origin) + origin すればいいだけなのでは？」と思われた方もいると思いますが、この方法には落とし穴があります。このメソッドの戻り値は origin <= value < bound を意図していますが、前述の式では浮動小数点数の丸め誤差によってごくまれに value == bound となってしまう場合があります。今回追加されたメソッドでは、それをよしなに制御して範囲内になるように保証してくれます。

`nextExponential()`

指数分布に従う乱数を生成する nextExponential() が追加されています。

`nextGaussian(double mean, double stddev)`

また、正規分布に従う乱数を生成する nextGaussian() に nextGaussian(double mean, double stddev) が追加され、平均と標準偏差を自分で計算する必要がなくなりました。
さらに、内部実装が変わってパフォーマンスも改善しています。以前は Polar Method で実装されていましたが、改良 Ziggurat アルゴリズムに変更されてより高速化しています。
$2 ^ {24}$ 回の呼び出しを実測してみたところ、 OpenJDK 64-bit 16.0.2 では 918 ms, 17 では 932 ms となっており、手元の環境ではなぜかあまり変化がなかったようです。あれ……？
(ちなみに、 nextExponential() も同じアルゴリズムで実装されています。)

`RandomGeneratorFactory`

RandomGeneratorFactory というファクトリも追加されています。これを使うと、アルゴリズム名からインスタンスを生成したり、性質に応じて (例えば内部状態が 256 bit 以下のものを) 抽出したりすることができます。
また、 RandomGeneratorFactory.getDefault().create() でアルゴリズムを明示せずにインスタンスを生成することもできます。現行実装では L32X64MixRandom が選ばれるようです。

なぜ L32X64MixRandom がデフォルトになったのかは正直よくわかりません……
L32X64MixRandom は 32 bit 環境に特化したものであり周期が短めで、一度に 64 bit 必要な乱数生成 (nextDouble() や nextLong() など) や大規模な並列実行には向いていません。
L64X128MixRandom が無難でよかったのでは、と思ってしまいます。

余談・リリース以降の更新点について

L32X64MixRandom#nextLong() の不思議な実装については、前回の記事をご覧ください。

コミットログを見ると、一時期 L32X64MixRandom と L128X256MixRandom の初期化周りで問題があったらしいですが、現在は解消されています。

また、 nextGaussian() と nextExponential() の分布が正しくなかった問題もあったようですが、こちらも解消されています。

アルゴリズムの選び方

LXM アルゴリズムが大量に追加されていてどれをどう使えばいいか分からなくなりそうだったので、 API ドキュメントの内容をざっくり私見も含めつつまとめると、優先度順に

セキュリティ関連・シード値など 予測不可能性が必須 → SecureRandom
32 bit 環境 → L32X64MixRandom
高速性 が重要 → Xoroshiro128PlusPlus
小～中規模の並列処理 がしたい → L64X256MixRandom
超大規模の並列処理 がしたい → L128X256MixRandom
多次元均等分布性 が重要 → L64X1024MixRandom
とくに要件がない、 とりあえず動けばいい → L64X128MixRandom
(または RandomGenerator.getDefault())

といった感じです。

「多次元均等分布性が重要」というのは、身近な例ではトランプなどのシャッフルです。
n 要素のシャッフルは $n!$ 通りの結果を持ちますが、小さな擬似乱数生成器だとこれだけのパターンを生成することができない場合があり、そうなると「絶対に出現しない盤面」が出てしまいます。
例えば、トランプ (ジョーカー 2 枚) なら $54! \approx 2 ^ {237}$ 通り、麻雀牌なら $136! \approx 2 ^ {773}$ 通り *4 になるので、最低でも (2冪の指数) ビット分の均等分布性を持つ擬似乱数生成器を選ぶ必要があります。
今回のアルゴリズムでいえば、トランプなら最低でも L64X256MixRandom を、麻雀牌なら L64X1024MixRandom を、ということになります。

ただこれは理想的な処理を行った場合の話で、例えば安直に nextLong(54) などとして乱数を生成してしまうとそれだけで 64 bit 分の情報量を消費してしまうので、トランプの例では $64 \times 54 = 3456$ ビット必要になってしまいます。それだと L64X1024MixRandom でも足りないのでビット数を節約するよう工夫しなければなりません。 (byte 単位に分割して自分で nextLong(max) 相当のコードを書く、など。)
さらに言えば、現時点で LXM ファミリを引数なしの RandomGenerator.of(algorithm).create() から生成した場合、内部的には long のシード値を用いて初期化されるため、初期状態は $2 ^ {64}$ パターンに限定されてしまいます。もし全パターンを均等に得たい場合は create(byte[] seed) に十分な情報量を持つソース (SecureRandom の出力など) を渡して初期化する必要があります。

均等分布性について

ちょうど均等分布性の話が出たので、 Package Summary の "The LXM Family of Random Number Generator Algorithms" の均等分布性に関連する部分の解説をしたいと思います。

exactly equidistributed とは

"exactly equidistributed" (勝手訳: 厳密に均等分布する) とは、 nextLong() で得られる値について、すべての値が厳密に等確率で出現させられる、ということです。

L32X64MixRandom 以外の LXM ファミリについては、この性質を満たします。
L32X64MixRandom は、 32 bit 精度 (nextInt()) では厳密に均等分布しますが、 64 bit 精度 (nextLong()) では厳密に均等分布しません。
詳しく説明すると、 L32X64MixRandom#nextLong() は ((long)nextInt() << 32) ^ (long)nextInt() として実装されているため、 nextLong() で厳密に均等分布させるためには nextInt() 2 回分 (= 2 次元に) 厳密に均等分布させる必要がありますが、 L32X64MixRandom#nextInt() は 1 次元までしか厳密に均等分布しません。そのため、 nextLong() では厳密に均等分布しないことになります。

また、 Xoroshiro128PlusPlus と Xoshiro256PlusPlus については記載がありませんが、厳密に均等分布しないと思われます。内部状態がすべて 0 にはならないので、その時に出力されるはずだった 0 の出現個数が他の値より 1 少なくなるためです。
具体例としては、 Xoroshiro128PlusPlus では 0 が出る確率が $\frac{2 ^ {64} - 1}{2 ^ {128} - 1}$ 、それ以外の値はそれぞれ $\frac{2 ^ {64}}{2 ^ {128} - 1}$ となります。

ちなみに、 LCG (線形合同法) は基本的に厳密に 1 次元均等分布します。
具体例で説明します。 64 bit の線形合同法 (L64) は周期が $2 ^ {64}$ であるので、その周期中に long がとりうる全ての値を各 1 回だけ、すなわち厳密に等確率 $2 ^ {-64}$ で出力します。したがって厳密に均等分布するといえます。

k-equidistributed とは

"k-equidistributed" (勝手訳: k 次元均等分布する) とは、要素数 k の long[] を連続する nextLong() で埋めたとき、すべての値の組み合わせが「ほぼ」等確率で出現させられる、ということです。
こちらは "exactly equidistributed" よりは緩めで、「厳密に」等確率でなくてもよいようです。上に挙げた Xoroshiro128PlusPlus のように $2 ^ {-128}$ オーダーでの違いは許容しよう、といった雰囲気です。

この性質は、従来のアルゴリズムでは Mersenne Twister の「623 次元均等分布」が有名でしょう。 (ただしこれは 32 bit 精度 (int[]) での値です。)

具体例として、 2 次元均等分布する L64X128MixRandom で考えてみましょう。
まず、内部の xoroshiro128 は {0, 0} 以外の任意の 2 次元ベクトルを生成することができます。 (つまり、 xoroshiro128 は単体で 2 次元均等分布します。)
ここに LCG パートを合わせるので、 XBG パートで {0, 0} だった場合の (つまり発生しえない) {mix(s), mix(s * m + a)} (s, m, a は LCG の内部状態と乗算定数・加算定数を示します) のベクトルが生成されるパターンが 1 つ少なくなって全周期中にそれぞれ $2 ^ {64} - 1$ 個、それ以外のベクトルはそれぞれ $2 ^ {64}$ 個ずつ生成されることになります。分母 (全周期) は $2 ^ {192} - 2 ^ {64}$ なので、 $2 ^ {-128}$ オーダーでの違いとなります。

なお、 RandomGeneratorFactory.of(algorithm).equidistribution() で得られる値は、こちらの k 次元均等分布のほうです。

以下に 64 bit 精度での均等分布次元をまとめた表を示します。

アルゴリズム名	均等分布次元	厳密に均等分布するか
L32X64MixRandom	1 (2 @ 32bit)
L64X128MixRandom	2	☑
L64X128StarStarRandom	2	☑
L64X256MixRandom	4	☑
L64X1024MixRandom	16	☑
L128X128MixRandom	2 ?	☑
L128X256MixRandom	4 ?	☑
L128X1024MixRandom	16 ?	☑
Xoroshiro128PlusPlus	1
Xoshiro256PlusPlus	3

? をつけた箇所は API ドキュメント及び equidistribution() ではなぜか 1 となっていますが、実際はそれぞれ 2, 4, 16 が正しいのではないかと思います。
L128X128MixRandom ・ L128256MixRandom ・ L1281024MixRandom は、内部の XBG パート (xoroshiro128 ・ xoshiro256 ・ xoroshiro1024) がそれぞれ 64 bit 精度で 2 / 4 / 16 次元均等分布します。
これと LCG パートを組み合わせて最終的な出力が得られるのですが、この時 LCG パートの出力がどのようなものであれ XBG パートが均等分布する = 任意の値 (k 次元ベクトル) をとることができるのですから、組み合わせた出力も (XBG パートでよしなにすることで) 任意の値をとることができる = 均等分布する、と考えられます。

おわりに

.NET といい Java といい、最近標準ライブラリの擬似乱数生成器の改善がアツいです。(2021年当時の感想)

全体の所感としては、高速性をとった .NET と拡張性をとった Java という印象を受けました。
また両者とも xo(ro)shiro 系アルゴリズムを採用しており、浸透してきたようで勝手に嬉しく思っています。

ただ、他に採用実績がない初出のアルゴリズムを標準ライブラリにぶち込んでいくのはなかなか挑戦的だな、という気持ちがあります。
もちろん内部構造はどれもよく研究されたものですので無謀というわけではないですが、公開されてから欠点が見つかることはよくあるので…

*1:Anonymous Author(s). 2017. Better Splittable Pseudorandom Number Generators (and Almost As Fast). PACM Progr. Lang. 1, 1, Article 1 (January 2017), 41 pages.

*2:David Blackman and Sebastiano Vigna. Scrambled linear pseudorandom number generators, 2019. To appear in ACM Trans. Math. Softw..

*3:Guy L. Steele Jr. and Sebastiano Vigna. 2021. LXM: better splittable pseudorandom number generators (and almost as fast). Proc. ACM Program. Lang. 5, OOPSLA, Article 148 (October 2021), 31 pages. https://doi.org/10.1145/3485525

*4:同種の牌も区別しているものとします。区別しなければ約 $2 ^ {617}$ 通りになります。

2023-03-16

JDK にバグ報告してみたおはなしと、 Java における LXM の不思議な実装について

はじめに

どの擬似乱数生成器が速いのかを BenchmarkDotNet で調べるために、いろいろな擬似乱数生成器を C# に移植して遊んでいたのが発端です。

Java では、JDK 17 から LXM ファミリという擬似乱数生成器が追加されています。
簡単に説明すると、線形合同法 (LCG) と xoroshiro/xoshiro を組み合わせて (Mix して) 出力する擬似乱数生成器です。組み合わせは 8 種類あり、内部状態 96 bit の小規模なものから 1152 bit の大規模なものまで取り揃えています。

実例として、 L32X64MixRandom の C# 移植例はこのようになります。

public sealed partial class L32X64Mix
{
    private uint _increment;
    private uint _lcgState;
    private uint _xbgState0, _xbgState1;

    public L32X64Mix(uint increment, uint lcgState, uint xbgState0, uint xbgState1)
    {
        if (xbgState0 == 0 && xbgState1 == 0)
            throw new ArgumentException("xbgState must not be all zero");

        _increment = increment | 1;
        _lcgState = lcgState;
        _xbgState0 = xbgState0;
        _xbgState1 = xbgState1;
    }

    public uint NextUInt()
    {
        // Mix
        uint result = _lcgState + _xbgState0;
        result = (result ^ result >> 16) * 0xd36d884b;
        result = (result ^ result >> 16) * 0xd36d884b;
        result = (result ^ result >> 16);

        // LCG
        _lcgState = _lcgState * 0xadb4a92d + _increment;

        // xoroshiro64
        (uint s0, uint s1) = (_xbgState0, _xbgState1);
        s1 ^= s0;
        s0 = BitOperations.RotateLeft(s0, 26) ^ s1 ^ s1 << 9;
        s1 = BitOperations.RotateLeft(s1, 13);
        (_xbgState0, _xbgState1) = (s0, s1);

        return result;
    }
}

これは 32 bit LCG + xoroshiro64 の組み合わせの最も小規模な LXM で、主に 32 bit 環境を主眼とした実装です。ちなみに RandomGenerator#getDefault() でもこれが生成されます。
~~デフォルトは L64X128 とかのほうが良かったのでは、と思わなくもない~~

テスト結果が合わない

擬似乱数生成器の実装において、テストはとてつもなく重要です。
うっかり間違った実装をしたとしても結果はランダムなので、全く気づけなくなります。

今回は Java の実装から乱数を出力させてテストケースを作成しました。特定のシードで初期化してから 20 個の nextLong() の結果があっていればおそらく大丈夫でしょう、ということで…

import java.util.random.*;

class javaprng {
    public static void main(String[] args) {

        RandomGenerator rng = RandomGeneratorFactory.of("L32X64MixRandom").create(42);
        for (int i = 0; i < 20; i++) {
            System.out.printf("%016x%n", rng.nextLong());
        }
    }
}

C# 移植側の nextLong() 互換実装はこんな感じです。

public sealed partial class L32X64Mix
{
    public ulong Next()
    {
        return (ulong)NextUInt() << 32 ^ (ulong)NextUInt();
    }
}

というわけでテストにかけてみたのですが、これが何度直しても通りません。
Java 側と C# 移植側の出力を比べるとどうにも合わないのです…。

この diff を見ると、半々程度の割合で上位 32 bit が合っていない場合があるようです。
そこで、改めて Java 側の nextLong() の実装を確認することにしました。

public long nextLong() {
    return ((long)nextInt() << 32) ^ (long)nextInt();
}

L32X64MixRandom は 32 bit ベースなので、 nextInt() がメインの遷移・出力関数です。これを 2 個つなげて long つまり 64 bit にしている、ように見えます。
ところが、その認識が誤っていたことに気づきました。

念のため説明しておくと、 Java には組み込みの符号なし整数型 (C# でいう ulong) がありません。
そのため long にキャストして拡張しているわけなのですが、これは符号付き整数型のため、符号拡張が行われます。
ということはつまり、 nextInt() が負の (最上位ビットが 1 の) 数を返した場合に、符号拡張のため上位 32 bit にも情報がはみ出します。具体例を挙げると、nextInt() が 0xfedcba98 を返した場合、 (long)nextInt() は 0x00000000fedcba98 ではなく 0xfffffffffedcba98 になります。

これを上位ビットと xor でつなげているため、下から 32 ビット目 (2 個めの nextInt() の最上位ビット) が 1 のときに上位 32 bit が反転するという現象が起きているわけです。
この情報をもとに diff をよく見ていただけると分かるかと思います。

そうなると、果たしてそれは妥当なのか、という疑問が浮かびました。乱数の出力が変わってしまっているわけですから、本来の性質を保てているか分からなくなってしまうのでは？と思いました。

なので、バグ報告をしてみることにしました。

JDK に報告してみる

バグレポートは https://bugreport.java.com/bugreport/ から投げることができます。アカウントなどは不要のようです。

ここにバグの概要や環境情報、再現用コードや回避手段などを記入して投げます。

1 日程度待つと、中の人が確認してくれた上で、チケットが発行された旨のメールが届きます。

これでチケットが web 上で確認できるようになりました。私が記入した内容が載っているので、知りたい方はご参照ください。英語に不安がある……

また、あとから何かに気づいたなど追加情報がある場合は、このメールにあるリンクから送信することができます。

あとは中の人たちがよしなにしてくれるのを待ちます。

バグじゃなかった？

チケット公開から 1 日ほど経ったころ、チケットが resolved になりました。 "Not an Issue" とのこと…

中の人曰く (意訳)、

報告者は、ランダムな 32 bit をつなげて 64 bit にするのが正しいと仮定しているが、これはドキュメント化されていない挙動である (ので、それが正解とは限らない) 。
現在の実装は驚くべきものに見えるかもしれないが、均等分布性は損なわれていない。

(現行実装の) nextLong() から 2 つの nextInt() の結果を復元することは可能であり、情報の損失や生成はない。
nextInt() 2 個と nextLong() の間には全単射の関係があり、前者が一様分布なら、後者も一様分布になる。

もし接続が xor ^ ではなく or | だったら、それは不具合だっただろう。

ということで、これで問題ないとのことです。なんと……

ただ実際、仮に直したとしても再現性が維持できなくなる問題が出てくるので、これはこれで良かったのではないか、とも思います。

なので、 C# における nextLong() の正しい互換実装はこのようになります:

public sealed partial class L32X64Mix
{
    public ulong Next()
    {
        // see https://bugs.openjdk.org/projects/JDK/issues/JDK-8304120
        return (ulong)NextUInt() << 32 ^ (ulong)(long)(int)NextUInt();
    }
}

せっかくなので、本当に問題ないかどうか、擬似乱数生成器のテストフレームワークである PractRand に nextLong() の出力を与えてテストしてみました。

RNG_test using PractRand version 0.94
RNG = L32X64MixRandomJava64, seed = 0x19aa8a23
test set = expanded, folding = extra

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 512 megabytes (2^29 bytes), time= 2.9 seconds
  no anomalies in 1220 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 1 gigabyte (2^30 bytes), time= 7.7 seconds
  no anomalies in 1293 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 2 gigabytes (2^31 bytes), time= 15.4 seconds
  no anomalies in 1368 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 4 gigabytes (2^32 bytes), time= 29.2 seconds
  no anomalies in 1448 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 8 gigabytes (2^33 bytes), time= 60.3 seconds
  no anomalies in 1542 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 16 gigabytes (2^34 bytes), time= 117 seconds
  no anomalies in 1636 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 32 gigabytes (2^35 bytes), time= 213 seconds
  no anomalies in 1716 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 64 gigabytes (2^36 bytes), time= 455 seconds
  no anomalies in 1807 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 128 gigabytes (2^37 bytes), time= 914 seconds
  no anomalies in 1902 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 256 gigabytes (2^38 bytes), time= 1667 seconds
  no anomalies in 1983 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 512 gigabytes (2^39 bytes), time= 3541 seconds
  no anomalies in 2058 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 1 terabyte (2^40 bytes), time= 7137 seconds
  no anomalies in 2132 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 2 terabytes (2^41 bytes), time= 14111 seconds
  no anomalies in 2194 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 4 terabytes (2^42 bytes), time= 29294 seconds
  no anomalies in 2255 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 8 terabytes (2^43 bytes), time= 59262 seconds
  no anomalies in 2313 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 16 terabytes (2^44 bytes), time= 119867 seconds
  no anomalies in 2366 test result(s)

時間の都合で 16 TB までですが、問題は検出されませんでした。
実際のところも問題なさそうです。

おわりに

想像していたより簡単にバグ報告ができることがわかりました。

また、ご対応いただいた中の人 (?) には大変ご迷惑をおかけしました…
思っていたより対応が速くて助かりました。

せっかくなので、今回作成した LXM のテストベクトルを付録として公開します。
シード値 42 で初期化してから連続する 20 個の nextLong() 出力を観測したものです。別言語への移植をされる方がもしいらっしゃいましたらご利用ください。

LXM PRNG test vectors

2022-06-19

Unicode の入力・表示テストに使える文字(列)

はじめに

アプリやゲームにおいて、「自由入力」のテキストボックスやそれを表示するラベル (ユーザ名・コメント欄・etc.) などを安易に設置すると、想定の斜め上を行く妙な文字(列)を入力され、意図しない表示・処理になることが多々あります。
本稿では、そのテストに使えるような文字(列)を記載していきます。なるべくコードポイント (U+xxxx) も併記するようにしました。

想定環境は主に PC ・スマートフォンで動作するクライアント (もっと具体的には Unity の TextMeshPro InputField) です。
Web やデータベース周りでは、例えば古典的な XSS や寿司ビール問題など別種の気を付けるべきポイントがあるかもしれませんが、あまり詳しくないのでここには記載しません。

なお、特に注記がない場合は Unicode / UTF-8 であるものとします。
環境によっては正しく表示されない可能性がありますがご了承ください。逆に考えると、その環境ではこれらのテストが有効であったことを意味します…
執筆環境は Windows 10 (游明朝が利用可能) / Firefox です。

省エネのため箇条書きスタイルでお送りしますが、ご了承ください。

はじめに
テストに使える文字(列)
余談
おわりに

テストに使える文字(列)

空文字列

それはそう

空白文字

U+0020 " " (半角スペース)
U+3000 "　" (全角スペース)
U+0009 " " (Tab)
- 環境によってサイズが大きく異なる
U+200B "" (ゼロ幅スペース)
その他 → スペース / 幅の比較
U+2800 "⠀" (点字カテゴリの点がない文字)
- 見た目上空白だが So (Symbol, Other) カテゴリのため、 Zs (Separator, Space) カテゴリを禁止してもすり抜ける
空白文字のみで構成された文字列を許容するか？

改行文字

U+000D U+000A (CR LF), U+000A (LF) のどちらか？
連打された場合にレイアウトが破綻しないか
- あるいは、そもそも入力できるのが適切かどうか
末尾の空行を行数にカウントするか

RTL (Right-to-Left)

右から左へ描画するシステム (アラビア文字など)
- العربية
  - U+0627 U+0644 U+0639 U+0631 U+0628 U+064A U+0629
  - データ上の並び順としては ‭ ا ـل ـعـ رـ ـب ـيـ ةـ となっている
U+202E (Right-to-Left Override)
- 後続文字の描画順を強制的に「右から左」にする
- ABCD と ‮DCBA
- 上記 2 つは同じに見えるが、後者はデータ上 U+202E に続けて DCBA と並んでいる
- 禁止ワードフィルタをすり抜ける、正しいファイル名に見せかけるなど大問題になりうる
  - "正規ファイルだよ‮xcod.exe‬" はデータ上 "正規ファイルだよ U+202E xcod.exe" であるので、実行ファイルとして開けてしまう
RTL と LTR の混在
- 例: アラビア文字 (RTL) の文章中でも、数字は LTR (Left-to-Right) として描画されるべき
  - لدي 100 تفاحة.
    - == I have 100 apples.

その他の制御文字・特殊な文字

U+0000 "�" (␀)
- ヌル文字 \0
- これが文字列終端になる環境 (C など) の場合、挿入することで後続の文字列を事実上消せる
  - Windows ではヌル文字とその後続をクリップボードにコピーできない
U+0007 "" (␇)
- ベル \a
- ターミナルで出力すると音が鳴るなどする
U+FFFD � (REPLACEMENT CHARACTER)
- UTF-8 として不正なバイト列を読んだ場合などで出現
- コピペなどで正規に(?)入力することもできるが、一般のユーザにはバグ・文字化けに見えそう

その環境における制御文字(列)

データベース (?) が csv の場合における , や "
Unity (TextMeshPro) における <b> や <s> , <color=red> など
- そもそも Rich Text を切るか、 < を <noparse><</noparse> に置換することでサニタイズする

長い文字列

テスト例
- Lorem ipsum
- 青空文庫 (あのイーハトーヴォのすきとおった風…)
KB ～ MB オーダーの文字列を突然コピペされたときに動作するか
IME の変換前状態で、一時的にテキストボックスの文字数制限を突破できる場合がある
- 毎フレーム処理したり、文字変更イベントを都度受け取ったりするタイプの環境では注意
文字の正規化処理で長くなる可能性 → 正規化
- U+FDFA ﷺ は NFKD ・ NFKC 正規化で 18 文字に分解されうる
  - U+0635 U+0644 U+0649 U+0020 U+0627 U+0644 U+0644 U+0647 U+0020 U+0639 U+0644 U+064A U+0647 U+0020 U+0648 U+0633 U+0644 U+0645
  - صلى الله عليه وسلم
  - C# では "\ufdfa".Normalize(System.Text.NormalizationForm.FormKD) で確認可能
- 正規化が必要な場合、正規化→長さチェックの順に行う (逆だと限界突破しうる)

大きなスペースをとる文字

以下原寸大。特に最初の 2 つは入力・表示できてしまう環境が多いため注意
U+A9C5 ꧅
U+FDFD ﷽
U+A9C1 U+A9C2 ꧁꧂
U+12031 𒀱
U+1242B 𒐫

大きなスペースをとる文字列

U+0E14 U+0E47 (x10) ด็็็็็็็็็็
U+05D1 U+059F (x10)
- ב֟֟֟֟֟֟֟֟֟֟

スペースをとらない・不可視の文字

U+200B "" (ゼロ幅スペース)
U+200C "‌" (Zero width non-joiner; ZWNJ)
U+2063 "⁣" (Invisible Separator) やほかにもたくさん
U+180E "᠎" (Mongolian Vowel Separator)
- 上記と異なり General Punctuation ブロックではないので注意
なりすましや文字数稼ぎに利用されうる
- アカウント名の末尾に追加して重複判定を回避する、4 文字以上必須のユーザ名を (見た目上) 空文字列にする、など
U+05D1 U+05BC (x10) בּּּּּּּּּּ
- U+05BC を大量に重ねても幅をとらない

複数の表現がある文字 (正規化)

同一の文字に複数の表現方法がある場合
- U+304C が
  - 単一の文字としての「が」
- U+304B U+3099 が
  - 「か」 + 濁点
- その他、アルファベットでのダイアクリティカルマークなど → 参照
これらが混在していると、検索・ソートなどを愚直に (バイト一致判定で) 行った場合に問題になる
- 正規化によってこれらを直感的に正しく行える
- ただし、非可逆な操作なので保存する場合は注意

UTF-16 において 2 バイトで表現できない (U+10000 以降の) 文字

U+29E3D 𩸽 (ほっけ)
U+1F97A 🥺 など多くの絵文字が該当する
UTF-16 ベースで、サロゲートペアを正しく扱えないシステムにおいて問題になる
- 例: C# において文字列長を string.Length でとっているとズレが生じる

フォントに含まれない文字

明らかに文化の異なる文字は自明
- U+1740 ᝀ ブヒッド文字や U+10000 𐀀 線文字 B など
Unicode の比較的小さな部分にある漢字は機械的に弾きにくいかもしれない
- U+34C7 㓇など
- JIS X 0213 の第 4 水準あたりは対応していないものが多そう
  - 上の字は Adobe-Japan1-4 に対応しているクレーに含まれないことを確認。ただ、当然一般的なものはほぼ含まれているので特殊な人名用漢字や異体字でない限り実用上問題になることは少なさそう
もし対応文字数が少ないフォントを利用している場合は、デザインのずれが許容できるフォールバックフォントを用意するか、厳しめの (ホワイトリストのような) 文字制限をかける

異体字 セレクタ

U+FE00 ～ U+FE0F, U+E0100 ～ U+E01EF を後ろにつけると文字の細かなバリエーションが変わる
漢字
- 葛󠄀 (U+845B U+E0100; 下部が "ヒ")
- 葛󠄁 (U+845B U+E0101; 下部が "L + 人")
- 邉邉󠄀 邉󠄁 邉󠄂 邉󠄃 邉󠄄 邉󠄅 邉󠄆 邉󠄇 邉󠄈 邉󠄉 邉󠄊 邉󠄋 邉󠄌 邉󠄍 邉󠄎 邉󠄏 邉󠄐 邉󠄑 邉󠄒 邉󠄓 邉󠄔 邉󠄕 邉󠄖 邉󠄗 邉󠄘 邉󠄙 邉󠄚 邉󠄛 邉󠄜 邉󠄝 邉󠄞 邉󠄟
  - 最初の一文字 U+9089 がオリジナル (単体) で、それ以降は U+E0100 ～ U+E011F の異体字セレクタを後続させている (フォントの関係上すべて別の字形になっているとは限らないが)
  - → 参照
絵文字のスタイル選択
- U+2615 ☕ に異体字セレクタをつけて
  - U+2615 U+FE0E ☕︎ (テキストスタイル)
  - U+2615 U+FE0F ☕️ (絵文字スタイル)

国と地域の旗の絵文字

U+1F1EF U+1F1F5 🇯🇵 (日本の国旗)
- 2 文字で表すタイプ → Regional indicator symbol
  - 🇯 と 🇵 (JP) からなる
- 仕様上、検索などで問題になりうる
  - 🇰🇷🇺🇸 (韓国とアメリカ; KR US) のテキスト上で 🇷🇺 (ロシア; RU) を検索するとマッチしてしまう
  - → 参考
U+1F3F4 U+E0067 U+E0062 U+E0065 U+E006E U+E0067 U+E007F 🏴󠁧󠁢󠁥󠁮󠁧󠁿 (イングランドの旗)
- 旗 + 地域コード(ここでは gbeng) + 終了で表すタイプ → Emoji tag sequences

外字

U+E000 ～ U+F8FF, U+F0000 ～ U+FFFFD, U+100000 ～ U+10FFFD
そもそも入力できて良いのか？を検討すべき
有名どころでは Apple の U+F8FF  (林檎のロゴ) や Twitter の U+EA00  (例の鳥) など
それ以外の用例は → Private use areas
特殊なところでは Ninja cat 🐱‍👤 → ニンジャキャット
- U+1F431 U+200D U+1F464 🐱 + ZWJ + 👤
- Windows 10 では 1 文字の Ninja cat 絵文字が描画される
  - 構成文字自体は一般的な (Unicode に存在する) ものだが、組み合わせたとき独自の描画になる

最近追加された文字

2022/06/01 現在最新の Unicode 14.0 (2021/09) で追加された文字
- U+1FAE0 🫠 (溶ける顔) など
超マイナーな文字ならともかく、絵文字は比較的入力しやすいので危ない
文字が追加される前提で設計しなければならない

複数のコードポイントで表現される文字

👨🏻‍👩🏿‍👦🏽‍👦🏼 → ソース (図6)
- 分割すると 👨 + 🏻 + ZWJ + 👩 + 🏿 + ZWJ + 👦 + 🏽 + ZWJ + 👦 + 🏼
- U+1F468 U+1F3FB U+200D U+1F469 U+1F3FF U+200D U+1F466 U+1F3FD U+200D U+1F466 U+1F3FC
- 1 書式素に 11 コードポイント、 UTF-8 では 41 バイト
  - 書式素 (Grapheme) : 人間が見て "1 文字" と思える単位 (要約)
- これを正しく "1 文字" として判定するには、書式素単位でカウントできる StringInfo.GetTextElementEnumerator() や GraphemeSplitter ライブラリなどを利用する
👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩
- U+1F469 U+200D を繰り返している。 35 コードポイント、 UTF-8 で 122 バイト
- カーソルを動かす / 選択すると分かるように、これでも 1 文字扱いされる
👩‍⚕️ (Woman health worker)
- U+1F469 U+200D U+2695 U+FE0F
- 👩 + ZWJ + ⚕ + 異体字セレクタ (emoji; ⚕️)
- → Unicode 14.0 における emoji ZWJ sequence の一覧
👨🏿‍🦳
- U+1F468 U+1F3FF U+200D U+1F9B3
- 👨 + 🏿 (dark skin tone) + ZWJ + 🦳 (white hair)
  - skin tone の範囲は U+1F3FB ～ U+1F3FF
  - hair の範囲は U+1F9B0 ～ U+1F9B3
#️⃣
- U+0023 U+FE0F U+20E3
- # + 異体字セレクタ(emoji) + 囲み(キーキャップ)
ஙொ
- U+0B99 U+0BCA
- U+0BCA ொ は直前の文字を挟み込む形で作用する

色がある前提の絵文字・色を付ける絵文字

モノクロ描画の場合、識別が難しくなる可能性はある
例 (上が通常、下は異体字セレクタ U+FE0E を後続させてテキストスタイルにしたもの)
- U+26AA U+26AB U+1F534 U+1F535 U+1F7E0 U+1F7E1 U+1F7E2 U+1F7E3 U+1F7E4
  - ⚪⚫🔴🔵🟠🟡🟢🟣🟤
  - ⚪︎⚫︎🔴︎🔵︎🟠︎🟡︎🟢︎🟣︎🟤︎
- U+2B1B U+2B1C U+1F7E5 U+1F7E6 U+1F7E7 U+1F7E8 U+1F7E9 U+1F7EA U+1F7EB
  - ⬛⬜🟥🟦🟧🟨🟩🟪🟫
  - ⬛︎⬜︎🟥︎🟦︎🟧︎🟨︎🟩︎🟪︎🟫︎
- Unicode の字形例ではハッチで描き分けている
複数のコードポイントを利用する場合
- U+1F408 U+200D U+2B1B 🐈‍⬛ (黒猫)
- U+1F44F U+1F3FB 👏🏻 (skin tone)

合字 (リガチャ)

連続すると見た目が変わる文字
コードポイント的には ae と æ (U+00E6) など
フォント(描画システム)側で解決する場合もあり
- ffi / ffi
- 前者がリガチャ無効、後者がリガチャ有効。コードポイントとしては同じ ffi
文字体系がリガチャ前提なデーヴァナーガリーなど
- द्ध्र्य は、 द ् ध ् र ् य で構成されている
  - U+0926 U+094D U+0927 U+094D U+0930 U+094D U+092F
  - → 参照

非常に似ている文字

A А Α
- U+0041 U+0410 U+0391 ; それぞれラテン文字・キリル文字・ギリシア文字
システム的には問題なくとも、なりすましや誤認に利用できる場合がある → ホモグラフ攻撃
- → セキュリティ関連の文献

環境に依存して見た目が変わる文字

ロケール
- 骨骨骨骨骨骨
- コードポイントはすべて U+9AA8
- lang にそれぞれ zh-CN, zh-TW, zh-HK, ja-JP, ko-KR, vi-VN (中国, 台湾, 香港, 日本, 韓国, ベトナム) を指定している
OS
- 絵文字は環境によって大幅に字形 (イラスト?) が異なる場合がある
- U+1F3AB 🎫 (チケット)
  - → 様々な環境での見え方
  - 確かに「チケット」だが、色合い・向きなどは多種多様
    - 色や向きなどに意味を持たせた表現をすると、別の表示になる受け手の解釈が変わってくる
    - どうしても統一したい場合は画像埋め込みか？ (それでも IME とは表示が異なる)

1 文字あたりのバイト数が大きい文字

コードポイント単位
- U+10000 以降の 4 バイトが最大 (UTF-8, UTF-16)
書式素単位
- イングランドの旗 🏴󠁧󠁢󠁥󠁮󠁧󠁿 は UTF-8 において 28 バイト
- 家族の絵文字の無限連結 👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩 (制限なし)
文字数制限がバイト・ワード単位でしか設定できない環境 (C# の string.Length に依存している場合など) では、上記の文字を入力した場合に「見た目上の文字数」が著しく少なくなってしまう
- 逆に、書式素単位で設定すると非常に大きいバイト数の文字を入力される可能性がある
厳密に判定するなら書式素の数を数える。また、十分余裕を持ったバッファを用意しておく
正規化で大きくなる文字 (前述)
- U+FDFA ﷺ は 1 文字から 18 文字に (UTF-8 では 3 バイトから 33 バイトに) 膨らむ

不正な文字列・バイト列

解釈できないバイト列
- UTF-8 における C0 AF
  - U+002F / を 2 バイトで表現した…ともとれるが、 / は 2F の 1 バイトで表現しなければならないため不正
  - これを / と解釈するとディレクトリトラバーサル対策の回避などに利用できてしまうため → セキュリティ
- UTF-16 における D8 D8 (サロゲートペアの片割れ)
  - サロゲートペアを用いる文字を入力した際、一時的に現れる場合がある
    - char 単位でしか検証できない環境 (Unity の InputField.OnValidateInput) など
  - 文字数制限でペアの片割れだけ弾いてしまう、片割れのままログ出力してしまうなどでエラーになりうる
- ただ、一般的な IME から直接入力・コピペする手段はないはず
- 不正な部分は U+FFFD � に置き換えられうる (VSCode で確認)
  - 環境によってはより深刻なエラーにもなりうるため、存在させない
非文字
- 文字ではないコードポイント (未定義とは異なり、将来的にも文字になりえない)
- U+FFFE
  - (UTF-16 において) U+FEFF (BOM) のバイト順を逆に解釈するとこれになる。したがって、これを認識した場合はバイト順を逆にして読むべきであると分かる
  - 補足: BOM → Byte Order Mark
    - UTF-8 において EF BB BF
    - ただし、 UTF-8 においては推奨はされない (あってもいいが、 UTF-8 はそもそもエンディアンに依存しないため入れる必要がない)
- 「存在してはいけない」わけではなく、内部的に使用されることはある (最も、外部とのやりとりに使うべきではない)
未定義の文字
- 将来的に定義されうる
  - U+32FF ㋿をあらかじめ入力しておくことで「元号を予言」する
    - → 参照 (ツイート日時は元号発表 2019/04/01 よりも前)

余談

上記に載せるほどではない、文字関連の余談です。

幽霊文字

実際の利用例がない文字 → Wikipedia
プログラム的には気にしなくてよい。しいて言えばフォントが対応しているかぐらい
- その定義からして使われることはまずないが…
マシュマロでは U+5F41 彁を伏せ字に利用している
- 利用例がないことを逆手に取っている → 参照

点字

U+2800 ～ U+28FF → Wikipedia
ドットアートが可能 ⠠⠵
U+2800 "⠀" は見た目上空白だがカテゴリが Other Symbol のため、空白カテゴリを禁止してもすり抜ける可能性がある (上述)

Methematical Alphanumeric Symbols

𝑰𝑵𝑻𝑬𝑹𝑵𝑬𝑻 𝑨𝑵𝑮𝑬𝑳
文字だけで (フォントを変えることなく) 書体を変えることができる → リスト
A 𝐀 𝐴 𝑨 𝖠 𝗔 𝘈 𝘼 𝒜 𝓐 𝔄 𝕬 𝙰 𝔸
- U+0041 U+1D400 U+1D434 U+1D468 U+1D5A0 U+1D5D4 U+1D608 U+1D63C U+1D49C U+1D4D0 U+1D504 U+1D56C U+1D670 U+1D538
基本的にコードポイントは連続しているが、一部既に存在した文字 (U+210E ℎ など) の箇所は未割り当てになっているので注意 (前述の ℎ に対応する U+1D455 など)
- また、既存だった文字は書体がずれがちなので注意
  - ... 𝑓 𝑔 ℎ 𝑖 𝑗 ...
  - きちんとやりたいならフォントを変えるべき

実際に問題を起こした文字列

Black dot bug
- iOS で特定の文字列を表示するとアプリがクラッシュしていた → 参照
- U+0020 U+003C U+26AB U+003E U+0020 U+1F448 U+1F3FB U+0020 (U+200E U+200F)x891 U+0020 U+200E
  - → gist
  - LTR と RTL が非常に多く含まれている
- Apple でさえ、バグるときはバグる
テルグ文字 (の一部の組み合わせ)
- 同じく iOS でクラッシュしていた → 参照
- U+0C1C U+0C4D U+0C1E U+200C U+0C3E
  - → pastebin
  - Black dot bug とは異なり短いが、壊れるときは壊れる

ひらがなは 2 バイト文字か？

UTF-8 において "2 バイト文字" ではないのは自明。 2 バイトなのは U+07FF までで、平仮名ブロックは U+3040 から始まる
では「すべてのひらがなは 3 バイト」と言えるか?
U+1B001 𛀁 (や行え) はひらがなであり 4 バイト (UTF-8 で F0 9B 80 81) なので、つまり一概には言えない

おわりに

以上のように、個性豊かな文字(列)がたくさん存在します。
たかが文字、されど文字…
~~全部 Unicode が悪い… と思いましたが文字は実世界の映しではあるので、つまり人類が悪い~~
また、本稿は問題になりうる文字を網羅したものではなく、あくまでそれらの一部です。

テキストボックス実装の際は、全部対応…　するのは骨が折れるどころか複雑骨折するので、何らかのライブラリを利用するか、目立つところは処理してあとは心の隅に置いておくか、とするとよさそうです。

コピペが簡単になるように以上をまとめたテキストファイルをご用意いたしました。
上述の文字(列)たちを LF 改行で記載しています。テストにご利用ください。
※ U+0000 (ヌル文字) だけは gist に入力できなかったため省略しています。ご了承ください。

Unicode の入力・表示テストに使える文字(列) (U+0000 null を除く)

2021-05-25

ブルアカ二次創作 STG を作った～開発裏話

はじめに

#ブルアカシューティングゲームが完成しました…！　https://t.co/pJT1RXB3ZB
モモイ/ミドリ/アリス/ユズを操作してミレニアムのつよい人たち+αと戦います。 PC のブラウザから気軽に遊べますのでぜひ #ゲーム開発部からのお願い pic.twitter.com/rc8V9ijear
— Andante (@andanteyk) 2021年5月20日

「ブルーアーカイブ」のキャラを操作して戦う、縦スクロール弾幕 STG を作りました。
PC ブラウザ上で遊べるので、未プレイの方はぜひプレイしてみてください。

https://andanteyk.github.io/MillenniumAssault/

ここでは、開発の裏話等々を残していきたいと思います。

思いついたように書いているのでだいぶ読みにくいと思いますが、箇条書きぐらいの雰囲気で読んでください。
需要は考えません。書きたいので書きます…

発端

🎉【創作物大募集】🎉
先生！ミレニアムのミドリさんとモモイさんから、要請が届いてます！#ゲーム開発部からのお願い
のハッシュタグを付けて作品を投稿すると、豪華な賞品がもらえるかもしれません……！

▼開催期間
4月16日(金)〜5月20日(木)23:59

詳細情報はこちらです！#ブルアカ pic.twitter.com/HkZCN12fax
— ブルーアーカイブ公式 (@Blue_ArchiveJP) 2021年4月16日

「ゲーム開発部」に関する作品を作ってタグをつけて投げると、プレゼントがもらえるかも… という公式さんのプレゼント企画です。

これを見て、「ちょっとやってみるかー」となりプロジェクトを作成したのが 04/18 です。

やろうと思えた要因としては、

ゲーム開発部のイベント・キャラ等々が好きだった
プログラミングならできるので、本当の意味で「ゲーム開発部」ができる
- (イラストとかに比べれば、の話なので、マサカリを投げないでくださいね…！)
ゲーム開発部の設定が「レトロゲーム好き」であり、こちらもレトロチックにすれば
- テーマが一致して強い
- 私だけでもなんとかグラフィック(・サウンド)を賄うことができそう
締め切り (04/16 - 05/20) まで 1 か月はある
- イラスト中心の企画で 2 週間とかだったら厳しかったでしょうね…
- 逆に、締め切りがなかったらそれはそれでリリースできなかったと思います。無限に延期できてしまうので…
GW にまとまった休みがとれて、かつ大きな予定がなかった

という感じです。

始めるにあたり、ざっくり要件・目標を定めました。

基本的にすべて自分で作ること
- 具体的にはプログラム・グラフィック・サウンド（・プランニング）
  - ライセンス周りが面倒で、かつ二次創作になるので、ややこしくなることは避けたかった
  - (フォントとライブラリは流石に無理なので、正式な手段でお借りしました)
新技術のテスト・学習をすること
- せっかくなので、今まで使ったことのない・使い切れていないライブラリや Unity の新機能を試してみる
- 具体的には、
  - UniTask v2
  - Input System
  - 2D Pixel Perfect
  - Tilemap
  - Google Sheets API
  - Addressable Asset System
  - WebGL 出力
  - など

ゲームのジャンルについては、とりあえず弾幕系シューティングにするか、というのは決まっていました。
ゲームシステム自体の元ネタはお察しかと思いますが、巫女さんと魔法使いのシューティングです。
理由としては、

工数がかかりにくそう (RPG とかに比べれば、ですが)
はるか昔 (DxLib でしたね) に作ったことがあり、雰囲気は分かっていること
ブルアカのテーマ (銃器を扱う) にマッチしていること

という感じです。

プラットフォームについては、今回は WebGL (ブラウザ上でプレイする形式) としました。
WebGL は試したことがなかったので、パフォーマンス上の問題や技術的制約に引っかからないか (一部の標準機能が封印されていたりします) 、といった懸念はありました。
ただ、言ってしまえば一発ネタなので、インストールの手間がかからず、すぐに遊べてすぐに終われるブラウザ上で完結する強さのほうが大きいのでは、と思い採用しました。
(実際この目論見はうまくいったような気がします。)

今回はソロ開発で「プログラム・グラフィック・サウンド・企画　私」状態だったので、「仕様はとりあえず作りながら考えるか」と見切り発車しました。

以降は各セクションの自分（？）からの所感や反省などです。

プランニング

ゲーム仕様レベルの設計思想や広報などを書きます。

自機

当初予定は「メイン双子、＋αでアリス」だったのですが、いつの間にかユズさんが増えていました。おかげで Player Select 画面を作り直すことになりましたが、よしとします。

基本的には本編に沿ったり、スキルからの連想で作っています。

モモイ: 広範囲型
ミドリ: 狙撃型 (EX スキルから)
アリス: 貫通型
ユズ: 爆発型

元ネタのほうで見たことのある挙動だな、と思った方もいらっしゃるかと思いますが、概ねその通りの想定で作っています。
(流石に銃弾がホーミングするのはおかしいのでオートエイムにするか、とかはありますが)

アリスさんがレーザーなのは… 本当はレールガンではあるのですが、本編のエフェクトもレーザーっぽい感じなのでよかったのではないでしょうか。

バランス調整はかなり難しかったですが、まぁ細かいところは置いておいて DPS を概ね同じにしておこう、程度の方針でした。

アリスさんとユズさんは対ビナー特効を持っています（貫通・爆発して複数のボディにヒットするため）。アリスさんについては火力が高すぎがちになっていましたが、下げすぎると今度は道中や通常ボスで戦いにくくなってしまうので、まぁいいか、ということにしました。

ユズさんが塩梅が難しく、かなりピーキーな性能になってしまったのがちょっと心残りです。
爆風をもうちょっと広く or 強くしてもよかったかな、とか…
（でもあまり広くしすぎると多段ヒットしたりして強くなりすぎるので…）

クリア報告ツイートを見ると（本当にありがとうございます）、ミドリさんの使用率がかなり高いようでした。やはりオートエイムはつよい…！

操作系統については、「なるべくシンプルにしよう」というのは当初からありました。
最初期はもはやショットボタンすらなく、常にオートショット状態で「移動」と「スキル」だけあるような状態でした。
というのも、一応スマートフォンでも動作させられる余地を残しておきたかったからです。
敵の攻撃も、東方のように高密度な弾幕を撃ってきて低速+細やかな移動で避ける、というスタイルよりは、高速弾をちょっとした反射神経で避ける、というバランスにしよう、と（当初は）思っていました。
スマートフォンでは細やかな操作は絶望的であるのと、そもそも画面上に弾を出しまくると動作環境的に重くなる懸念があったためです。

まぁやっぱり押せたほうがいいよね、ということで、最終的には移動・ショット・スキルの 3 系統になりました。
低速移動はショットと兼ねています。最初は常に等速 (現在のショット中と同じ) だったのですが、もともと自機の移動が遅めで爽快感がなかった・緊急回避が難しかったので、ノーショット時に加速 (x1.5) するようにしました。

スキルストックに上限がなくて画面をはみ出していくのは…　仕様です。
最初に気づいたとき、見た目がバグっぽくて面白い (ファミコンのころにありがちな感じな) のと、ユーザー有利なバグなのでそのまま仕様にしてしまおう、となった経緯があります。

ステージ

最初は「まぁ 3 面ぐらい遊べれば十分だろう」と思っていたのですが、カリンさんとネルさんのスプライトを描いた際に「同じメイドなら多少増やしても工数が少ないのでは？」などと思ってしまい（そんなことはなく普通に大変でした）、アスナさんとアカネさんを追加しました。

これで 5 面 (ユウカさんと C&C 4人) になったので、せっかくだしあと 1 面… となり、ビナーを追加することにしました。
採用理由としては、

見た目が派手でシューティングゲームっぽい
- 実際、告知動画でも「映え」があったと思います。たぶん…
ブルアカ本編で最初に戦ったボスなので思い入れがある
(サウンドの都合上、戦闘 BGM がビナー戦のものだった)

蛇っぽい動きを作るのはなかなか難しかったですが、苦労に見合っただけの働きはしてくれたと思います。
あの動きは、 DOTween の Sequence を少しずつインターバルを入れて再生させることで実現しています。
例えば、頭は即時、次の体パーツは 0.1s 遅れ、次のは 0.2s ... といった具合です。

ビナーの動きといえば、開発初期は若干動きが怪しくて、ボディが一か所に固まってしまうことが多かったのです。
そうすると自機の弾が多段ヒットするようになり（ヒットで消滅する前に複数のボディに当たる）、耐久弾幕 (浄化の嵐) で無敵になる前の数秒間の隙にスキルを叩きこむことによって HP を削り切り、耐久弾幕をスキップできる…　というバグがあって大変笑いました。マリス砲とか妹紅さんの使い魔とかそういったものが脳裏をよぎりました…

話を戻して…
道中の設計としては、以下に注意していました。

1 面はとにかく簡単にすること
- 操作に慣れさせるまで、しばらく弾は撃たない (撃ったとしても自機狙いではない)
- 開幕で離脱されると悲しいので…　退屈なぐらいでも構わない、としました。
工数を減らす（同じ動作・射撃設定の敵を使いまわす）
- スポーン位置を変えるだけで、ある程度別のムーブっぽく見えるようにはしました
- プレイヤーとしてもパターンが見えるようになるので、一応それらしくなります

ただ、コピペが続いてあまりにも単調になってしまったのと、雑魚の行動パターン作成にモチベーションがわかなかったため、開発後期に中ボスを導入しました。
これでバリエーションを増やしつつ、出来のよくない雑魚戦を削ることができました。
（実は中ボス戦の裏にも旧レイアウトの敵が配置されたままになっており、実際早く中ボスを撃破するとその敵が出てきます。中ボス出現中は雑魚の湧きをキャンセルするようにしています。）

近い理由で、6 面は道中がありません。楽をしたかったのと、即ビナーが出てくるインパクトがあって良いのでは、となったのがあります。

個人的にうまくいったかなと思っているのが 3 面の、中ボスカリン撃破後に画面外から狙撃されるところです。
シチュエーション的にそれっぽく、かつ "caution!" のインパクトがある（しかし脅威ではない）ので、楽しくなったかと思っています。

難易度想定としては、東方でいう Easy と Normal の中間ぐらいです。なぜなら私の腕前がそれぐらいだからです… (Normal で 1-2 コンティニューでクリアできるぐらい)
開発者補正で回避力が上がっている説はあるので、普通のプレイヤーにとっては Normal ぐらいになったかもしれません。
完全に別の話ですが、プレイ後の感想で「東方をやりたくなった」とあって若干嬉しくなりました。ちょうど新作 (虹龍洞) が出ているのでぜひ…！

ボス

一発ネタなので、おそらく繰り返してプレイしてくれる方は少ないでしょう。
したがって「覚えれば余裕だけど初見殺し」の戦略はなるべく回避しなければなりません。

そこで、 "caution!" 警告エフェクトを事前に焚いておくことで、驚かせつつキルはとらない程度のバランスになるようには気を付けていました。
5-6 面は警告があっても避けられない場合があるかもですが、そこは後半面なので許してもらって…

弾幕の設計にあたっては、攻撃に全く寄与しない（後ろとか左右遠くにすっ飛んでいく）弾を増やして、インパクトを確保しつつ実際そこまで難しくない、みたいなバランスにできれば…　と思ってはいたのですが、実際はなかなか難しかったです。
作っているとどうしても「こうすればプレイヤーに当てられる」という方向に意識が持っていかれがちですね… 当てられて嬉しい人間は作者しかいないのですが…（なんならプレイをやめられたら作者にも損なのに）

東方を観察していると、弾にかなり細かく加速度が設定されていて (発射瞬間の速度は遅く（どの方向に来るか分かる）、急に加速して (プレイヤーが認識する速度になる) 、プレイヤー付近に来たころに減速する（認識していた速度より避けやすくなる）、といった) 、流石だなと思ったりしました。
設計上加速度をつけるのが若干面倒な感じになってしまっていたので、もし次があれば楽に加速できるようにしておきたいです。

また、今回特有の制約として「同時に大量に弾を出すと処理落ちする」問題がありました。大量にといっても 32 個とかのレベルでも若干怪しいです。
そのため、後期に作られたキャラ (アカネ/アスナ/ビナーあたり) は、螺旋状に出したり時間差で撃ったりというのを気を付けていました。

キャラごとに弾幕の方向性みたいなものを決めていました。

ユウカ: バリア、数学っぽい(四角や円など)
アカネ: 反射、爆発 (背後ではじける巨大弾のやつです)
カリン: スナイパー(高速巨大弾)、曳光弾(弾から弾を出す)
アスナ: 高速移動(スキルからの連想)、軌道が曲がる弾(つかみどころない感)
ネル: 乱射、力技感

「げきこう」「コールサインダブルオー」あたりは調整の余地があったな、という反省があります…
激昂はもう少しプレモーションを増やしたり見た目上の綺麗さが出せれば…　とダブルオーは轢かれる (回避した先に弾源が来る) 事故が多発していたので、うまいことできなかったな…と

ビナーの耐久弾幕 (浄化の嵐) は、「それっぽさ」を出すのにとてもいい感じになったと思います。ブルアカ本編でもかなり火力が高い攻撃で苦戦しましたし…
一応ノーダメージで抜けられることも確認してはいますが、まぁもう少しマイルドにしてもよかったのでは、と反省はあります… 最初の大縄跳びは普通に私も苦手です。

ところで、 1 面にユウカさんを置いたのは「ゲーム開発部が作ったなら多分そうするだろうな」という感じがあったからです。かにビーム先生のイラストのアレとかの雰囲気で…
とても好きなキャラクターなので、雑に置いたわけではないです。念のため。 Extra とか作るならユウカさんにしていたかもしれません。

アイテム

いわゆる「得点アイテム」や「パワーアイテム」は最初から実装しない予定でした。というのも、元ネタよりも画面が狭く、半透明表現なども使えないので画面がごちゃごちゃしそうなため、またパワーアップの実装とバランス調整に手間がかかりそうだったためです。

ただ、いざ抜いてみると「敵や弾がまだあるのを避けながら、上に行って全回収する」とか、「ボスが落とした点符を速やかに回収してまた下に戻る」みたいな操作ができなくなってしまって少し退屈になってしまったので、よく考えられているな…　と思いました。

エクステンドとスキルアップ(ボム)は、かなり大盤振る舞い目に設定しました。
おそらく繰り返しプレイはされずに負けたらそれきりでしょうから、多少残機が減ってもすぐに補充できるようにと思って増やしていました。せっかくなので最後まで見てほしいので…
プレイ感想を見るに、なんならもうちょっと増やしてもよかったかもしれませんね…

デザインとしては、セリナさんのスキルの救急箱がモチーフです。ただ赤十字レギュレーションに引っかかる可能性が…？との杞憂のため、ハートアイコンにしておきました。調べた感じでは色反転は大丈夫そうでしたが。

あと、アイテムではないですがスコアについて…
ステージクリアのスコアがかなり大きめ (ラスボスまで行っても撃破点がだいたい 100 万行くかどうかのところ、ステージ x 100 万) になっているのは、結果ツイートからどれぐらいまで進めたかを推測しやすくするためです。

プロモーション

せっかくなので動画を撮影してツイートにくっつけることにしました。静止画では弾幕が伝わらないので…

動画撮影・編集環境がそもそもなかったので、構築から始めました。 2 日ぐらいかかって締め切り当日に差し掛かったので割と危なかったです…

撮影は OBS , 編集は AviUtl です。編集といってもクロスフェードさせただけですが…
動画はいつもは GameBar で撮っているのですが、枠の切り取りができなかったので艦これブラウザのデバッグで入れたまま放置されていた OBS を使いました。
環境構築を含めて結構手間だったので、世の動画勢各位はすごいなと思うなどしました…

動画制作時は、出し惜しみしないことを念頭に置いていました。
今回はネタバレよりもプレイされないことのほうがデメリットなので…
その点ではビナーはいい感じのサムネイルになったのではと思います。

プログラミング

開発は Unity 2021.1.3f1 で行いました。
ソースコードはこちらで公開しています。
コミットログを眺めてもらうと開発の雰囲気が分かるかもしれません。

以下、使ってみたライブラリや機能の所感を書いていきます。

UniTask

非同期処理を簡潔に書けるようにするライブラリです。
このプログラムの中核をなしています。ほぼすべてのスクリプトで using しています。

というのも、今回の制作における重要な目的のひとつが「UniTask v2 に慣れる」だったためです。
基本的に Unity 標準のイベントは Start だけ使って、他 (OnTriggerEnter2D, Button.onClick など) は UniTask に用意された要素で実装しています。

UniTaskAsyncEnumerable がかなり使い勝手が良かったです。
雑に説明すると、普通の for 文が空間方向の繰り返し (円形のような) であるのに対して、これを使うと時間方向にも簡易に繰り返す (例としては螺旋など) ことができます。
詳しくはソースコードを参照してもらうのが早いのですが、例えば、螺旋状に弾を撃つ攻撃 (アカネの初回攻撃) は、以下のように実装できます（エフェクト等は省略しています）：

f:id:andantesoft:20210524221832g:plain

async UniTask Phase(float direction, CancellationToken token)  
{  
    float baseRadian = Seiran.Shared.NextRadian();      // 撃ち始め角度の乱数(-pi ~ +pi)  
    int ways = 24;  
    
    // ways 回 だけ 0.05 秒ごとに ForEachAsync の中身を実行する  
    await UniTaskAsyncEnumerable.Timer(TimeSpan.Zero, TimeSpan.FromSeconds(0.05), PlayerLoopTiming.FixedUpdate)  
        .Select((_, i) => i)  
        .Take(ways)  
        .ForEachAsync(i =>  
        {  
            // 弾の生成  
            var bullet = BulletBase.Instantiate(m_NormalShotPrefab, transform.position, BallisticMath.FromPolar(32, baseRadian + i * Mathf.PI * 2 / ways * direction));  
        }, token);  
}

とても簡潔に書けます。

並列実行も簡単で、「動きながら撃つ」も await (Move(token), Shot(token)); と書くだけで実現できます。
これのおかげで移動コードと射撃コードを別々に実装することが可能です。

また、 "HP が 0 になったら、攻撃を中止して次のフェーズに移る" といった処理は、キャンセル機構を使用して実装しています。

// destroy されたとき(エディタで再生中止された or 撃破されたとき)にキャンセルされる  
var destroyToken = this.GetCancellationTokenOnDestroy();  
// HP が 0 になったときにキャンセルする (別途被ダメージ処理で hpTokenSource.Cancel() する)  
var hpTokenSource = new CancellationTokenSource();      

// どちらかがキャンセルされたときにキャンセルされる CTS を生成  
using (var combinedTokenSource = CancellationTokenSource.CreateLinkedTokenSource(destroyToken, hpTokenSource.Token))  
{  
    var combinedToken = combinedTokenSource.Token;  

    // ここの action() の実装に各フェーズの動作を記述する  
    await action(combinedToken).SuppressCancellationThrow();  
}

こうすると、(action() を適切に実装していれば) HP が 0 になった瞬間に上のブロックを抜けて、次のフェーズの処理に進むことができます。

初心者向け(?)逆引き

一番最初にあれば助かったな、と思うシリーズです。
文献としては https://qiita.com/toRisouP/items/8f66fd952eaffeaf3107 がとても詳しいですが、前提知識が割と必要な気がしたので、雑に使いたい人は下を見てみるとよい…かもです。

※ 間違っていたらマサカリを投げてください

(m 秒後から) n 秒ごとに繰り返したい

// timeSpanDelay 経過後にループが始まる。 (TimeSpan.Zero を渡せば今すぐ)  
// ループ(ラムダ式の処理)は timeSpanInterval ごとに呼ばれる  
await UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
.ForEachAsync(_ => { /* 同期的な処理 */ }, token);  

// timeSpanDelay == timeSpanInterval なら、  
// UniTaskAsyncEnumerable.Interval だと簡潔  

// これも等価  
await foreach(var _ in UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
    .WithCancellation(token)) {  
    /* 同期的な処理 */  
}

フレーム単位なら TimerFrame が、毎フレームなら EveryUpdate が使えます。
また、 FixedUpdate 相当のタイミングで実行したい場合は PlayerLoopTiming.FixedUpdate を引数に渡すことで実現できます。

やりたい処理が非同期なら、以下が使えます。
(2 秒動く → 1 秒待つ → ... など)

await UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
.ForEachAwaitWithCancellationAsync(async (_, token) => {  
    await Move(token);    // など, 非同期的な処理  
}, token);  

// これも等価  
await foreach(var _ in UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
    .WithCancellation(token)) {  
    await Move(token);    // など, 非同期的な処理  
}

一定回数の繰り返し

// x 回繰り返したら終わる  
await UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
.Take(x)            // ←これで回数制限できる  
.ForEachAsync(_ => { /* 同期的な処理 */ }, token);

LINQ が使えます。

何回目のループか知りたい (for 文の i が欲しい)

await UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
.Select((_, i) => i)        // ← これでインデックスに変換できる  
.ForEachAsync(i => { /* 同期的な処理; i がインデックスとして使える */ }, token);

別のシーケンスが使いたいときは、

// このシーケンスを処理の引数に使いたい  
static IEnumerable<float> Linear(float start, float end, int way)  
{  
    for (int i = 0; i < way; i++)  
        yield return Mathf.Lerp(start, end, i / (way - 1f));  
}  

await UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
.Zip(Linear(128, -128, density + 1).ToUniTaskAsyncEnumerable(), (a, b) => b)    // これで突っ込む  
.ForEachAsync(y => { /* 処理 (Linear で求めた y が使える)*/ }, token);

投げっぱなしにする

var bullet = BulletBase.Instantiate(...);

// 投げっぱなしの非同期処理は UniTaskVoid を戻り値にすると効率がいい (らしい)
UniTaskVoid MoveBullet(BulletBase bullet, CancellationToken token) { ... }

// .Forget() すると警告を消せる
MoveBullet(bullet, bullet.GetCancellationTokenOnDestroy()).Forget();

キャラ側で弾の特殊挙動を記述する際など、出したらそれっきりで以降放置するような場合に便利です。
(弾側に記述しろ、はまぁその通りではあるのですが…)

キャンセル周りについて

実装において、慣れが必要なのはキャンセルの部分です。
このエラーメッセージを無限に見ました。

f:id:andantesoft:20210524221835p:plain

コルーチンと違って GameObject が Destroy されても UniTask のコードは動き続けます。
例えば安直に await UniTask.Delay(5000); としてしまうと、待機中に Destroy(gameObject) された場合、後続のコードで破壊済みの this や transform を参照して落ちます。
したがって、必ずキャンセル処理を実装する必要があります。

具体的にどうするのかというと、

呼び出しの大本で this.GetCancellationTokenOnDestroy() を使って Destroy 時にキャンセルされるトークンを生成する
- もし別のキャンセル事由がある場合は (HP が 0 になったとか)、上に書いたように CancellationTokenSource.CreateLinkedTokenSource で合成できる
そのメソッドから呼び出す非同期メソッド すべて に CancellationToken を必ず渡す
- 子孫にもそのまま渡していく
- UniTaskAsyncEnumerable.Timer などは .WithCancellation(token) (await foreach の場合) や .ForEachAsync(..., token) (メソッド呼び出し式の場合) で渡す
UniTask(Void) を返す非同期メソッドを自分で実装するときは、必ず CancellationToken を引数に含める

という感じです。
すごい量の cancellationToken: token を書くことになりますが、怠ると予期しないタイミングでエラーになるので横着せずに書いていきました。

また、トークンを渡し忘れると上に書いたエラーだけでなく「撃破したのに弾を撃ち続ける」なども起こります。
必ずキャンセルを意識するようにしなければなりません。

DOTween の待機について

UniTask の機能で Tween を待機することができますが、その際の注意点です。

まず、 DOSpeed() (弾速を変更する; ≒加速度設定) が DOTween.To を使って定義されているとして、

// Speed は bullet のプロパティです
public DG.Tweening.Core.TweenerCore<Vector3, Vector3, DG.Tweening.Plugins.Options.VectorOptions> DOSpeed(Vector3 endValue, float duration)
    => DOTween.To(() => Speed, value => Speed = value, endValue, duration)
        .SetEase(Ease.Linear)
        .SetLink(gameObject);

段階的に加速させるコードを以下のように書いたとしましょう。
最初にちょっとだけ加速して予兆を見せてから、一気に加速するイメージです。

await bullet.DOSpeed(BallisticMath.FromPolar(32, radian), 1);
await bullet.DOSpeed(BallisticMath.FromPolar(192, radian), 1);

するとこれを引きます。

f:id:andantesoft:20210524221835p:plain

1 行目の実行中にスキルなどで bullet が Destroy されると、 2 行目で bullet が参照できなくなるので落ちます。
(厳密には、 DOTween.To の getter を参照されたタイミング辺りで落ちます。)
まぁ CancellationToken を渡していないせいだろうと、これに変えます。

await bullet.DOSpeed(BallisticMath.FromPolar(32, radian), 1).WithCancellation(token);
await bullet.DOSpeed(BallisticMath.FromPolar(192, radian), 1).WithCancellation(token);

するとこれを引きます。

f:id:andantesoft:20210524221835p:plain

何がいけなかったのかというと、 .WithCancellation(token) は .ToUniTask(TweenCancelBehaviour.Kill, token) と同じ意味になるのですが、この TweenCancelBehaviour.Kill の場合、キャンセルされた際でも OperationCanceledException が飛ばないようです。
その結果、 1 行目がキャンセルされてもそのまま 2 行目に実行が継続されて落ちてしまっています。

したがって、飛ぶように KillAndCancelAwait を指定してあげればよい、というわけです。

await bullet.DOSpeed(BallisticMath.FromPolar(32, radian), 1).ToUniTask(TweenCancelBehaviour.KillAndCancelAwait, token);
await bullet.DOSpeed(BallisticMath.FromPolar(192, radian), 1).ToUniTask(TweenCancelBehaviour.KillAndCancelAwait, token);

こうすれば、 1 行目の実行中にキャンセルが走った場合、きちんとキャンセル例外が飛んで実行が中断され、 2 行目に進まなくなります。

まとめ

キャンセル周りの手間をかけたとしても、全体的にすごく楽に書けるので良かったです。なんなら公式で組み込みにしてくれてもいいのでは、と思うレベルの必要度でした。
あと Unity の非同期はほぼシングルスレッドなので、WinForms のように UI スレッドに切り替えないでコンポーネントに触ったら落ちる、みたいな地雷が少ないのも初心者にはやさしいです。
まぁ習熟は必要で、実際私が初期に書いたコードは若干怪しい感じになっており、少し慣れた今リファクタリング(バグ修正？)してもいいかもしれませんね…

Input System

Unity の新しい入力管理システムです。
導入の利点などは https://forpro.unity3d.jp/unity_pro_tips/2021/05/20/1957/ に詳しいです。
(ちょうどこの記事を書いているときに見つけました…)

ただ、何度も地雷を踏んだので、あまり印象が良くないです… プロダクトに使うにはまだ不安定なのでは、という印象がありました。（私が不慣れなだけの可能性はあるので、 Input System マスターの方がいらっしゃったらすみません）

旧 Input の使い方がわかっている方は、移行用のドキュメントがあるので見るのが早いです。

以降、私が爆発したポイントを列挙していきます。

`Input.GetKeyDown|Up()` 互換が (Stable 版には) ない

2021/05/21 現在の最新 Stable 版 (1.0.2) には、上記メソッド互換の機能が存在しません。…存在しません！！

近いものとしては、 input.Player.Fire.started|performed イベントと設定を駆使する方法で取れなくはなさそうです。しかし、設定が難しい（挙動がどう変わるのか分かりにくい）うえ、 event なので扱いが難しいです。
他には、 Keyboard.current.aKey.wasPressed|ReleasedThisFrame があり、こちらはプロパティなので自然に使えます。しかし、これはキーを直接指定するものであり、ゲームパッド等々との併用には使えません。せっかく手間をかけて入力を仮想化した意味が薄れてしまいます。

Preview バージョン (1.1.0-preview.3) には input.Player.Fire.WasPressed|ReleasedThisFrame() が実装されており、これが GetKeyDown|Up() 互換で使えます。したがって、 Preview 版を入れる必要があります。
(Package Manager からは指定できないようなので、 manifest.json を直接書き換えて導入します。)

あまりにも基本的なメソッドが欠けているので、旧 Input に戻したほうがいいのでは…？　という強い誘惑にかられました…

`Keyboard.current` は null になりうる

先の記事にはちゃんと書いてありましたが、私は知らなかったので…

キーボードが繋がっていたとしても、 Scene のロード中などに一時的に null になる場合があります。そのため、必ず null チェックを入れる必要があります。
デバッグコマンドだから Keyboard.current で直指定でもいいや、としていると引っかかりがちなので注意です。

エディタ上で再生開始時に一切の入力を受け付けなくなる

再生開始時に、ランダムにキーボード・クリックその他すべての操作が無視されるようになります。
Input Debug ビューからのキーテストは反応しますが、 Game ビューには反映されません。

これはいまだに原因がわかっていません…

ワークアラウンドは「Hierarchy ビューで InputSystemUIInputModule (EventSystem ?) がアタッチされているオブジェクトを選択する」です。なぜかは分かりませんが、以降操作できるようになります。
もし解決策をご存じの方がいらっしゃればご一報ください…

情報が薄い

一番致命的なやつです…
採用例が少ないので、公式のマニュアル(英語)を見て、分からなければフォーラム(英語)を巡回する羽目になります。

「導入してみた」記事は日本語でもよくありますが、実用してみた場合はあまりなかったりするので…

良かった点

dis るだけ dis ってもアレなので、良かった点を書きます。

まず、キーボード/ジョイパッド等々への対応はとても楽です。デフォルト設定も存在しており、コピペすれば概ねいい感じに対応できます。

また、スマートフォン対応用の On-Screen Button/Stick が標準で実装されており、スクリプトを貼るだけで「タップすると Z キー相当のイベントが走るボタン」「ドラッグで Left Stick 扱いされるスティック」が実装できます。
雑にスマートフォン対応するだけならあっという間です。
加えて拡張性もあります。今回はショットボタンをトグル形式 (押しっぱなし扱いになるボタン) にしましたが、以下の短いスクリプトを書いて貼り付けるだけです。

[RequireComponent(typeof(Toggle))]  
public class OnScreenToggle : OnScreenControl  
{  
    private Toggle m_Toggle;  

    [InputControl(layout = "Button")]  
    [SerializeField]  
    private string m_ControlPath;  
    protected override string controlPathInternal { get => m_ControlPath; set => m_ControlPath = value; }  

    private void Start()  
    {  
        m_Toggle = GetComponent<Toggle>();  

        m_Toggle.onValueChanged.AddListener(value =>  
        {  
            SendValueToControl(value ? 1f : 0f);  
        });  

        SendValueToControl(m_Toggle.isOn ? 1f : 0f);  
    }  
}

2D Pixel Perfect

今回のようなレトロチックなゲームを実装するにあたり必須になるコンポーネントです。
カメラにアタッチするだけで Sprite の (見た目上の) 位置を整数にそろえてドットがくっきり表示されるようになり、かつ Pixel Perfect に拡大してくれるようになります。

UI と併用するときに少しだけ注意が必要で、 Custom Canvas Scaler を Canvas にアタッチしたうえで、 Canvas を Screen Space - Camera にする必要があります。 (やらないと UI 側と Sprite 側で描画がずれます。)

Custom Canvas Scaler は同梱されていませんが、 GitHub にあります。

Tilemap

その名の通りタイルマップです。今回は背景に使用しました。
かなり直感的なエディタがついているので、ほとんど迷わずに制作できました。

強いて問題を挙げると、そのままだと半グリッドだけずれている (16x16 のタイルなら、オフセットが (8, 8) になっている) ことです。これは Tilemap コンポーネントの Tile Anchor を (0.5, 0.5) から (0, 0) にすれば直ります。が、今度はエディタで塗るときにカーソルが半グリッドずれるので、編集時は (0.5, 0.5) にして終わったら (0, 0) にするというちょっと面倒な運用をしていました。

あとはアセットが大量に生成される (スプライト単位ではなくタイル単位なので、 1 枚の画像に 16 個タイルを置いていた場合でも 16 個アセットができる) のがちょっと…　となるぐらいでしょうか。これは単に気持ちの問題ですが。

Google Sheets API

Google Spreadsheet と連携するものです。ステージの雑魚敵を設定する際、シートのデータ → ScriptableObject の設定値に変換するために使いました。（もちろんエディタ専用です。）
ScriptableObject において配列の直編集は相当な苦行なので、ステージエディタなどをする場合はほぼ必須だと思います。
(ローカルの CSV をいじれる環境があれば CSVReader 実装でいいかもしれませんが、 Office がないので…)

実装は StageDataEditor.cs にあります。導入もコメントに書いたので良ければ参考にしてください。
client_secret.json の生成 (アクセス権の獲得) が若干手間かもしれませんが、それだけの価値はあります。

シートの中身はこんな感じで、

f:id:andantesoft:20210524221840p:plain

Unity 上でこのボタンを押すと Enemies がシートに合わせて設定されます。

f:id:andantesoft:20210524221843p:plain

今回の機能は「位置を決めて Instantiate するだけ」でしたが、弾の動きとか HP とかも記述できるようにしておけばバリエーションを増やしやすかったかも、という反省があります。Prefab Variant を生産し続けてゴリ押しして終わらせてしまいました…

なお、導入にあたって Visual Studio の nuget パッケージ管理から直接突っ込むとうまく動作しませんでした。
別のプロジェクト (WinForms とか) でダウンロードしてから、バイナリ *.dll だけを Editor フォルダ下に突っ込む手法で動かしていました。
この時、 netstandard2.0 のものだけ入れるようにしましょう。同名の *.dll が複数あると Unity がエラーを吐きます。

また、毎回の注意点として、 client_secrets.json といった機密情報は git に含めないように十分注意が必要です。

Addressable Asset System

悪名高い Resources/AssetBundle の後継です。
今回は AssetBundle のように本体と分割して扱うことは考えていなかったので、いわば "Better Resources" のような運用をしていました。本来の使い方ではないかもですが…

運用としては、Inspector でチェックボックスを入れればパスが得られるので、それを

var prefab = await Addressables.LoadAssetAsync<GameObject>("some/prefab/path.prefab");

とするだけで読み込めます。 Resources と使用感はほとんど変わりません。 UniTask があるので await もできます。

注意すべき点としては、 WebGL ビルドする前に必ず Addressables もビルドする必要があることが挙げられます。何度となく忘れて古いアセットがロードされました…
一時はビルド前に自動で Addressables ビルドが走るようにエディタスクリプトに書いておいたのですが、いつからかビルドに失敗するようになってしまったので結局手動でビルドしていました。うまく自動化できるとよかったのですが…

WebGL

謎の `OnJointBreak2D` エラー

一番最初に直面したのがこれです。
Development Build は正常に成功するのですが、実行して InGame に入ると以下のエラーがコンソールに出て、動作が不安定になります。

Script error: OnJointBreak2D  
This message parameter has to be of type: [UNREGISTERED]  
This message will be ignored.

これは UniRx を入れており、かつ Project Settings の Strip Engine Code が有効になっていると発生します。 UniRx 側で Joint2D を参照しているにもかかわらず、ビルド時に未使用判定を受けて Joint2D のコードが削除されてしまい、実行時エラーとなります。
(UniRx は悪くないです、念のため)

これを防ぐためには、ルートの Assets フォルダ直下に link.xml というファイルを作成し、こんな感じに記述します。

<linker>  
  <assembly fullname="UnityEngine">  
    <type fullname="UnityEngine.Joint2D" preserve="all" />  
    <type fullname="UnityEngine.Collider" preserve="all" />  
    <type fullname="UnityEngine.BoxCollider2D" preserve="all" />  
    <type fullname="UnityEngine.CircleCollider2D" preserve="all" />  
  </assembly>  
  <assembly fullname="Unity.ResourceManager, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null" preserve="all">  
    <type fullname="UnityEngine.ResourceManagement.ResourceProviders.LegacyResourcesProvider" preserve="all" />  
    <type fullname="UnityEngine.ResourceManagement.ResourceProviders.AssetBundleProvider" preserve="all" />  
    <type fullname="UnityEngine.ResourceManagement.ResourceProviders.BundledAssetProvider" preserve="all" />  
    <type fullname="UnityEngine.ResourceManagement.ResourceProviders.InstanceProvider" preserve="all" />  
    <type fullname="UnityEngine.ResourceManagement.AsyncOperations" preserve="all" />  
  </assembly>  
  <assembly fullname="Unity.Addressables, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null" preserve="all">  
    <type fullname="UnityEngine.AddressableAssets.Addressables" preserve="all" />  
  </assembly>  
</linker>

これでビルドすると、 fullname で指定したクラスがビルドに確実に含まれるようになり、うまくいきます。
(Joint2D 以外でも Collider や Addressables で似た事象が起きたので追加してあります。)

Strip Engine Code を無効にする手もあり、もちろんそちらのほうが手軽ですが、副作用があるので可能なら上の手段をとったほうがよさそうです。

エディタが重い・ビルドが重くて長い

こればかりはどうしようもないですが…

スクリプトを変更するたびに 10-15 s ぐらい待たされます。リリースビルドに至っては CPU をフルに消費した状態で 10-12 分程度かかります。なかなかしんどいです…

また、エディタ実行時の重さもだいぶひどいです。なんなら 1 fps になることもしばしばありました。
この辺りは私の実装が悪い説も大いにあるのですが、だとしてもしんどいです。
(これに関しては、何かのプロファイリングを知らぬ間に有効にしてしまっていた説もあります…)

GameObject のキャッシュ機構とかを作るべきだったな、とはずっと思っていました。思っていたら期間が終わりました…
逆に言えば、最適化のしがいはありそうです。

GitHub Pages で動かない

今回は公開場所を GitHub Pages にしたのですが、そこでは Project Settings の Compression Format を Disabled にする必要があります。 Brotli や Gzip だと起動時にエラーが出ます。
(また、記憶が怪しいですが確か Brotli にすると localhost での実行時でもエラーが出ます。)

というのも、 Brotli や Gzip にした場合はサーバ側で配信する際に設定が必要らしいです。自前サーバならよしなに設定すれば OK なのですが GitHub Pages では設定しようがないので Disabled にして回避します。

ツイートボタンを置きたい

Twitter の民としては、ゲーム内にツイートボタンを置きたくなります。
リザルトをつぶやけるようにしておけば、プレイヤーがクリアしてくれたか分かってとても嬉しくなります。（ありがとうございます。）

ただ、ここで問題があります。
エディタでは Application.OpenURL(string url) を呼ぶだけで対応する URL を開くことができます。しかし、ビルド (ブラウザ上) でこれを実行すると、見事ポップアップブロックに弾かれます。スマートフォンのブラウザの場合、ブロックされたことすら通知されず握りつぶされます。

原因はというと、現代のブラウザでは邪悪なポップアップを防ぐため、ユーザ起因のアクションでのみポップアップを開くことができるようになっているためです。
（これ自体はもちろん正当な処理です。）

そして、Unity 内のボタンをクリックした際、入力から実際に反応する (uGUI の onClick イベントが呼ばれる) までには若干のラグがあります (ほんの少し非同期になっているイメージです)。すると「ユーザ起因のアクション」でないとみなされ、ブロックされてしまいます。

これを回避するためには、 js レイヤーのイベントを利用してウィンドウを開かなければなりません。そのための仕組みが用意されています。
(公式マニュアル)

まず、 Assets/Plugins/ のどこかに以下のスクリプト (TweetPopup.jslib) を用意します。

// note: keyup イベント上での発行は IE, FireFox では popup block に引っかかる  
// が、タイミングを合わせる意味でもここに書いておく  
// (クリックでもイベントが消費されるので、意図通りに操作すれば出ない…はず)  
mergeInto(LibraryManager.library, {  
    RegisterPopupEvent: function(url) {  
        var resolvedUrl = Pointer_stringify(url);  
        var open = function(event) {  
            if (!(event instanceof MouseEvent) && event.key != "z")  
                return;  
            window.open(resolvedUrl);  
            document.getElementById('unity-canvas').removeEventListener('click', open);  
            document.removeEventListener('keyup', open);  
        };  
        document.getElementById('unity-canvas').addEventListener('click', open, false);  
        document.addEventListener('keyup', open, false);  
    }  
});

そして、 C# コードからはこのように呼び出します。

#if UNITY_WEBGL && !UNITY_EDITOR  
[DllImport("__Internal")]  
private static extern void RegisterPopupEvent(string url);  
#endif  

public void RegisterTweetEvent(string url)  
{  
#if UNITY_WEBGL && !UNITY_EDITOR  
    RegisterPopupEvent(Uri.EscapeUriString(url));  
#else       // エディタ上ならやる必要はない (むしろ呼び出すと実行時エラー)  
    Application.OpenURL(Uri.EscapeUriString(url));  
#endif  
}

すると、 RegisterTweetEvent() を実行したあと、次にクリック/キー入力されたとき、指定した URL が別窓で開くようになります。Twitter 用の URL パラメータはマニュアルや "Twitter Intent" で検索してください。

ただし、 //note: に書いた通りキー入力経由でポップアップさせた場合は、環境によってはブロックされてしまいます。ブロックされないイベントは非常に限定されており、どのブラウザでも通るのは click ぐらいで、 keydown/up などのキー関連イベントでは環境依存 (少なくとも FireFox では全面的にダメ) なようです。
これは仕様なので回避策はありません。諦めましょう。

また、スマートフォン環境ではまた別の手法 (twitter:// インテントを使ってアプリを開くなど) が必要らしいです。今回はそこまでしませんでしたが…

スマートフォン対応 (スマートフォン上で動作しているか検出する)

もともと想定環境ではありませんが、そのままだと「ボタンはタップで押せるので InGame までは進めるが、以降キー入力ができずただ殴られるだけになり終了」という大変ユーザー体験の悪い状態になるので、最低限操作できるようにだけはしておきたいです。

スマートフォン上での入力エミュレーションについては Input System の項で述べたとおりです。
あと必要なのは、操作用 UI を出し分けるためにスマートフォン上で動作しているかを検出することです。これは、twitter ポップアップの項と同じように IsMobile.jslib を作って、

mergeInto(LibraryManager.library, {  
    IsMobile: function() {  
        return Module.SystemInfo.mobile;  
    }  
});

として、同じ要領で IsMobile() を C# スクリプト側から呼べばよいです。
UnityLoader.SystemInfo.mobile としている文献がよくヒットしますが、そちらは現在の Unity バージョンでは廃止済みなので実行時エラーになります。今は代わりに Module が使えます。

もっと単純に Application.isMobilePlatform でとれるかも？という話も見かけますが、うまくいかなかったような気がします（記憶があいまいなので、一度試してみるとよさそうです…）

ところでリリース後の話ですが、やはりというかスマートフォン上で起動したユーザーが少なからずいたようなので、この工夫は無駄ではありませんでした。備えあれば憂いなしです。

グラフィック

グラフィック担当の私です。画像作成の際に気を付けていたことなどを書きます。

全体的な傾向

まず、テーマはレトロチックです。ファミコンぐらい想定です。
（ぐらいというのは、厳密に色数やスプライト数を制限したりすると可視性やデザインセンスの面で厳しいので…）
ということで、以下のレギュレーションを設けました：

半透明禁止
- 代わりにディザリングやカットアウトを使います
- 雑にフェードイン/アウトさせたり、境界をぼかしてごまかしたりできないので、一番つらかったかもしれません
加算合成禁止
- 弾幕を光らせることができない…！
回転禁止
- 2D Pixel Perfect がよしなにしてくれるとはいえ、見た目がよくならなさそうだったため
- 自機の弾は例外です（超高速で目立たないかと…）
1 スプライトの色数を 2-4 色程度に抑える
- ディザリングで頑張る

また、目には見えないところですが、なるべくスプライト自身のサイズを削る工夫をしていました。
もともと小さいのでパフォーマンスとかファイルサイズは誤差みたいなものですが、なんというか「レトロチック」なので…

例えば、下のようなボタンの背景は 8x16 のスプライトを 9slice で引き延ばして利用しています。

f:id:andantesoft:20210524221845p:plain

ツールは GIMP を使用しています。

アニメーション

全体的に、左右非対称に描いたうえで左右反転させて差分を作り、 2 コマのアニメーションにする手法を使っていました。
手間を減らしつつ最低限アニメさせることができてよいです。
止まっているよりはだいぶ工夫感が出る…はず…

消滅していくアニメーション ("Start!" など) を描くにあたり、 GIMP の消しゴムレイヤー (塗ったところが消える) が便利でした。いちいちレイヤー結合しては削除して… といったフローが不要になります。

キャラクターグラフィック

最初は「双子ならほぼ色変えだけで済むので、双子中心で作って余力があればアリスを」といった感じだったのですが、途中でスプライトを全入れ替えするわ（後述）、ブルアカ本家の実装祝いにユズさんまで実装するわで普通に工数が重かったです。でも楽しかったです。

メイド部もコスチュームが近いので楽…かと思いきや、よく見るとバリエーションに富んでいたので輪郭ぐらいしか流用できませんでした。ドット絵の練習にはなりましたね…

あと、余裕があればクリア画面に専用ポーズの画像を出したりしたかったのですが、まぁ時間的に無理でした…

// あと、こういったテーマ企画の際は、三面図みたいなものを 3D モデルのキャプチャでいいので公開してほしい気持ちになりました。自機の背中を書きたくても資料がなく、ストーリーの出撃イベントを巡っては小さなちびキャラの背中を観察していました…

背景スプライト

以下のような画像を使っています。制約があったほうがそれっぽいかな… と思い、1 ステージ当たり 16 枚分にしました。色数も 1 枠当たり 2 色に抑えています。

f:id:andantesoft:20210524221849p:plain

工場のフックのケーブルと箱の胴体は、実は同じスプライト (上の画像の 8 番目) です。ファミコンとかでこういうのしがちなイメージがあったので勝手にテンションが上がりました。言わないと誰も気づかないと思うので書きます。

f:id:andantesoft:20210524221850p:plain

基本的に「背景」なので、弾や敵の認識の邪魔にならず、かつキャラの色にかぶらないようにするのがかなり難しかったです。特にユウカさんは #000080 と #FFFFFF を併せ持っていて、かつ #00FFFF のバリアまで撃ってくるので、明るくても暗くても目立たなくなり大変でした…

UI

可能な範囲で本家っぽくなるようにしました。ボタンの形と三角形の飾りぐらいですが…

あとは「そもそもの画面数と遷移を減らそう」が方針としてありました。画面と遷移が増えるとその分バグと工数が増えるので、本当に最低限としました。ポーズはフォーカスアウトで、タイトルに戻るは F5 でできます…！

また、こういった短時間だけ遊ぶゲームは操作分からなくなりがち問題があるので、最初に「このボタンがこれ」と表示して終わり、ではなく、常に画面下とか右に「何キーが何なのか」を書いておくようにしていました。 Apex Legends とかその辺り親切ですよね…

UI といえば、フォントは大切ですね…
最初は PixelMplus のフォントを使っており、ターミナルらしくて味が出てはいたのですが、 ＭＳ　ゴシック 感がすごかったので、ゲームらしいフォントに途中で入れ替えました。
名残が "Warning!" エフェクトなどにみられるかと思います。

ただ、変えたら変えたでフォントの横幅がだいぶ異なり (半角と全角ぐらい違います)、今まで収まっていたテキストがはみ出したりして大変でした。フォント選定は最初期に慎重に行いましょう…

フォントといえば、 TextMeshPro の RASTER モードではシャドウや囲みができないようです (SDF 限定)。
もしやりたければ最初からテクスチャに焼きこむとかでしょうか…？

サウンド

一番難しかったのがこれだったかもしれません。

BGM

"Andante" とかいうユーザー名をしておきながら音楽的素養がほぼ 0 なので、耳コピするだけでも大変でした。
なるべく耳コピしやすく、かつ使いやすくて印象的な曲を…　ということで、タイトルとビナー戦の BGM をチョイスしました。
（ビナー戦は印象的な繰り返しのフレーズが多く、それっぽくしやすかったので大変助かりました…）

本当は通常戦闘曲や勝利ジングルも入れて BGM 切り替えをしたかったのですが、私の能力では限られた時間内にとても再現しきれなかったので諦めました…

ちなみに、サウンドは「ピストンコラージュ」で作っています。洞窟物語などで使われているツールです。
最初は Domino でやろうかと思ったのですが初期音源があまりにも貧弱でそれっぽくならず (それはそう)、どうしようかと思っていたら HDD の奥底からこのツールが見つかったのでこれで行きました。10 年ものとかです…

ファミコン感を出すために 25%/12.5% 矩形波の素材を作ったりもしました。それっぽく聴こえてかなりテンションが上がったのを覚えています。

SE

SE も自作です。同じくピストンコラージュ製です。
爆発音はだいたいドラムやスネア、UI の「ピ」などは単発の矩形波音などでできています。

反射音とかボスアラートがちょっとうるさかったかな、という反省があります…

また、プログラミングセクションの話かもですが、 SE の再生優先度を設定していれば… とリリースしてから思いました。
アリスさんのスキル SE や被弾音がかき消されてしまう場合があったので…

同じくプログラミング的な話ですが、 SE には一応同時発声数制御を入れてあります。最大 8 枠で、オーバーしたら古い順に停止・上書きされる仕組みです。また、同一フレームで同じ音が鳴った場合には再生しない処理も入っています。
WebGL 環境では結構発声数の制約が厳しく、あまりたくさん鳴らすとすごいノイズが出たかエラーを吐くかしていたので (記憶があいまいです)、そもそもそうならないように制限を入れていました。

The Cutting Room Floor

いわゆる「没画像集」のコーナーです。供養のためと、私は TCRF が大好きな人種なので…

自機 (16x16)

f:id:andantesoft:20210524221822p:plain

もともとは自機が 16x16 だったのですが、ディティールがつぶれてスプライトが描きづらい・誰か判断しにくい問題があったため、現状の 32x32 に描き直しました。ユズさん実装時点では 32x32 に移行済みだったので、ユズさんの分はありません。

それにあたり、流石に当たり判定がわかりにくくなったので、当たり判定表示 (赤丸) を追加したりしました。ユズさんだと色が近いので見にくかったりしますが…

壁際に立つとめり込むのは 16x16 時代の名残です。

敵弾

f:id:andantesoft:20210524221817p:plain

これらもありましたが、それぞれ以下の理由で没になりました。

(緑弾) イメージに合うキャラがいなかった
(二重円弾) 東方っぽくなりすぎる (個人的に一番好きなデザインなので入れたい気持ちはありました)
(粒弾) 見えない!!

あまりカラフルにしても（デザイン上の問題 (レトロゲーム感) とか工数とか工数とか…）という気持ちがあったので、今回は色数を抑えめにしました。

NES (ファミコン) の解像度 256x224 (うち、フィールドは 176x224) にした都合上画面がだいぶ狭いので、サイズがそれぞれ小さめになっています。

弾といえば、進行方向が分かる弾（楕円形とか、鱗弾とか）を入れたい気持ちはあったのですが、 Pixel Perfect である関係上うかつに回転させると見た目がよくなさそうだったので、すべて円形弾としました。

バリケード

f:id:andantesoft:20210524221828p:plain

ユウカさんのバリアの自機が通れないバージョンです (当たると弾が消えます)。完全に動作しますが使っていません…

当初はブルアカ本編のように、遮蔽に隠れつつ射撃するようなシチュエーションがあってもいいのでは、と作っていました。

背景スクロールに合わせるとすごく移動が遅くなるので、使いどころが難しく没になりました。

ユウカ（左右移動）

f:id:andantesoft:20210524221830p:plain

上二つは使用したスプライト、下二つが左右移動用のスプライト（未使用）です。
よく見ると髪や足が動いています。
使うのを忘れていました…　最も、時間的に全員分作るのは厳しかったかとは思います。

当たり判定バグ

リリースが完全に終わって、土曜日になってから気づいたのですが…

f:id:andantesoft:20210524221853p:plain

緑の円がモモイさんと敵弾の当たり判定です。 (他のキャラ・色でもサイズは同じです)
モモイさんは二重円になっていますが、内側の当たり判定表示の白い円とほぼ同じサイズのものが被弾判定、外側の大きな円が物理判定（前述のバリケードに侵入できないようにする判定）です。…そのはずでした。

実際のところ、物理判定 (外側の円) に当たることでも被弾します。想定半径の 3 倍です……

OnTriggerEnter|Stay2D() 、isTrigger なものだけに反応すると思ったらそうではないんでしたね…　忘れていました…

それでめちゃくちゃ当たっていたようです。申し訳ないです…
試しに修正した状態で "浄化の嵐" を受けてみたところ、すんなり突破できてしまいました…

今直すのはレギュレーション的にどうなのだろうというのと、難易度がそこそこ変わりそうなので (本当に開発初期からこの状態だったので、これ前提で弾密度を組んでしまった)、一旦そのままにしておきます…

ポジティブに考えると、弾数少なめで圧迫感が出るのでまぁ良かったのではないでしょうか…

Debugging Functions

ゲーム内の Info に書いたものですが、ここにも残しておきます。

F8 キーを押すと高速周回モード (3 倍速) になります
Player Select 画面で ↑↑↓↓←→←→XZ すると、
- デバッグモードになります
  - 被弾しても HP が減らなくなります
  - スキルを撃っても減らなくなります
  - スコアがアビドス状態になります (不正防止のため)
- 入力に成功すると爆発音が鳴ります
- ユズ以外を選択する場合は、Z を押す前にカーソルを動かしてください
Player Select 画面で 1~6 キーを押しながら開始すると、対応したステージから開始します
- (qwerty の上のキーです)

おわりに

という感じで作っていました。久しぶりのゲーム制作でしたがとても楽しかったです。

この記事を書き終わる前に結果が出てしまいました。

【特別賞】
なんと今回「ミレニアムプライス級！」と思われる素敵な作品が他にも2つありましたので、別枠で特別賞もお送りします！

1つ目は Andante さんの作品です！

ゲーム開発部のみなさんが夢中で遊んでしまうくらい素敵なゲームで、今回特別賞となりました！

おめでとうございます🎉#ブルアカ https://t.co/hjXXapenlU
— ブルーアーカイブ公式 (@Blue_ArchiveJP) 2021年5月24日

「特別賞」を頂きました。
まさか本編のシナリオに合わせてくるとは思わず震えていました。ありがとうございました。

また、プレイしてくださった方々にも大きな感謝を…。少しでも楽しい時間になったら幸いです。

「ブルーアーカイブ」本編ももちろん楽しいゲームですので、もし初めて興味を持った方がいらっしゃればぜひ…！
「ゲーム開発部」のメンバーがメインストーリー Vol. 2 で活躍しています。
https://bluearchive.jp/

2021-03-28

.NET 6 (Preview) における System.Random の実装変更

はじめに

2021 年 2 月に、 .NET 6 Preview 1 が公開されました。
なんとここで System.Random の仕様に大きめの追加・変更があったようなので、紹介します。

※ 本記事の内容は .NET 6 Preview 2 で確認しています。.NET 6 のリリース版では内容が変更される可能性があります。

`xoshiro256**` 擬似乱数生成器の採用

驚くべきことに、以前の記事で散々文句をつけた (そして変わらないだろうと思っていた) 擬似乱数生成アルゴリズムが変更になりました。

新しく採用されたのは xoshiro256** です。このアルゴリズムは速度面・品質面でかなり優秀です。
ざっくり比較すると次のようになります。

アルゴリズム	周期	サイズ (byte)	均等分布次元	失敗するテスト	`Next` 実行時間 (ns)
.NET 5 (Lagged-Fibonacci)	??? ( $\lt 2 ^ {1705}$ )	280	??? (< 55) @ 32 bit	BCFN, DC6	9.351
.NET 6 (xoshiro256**)	$2 ^ {256} - 1$	72	4 @ 64 bit	-	2.744

`xoshiro256**` とは

xoshiro256** は、 2018 年に Sebastiano Vigna 氏が開発した擬似乱数生成器です。
この方は Chrome などで採用されている xorshift128+ や、高速で有名な xoroshiro128+ を開発された方です。 xoshiro256** はそれらの改良版にあたります。

xoshiro256** の C# での実装例を示します。

// 内部状態 (全 0 以外なら可)
private ulong s0, s1, s2, s3;

// 64 bit 擬似乱数生成
public ulong NextUInt64()
{
    ulong result = BitOperations.RotateLeft(s1 * 5, 7) * 9;
    ulong t = s1 << 17;

    s2 ^= s0;
    s3 ^= s1;
    s1 ^= s2;
    s0 ^= s3;

    s2 ^= t;

    s3 = BitOperations.RotateLeft(s3 , 45);

    return result;
}

xoshiro256** は、 Xorshift や Mersenne Twister と同じ系列の理論を持ちます。
内部状態は 256 bit (64 bit x 4) 、周期は $2 ^ {256} - 1$ 、出力は 64 bit 精度で 4 次元に均等分布します。
出力関数の工夫により、 Xorshift や Mersenne Twister でみられた線形性テストでの失敗を克服しており、 BigCrush や hwd テストに合格します。
加えて生成は非常に高速で、作者のベンチマークによれば 1 秒間に 9.5 GB 程度の乱数を生成することができます。

あえて欠点を述べるとすれば、内部状態復元攻撃が比較的容易に行えること (4 つの連続する 64 bit 出力が観測できれば確実に復元可能) 、特定の (限定された) 状況下ではテストに失敗することなどが挙げられます。

既存の実装例としては Math.NET が挙げられます。標準ライブラリレベルで採用している言語は今のところ見つけられませんでした。

原典の論文はこちらを参照してください。
ちなみに、 xoshiro256++ などの出力関数を変更したバリアントも存在します。

シード指定時の互換性の維持

ところで、安直に System.Random の内部実装を変更してしまった場合、従来の乱数列の再現を期待するプログラムの動作が壊れてしまいます。

.NET 6 では、再現性が不要な new() コンストラクタではでは新しい xoshiro256** を、再現を期待する new(int seed) コンストラクタでは従来のアルゴリズムを用いる、というように切り替えることで対策をとっています。 *1
したがって、 xoshiro256** を使用したい場合はシード値を与えることができません。ちょっと残念ですが致し方ありません。

以降、本記事では new() で初期化した (xoshiro256** を使っている) ほうをベースに検証します。

出力関数

内部の状態遷移だけでなく、出力面でも強化が入っています。

`NextInt64()` シリーズ・ `NextSingle()` の追加

Next() の long を返すバージョンである NextInt64() / NextInt64(long maxValue) / NextInt64(long minValue, long maxValue) が追加されています。

なお、 NextInt64() の値域は $0 \le x \lt 2 ^ {63} - 1$ であり、 long.MaxValue は返さない点に注意が必要です。 *2
Next() の仕様に合わせたものかとは思いますが、それは旧アルゴリズムの設計上 int.MaxValue が出せないことによる措置でした (以前の記事を参照) 。アルゴリズム自体が変更になったことでこの制約に縛られる必要もなくなったはずで、無意味でよろしくない制約では？と思ってしまいます…
(せめて NextUInt64() が露出していれば…)

また、 NextDouble() の float を返すバージョンである NextSingle() も追加されています。

`Next(int maxValue)` の内部実装変更

xoshiro256** が使用される場合、 Next(int maxValue) などの「一定範囲に変換する処理」も効率が良いものに変更されています。
ざっくり抜粋すると以下のようになっています。

// ~= (int)Math.Ceiling(Math.Log(maxValue, 2))
int bits = BitOperations.Log2Ceiling(maxValue);
while(true)
{
    ulong result = NextUInt64() >> (64 - bits);
    if (result < maxValue)
        return maxValue;
}

maxValue 以上の最小の $2 ^ {bits}$ を求めて $0 \le result \lt 2 ^ {bits}$ の範囲で乱数を生成し、 $0 \le result \lt maxValue$ なら採用、そうでなければ再抽選する、というアルゴリズムです。
多少実行時間にブレがありますが、剰余や浮動小数点変換を使用する手法に比べて確率の偏りがなく高速です。
再抽選する確率は最悪の場合 ( $maxValue = 2 ^ {n} + 1$ ; 特に $n$ が大きい場合) でも 1 / 2 より小さくなるので、運が悪かったとしてもそれなりの試行回数で終了します。
(擬似乱数生成器の特性上、無限ループに陥る心配はありません。)

`NextDouble()` の内部実装変更

また、 NextDouble() の実装も変更になっています。

return (NextUInt64() >> 11) * (1.0 / (1ul << 53));

53 bit の乱数を生成して $2 ^ {53}$ で割ることで $0 \le result \lt 1$ を得る、という手法です。
"53" は double 型の仮数部のビット数 (+1) から来ています。

従来のアルゴリズムでは高々 $2 ^ {31} - 1$ パターンしかなかったのが $2 ^ {53}$ パターン出るようになったので、かなり精度が向上しました。

`NextBytes()` の内部実装変更

さらに、 NextBytes() も変更されています。
詳細は省きますが、ざっくり説明すると 1 回の乱数生成で得られる 8 byte 分の乱数を一度に書き込むようになっています。
(C 言語で uint64_t * にキャストしてごりごり書き込んでいくイメージ、といえば伝わりやすいでしょうか…)

従来は 1 回あたり 1 byte ずつちまちま書き込んでいたので、かなりの効率化が見込めます。 (後述しますが、実際非常に高速になっています。)

パフォーマンス

メモリ

.NET 6 では、 System.Random は 1 インスタンスあたり 72 byte を消費します。 *3
内訳は以下のようになっています。 (実装はイメージです)

class Random    // クラスのヘッダ(型情報など) 16 byte
{
    class Impl  // 子クラスのヘッダ 16 byte
    {
        ulong s0, s1, s2, s3;   // 擬似乱数の内部状態 32 byte
    }
    private Impl impl;  // 子クラスへの参照 8 byte
}

クラスが入れ子になっているため若干余分に確保してしまっていますが、以前 (280 byte) に比べると 1/4 近くになっています。

速度

とりあえず実測してみましょう。検証環境は以下の通りです。

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
Intel Core i7-7700HQ CPU 2.80GHz (Kaby Lake), 1 CPU, 8 logical and 4 physical cores

.NET Core 5.0.4 (CoreCLR 5.0.421.11614, CoreFX 5.0.421.11614), X64 RyuJIT
.NET Core 6.0.0 (CoreCLR 6.0.21.15406, CoreFX 6.0.21.15406), X64 RyuJIT

各メソッドコール 1 回にかかった時間は以下の通りです。± は標準偏差、 Speed x は何倍速くなったかを示します。

Method	.NET 5 [ns]	.NET 6 [ns]	Speed x
`new()`	1989.19 ± 37.66	151.631 ± 4.83	13.119
`Next()`	9.351 ± 0.15	2.744 ± 0.03	3.408
`Next(401)`	12.575 ± 0.14	6.809 ± 0.10	1.847
`Next(168, 401)`	12.227 ± 0.17	5.142 ± 0.11	2.378
`Next(1 << 30)`	12.563 ± 0.19	2.941 ± 0.09	4.272
`Next((1 << 30) + 1)`	12.54 ± 0.15	14.323 ± 0.20	0.876
`NextDouble()`	10.43 ± 0.12	2.989 ± 0.05	3.489
`NextBytes(byte[256])`	2333.249 ± 19.59	41.31 ± 0.53	56.481
`NextInt64()`	#N/A	2.612 ± 0.08	#N/A
`NextInt64(401)`	#N/A	6.693 ± 0.15	#N/A
`NextInt64(168, 401)`	#N/A	4.916 ± 0.12	#N/A
`NextInt64(1L << 62)`	#N/A	3.844 ± 0.12	#N/A
`NextInt64((1L << 62) + 1)`	#N/A	14.55 ± 0.23	#N/A
`NextSingle()`	#N/A	3.168 ± 0.04	#N/A

速度差が特に大きかった new() と NextBytes() の処理時間の比較を以下に示します。

f:id:andantesoft:20210328221840p:plain

それ以外の Next() 系メソッドの処理時間の比較を以下に示します。

f:id:andantesoft:20210328221829p:plain

また、 .NET 6 で追加されたメソッド群と既存の似たメソッドの処理時間を比較したグラフを以下に示します。
(これだけ .NET 6 の中での比較です。)

f:id:andantesoft:20210328221834p:plain

ブレはありますが、全体的に 2 - 3 倍程度に速くなっています。特筆すべきは new() (約 13 倍速) と NextBytes (約 56 倍速) でしょう。 new() はかなり複雑だった初期化処理が単に乱数を設定するだけになったこと、 NextBytes は乱数をまとめて配列に書き込むようになったことが影響していそうです。

ただし、注意すべきは Next((1 << 30) + 1) と NextInt64((1L << 62) + 1) です。
これらは意図的に遅くなる (再抽選率がほぼ 1 / 2 と高くなる) 値を選んだケースで、最善の場合 (再抽選率 0) の Next(1 << 30), NextInt64(1L << 62) と比べると 3 - 5 倍程度時間がかかっており、 Next では .NET 5 のものよりも遅くなっています。

以上のように maxValue に依存して速度が結構変わるので、注意…するほどではないと思いますが、覚えておくとよいかもしれません。

32 bit 環境での速度について

xoshiro256** は、64 bit 環境 (ulong 上での計算が高速に動作する環境) を想定して設計されたアルゴリズムです。
従来のアルゴリズムは 32 bit 環境メイン (int ベース) のため、 32 bit 環境においては System.Random の動作が若干遅くなる可能性はあります。
検証環境がないので実測はできていませんが…

(2021/08/31 追記:)
32 bit 環境 (厳密には x64 か arm64 以外のプラットフォーム) においては、 xoshiro256** の代わりに xoshiro128** アルゴリズムの実装が使用されます。これは xoshiro256** のワードサイズを 64 bit から 32 bit にしたようなもので、性質も概ね同様です。周期は $2 ^ {128} - 1$ となっています。
したがって、上述の打ち消し部分の心配は杞憂でした。きちんと考えられていますね…!

余談: 静的インスタンスの追加 (未対応)

2021/03/28 時点ではリクエストレベルですが、 PR #50297 で静的なインスタンスを取得するプロパティが提案されています。

// ライブラリ内の定義 (イメージ) 
public class Random {
    public static Random Shared { get; }
    // ...
}

// 使用例
int randomValue = Random.Shared.Next(10);

これによって、再現性が不要なら乱数インスタンスを自分でいちいち生成・保持する必要がなくなります。
また、よく見かける誤用である「乱数が必要になるたびに new Random().Next() する」ことをある程度防げるのでは、とも思い、とても便利そうです。
正式採用されることを願って…!

(2021/08/31 追記):
.NET 6 Preview 4 で Random.Shared が実装されました。🎉

おわりに

永遠に悲しみを背負い続けるのだろうと思っていた乱数周りに手が入るとは、と大変驚いて・喜んでいます。
従来のカオティックなアルゴリズムに比べて理論的にも実用的にも優れており、かつこちらで対応する必要はほぼないのでとてもありがたいです。
メジャーリリースを楽しみにしています。

SCP-1214-EX ～ SCP-1214 の再現実験

補遺1214-4:

20██/██/██ に、 SCP-1214 の再現実験に成功したと主張するウェブサイトが財団の Web クローラによって発見されました。

+ 公開されていたウェブサイトの内容：

という体で始めます。本記事では、 SCP-1214 - 特異乱数生成プログラム (オリジナルの英語版) の機能面における再現を目指します。

SCP-1214 は、要約すると以下のような性質を持っています。

0-9 A-Z :;<=>?@ の 43 種類の文字をランダムに生成し、1 秒ごとに 50 文字ずつ表示しつづける C# プログラム
アルゴリズム的には一般的なもので、不審な点はない
にもかかわらず、██分経過すると特定の文字が頻繁に生成されるなど、乱数らしからぬ挙動になっていく
██分～██時間経過すると、徐々に単語・文章が混じり始める
さらに██時間経過すると、生成される文字種が減っていく
[補遺1214-3 非常事態報告を参照]

SCP-1214 (フェーズ0: 起動直後)。
出力される文字は十分にランダムです。

SCP-1214 (フェーズ1: 起動後██分経過)。
"I" が連続して出力しやすくなっています。

SCP-1214 (フェーズ2: 起動後█時間経過)。
連続する文字に加え、 "PLEASE" "STOP" "HURTS" などが観察されます。

SCP-1214 (フェーズ3: 起動後██時間経過)。
"4, 8, S, O" などの文字が極端に出現しにくくなっています。

非常事態報告はともかくとして、このような挙動を擬似乱数生成器で再現することは可能でしょうか？

実装手法の検討

前提として、「"特異な" 文字列を直接プログラムで生成する手法」は、あまり面白くないのでしないものとします。あくまで「きちんと使えば」擬似乱数生成器として機能するプログラムで実現することを目標とします。

一般的な擬似乱数生成器は、当然ながらあっという間にランダムになってしまうので、ほぼ実現不可能です。では、敢えて壊れた生成器を設計すること (例えば以前の記事で挙げたように Xorshift を全 0 で初期化するとか、誤った遷移式で構成するとか) で実現できるかというと、それも難しい気がします。大抵の場合「どのように壊れるか」は制御できず、オリジナルの「同一の文字が並びやすいが、時々別の文字も出る」といった挙動を再現することは困難でしょう。

実現できそうな手法としては、PCG の作者が紹介している "Party Tricks" が挙げられます。これは、内部状態に「仕込み」を入れておくことで、特定のタイミングで好きな出力列が出るようにする、というものです。リンク元の記事では、特定回数乱数を進めるとハムレットを出力する例を紹介しています。

仕込みを入れているので、原理的に実質「安直な」手法と同じでは？　と思われるかもしれませんが、この手法は初期化を適切に行えばきちんと擬似乱数生成器として利用できること、またこの手法が適用できる擬似乱数生成器では「偶然に」同じ現象が発生する可能性は 0 ではないことから *1 、この手法を採用します。

しかしここで困難となるのが、「欲しい出力列と同じ量だけ内部状態が必要であること」です。当然ではありますが、仕込める情報量は内部状態の bit 数が上限になります。今回の要件は、

1 文字あたり 43 種類
1 行 (= 1 秒) あたり 50 文字 == $43^ {50}$ 種類
オリジナルの文章から、 100 日 (= 8640000 秒) 程度は制御下で動かしたい

なので、最低でも $43^ {50 \cdot 8640000}$ 種類分、つまり $\log _ {2} 43^ {50 \cdot 8640000} \approx 2344146375$ bit の情報量 = 内部状態が必要になります。状態空間が広いことで有名な Mersenne Twister でも 19937 bit 分、今回の要件で言えば最大でも $19937 / \log _ {2} {43} \approx 3674$ 文字分 (約 73 秒分) しかありません。当然ですが、これほど巨大な内部状態を持つ既存の擬似乱数生成器は存在しない（はず）なので、自分で作らなくてはなりません。

設計

今回は、設計が比較的容易である Lagged Fibonacci 法を採用することにしました。

Lagged Fibonacci 法の遷移式は、以下のように表されます。　*2

$\begin{aligned} x_{n} = x_{n-j} + x_{n-k} \pmod{m} \end{aligned}$

プログラム的に書けば、以下のようになります。遷移式から分かるようにとてもシンプルになります。

const int j = ..., k = ...;
// m = 2^64 とするため、 mod m は不要になります

ulong state[j];
int stateIndex = 0;

public ulong Next()
{
    // インデックスを [0, j) の範囲に変換するメソッド
    int mod(int index) => (index + j) % j;

    stateIndex = mod(stateIndex + 1);

    return state[stateIndex] = state[stateIndex] + state[mod(stateIndex - k)];
}

$f(t) = t^ {j} + t^ {k} + 1$ が原始三項式となるならば、最大周期 $2^ {63} (2^ {j} - 1)$ が実現できます。 *3

それでは、なるべく大きい $j$ を持つ原始三項式を調べてみましょう。 2021/01/18 時点で知られている最大の $j$ を持つ原始三項式の一つが以下になります。 *4

$\begin{aligned} x^ {74207281} + x^ {9999621} + 1 \end{aligned}$

この多項式を利用して $j = 74207281, k = 9999621$ とすることで、最大周期 $2^ {63} (2^ {74207281} - 1)$ を実現する擬似乱数生成器を作ることができます。10 進にするとだいたい 1407332901 桁、 $10^ {1.4 \times 10^ {9}}$ ぐらいです。内部状態は 4749265984 bit ~= 566 MiB という暴力的な数値を誇ります。これを「一般的アルゴリズム」と呼称するのは無理がある気がしてきましたが、見なかったことにして進めます。

余談ですが、大きいほうの定数 74207281 はメルセンヌ素数 $2^ {74207281} - 1$ の指数から来ています。構造が単純なメルセンヌ素数をベースにすると、諸々の計算を効率的に行えるのです。
また、この原始三項式が発見されたのは 2016 年ですが、本家の SCP 記事が書かれたのは 2012 年のようです。「当時は未知だったはずの定数をどうやって知りえたのかは不明です」と言えば SCP らしくなるでしょうか…？

話を戻しましょう。 566 MiB もあれば、さきほど計算した 100 日分の情報量 (2344146375 bit ~= 279 MiB) ですら余裕でクリアできます。

内部状態設定

設計は出来ました。あとは所定の出力を得るために、内部状態を設定する必要があります。希望する出力列は "特異な" プログラムから得るとして、内部状態をどう逆算すればよいでしょうか。といっても、遷移関数がシンプルであることから、逆算は非常に簡単です：

// この時点で ulong[] output には希望する出力列が入っているものとする
// StateLength = output.Length = 74207281, Lag = 9999621

for (int index = StateLength - 1, lagged = index - Lag; index >= Lag; index--, lagged--)
    output[index] -= output[lagged];
for (int index = Lag - 1, lagged = StateLength - 1; index >= 0; index--, lagged--)
    output[index] -= output[lagged];

// この時点で output は対応する内部状態になっている

実装

以上で理論面での準備が整ったので、実装を行いました。リポジトリはこちらです。理論は明らかですので "Explained" としています。

https://github.com/andanteyk/SCP-1214-EX

実装にあたって、本体(GUI) random_number_test と特異シード生成器 seed_generator は別のプロジェクトにしており、 seed_generator で内部状態をファイルに保存したのち random_number_test で読み込んで表示するようになっています。ちょっと面倒ですが、これによって本体側のプログラムに "特異性" (仕込み用コードともいいます) を持たせないようにしています。

一応「約 60 行のソースコード」という制約にしたがってファイルごとのサイズは 60 行ぐらいにしました。全体のサイズを 60 行にするとコードゴルフめいて不自然になりそうだったので許してください…

また、 .NET 5 での実装です。オリジナルは Visual Studio 2012 で開発されていたようなので .NET Framework 4 ぐらいで書くべきなのかもですが、書いていてつらくなってきたので最新のにしてしまいました。
余談ですが、当初 .NET Framework 4.8 で書いていたのを .NET 5 に書き換えた際、 I/O が ██ % 速くなってちょっと感動しました。 MemoryMarshal.Cast で ulong[] を直接入出力できるようになったのが大きそうです。

余談：ある範囲の一様分布乱数を大量に生成する手法について

SCP-1214 の実装では、 ASCII 48 ～ 90 (43種類) の範囲の乱数を大量に生成する必要があります。しかし、安直に Next() % 43 + 48 としてしまうと、 Next() 1 回に対して 1 個の出力しか得られないのでもったいないです。ここで Next() は ulong 、つまり 64 bit 分の情報量を持つのですから、 $\lfloor \log _ {43} 2 ^ {64} \rfloor = 11$ 文字まで一度に生成することができます。

今回は以下のように実装しました。

public IEnumerable<char> NextChars()
{
    while (true)
    {
        ulong r = Next();
        for (int i = 0; i < 11; i++)
            yield return (char)('0' + Math.BigMul(r, 43, out r));
    }
}

整数64bit . 小数点以下64bit の固定小数点数をイメージすると分かりやすそうです。 r が小数点以下 64 bit にあたります。 r を 0 ~ 1 の乱数とみなして $43 ^ {11}$ を掛けて、整数部を 43 進数にして各桁を取り出す、というイメージです。

なお、今回は確率の偏りを除去するコードは含めていません。どのみち仕込みを入れるので…
もし実用目的で転用する場合は入れるとよいでしょう。

起動実験記録 ██ (20██/██/██ 実施):

SCP-1214-EX の起動実験 ██ において、今まで観測されていなかった "KETER" の単語が出現しました。

SCP-1214 (起動後█時間経過)。
中央付近、Y が連続している行に "KETER" の語がみられます。

何らかの SCP に関連する情報を含んでいる可能性があるため、 ██████ 研究員によって調査が続けられています。 *5

- (公開されていたウェブサイトの内容を閉じる)

財団はウェブサイトを無害なものに置換し、投稿者および閲覧者に対しクラス A 記憶処理を施しました。

ライセンス

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

This article is based on "SCP-1214 - Anomalous Random Number Generator" by "DrCarnage".

*1:もちろん天文学的に低い確率にはなりますが、不可能ではない点が重要です。逆に、例えば内部状態が 128 bit しかない Xorshift からハムレットが出力される可能性は 0 であると断言できます。Xorshift から確実に生成できる出力列の最大長は 128 bit == 16 byte 分しかありません。

*2:実際には + 以外の演算子を使用することもできます。例えば、以前記事にした System.Random では - を使用しています。

*3: Brent, R. P. (1994). On the periods of generalized Fibonacci recurrences. Mathematics of Computation, 63(207), 389-401.

*4:出典: https://maths-people.anu.edu.au/~brent/trinom.html 。先の論文を書かれた Brent 氏が調べています。

*5:これについては仕込みとかではなく、本当に偶然に発見されたものです。出現確率は雑に計算すると 1/pow(43, 5) ~= 1.5 億分の 1 です。とはいえシーケンスが十分に長いため、こういったことも起こりえます。

2021-01-09

.NET System.Random の実装と欠陥について～重箱の隅をつつきたおす～

はじめに

.NET (C#) には、組み込みの擬似乱数生成器 System.Random が用意されています。ここでは、 System.Random の実装と性質・ひいては欠陥について、可能な限り深くまで調べて難癖をつけていきます。

結構いろいろあって内容が増えてしまったので、雰囲気をつかみたい方は目次をみてください。

はじめに
内部実装
外部実装・その他の問題
おわりに

内部実装

ここでは、 System.Random に実装されているメソッドの中身を詳しく見ていきます。

内部実装の参照

System.Random の内部実装は以下サイトで確認することができます。

両者は基本的には同一ですが、 new Random() の動作だけ異なります。詳細については new Random() の項を参照してください。

System.Random の定義だけ並べると以下のようになっています。ひとつひとつ追っていきたいと思います。

public class Random
{
    public Random();
    public Random(int Seed);

    public virtual int Next();
    public virtual int Next(int maxValue);
    public virtual int Next(int minValue, int maxValue);
    public virtual void NextBytes(byte[] buffer);
    public virtual void NextBytes(Span<byte> buffer);   // .NET Standard 2.1~
    public virtual double NextDouble();
}

`new Random()`

ライブラリ側で int 型のシード値を選択し、後述する new Random(int Seed) を呼び出します。このコンストラクタだけは、.NET Framework と .NET Core 以降で動作が異なります。

.NET Framework: 同タイミングでの初期化でシードが重複する問題

.NET Framework では、 Environment.TickCount (システム起動後のミリ秒単位の経過時間) をシードに用います。そのため、同じタイミングで生成された Random はかなり高い確率で同じ乱数列を返すようになってしまいます。例えば、同一フレーム中に別々の場所でインスタンス生成した場合などで、意図せず出力が重複する事故が予想されます。余談ですが、手元の C# Interactive で試してみたところ、1 ミリ秒の間に 2 万個程度の同じ系列を返すインスタンスを生成できました。

.NET Core: シード重複問題の改善

対して .NET Core 以降では、このような問題が起こらないよう対策がとられています。具体的には、スレッドごとに独立な static Random インスタンスの Next() をシードとします。そして、シードを生成するほうは普通の static な Random インスタンスの Next() をシードとしています。そしてそして、そのシードを生成するほうは、extern 関数 SystemNative_GetNonCryptographicallySecureRandomBytes をシードとしています。
要するに、外部取得シード → static Random → ThreadStatic Random → インスタンス Random 、という流れで初期化されていきます。

なお、 SystemNative_GetNonCryptographicallySecureRandomBytes の Unix 環境における実装は、

Arc4Random が利用できればそれを、
できなければ、/dev/urandom/ と lrand48() を xor したものを

返すようです。

ところで、 Next() の性質上、シードに int.MaxValue は絶対に選択されなくなりました。 (.NET Framework では起動から 25 日弱経てば生成される可能性がありました。) 詳細は Next() の項で述べます。

余談: 同じアルゴリズムによる初期化について

乱数のシード設定に同じ擬似乱数生成アルゴリズムを用いるのは果たして大丈夫なのか、という懸念が少しだけあります。シード設定には根本的に構造が異なる擬似乱数生成器を用いるほうがよい、気がするので… xoshiro/xoroshiro の作者のサイトにはこのような記述があります。

as research has shown that initialization must be performed with a generator radically different in nature from the one initialized to avoid correlation on similar seeds.

(肝心の "research" の中身にアクセスできないので厳しいですが、 Mersenne Twister の作者が書かれているようです)

`new Random(int Seed)`

Seed をもとに内部状態を初期化します。同じ Seed を指定すれば、完全に同じ出力列が得られます。

初期化に使われているアルゴリズムは、微妙に根拠が怪しい気もするラグ可変の Fibonacci 法らしきものと、遷移関数と異なるラグを持つ Lagged Fibonacci 法 4 周分です。 (もし根拠をご存知の方がいらっしゃれば教えていただけるとありがたいです。)

なるべく分かりやすいように整理した等価なコードを示します。

// 内部状態:
int[] _seedArray = new int[56];      // [0] は未使用
int _inext;   // I(ndex) Next ?
int _inextp;  // I(ndex) Next P ?


// Seed の絶対値を取る
Seed = (Seed == int.MinValue) ? int.MaxValue : Math.Abs(Seed);

// 定数 161803398 は黄金比が由来とのこと
_seedArray[55] = 161803398 - Seed;


// ラグ可変の Fibonacci 法らしきもの (？) 
{
    int prevState = _seedArray[55];
    int nextState = 1;

    for (int i = 1; i < 55; i++)
    {
        int leapIndex = 21 * i % 55;
        _seedArray[leapIndex] = nextState;

        // (prevState - nextState) mod int.MaxValue のイメージ
        nextState = prevState - nextState;
        if (nextState < 0)
            nextState += int.MaxValue;

        prevState = _seedArray[leapIndex];
    }
}

// ラグの異なる Lagged Fibonacci 法で 4 周する
for (int k = 0; k < 4; k++)
{
    // lagIndex は (1 + (index + 30) % 55) に等しい  
    for (int index = 1, lagIndex = 32; index < 56; index++, lagIndex++)
    {
        // ([index] - [lagIndex]) mod int.MaxValue のイメージ
        _seedArray[index] -= _seedArray[lagIndex];
        if (_seedArray[index] < 0)
            _seedArray[index] += int.MaxValue;

        if (lagIndex == 55)
            lagIndex = 0;
    }
}

// ラグ (インデックス) の初期化
_inext = 0;
_inextp = 21;        // 💀💀💀

なお、初期化後の _seedArray の各要素は $0 \le x \le 2^ {31} - 2$ の範囲になります。 int.MaxValue は含まない非負の値をとるのが重要なポイントです。

絶対値が同じ `Seed` は同じ乱数列を生成する

Seed は絶対値をとってから計算するため、例えば new Random(401) と new Random(-401) は同じ乱数列を生成します。なお、Seed == int.MinValue の場合はなぜか int.MaxValue として扱われます。したがって、全ての int 値の入力 ( $2^ {32}$ パターン) に対して、実質のシード値は

0 : 0 の 1 個
1 <= x < int.MaxValue : x, -x の 2 個
int.MaxValue : int.MaxValue, -int.MaxValue, int.MinValue の 3 個

と微妙に偏ります (？) 。

初期状態のパターン数が少ない

以上から、初期状態は $2^ {31}$ パターンに限定されます。内部状態のとりうるパターン数 $(2^ {31} - 1) ^ {55} \approx 2^ {1075}$ *1 よりかなり小さく、ブルートフォースでもなんとかなる程度の量です。

内部状態 `_seedArray` の無駄

_seedArray は要素が 56 個あるにもかかわらず、実際に使っているのは [1] ~ [55] までで [0] は使用されておらず、残念感があります。55 個しか使わないのが理論上正しいので、 0 基点にして 55 要素で良かったのでは、と思ってしまいます。

余談: 初期化時の制約について

System.Random では上記のアルゴリズムで初期化が行われていますが、別のアルゴリズムで差し替えようと思ったとき (?) 、問題なく初期化するにはどうすればよいでしょうか。擬似乱数生成器の設計によりますが、一般に内部状態を初期化する際は特殊な条件を満たす必要があります。例えば Xorshift では全 0 以外で初期化する必要があり、そうでないと永遠に 0 を吐き出し続けてしまいます。

System.Random では、内部状態にひとつでも非 0 の要素があれば (全 0 でなければ) 大丈夫です。ただしこれは法 $m = 2 ^ {31} - 1$ 上で正しく設計されていた場合の話です。正しく、がどういう意味かは Next() の項で説明しています。

もし法 $m = 2 ^ n$ ならば、ひとつでも奇数の要素があれば大丈夫です。 (つまり、どれかは最下位ビットが 1 になっている必要があります。) 少しだけ条件が厳しくなります。

ただし、これらは最低条件 (最長周期を満たす条件) であって、まともな初動の出力が得られるかはまた別の話です。例えば {1, 0, 0, 0, ..., 0} といった極端な初期状態を設定すれば、しばらくの間 0 とか 1 のようなものが出力され続けるでしょう。現実には、なるべくランダムなバイト列で埋めてから、これらの条件を満たすかどうかチェックする (ダメならやり直す) 、という流れになります。ただ、 System.Random ではその手のチェックは入っていません。要素が 55 個もあるのでどれかは条件を満たすだろう、という楽観的な見込みなのかもしれません (実際問題ないとは思いますが) 。

また _inext や _inextp といったインデックスについては、別種の注意を払って初期化する必要があります。コメントの意味深な 💀💀💀 については、次の Next() の項で解説します。

`int Next()`

0 <= x < int.MaxValue の範囲の擬似乱数を出力します。

Next() は他の出力系メソッドのベースになっています。他のメソッドは、このメソッドの出力を加工して出力しています。 (実際のコード上では InternalSample() というメソッドに実装されていますが、Next() と完全に等価なので、簡単のためこのように表現します。)

Next() 、つまり System.Random の遷移関数は、 MSDN にもあるように Lagged Fibonacci 法の一種である「引き算法」で実装されています。

The current implementation of the Random class is based on a modified version of Donald E. Knuth's subtractive random number generator algorithm.

ちなみに、文献としては TAOCP が参照されていますが、実際のコードは Numerical Recipes の ran3 が原典のようです。

引き算法の遷移関数を漸化式で書くと以下のようになり、名前通り引き算で遷移していることが分かります。

$\begin{aligned} x_{n} = x_{n-j} - x_{n-k} \pmod{m} \end{aligned}$

なお、ここでの $\mathrm{mod}$ は剰余演算子 % とは微妙に異なり、必ず非負の値をとるものとします。例えば、 $-1 \equiv 4 \pmod{5}$ です。

System.Random においては、 $j = 55, k = 34, m = 2^ {31} - 1$ です。

Next() を分かりやすいように整理した等価なコードを示します。

// index を +1 して、配列範囲からあふれたらループさせる (% 55 (+1) のイメージ)
if (++_inext >= 56) 
    _inext = 1;
if (++_inextp >= 56)
    _inextp = 1;

// ([_inext] - [_inextp]) mod int.MaxValue のイメージ
_seedArray[_inext] = _seedArray[_inext] - _seedArray[_inextp];
if (_seedArray[_inext] < 0)
    _seedArray[_inext] += int.MaxValue;

return _seedArray[_inext];

さて、擬似乱数の紹介と言えば「周期」が代表的ですが、System.Random の周期は不明です。正しく実装された場合よりも短くなっていると推測されます。 なぜかというと、誠に遺憾ながら System.Random の遷移関数の実装に重大な誤りが複数含まれているためです。

遷移関数の実装ミス (1) - ラグ k の指定

誤りのひとつは、 Random(int seed) コンストラクタの項で意味深な 💀💀💀 を貼っていた _inextp = 21; で、正しくは 31 を代入すべきでした。この値は 2 つめのラグ (漸化式での $k$ ) を指定するものです。

Lagged Fibonacci 法で最大周期を達成するためには、法 $m = 2^ n$ の場合はラグ $j, k$ に $\mathrm{GF}(2)$ 上の原始多項式の指数を用いる必要があります。 (とても雑に言えば、 $j, k$ は適当に決めてはダメで、特別な場合だけ最大周期になるということです。) 例えば、以下に示す $f(x)$ は $\mathrm{GF}(2)$ 上での原始多項式です:

$\begin{aligned} f(x) = x^ {55} + x^ {24} + 1 \end{aligned}$

この指数である 55 と 24 をラグとして用いることで、最大周期を達成できます。 _inextp の正しい初期値 31 は、 55 - 24 から来ています。

そして、System.Random で使われているラグ $(55, 34)$ を多項式で表した $x^ {55} + x^ {34} + 1$ は、原始多項式にはなりません (既約多項式ですらありません。詳細は後述) 。そのため、 System.Random の周期は、達成可能な最大周期よりも短くなっており、かつシードによって周期長が変動してしまう可能性があります。

余談ですが、皮肉にも new Random(int Seed) における 2 つめの初期化フローにおいては、 _inextp = 31; 相当の "正しい" 実装になっています。

遷移関数の実装ミス (2) - 法 m の指定

また、 ~~コピペ元~~ 実装のベースになったと思われる Numerical Recipes の ran3 の実装と比べると、 $m$ の値も $10^ {9}$ から $2^ {31} - 1$ に変更されています。さらに言えば、原典となる TAOCP の ran_array では $2^ {30}$ でした。MSDN の modified version という記述はこの $m$ の変更を指しているものと思われます。 *2

法 $m = 2^ n$ の場合は、下位 $i$ 番目のビット (最下位は 0 とします) の周期が $2^ {i} (2^ {j} - 1)$ となるため、最大周期は $2^ {n-1} (2^ {j} - 1)$ となります。 *3 System.Random でいえば $2 ^ {30} (2 ^ {55} - 1) \approx 2 ^ {85}$ です。

しかし、 System.Random においては $m = 2^ {31} - 1$ で、これは奇数 (もっと言えば素数) なので、以上の議論は適用できません。私が調べた限りでは、少なくとも「 $\mathrm{GF}(2^ {31} - 1)$ 上の」多項式 $f(x) = x^ {55} + x^ {34} + 1$ が原始多項式である必要がありそうです。しかし、 (そもそもラグが誤っているのを無視しても) $\mathrm{GF}(2)$ 上で原始多項式であることと $\mathrm{GF}(2^ {31} - 1)$ 上で原始多項式であることは全く関係がないのと、 $\mathrm{GF}(2^ {31} - 1)$ 上での原始性判定は法の大きさのために困難であると推測されるのとがあります。原始性判定には $(2^ {31} -1) ^ {55} - 1$ の素因数分解を知っている必要がありますが、巨大なため FactorDB でも完全な分解が載っておらず (297 桁の未分解の数を含みます) 、まだ人類は知らない可能性が高いです。

ちなみに $m = 2 ^ {31} - 1$ の場合は、理論上の最長周期は $(2 ^ {31} - 1) ^ {55} - 1 \approx 2 ^ {1705}$ になります。

余談: m = 2 ^ 31 の場合の最下位ビットの周期について

注記: この項での内容は実際の System.Random には適用できません。参考情報程度にお考え下さい。

オリジナルの $m = 2^ {31} - 1$ の場合は解析が厳しいことを上で述べましたが、 +1 して $m = 2^ {31}$ とした場合なら、法が 2 のべき乗になるので本来の $\mathrm{GF}(2)$ 上での理論が適用可能であり、話が比較的簡単になります。

System.Random の $\mathrm{GF}(2)$ 上での多項式は、 Wolfram Alpha 先生曰く以下のように因数分解されます:

$\begin{aligned} f (x) &= x^ {55} + x^ {34} + 1 = f _ 1(x) \cdot f _ 2(x) \cdot f _ 3(x) \\ f _ 1(x) &= x^ {9} + x^ {8} + x^ {7} + x^ {6} + x^ {5} + x^ {3} + 1 \\ f _ 2(x) &= x^ {19} + x^ {18} + x^ {17} + x^ {16} + x^ {14} + x^ {11} + x^ {7} + x^ {6} + x^ {5} + x^ {4} + 1 \\ f _ 3(x) &= x^ {27} + x^ {25} + x^ {23} + x^ {21} + x^ {20} + x^ {17} + x^ {15} + x^ {13} + x^ {11} + x^ {8} + x^ {7} + x^ {6} + x^ {4} + x^ {3} + 1 \\ \end{aligned}$

なお、 $f _ 1, f _ 2, f _ 3$ は原始多項式となることを確認しています。

ここで、内部状態の最下位ビットだけを考えることにすると、遷移式 $x _ i = x _ {i - 55} - x _ {i - 34} \pmod m$ の減算を $x _ i = x _ {i - 55} \oplus x _ {i - 34} \pmod m$ のように XOR に置き換えても意味は変わりません (参考) 。 XOR に置き換えた式から、最下位ビットは LFSR (Xorshift や Mersenne Twister の仲間) と同じ働きをすることが分かります。

LFSR では、 $s$ 回の遷移を $x ^ s \pmod{f}$ と多項式で表すことができます。ここで、 $x = 0$ にすると $s$ にかかわらず = 何度遷移しても 0 になるので、周期が 1 になってしまいます。 (そのため、LFSR ベースの擬似乱数生成器では「全 0 以外で初期化せよ」とよく書かれています。) 今回は法とする多項式が原始ではないので、計算が少しだけ複雑になります。

$f$ を因数分解した $f _ 1, f _ 2, f _ 3$ について、 $x _ 0 \not \equiv 0 \pmod{f _ i}$ を満たす $f _ i$ の位数 ( $x ^ k \equiv 1 \pmod{f _ i}$ を満たす最小の自然数 $k$ ) の最小公倍数が、初期値 $x _ 0$ から始まる系列の周期となります。 ( $f _ i$ は $\mathrm{GF}(2)$ 上の原始多項式なので、位数はそれぞれ $2^ {9} - 1, 2^ {19} - 1, 2^ {27} - 1$ となります。) 逆に考えると、 $x _ 0 \equiv 0 \pmod{f _ i}$ となる $f _ i$ が存在すれば、その分だけ周期が短くなる、ということです。

以上から、全てのとりうる初期状態 $2 ^ {55}$ パターン内での、最下位ビットの周期の内訳を計算したものを下表に示します。最初の 3 列が $x _ 0 \pmod{f _ i}$ が 0 かそれ以外かを示します。「ストリームの本数」は初期値の個数を周期で割ったもので、互いに交わらない乱数列の数を示します。 (ストリーム A で出現する数値は他のストリームでは一切出現せず、その逆も同様です。初期値を変更しない限りストリームが変わることはありません。) なお、最初の 0, 0, 0 の列は 0 で初期化した場合で、一応含めましたが実質ノーカンです。

f1	f2	f3	属する初期値の個数	周期	ストリームの本数
0	0	0	1	1	1
0	0	any	134217727	134217727	1
0	any	0	524287	524287	1
0	any	any	70368609435649	70368609435649	1
any	0	0	511	511	1
any	0	any	68585258497	134217727	511
any	any	0	267910657	267910657	1
any	any	any	35958359421616639	70368609435649	511

割合にすると 99.9998 % ぐらいは周期 $70368609435649 \approx 2^ {46}$ になりますが、それでも実現可能な最大周期 $2^ {55} - 1$ よりかなり小さくなります。また、とても運が悪いとたった 511 回でループする出力列が割り当てられる可能性があります。

具体例を挙げてみます。最下位ビットだけを集めて構成した MinimalBottomSystemRandom において、初期状態 0x6c98d1cf は表の 2 行目に分類されます。そのため、内部状態は 55 ビット分あるにもかかわらず周期として 134217727 が出力されます。

class MinimalBottomSystemRandom
{
    // State の最下位ビット (0x1) が x[0] の最下位ビット, 次のビット (0x2) が x[1] の最下位ビット, ... を表します
    public ulong State { get; private set; }
    const ulong Polynomial = 1 ^ (1ul << 34) ^ (1ul << 55);

    public MinimalBottomSystemRandom(ulong state) => State = state;

    public ulong Next()
    {
        // 55 bit LFSR として構成します
        State <<= 1;
        if ((State & (1ul << 55)) != 0)
            State ^= Polynomial;

        return State;
    }
}

static void Test()
{
    ulong initialState = 0x6c98d1cf;
    var rng = new MinimalBottomSystemRandom(initialState);

    {
        ulong i = 0;
        do
        {
            rng.Next();
            i++;
        } while (rng.State != initialState);

        Console.WriteLine($"loops at {i}");
        // `loops at 134217727`
    }
}

ちなみに、初期値 0x192b762df1 は 3 行目に分類され、周期 524287 となります。

本項の内容は、文献 *4 を参考にしました。ただし、記載している値に誤りがあるような気がします。Fig. 30 の累乗の計算に誤りがあったり、 System.Random の多項式の係数を (55, 21) としていたりします。

遷移関数の性質の要約 - 周期は不明

要約すると、 System.Random には周期を保証できる要素が存在しないという、とても悲しい状態にあります。しかし、これらを修正すると生成する乱数列が変わってしまうため、シードを固定して同じ動作を再現することを期待しているプログラムを壊してしまいます。標準ライブラリのつらさを感じます。

一応 .NET (Framework) のメジャーバージョンをまたいだ場合には、乱数列の再現性は保証しないと明記はされているので、変更することは理論上は可能だとは思いますが、 .NET 5 でも変わらなかったところを見ると…という感じです。

この項は dotnet/runtime に立てられた Issue をもとにしています。別の問題についての言及もあるので、リンクをたどってみると面白いです。

`Next()` は `int.MaxValue` を含まない

以上では、 Next() の遷移関数としての性質について述べました。ここからは、出力関数としての特性を観察します。

MSDN にもあるように、このメソッドは 0 <= x < int.MaxValue (== 2147483647) の範囲の乱数を返します。

A 32-bit signed integer that is greater than or equal to 0 and less than MaxValue.

int.MaxValue は範囲に含まれない のが重要なポイントです。 (この制限は、内部状態が同様に 0 <= x < int.MaxValue の範囲を取っており、それをそのまま出力しているためです。遷移関数の説明での $m$ によります。)

大変面倒なことに、すべてのベースとなるメソッドの値域が 32 bit 全域を埋めないどころかそもそも 2 のべき乗ではありません。そのため、ビット演算・構造を活用した効率化ができないことが問題になります。例えば、4 バイトのランダムな byte[] を得るために BitConverter.GetBytes(random.Next()) などと書いてしまった場合、[3] の最上位ビットが常に 0 だったり、[0] の確率が偏ったりします。

`Next()` の出力パターン数は奇素数である - 範囲加工における偏り

また、出力されうるパターンの数 $2^ {31} - 1 = 2147483647$ は素数です。したがって、 $1, 2^ {31} - 1$ 以外のすべての x に対して 2147483647 % x > 0 を満たします。これが何を意味するかというと、出力をある範囲に加工する際、乗算や剰余を使って安直に変換すると必ず余りが出る = 確率に偏りが生まれることを示します。

例えば、 random.Next() % 401 によって 0 から 400 までの値を得たいとします。 *5 この時、 2147483647 % 401 == 327, 2147483647 / 401 == 5355320 となります。したがって、0 ～ 326 までの範囲は 5355321 / 2147483647 、327 ～ 400 までの範囲は 5355320 / 2147483647 の確率で得られます。このように微々たる差ではありますが、確実に差が生まれます。最も相対的な差が大きくなるのは $x \ge 2 ^ {30}$ の場合で、多いほうと少ないほうで 2 倍確率が異なる (2 / 2147483647 と 1 / 2147483647) ことになります。

一番影響がありそうな事例としては、 random.Next() & 0xff といったコードでしょうか。 $m = 2^ n$ の生成器なら偏りなく各ビットを得ることができますが、そうではないので 0xff が 8388607 / 2147483647 、それ以外が 8388608 / 2147483647 の確率で出現します。

最も、偏りについては「変換手法を工夫すれば」回避可能です。ただ、そんな工夫は System.Random には存在せず、むしろ上述した剰余を使う手法よりも偏りが発生する手法を採用しています。これについては Next(int maxValue) の項で説明します。

`_inextp` は必要か

既に述べた _seedArray の無駄に近い話ですが、これが使用されているのは Next() のほうなのでこちらに書きます。

_inextp は常に (_inext + 20 % 55) + 1 となるので削除可能ではあります。ただ、都度剰余などの計算をしなくてもよくなるので、一概に無駄とは言えないかもしれません。

実際に確かめてみましょう。変更前後で BenchmarkDotNet を使ってベンチマークを取ってみたところ、速度は全くと言っていいレベルで変わりませんでした (変更前 11.72 ± 0.560 ns 、変更後 11.65 ± 0.303 ns 。± は標準偏差) 。 int 1 つ分とはいえメモリを占有することを考えると、やっぱり不要かもしれません。

// 変更後バージョン。 Next() の先頭だけ抜粋: 
if (++_inext >= 56) 
    _inext = 1;
int _inextp = _inext + 21;      // note: ローカル変数なので保存不要
if (_inextp >= 56)
    _inextp -= 55;

余談: 下位ビットの品質について

線形合同法ベースの擬似乱数生成器では「下位ビットは品質が良くない (周期が短い) のでなるべく上位ビットを使え」「範囲に変換するときに剰余 % maxValue を使うな」とよく言われますが、 System.Random ではどうでしょうか。

ふわっとした説明しかできないので申し訳ないのですが、 System.Random においては問題なさそうです (その他もろもろの問題は見なかったことにするなら…) 。というのも、法が $m = 2 ^ n$ ではないので、最上位ビットの情報が剰余を通じて最下位ビットに伝播するため、すべてのビットの周期が最上位ビットと同様になります。

対して $m = 2 ^ n$ の場合は、ビット間の情報はキャリー (繰り上がり・下がり) のみによって伝播するため下位ビットから上位ビットへの一方通行になります。その場合は前述したように最下位から $i$ ビット目の周期は $2^ {i} (2^ {j} - 1)$ となって下位ほど周期が短くなるので、上位ビットを使ったほうが良いことになります。

このように、この問題は線形合同法固有の話ではありません。逆に、線形合同法でも法を奇素数などに設定すればすべてのビットの周期が同じになります。最も、その場合は System.Random と同じようにバイト・ワード全域への均等な出力 (例えば Next() & 0xff) が困難になるので一長一短です。

余談ですが、Xorshift や Mersenne Twister などの LFSR ベースの擬似乱数生成器ではこの問題は生じません。 $n$ ビットの状態を持つとき、すべてのビットの周期が $2 ^ n - 1$ になります。

`int Next(int maxValue)`

0 <= x < maxValue を満たすランダムな x を返します。

実は Next(0) は有効で、 Next(1) と同様に常に 0 を返します。 Next(-1) ではきちんと ArgumentOutOfRangeException がスローされます。

変換関数は、一旦 0.0 <= x < 1.0 の double 値に変換してから maxValue を掛ける、という手法で実装されています。等価な実装を示します:

return (int)(Next() * (1.0 / int.MaxValue) * maxValue);

浮動小数点数の丸めによって確率が偏る

double 上で計算しているので、浮動小数点数の丸めによる計算誤差が生じ、結果として確率が偏る場合があります。

Next(int.MaxValue) の場合が分かりやすいので、例に挙げて説明します。出力範囲としては Next() と同じ 0 <= x < int.MaxValue になりますが、Next() と Next(int.MaxValue) の結果は同一の入力に対して等価になりません。 Next(int.MaxValue) は均等な出力を生成せず、絶対に出力されない値とより多く出力される値が存在します。

この問題は、 Next() * (1.0 / int.MaxValue) * maxValue (double 値) の小数点以下のビットがすべて 1 になっていた場合に発生します。具体例を挙げると、Next() == 4194305 の場合の計算結果は内部表現 0x415000003fffffff (10進 4194304.9999999991) をとり、これを丸めた結果 4194304 と元々の Next() と違う値が返ります。なお、 Next() が前後の数値 4194304, 4194306 を返した場合の計算結果は Next() と同じになります。つまり、Next(int.MaxValue) から 4194305 を得る確率は 0 となり、対して 4194304 を得る確率は 2 / 2147483647 と通常の 2 倍になります。

Next(int.MaxValue) において、入力 ( Next() ) と出力が異なる要素は 9437184 個存在し、全体の約 0.44 % にのぼります。また、出力が異なった結果重複して振り分けられる数も存在することから、絶対出力されない要素が 9437184 個、通常の 2 倍の確率で出力される要素も 9437184 個存在することになります。

このことは目に見える問題となって現れます。より詳細な解析を行っている文献によれば、 Next(int.MaxValue) の返り値が奇数となる確率は約 50.34 % (厳密には 1081081855 / 2147483647) となり、明らかに想定される確率 (50 %) から離れています。

`int Next(int minValue, int maxValue)`

minValue <= x < maxValue の範囲の擬似乱数を出力します。

こちらも、 minValue == maxValue を許容して常に minValue を返します。もちろん minValue > maxValue ならば ArgumentOutOfRangeException をスローします。

範囲が広い場合に確率が偏る

範囲が狭い maxValue - minValue <= int.MaxValue のときは NextDouble() * (maxValue - minValue) + minValue を返すので、 Next(int maxValue) と同様です。

特筆すべきは maxValue - minValue > int.MaxValue の場合で、計算手法が異なります。前提として、元々の範囲より広い範囲に安直に変換すると絶対に出ない値が生じるなど、出力が偏ってしまいます。 (前述した浮動小数点数の丸め誤差とは別です。) 一番単純な例を挙げると、 0 <= x < 2L * int.MaxValue にしようとして x * 2 とすると全て偶数になってしまう、という感じです。余談ですが、この問題は実際に PHP で発生しているようです (雑談の項を参照) 。 System.Random では、この問題を回避するために乱数を継ぎ足す処理が入っています。

maxValue - minValue > int.MaxValue の場合の等価なコードを示します。

int result = Next();            // 0 <= x < int.MaxValue

if (Next() % 2 == 0)            // ※均等ではない
    result = -result;           // ※ 0 が出やすくなる。 -int.MaxValue < x < int.MaxValue

double d = result;
d += int.MaxValue - 1;          // 0.0 <= x < 2.0 * int.MaxValue - 1
d /= 2u * int.MaxValue - 1;     // 0.0 <= x < 1.0

return (int)((long)(d * ((long)maxValue - minValue)) + minValue);

上から順に難癖をつけていきます。まず Next() % 2 == 0 ですが、前述したように Next() のパターン数は $2^ {31} - 1$ 個なので偏りが生じます。 1073741824 / 2147483647 (50.000000023283064 %) の確率で true 、 1073741823 / 2147483647 (49.999999976716936 %) の確率で false になります。

次に result = -result ですが、 0 を入れると値が変わらないことに気づけます。したがって、他の数値の 2 倍の確率で 0 が出現することになります。 (0 が概ね $2^ {-31}$ 、他は $2^ {-32}$ 程度になります。)

残りの d の計算については、 Next(int maxValue) の処理を 0.0 <= x < 2u * int.MaxValue - 1 の範囲で行うイメージです。ただし、ここでは逆数の乗算 d *= 1.0 / constant; ではなく除算 d /= constant; を使用しています。この 2 つの演算はパッと見同じに見えますが、結果は異なります。具体的には、 Next(int.MinValue, int.MaxValue) で呼び出した際、 Next(int maxValue) の項で挙げた浮動小数点数の丸めによる誤差 (result != d * (maxValue - minValue) となる場合) が生じないようです。その代わり、除算なので多少遅くなりそうです。

`double NextDouble()`

0.0 <= x < 1.0 の double 値を返します。

等価な実装を示します。 (実際の実装は Sample() メソッドにあります。) Next(int maxValue) の計算で使われているものと同じです。

return Next() * (1.0 / int.MaxValue);

出力される最大値の誤記

0 より大きい最小の出力値は 4.6566128752457969E-10 ( 内部表現 0x3e000000_00200000 ) 、最大値は 0.99999999953433871 ( 0x3fefffff_ffc00000 ) になります。 MSDN には、取りうる最大値は 0.99999999999999978 ( 0x3fefffff_fffffffe ) であると書いてありますが、Next() が返す最大値を考えれば誤りであることは明らかです。

精度が低い

さて、 Next() の取りうる値は $2^ {31} - 1$ 種類ですから、 NextDouble() が取りうる値も同様に $2^ {31} - 1$ 種類となります。実際に double の取りうる値の数と比べてみましょう。

double において、 0.0 <= x < 1.0 の範囲には $1023 \times 2 ^ {52} \approx 2 ^ {62}$ 個の数値が存在します。 ( 0.0 の内部表現は 0x00000000_00000000 、 1.0 の内部表現は 0x3ff00000_00000000 であることからわかります。) したがって、本来取りうる値の $2 ^ {-31}$ 程度しか埋められないことになります。だいぶ疎です。

最も、全領域をカバーするのは計算コスト的に割に合わないので、実用的には 52 ～ 53 bit 精度で妥協する場合が多いです。この 52 は、 double 型の仮数部の桁数から来ています。 (+1 はケチ表現の分です。) 例えば、以下の手法では 53 bit 精度の double 値が得られます。

// ここでの Next() は ulong 型 (64bit) 全域のランダムな値を返すものとします
return (Next() >> 11) * (1.0 / (1ul << 53));

何故素直に Next() * (0.5 / (1ul << 63)) としないのかというと、乗算の前に Next() が double にキャストされて結局 53 bit 精度になってしまうためです。

範囲加工における注意 - 最大値を含む可能性

Next() には範囲を指定するオーバーロードがありますが、 NextDouble() にはありません。 MSDN を見ると、以下の式で手動変換するとよい、とあります。

NextDouble() * (maxValue - minValue) + minValue

このコードには注意すべき点があります。 NextDouble() は 0 <= x < 1 なので、この式も minValue <= x < maxValue となりそうですが、 minValue の絶対値が大きく maxValue - minValue が相対的にかなり小さい場合などに x == maxValue となる場合があります。具体例としては (987654321, 987654444) が挙げられます。余談ですが、Java の java.util.Random#doubles(double, double) では、このような場合に Math.BitDecrement() 相当のメソッドを使って 1 つだけ小さくすることで回避しているようです (実装)。

通常はあまり気にしなくても良いかと思いますが、 x == maxValue になるとゼロ除算や予期しない ∞ ・ NaN が発生しうる場合 (Math.Log() など) には注意が必要です。

`NextBytes(byte[] buffer), NextBytes(Span<byte> buffer)`

byte[] または Span<byte> 全域をランダムな値 ( 0x00 <= x <= 0xff ) で埋めます。 Span<byte> のほうは .NET Standard 2.1 から使えます。

等価な実装を示します。処理的にはどちらも同様に Next() の下位 8 ビットを使用して埋めていきます。

for (int i = 0; i < buffer.Length; i++)
    buffer[i] = (byte)(Next() & 0xff);

`0xff` が生成される確率が低い

さて、何度か述べたように Next() は $2^ {31} - 1$ 通りなので、 Next() & 0xff (言い換えれば Next() % 256) は均等になりません。 0xff が 8388607 / 2147483647 、それ以外はそれぞれ 8388608 / 2147483647 の確率となり、 0xff が出現する確率がわずかに低くなります。

`Next()` 1 回あたり 1 byte しか利用しない非効率な実装

本来 4 byte に近い情報量のある Next() 1 回あたり 1 byte 分しか生成しない、とても効率の悪い実装となっています。 Next() の値域問題もあるので 4 byte フルに使うわけにはいきませんが、少なくとも 3 byte 分は使えるので 3 倍近く速くできそうな気がします。

外部実装・その他の問題

以上で System.Random に実装されているメソッドの紹介は終わりです。あとは MSDN などを見ながら、さらなる重箱の隅をつついてきます。

スレッドセーフではない

System.Random はスレッドセーフではありません。乱数生成のたびに内部状態を更新する必要があるので、それはそうです。 MSDN のマルチスレッド処理のサンプルを見ると、乱数を取得する箇所を lock ステートメントで囲って対応しています。

lock で囲む以外の対応策としては、スレッドごとに System.Random インスタンスを生成する手法があります。無理にロックしなくていいのでこちらのほうが速くなりそうな気がします。 (試せてはいませんが……)

ただ、前述したように初期状態のパターンが $2 ^ {31}$ に限定される問題 (生成する乱数列のバリエーションが少ない、最悪衝突する可能性) があったり、.NET Framework ならより深刻なシードが同一になる問題があったりするので、難しいところがあります。 xoroshiro128+ などの jump() や、 java.util.SplittableRandom の split() のようなものをサポートしていればこの辺りが解決できるのですが、残念ながら System.Random では非対応です。

再現が難しい / シリアライズできない

System.Random では、同じ乱数列を再現したい場合 new Random(int Seed) を使用することになります。しかし難点がいくつかあります:

内部状態の情報量に対して、初期状態がしかない
- シードだけを保存する場合、とりうる状態 (→出力される乱数列) がかなり制限される
途中から再開することができない
- 例えば、乱数を $2^ {30}$ 個消費した実験の続きをしたい場合、もう一度 $2^ {30}$ 個消費しなければならない

内部状態の保存 (シリアライズ) ができれば簡単に途中から再開できるようになりますが、 System.Random はそのままではシリアライズできません。内部状態は private フィールドで、属性も特についていないためです。 protected なら継承すれば合法的に触れたかもしれませんが…

リフレクションを使えばできないことはないですが、ちょっと面倒です。保存すべきフィールドは int[] _seedArray, int _inext, int _inexp の 3 つです。以下に状態を読み書きするサンプルを示します。テストのために内部状態を適当に書き換えていますが、実際に保存用途に使う場合はスキップしてお好みの入出力コードを書いてください。ただ private フィールドなので外部アクセスは本来想定外の操作であり、将来的な動作は一切保証されません。

var rng = new Random();

var bindingFlag = BindingFlags.NonPublic | BindingFlags.Instance;
var stateField = typeof(Random).GetField("_seedArray", bindingFlag);
var inextField = typeof(Random).GetField("_inext", bindingFlag);
var inextpField = typeof(Random).GetField("_inextp", bindingFlag);

// 内部状態からの読み込み
var state = stateField.GetValue(rng) as int[];      // int[56]
var inext = (int)inextField.GetValue(rng);
var inextp = (int)inextpField.GetValue(rng);

// 書き込みテスト用(次の出力で 0 が出るようにする + ラグ指定修正)
state[2] = 12345;
state[33] = 12345;
inext = 1;
inextp = 32;

// 内部状態への書き込み
stateField.SetValue(rng, state);
inextField.SetValue(rng, inext);
inextpField.SetValue(rng, inextp);

Console.WriteLine(rng.Next());      // `0`

ところで、内部状態全体の保存が面倒だからと言って、シード値だけを保存して乱数のセーブポイントを通るたびに (頻繁に) new Random(seed) しなおすような実装はくれぐれも行わないようにしてください。繰り返しになりますが初期状態は $2 ^ {31}$ パターンしかないので、出力列が著しく限定され、最悪の場合意図せず同一の乱数列を出力してしまう可能性があります。

拡張性

継承による実装の拡張

MSDN を見ると、 System.Random を継承して別の擬似乱数生成器を実装したり、NextBytes(byte[] bytes, int min, int max) などの追加メソッドを生やしたりする手法が紹介されています。

しかし、継承した場合もれなく System.Random の内部状態 280 byte がついてきます (実測値。実装によって変わるかもしれません) 。もし別の擬似乱数生成器を実装するなら無駄になってしまいます。また、Sample() メソッドを上書きすれば大体 OK 、といったことが書かれていますが、 double ベースの計算になるので上述した問題が生じます。といってもすべての public メソッドが virtual なので、すべて自前実装で置き換えてしまえば問題はありません。

アルゴリズムを差し替えたり出力関数を柔軟に追加したりすることを考えると、 interface IRandom を定義しておいて、出力関数などは拡張メソッドにする (今なら interface のデフォルト実装でしょうか？) 手法が思いついたりしますが、 System.Random の実装当時 (.NET Framework 1.1 → C# 1.2) には拡張メソッドが存在しないのでダメです。歴史の重みです。

いくつかの擬似乱数生成器を実装している Math.NET Numerics を覗いてみると、擬似乱数生成器側は class RandomSource を基底として遷移関数と基礎的な出力関数を実装し、複雑な変換関数 (正規分布など) の実装は class Normal といった別クラスに分離して new Normal(new Xoshiro256StarStar()).Sample() といった感じで利用できるようにしているようです。これが綺麗な気がします。

各種分布への変換

正規分布への変換

上の項で分布の話が出たので、一様分布以外では多分最もメジャーな正規分布への変換についても触れておきます。

Java には java.util.Random#NextGaussian がありますが、我らが System.Random にはもちろん実装されていないので、自力で対応する必要があります。

ざっくり Polar Method で実装すると以下のようになります。

/// <summary>
/// 平均 0, 標準偏差 1 の正規分布に従う独立な乱数のペアを取得します
/// </summary>
public (double x, double y) NextGaussian()
{
    double u, v, s;
    do
    {
        u = random.NextDouble() * 2 - 1;
        v = random.NextDouble() * 2 - 1;
        s = u * u + v * v;
    } while (s >= 1 || s == 0);

    s = Math.Sqrt(-2 * Math.Log(s) / s);
    return (u * s, v * s);
}

x, y は独立なので、どちらを使っても・ペアで使っても大丈夫です。1 つだけ要る場合は単に捨てればよいです。もし平均と標準偏差を変えたければ returnValue * stdev + mean としてください。

正規分布への変換には Box-Muller Transform もありますが、Polar Method のほうが若干高速です。雑にベンチマークを取ったところ、手元の環境では Polar Method が 44.90 ± 1.041 ns 、Box-Muller Transform が 56.32 ± 0.702 ns (± は標準偏差) でした。 Box-Muller Transform の微妙な利点としては、工夫すると消費する乱数が 2 個固定になる点が挙げられます。また、より高速な実装手法として Ziggurat algorithm がありますが、テーブルが必要だったり実装が大変だったりするのでここでは取り上げません。大量に正規分布乱数が必要であれば検討するとよいと思います。

その他の分布への変換

Math.NET Numerics を活用するとよいと思います。 (丸投げ)

数学的な確率分布以外では、円|球の中|外周にランダムに配置する計算が (特に Unity で) よく使われます。こちらの説明が分かりやすいです。

シャッフル

MSDN のサンプル実装は非効率

コレクションの要素の順序をランダムに入れ替える「シャッフル」について検討します。 System.Random には組み込みのシャッフル関数は存在しません。ただ、 MSDN にはカードのシャッフルのサンプル実装があります。

var deck = new Card[52] { ... };

// シャッフル用インデックス
var order = new double[deck.Length];
for (int i = 0; i < order.Length; i++)
    order = random.NextDouble();

// order をキーとして deck をソート
Array.Sort(order, deck);

この手法には何点か問題があります:

NextDouble() の出力値が同じ要素が存在した (衝突した) 場合の動作が不定です。
- MSDN の Array.Sort を見た限りではイントロソート (不安定) のようですので、衝突した場合どちらに偏るかは場合によります。
  - ちなみに安定ソート ( Enumerable.OrderBy ) なら確実に偏ります。元々先頭に近いほうが必ず前に来ます。
- 直感的には奇跡でも起こらない限りあり得ないのでは、と思いそうですが、誕生日のパラドックスより 54562 個程度の要素に対して実行すると概ね 1/2 の確率でどれかが衝突します。
時間的に非効率です。一般にソートの計算量は $O(n \log n)$ ですが、より効率的に $O(n)$ でシャッフルする手法が存在します。
空間的に非効率です。同じ要素数の double[] を確保する必要があります。

素直に Fisher-Yates シャッフルを実装しましょう。例では直書きしましたが、 IList<T> の拡張メソッドにしたりすると便利です。

var deck = new Card[52] { ... };

for (int i = deck.Length - 1; i > 0; i--)
{
    int r = rand.Next(i + 1);
    (deck[i], deck[r]) = (deck[r], deck[i]);
}

副作用をなくして IEnumerable<T> に対応する場合は、取り出し版のアルゴリズムで 0 ～ n - 1 の連番をシャッフルした配列を作成して、 source.ElementAt(randomArray[i]) といった感じで参照する手法が考えられます。

余談: ランダム値のソートによるシャッフルの注意点

話はそれますが、ランダムな値をキーとしてソートする場合、横着して以下のように書くと例外 (ArgumentException など) がスローされる場合があります。

// DANGER!
Array.Sort(deck, (_, _) => random.Next(-1000, 1000));

そもそもソートは値を一定の順番に並べるためのものなので、比較するたびに大小が変わるような一貫性のない操作を行うと破綻してしまうためです。しかも性質が悪いのが「確実に例外がスローされるわけではない」点で、初回は成功したからといって油断していると後で刺されたりします。

爆発するかどうかはソートの形式によります。 (a, b) => Next() のように 2 引数を取って比較するもの (Comparison<T> や IComparer<T> をとるものなど) は危険で、ランダムに例外が投げられます。対して、 a => Next() のように 1 引数をキーとして取るもの ( Enumerable.OrderBy(Func<TSource, TKey>) など) は、問題ないこともあります。内部実装として、メソッドを 1 回評価して配列などに格納 → デフォルトの比較関数でソート、というようになっていれば、比較自体は一貫して行えるため問題ありません。

乱数性テスト

出力列の品質、言い換えれば「出力列が乱数らしい振る舞いをしているか」を調べてみます。遷移・出力関数の各所に問題があるのは今まで述べたとおりですが、テストを通しても検出できることを示す、という位置づけにします。

「テスト」は、出力された乱数列に統計的検定や構造解析を行うことで、何らかの乱数らしからぬ構造が見出せるか、を調べるシステムをいいます。「良い乱数であることを示す」よりは、「特定条件下で明らかに悪いことを示す」ようなイメージです。ただ、たくさんのテストを実施して問題が検出されなければ、品質が良い (真の乱数列に近い性質を持つ) とみなせそうです。 *6

PractRand のテストで速やかに失敗する

強力で汎用的な乱数性テストツールとしては PractRand が有力です。自動で複数種のテストをかけることができ、検出力が高く誤検知 (真の乱数を入力してもテストに失敗すること) もほぼありません。私は PractRand でデフォルトの最大値である 32 TB の出力を検定し、 FAIL となるテストが 1 つも存在しないことを前提として擬似乱数の設計・選定を行っています。

今回は、より多くのテストを行う設定の -te 1 -tf 2 -tlmaxonly を指定しました。出力には、 Next() では 32 bit 全域の出力ができないため NextBytes() 相当の実装を使用しました。大抵のテストツールでは基本的に 32 or 64 bit 全域を出力するメソッドがあることを前提としているので、そのままではテストにかけられないこと自体がとても厳しいです。というのも、この変換がテスト結果に影響を及ぼす可能性があるので、妥当かどうか微妙なところがあるのです…

結果を以下に示します。疑わしいテスト結果だけが表示されており、成功したテストは ...and から始まる行にまとめて書いてあります。結果は Evaluation のところに注目してください。雰囲気としては以下のような感じです。

usual : まれによくある
- これはあまり問題になりません。別のシードでは起きなかったりする微妙なエラーです
suspicious : だいぶ怪しい
- 大抵の場合次の length で FAIL します
FAIL : 確実にアウト
- 明らかに何らかの欠陥があります

テスト結果 (長いので折り畳み - クリックすると開きます)

RNG_test using PractRand version 0.94
RNG = .netrandom, seed = 0xb2540eef
test set = expanded, folding = extra

rng=.netrandom, seed=0xb2540eef
length= 32 megabytes (2^25 bytes), time= 2.7 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/8]BCFN(0+1,13-5,T)          R= +20.1  p =  4.8e-8   very suspicious
  ...and 936 test result(s) without anomalies

rng=.netrandom, seed=0xb2540eef
length= 64 megabytes (2^26 bytes), time= 14.9 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/8]BCFN(0+1,13-5,T)          R= +41.1  p =  2.9e-16    FAIL !
  [Low1/8]DC6-6x2Bytes-1            R=  +6.5  p =  4.7e-4   unusual
  ...and 1006 test result(s) without anomalies

rng=.netrandom, seed=0xb2540eef
length= 128 megabytes (2^27 bytes), time= 30.8 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/8]BCFN(0+1,13-4,T)          R= +79.5  p =  1.0e-34    FAIL !!!
  [Low1/8]DC6-6x2Bytes-1            R=  +8.7  p =  3.4e-5   mildly suspicious
  [Low1/8]DC6-5x4Bytes-1            R=  +8.9  p =  1.5e-5   mildly suspicious
  ...and 1078 test result(s) without anomalies

rng=.netrandom, seed=0xb2540eef
length= 256 megabytes (2^28 bytes), time= 48.0 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/8]BCFN(0+0,13-3,T)          R= +44.0  p =  1.2e-20    FAIL !!
  [Low1/8]BCFN(0+1,13-3,T)          R=+129.4  p =  4.8e-61    FAIL !!!!
  [Low1/8]DC6-6x2Bytes-1            R= +14.5  p =  1.1e-7   very suspicious
  [Low1/8]DC6-5x4Bytes-1            R= +20.1  p =  5.5e-13    FAIL
  [Low1/32]FPF-14+6/16:cross        R=  +5.7  p =  4.8e-5   unusual
  ...and 1146 test result(s) without anomalies

rng=.netrandom, seed=0xb2540eef
length= 512 megabytes (2^29 bytes), time= 68.1 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/8]BCFN(0+0,13-3,T)          R= +91.4  p =  4.8e-43    FAIL !!!
  [Low1/8]BCFN(0+1,13-3,T)          R=+257.6  p =  1.0e-121   FAIL !!!!!
  [Low1/8]DC6-6x2Bytes-1            R= +30.8  p =  4.1e-20    FAIL !!
  [Low1/8]DC6-5x4Bytes-1            R= +36.5  p =  2.3e-24    FAIL !!
  ...and 1216 test result(s) without anomalies

rng=.netrandom, seed=0xb2540eef
length= 1 gigabyte (2^30 bytes), time= 96.9 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(0+3,13-1,T)                  R= +11.4  p =  1.4e-5   mildly suspicious
  BCFN(0+4,13-1,T)                  R= +13.0  p =  1.7e-6   suspicious
  [Low1/8]BCFN(0+0,13-2,T)          R=+388.0  p =  6.9e-198   FAIL !!!!!!
  [Low1/8]BCFN(0+1,13-2,T)          R=+465.4  p =  1.9e-237   FAIL !!!!!!
  [Low1/8]BCFN(0+2,13-3,T)          R= +18.9  p =  9.2e-9   very suspicious
  [Low1/8]DC6-6x2Bytes-1            R= +57.2  p =  5.1e-32    FAIL !!!
  [Low1/8]DC6-5x4Bytes-1            R= +62.9  p =  1.5e-35    FAIL !!!
  [Low4/16]BCFN(0+2,13-2,T)         R= +26.9  p =  2.5e-13    FAIL
  ...and 1286 test result(s) without anomalies

rng=.netrandom, seed=0xb2540eef
length= 2 gigabytes (2^31 bytes), time= 146 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(0+3,13-0,T)                  R= +27.2  p =  4.7e-14    FAIL
  BCFN(0+4,13-1,T)                  R= +28.3  p =  1.0e-14    FAIL
  [Low1/8]BCFN(0+0,13-1,T)          R= +1303  p =  2.3e-701   FAIL !!!!!!!
  [Low1/8]BCFN(0+1,13-1,T)          R=+819.6  p =  8.3e-441   FAIL !!!!!!!
  [Low1/8]BCFN(0+2,13-2,T)          R= +47.7  p =  5.7e-24    FAIL !!
  [Low1/8]DC6-6x2Bytes-1            R=+110.9  p =  1.1e-52    FAIL !!!!
  [Low1/8]DC6-5x4Bytes-1            R=+117.3  p =  2.9e-74    FAIL !!!!
  [Low4/16]BCFN(0+2,13-1,T)         R= +42.0  p =  4.8e-22    FAIL !!
  [Low4/16]BCFN(0+3,13-1,T)         R= +13.9  p =  5.8e-7   suspicious
  ...and 1359 test result(s) without anomalies

rng=.netrandom, seed=0xb2540eef
length= 4 gigabytes (2^32 bytes), time= 241 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(0+3,13-0,T)                  R= +57.5  p =  2.8e-30    FAIL !!!
  BCFN(0+4,13-0,T)                  R= +50.5  p =  1.6e-26    FAIL !!
  [Low1/8]BCFN(0+0,13-1,T)          R= +2589  p =  1e-1393    FAIL !!!!!!!!
  [Low1/8]BCFN(0+1,13-1,T)          R= +1659  p =  9.2e-893   FAIL !!!!!!!
  [Low1/8]BCFN(0+2,13-1,T)          R= +82.8  p =  4.8e-44    FAIL !!!
  [Low1/8]BCFN(0+4,13-2,T)          R= +10.7  p =  4.6e-5   unusual
  [Low1/8]DC6-6x2Bytes-1            R=+204.2  p =  6.8e-109   FAIL !!!!!
  [Low1/8]DC6-5x4Bytes-1            R=+219.3  p =  1.7e-100   FAIL !!!!!
  [Low1/32]BCFN(0+6,13-4,T)         R= +12.2  p =  2.9e-5   unusual
  [Low4/16]BCFN(0+2,13-1,T)         R= +89.6  p =  1.0e-47    FAIL !!!
  [Low4/16]BCFN(0+3,13-1,T)         R= +24.5  p =  1.1e-12    FAIL
  ...and 1433 test result(s) without anomalies

rng=.netrandom, seed=0xb2540eef
length= 8 gigabytes (2^33 bytes), time= 497 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(0+3,13-0,T)                  R=+115.8  p =  2.0e-61    FAIL !!!!
  BCFN(0+4,13-0,T)                  R= +88.9  p =  4.5e-47    FAIL !!!
  [Low1/8]BCFN(0+0,13-0,T)          R= +5800  p =  9e-3101    FAIL !!!!!!!!
  [Low1/8]BCFN(0+1,13-0,T)          R= +2740  p =  8e-1465    FAIL !!!!!!!!
  [Low1/8]BCFN(0+2,13-1,T)          R=+169.1  p =  1.7e-90    FAIL !!!!!
  [Low1/8]BCFN(0+4,13-1,T)          R= +15.6  p =  7.9e-8   very suspicious
  [Low1/8]DC6-6x2Bytes-1            R=+386.9  p =  1.0e-179   FAIL !!!!!!
  [Low1/8]DC6-5x4Bytes-1            R=+415.2  p =  1.1e-253   FAIL !!!!!!
  [Low4/16]BCFN(0+2,13-0,T)         R=+156.1  p =  5.4e-83    FAIL !!!!
  [Low4/16]BCFN(0+3,13-0,T)         R= +34.5  p =  5.3e-18    FAIL !
  ...and 1530 test result(s) without anomalies

rng=.netrandom, seed=0xb2540eef
length= 16 gigabytes (2^34 bytes), time= 976 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(0+3,13-0,T)                  R=+234.3  p =  8.5e-125   FAIL !!!!!
  BCFN(0+4,13-0,T)                  R=+172.1  p =  1.4e-91    FAIL !!!!!
  BCFN(0+6,13-0,T)                  R= +12.4  p =  3.6e-6   unusual
  [Low1/8]BCFN(0+0,13-0,T)          R=+11611  p =  1e-6207    FAIL !!!!!!!!
  [Low1/8]BCFN(0+1,13-0,T)          R= +5513  p =  2e-2947    FAIL !!!!!!!!
  [Low1/8]BCFN(0+2,13-0,T)          R=+273.9  p =  5.6e-146   FAIL !!!!!
  [Low1/8]BCFN(0+3,13-0,T)          R=  +9.6  p =  1.1e-4   unusual
  [Low1/8]BCFN(0+4,13-1,T)          R= +22.3  p =  1.7e-11   VERY SUSPICIOUS
  [Low1/8]DC6-6x2Bytes-1            R=+735.4  p =  1.2e-265   FAIL !!!!!!
  [Low1/8]DC6-5x4Bytes-1            R=+780.1  p =  6.6e-429   FAIL !!!!!!!
  [Low4/16]BCFN(0+2,13-0,T)         R=+342.4  p =  1.2e-182   FAIL !!!!!!
  [Low4/16]BCFN(0+3,13-0,T)         R= +70.4  p =  3.7e-37    FAIL !!!
  ...and 1625 test result(s) without anomalies

64 MB まで検定した時点で BCFN テストに、 256 MB から DC6 テストに FAIL しました。ほぼ瞬殺です。無事失敗したのと時間がかかるのとで 16 GB で中断しました。

参考として他の擬似乱数生成器はどうなのかというと、有名どころとしては線形合同法 (LCG) ・ Mersenne Twister ・ Xorshift ・ xoroshiro128+ は FAIL していて、PCG ・ xoshiro256** ・splitmix (≒ java.util.SplittableRandom) は 32 TB でもパスしています。詳しくはこちらの "Failed Test" 列を参照してください。 hwd 以外は PractRand のテストです。

Hamming-weight dependencies

次に、xoroshiro/xoshiro の作者が作った Hamming-weight dependencies テスト (略称 hwd) *7 を試してみます。これは TinyMT において BRank 系以外のテストで初めて問題を検出できた実績のあるテストです。こちらは 1 PB (ペタバイト！) テストして p < 1e-20 にならなければパスしたといえます。

こちらでは試しに Next() 相当の実装を使用しました。また、HWD_BITS=32 (出力のワードサイズが 32 bit) としました。

結果の一部を以下に示します。本項執筆時点では 25 TB まで検定して p = 0.761 なので、意外なことに問題は検出されていなさそうです。最後までやると 2-3 週間ぐらいかかるのでこの辺りで許してください…

mix3 extreme = 1.51920 (sig = 00000100) weight 1 (16), p-value = 0.89
mix3 extreme = 2.67035 (sig = 00010010) weight 2 (112), p-value = 0.573
mix3 extreme = 3.41468 (sig = 00101200) weight 3 (448), p-value = 0.249
mix3 extreme = 3.23865 (sig = 12002010) weight 4 (1120), p-value = 0.74
mix3 extreme = 3.64975 (sig = 12222100) weight >=5 (4864), p-value = 0.721
bits per word = 32 (analyzing bits); min category p-value = 0.249

processed 2.5e+13 bytes in 4.14e+04 seconds (0.604 GB/s, 2.174 TB/h). Sun Jan  3 00:05:51 2021

p = 0.761
------

ジャンプ

ジャンプ機能がない

擬似乱数生成器によっては、「ジャンプ」機能を備えているものがあります。具体例を挙げると、 xoroshiro128+ では $2 ^ {64}$ 回の next() 呼び出しと等価な操作を速やかに行うことができる jump() 関数が用意されています。この機能は並列実行などで複数の乱数列が必要な場合に便利で、 new Random() ではなく var child = original.Jump(); のようにしてインスタンスを生成することで、先の例でいえば $2 ^ {64}$ 回 next() を呼び出すまでは重複しない保証のある乱数列を得ることができます。

さて System.Random ではどうなのかというと、少なくとも用意はされていません。設計するのもなかなか難しそうな気がします。 $\mathrm{GF}(2 ^ {31} - 1)$ 上での多項式計算を頑張ればできるかもしれませんが、 Next() の項で述べたように原始か分からなかったり、そもそも計算がよくわからなかったりするので私は何も分かりません。

余談: 「正しく」実装されていた場合のジャンプの設計

注記: 例によって System.Random には直接適用できません。

また机上の空論になってしまいますが、もしラグ指定が正しく法も 2 のべき乗である $k = 24, m = 2 ^ {31}$ だったのならば、限定的ながら可能です。

先に述べたように、 $m = 2 ^ n$ ならば最下位ビットだけを見ると LFSR として扱うことができます。 LFSR でのジャンプ手法を用いることで、「少なくとも $s$ ステップ以上の距離がある状態」を作り出すことが可能です。「少なくとも」というのは最下位ビット以外については制御できないためで、実際の距離は $(2 ^ {55} - 1)i + s \; (i \ge 0)$ という感じになると思います、たぶん…

LFSR のジャンプは、 $j(x) = x ^ s \pmod{f(x)}$ を事前に計算しておいて ( $f(x)$ は遷移関数の特性多項式です) 、実行時に $j(x)$ の $x$ に現在の状態を代入することで行います。例えば、 $2 ^ {54}$ ステップのジャンプ多項式 $j _ {2 ^ {54}}(x)$ は、 xoroshiro128+ の JUMP[] と同じフォーマットなら 0x0010010010200200 として表せます。あとは xoroshiro128+ の jump() と同じ雰囲気で実装すれば少なくとも $2 ^ {54}$ ステップ以上の距離がある状態を作り出すことができます。

ただ、変わるのは最下位ビットだけなので、この手法だけでは出力自体はしばらく元の出力列とほとんど同じになることが予想されます。難儀です。とっても雑に見積もると、キャリーが 1 bit 上に伝播するのに 1 周かかる (= 55 回) x 31 bit なので 1705 回ぐらい乱数を読み飛ばすことで目に見える相関はなくなりそうな気がします。 (気がするだけで確たる根拠はないです…) もちろん重い処理なので手軽ではないですが…

「ガチャシミュレーション」における異常な振る舞い

本項の検討は、 dotnet/runtime の Issue #40490 およびオリジナルの StackOverflow への投稿に基づきます。ここまでの問題は誤差レベルのものが多かったですが、これは実用的なユースケースで目に見える問題が生じます。

System.Random を用いて、単発で確率 $p$ で当たるガチャを当たるまで引く (!) とき、最初に当たるまでに引いた回数 $n$ はどんな分布になるかのシミュレーションをしてみましょう。数学的には幾何分布というらしいです。

以下のように実装してみます。ガチャで当たるまでの回数の分布を、100 万回ぐらいシミュレーションしてみます。

var rand = new Random();

double p = 0.05;        // 当たる確率
var distribution = new int[256];        // (i + 1) 回目で初めて当たりを引いた回数

for (int i = 0; i < 1 << 20; i++)
{
    int done = 0;       // 引いた回数(-1)
    while (rand.NextDouble() >= p)      // 当たるまで回す!!
        done++;

    distribution[Math.Min(done, distribution.Length - 1)]++;
}

// 出力
for (int i = 0; i < distribution.Length; i++)
    Console.WriteLine($"{i + 1,3}: {distribution[i]}");

結果をグラフに書くと以下のようになります。

f:id:andantesoft:20201230224030p:plain

55 (回目に引いたときに初めて当たった回数) に不自然なピークがあるのが分かります。拡大して見てみましょう。ここで、追加の「理論値」は幾何分布の確率質量関数から求めています。

f:id:andantesoft:20201230224036p:plain

あるべき数の大体 1/2 ぐらいになっていそうです。なお、この現象は確率 $p$ に依存せず発生するようです。

原因を考えてみましょう。遷移関数についての今までの説明から、55 回目の遷移・出力は $x _ {55} = x _ {0} - x _ {34} \pmod{ m}$ と表せます。確率 $p$ は簡単のため整数で定義することとし、 $1 \le p \lt m$ として $x _ i \lt p$ のときに「成功」とします。

まず、式中の $x _ 0, x _ {34}$ がとりうる値の範囲を考えます。 $x _ {34}$ については、「55 回目に初めて成功した」すなわち「54 回目まではすべて失敗した」前提条件から、 $x _ {34} \ge p$ です。 $x _ 0$ は、現在の 55 回前ですから「直前の試行の最後の出力」を指します。 (一番最初の試行でない限り) 最後は成功で終わっているので、 $x _ {0} \lt p$ です。

以上の条件下で $x _ {55} \lt p$ を満たすには、 $x _ {0} - x _ {34} + m \lt p$ である必要があります。ここで $m$ を足したのは mod を打ち消すためです ( $x _ {0}, x _ {34}$ の値域から、 $x _ {0} - x _ {34}$ は必ず負値になります) 。この 3 つの関係式を満たす $x _ {0}, x _ {34}$ ペアの個数は $p(p-1) / 2$ 個となります。 $x _ 0 \lt p, x _ {34} \ge p$ の範囲条件を満たすペアの総数 (上記関係式は満たさなくてもよい場合) は $p(m - p)$ 個ですから、この範囲内で成功する確率は $(p(p-1)/2)/(p(m-p)) = (p-1) / 2(m - p)$ となります。本来の確率は $p/m$ ですから、 $p$ がある程度小さければ本来の確率の大体 1/2 ぐらいになり、実験と一致しそうです。

イメージしやすいように図に描いてみましょう。 $x _ {0}, x _ {34}$ 全域 (グラフ全体) に対して、 $x _ {0} \lt p, x _ {34} \ge p$ を満たすのは赤い部分です。色が濃い部分が成功、薄い部分は失敗を表します。 (色が濃い部分 / グラフ全体) に対して、 (赤色の濃い部分 / 赤色全体) の割合が半分ぐらいになっているのが分かるかと思います。

f:id:andantesoft:20201230224120p:plain

さて、原因は分かったので対策を考えてみましょう。直前の試行の最後の出力を参照して $x _ 0 \lt p$ となっている、すなわち直前の試行の影響を受けているのがよくないので、例えば試行が終わった直後にランダムな個数だけ乱数を消費してみるのはどうでしょうか。あまり行儀は良くないですがサンプルということで許してください…

// 抜粋
for (int i = 0; i < 1 << 20; i++)
{
    int done = 0;       // 引いた回数(-1)
    while (rand.NextDouble() >= p)      // 当たるまで回す!!
        done++;

    distribution[Math.Min(done, distribution.Length - 1)]++;

    // 追加コード: ランダムに 0 - 255 個消費する
    int skipAmount = Guid.NewGuid().ToByteArray()[15];
    for (int k = 0; k < skipAmount; k++)
        rand.Next();
}

結果をグラフに書くと以下のようになり、本項の現象がみられなくなっています。

f:id:andantesoft:20201230224033p:plain

一応補足ですが、乱数の消費回数を決定するのに rand.NextInt(256) を使わなかったのには理由があります。自分自身の乱数を使用すると乱数列が重複する可能性が上がってしまうためです。説明を簡単にするために 1 byte のカウンタを擬似乱数生成器と言い張ることにしましょう:

int rand() => (x = (x + 1) % 256);

ここで、 x == 128 のときは rand() => 129 となるので 129 回消費して x == 2 になります。また、 x == 0 のときは rand() => 1 となり 1 回消費して x == 2 になります。これらより、別の内部状態からランダムスキップによって同じ内部状態になってしまい、以降の出力列が重複してしまうことが分かります。 rand() とは関連性のない別系列の乱数 (ここでは Guid.NewGuid() の最後のバイト) を用いることで、この問題を回避している、というわけです。

話を戻してまとめに入ります。遷移・出力関数の実装がシンプルなため、「内部での状態更新処理」と「外部での乱数の利用処理」が嚙み合ってしまった場合このように問題が表出します。とはいえ「内部処理を把握したうえで注意して書け」というのは現実的ではありません。強いて対策を挙げるとすれば、別の擬似乱数生成器を採用するなどでしょうか……？

乱数列の過去と未来を知る

未来の予測 (内部状態復元攻撃)

出力から内部状態を復元して、将来の乱数の予想を試みます。

一番簡単な Next() について検討します。 Next() では内部状態をそのまま返しているので、連続する 55 個の出力列を記録できれば、それがそのまま内部状態 _seedArray になります。あとは _inext = 0; _inextp = 21; としてインスタンスに設定すれば出力列が再現できます。

// コピー元
var rand = new Random();

// 出力の記録 (内部状態に合わせるため [0] は飛ばす)
int[] output = new int[56];
for (int i = 1; i < output.Length; i++)
    output[i] = rand.Next();

// クローンの生成・設定
var clone = new Random();
SetInternalState(clone, output, 0, 21);

// 検証
for (int i = 0; i < 256; i++)
    Debug.Assert(rand.Next() == clone.Next());

// ---

// リフレクションで内部状態を設定する
static void SetInternalState(Random rng, int[] state, int inext, int inextp)
{
    var bindingFlag = BindingFlags.NonPublic | BindingFlags.Instance;
    var stateField = typeof(Random).GetField("_seedArray", bindingFlag);
    var inextField = typeof(Random).GetField("_inext", bindingFlag);
    var inextpField = typeof(Random).GetField("_inextp", bindingFlag);

    stateField.SetValue(rng, state);
    inextField.SetValue(rng, inext);
    inextpField.SetValue(rng, inextp);
}

また、もし内部状態全域が分からなくとも、遷移式 $x _ {i} = x _ {i-55} - x _ {i-34} \pmod{2^ {31} - 1}$ より 55 回前と 34 回前の出力を得ることによって、次に出力される値を求めることができます。

NextDouble() の場合は、 (int)Math.Round(value * int.MaxValue) などで整数に逆変換すれば、 Next() と同じ手法が適用できます。

その他の範囲に加工するもの (Next(int maxValue), NextBytes など) を情報源として内部状態の完全な復元を行う手法については、パッとは思いつきません。Lagged Fibonacci 法に対して適用できるアルゴリズムがあれば、それが使えるかもしれません。

別の手法としては、初期状態が高々 $2^ {31}$ パターンしかないことから、同じ乱数列を出力する系列を $2^ {31}$ パターンの中から力ずくで探索する手法が挙げられます。初期化してからそれほど使用されていない (Next() 呼び出し回数が少ない) と推測される場合に特に有効です。また、 .NET Framework では初期化は起動時間ベースなので、全空間を探索しなくともある程度絞り込むことができます。例えば、初期化タイミングが 1 分オーダーでも分かっているなら、 60000 (ms) 個分試せばどれかは当たるでしょう。

過去の状態・出力列の逆算

Next() の逆演算 (直前の状態に戻す演算) を考えてみましょう。これが分かると、ある時点での内部状態が判明した際、過去の状態 (乱数列) の逆算ができます。難しいことは何もなく、減算を加算にしてインデックスを戻す処理を書くだけです:

uint prev = (uint)_seedArray[_inext] + (uint)_seedArray[_inextp];
if (prev >= int.MaxValue)
    prev -= int.MaxValue;

_seedArray[_inext] = (int)prev;

if (--_inext <= 0) _inext += 55;
if (--_inextp <= 0) _inextp += 55;

均等分布次元

System.Random の「均等分布次元」について考えてみましょう。よく Mersenne Twister の説明で「623 次元に均等分布する」と言われているアレです。

前提: 均等分布次元とは

そもそも均等分布次元とは何かというと、雑に説明すると「要素数 n の配列を連続する乱数で埋めたとき、全てのパターンが出現しうる最大の n」です。 623 次元に均等分布する Mersenne Twister では、 int[623] の配列を連続する Next() で埋めるとき、 int[623] で表現できるありとあらゆるパターンが出現しうることが保証されています。

この性質は当たり前に存在するわけではありません。例えば線形合同法は 1 次元均等分布なので、 int[2] ですらごく限られたパターンしか生成できません。より具体的には、以下の線形合同法では [0] = 0 なら [1] = 2531011 以外にはあり得ません。それ以外の 0 から始まるベクトル ({0, 1} など) は絶対に生成されません。線形合同法でランダムな 3 次元の点をプロットすると平面上に並ぶ、というのは有名な話です。

uint lcg(uint x) => x * 214013 + 2531011;

System.Random の均等分布次元

話を戻して、 System.Random ではどうでしょうか。そもそも遷移関数の実装ミスによって周期決定すらおぼつかない状態なので、実際の均等分布次元を求めることは困難です。はい……

ただ、もしも $\mathrm{GF}(2 ^ {31} - 1)$ 上で $x ^ {55} + x ^ {34} + 1$ が原始多項式であり、最長周期を実現できていたなら 55 次元に均等分布します。 (各要素の値域は変わらず $0 \le x \lt 2 ^ {31} - 1$ であることに注意は必要です。)

証明といえるほど厳密ではないですが説明しましょう。最長周期 $(2 ^ {31} - 1) ^ {55} - 1$ を実現できているなら、内部状態は全 0 を除いて全ての表現可能な状態を取ることができます。 (表現可能な状態のパターン数は最長周期と同じ数になります。) なお、全 0 は擬似乱数生成器の構造的にどうしようもないので見なかったことにします。 Mersenne Twister の論文 *8 の k 次元均等分布の定義 (Definition 1.1.) においても "except for the all-zero combination that occurs once less often." と述べられており、例外と考えてよいと思います。

そして、要素数 55 の内部状態と連続する 55 個の出力は一対一に対応します (全単射) 。言い換えれば、内部状態→出力の逆となる出力→内部状態の変換を行えます。具体的に以下のコードを用いて、連続する 55 個の出力から対応する内部状態を求められます。

// note: output.Length == 55, 0 <= output[i] < int.MaxValue
static int[] OutputToState(int[] output)
{
    if (output.Length != 55)
        throw new ArgumentException(nameof(output));

    const int Lag = 34;     // 55 - inext の初期値(21)

    var state = new int[56];

    int index, laggedIndex;       // == inext, inextp

    for (index = 55, laggedIndex = index - Lag;
        index > Lag;
        index--, laggedIndex--)
    {
        state[index] = output[index - 1] + output[laggedIndex - 1];
        if (state[index] < 0)
            state[index] += int.MaxValue;
    }
    for (laggedIndex = 55;
        index > 0;
        index--, laggedIndex--)
    {
        state[index] = output[index - 1] + state[laggedIndex];
        if (state[index] < 0)
            state[index] += int.MaxValue;
    }
    return state;
}

内部状態がすべての可能な値を取ることと、内部状態と連続する出力は一対一対応することから、連続する 55 個の出力もすべての可能な値を取るといえます。したがって、55 次元に均等分布するといえます。

余談: 好きな「乱数」列を出力させる

さて、上の項で内部状態⇔出力列の計算が可能であることを示しました。ということは、欲しい出力列に対応する内部状態を設定することで、55 個までの範囲で好きな値を出力させることができます。

上の OutputToState() メソッドを利用して、文字列を仕込んでみました。実行例を以下に示します。

var rand = new Random(1);
var state = new int[] { 0, 292, 414, 406, 405, 358, 194, 456, 327, 414, 354, 401, 419, 347, 183, 304, 247, 303, 251, 236, 334, 307, 257, 330, 302, 300, 243, 162, 347, 226, 299, 239, 304, 316, 246, 151, 185, 150, 188, 219, 137, 220, 206, 160, 568, 602, 619, 558, 247, 530, 441, 537, 380, 440, 553, 443 };

// リフレクションで _seedArray, _inext, _inextp を設定する
SetInternalState(rand, state, 0, 21);

var randomBytes = new byte[128];
rand.NextBytes(randomBytes);

// randomBytes を ASCII とみなして文字列化
Console.WriteLine(new string(randomBytes.Select(i => (char)i).ToArray()));

// > output:
// > OEEO@aAe?IU?#This message was created by Andante.Shioi-chan kawaii#AsS?oE2uo

# で囲まれているところが仕込んだ文字列です。 (# も含めて計 55 文字ジャストです。) 前述した Prev() を併用すれば、一定時間後に吐き出すような仕込みも可能です。

パフォーマンス

速度

パフォーマンスといえばまずは速度です。とりあえずベンチマークを取ってみましょう。今回は BenchmarkDotNet を使用し、.NET 5 環境で測定しました。

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
Intel Core i7-7700HQ CPU 2.80GHz (Kaby Lake), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.101
  [Host]     : .NET Core 5.0.1 (CoreCLR 5.0.120.57516, CoreFX 5.0.120.57516), X64 RyuJIT
  DefaultJob : .NET Core 5.0.1 (CoreCLR 5.0.120.57516, CoreFX 5.0.120.57516), X64 RyuJIT

せっかくなので、比較対象として拙作 Seiran128 擬似乱数生成器を使います。PractRand 32 TB をパスする品質を持ち、けっこう高速です。また、new() では RNGCryptoServiceProvider ベースの初期化を行ったり、 NextInt(int max), NextInt(int min, int max) では偏りがなくなるように操作を行ったりなど、速度を多少犠牲にしてでも品質を維持するように実装しています (つまり、速度だけ見てチューンするなら改善の余地がある、ということです) 。 Seiran 側の実装はこちらです。

各メソッドについて、処理時間は以下のようになりました。± は標準偏差です。

Method	System.Random [ns]	Seiran [ns]	x Speed
`new()`	1741.159 ± 23.02	120.738 ± 1.079	14.421
`new(401)`	470.529 ± 6.842	8.185 ± 0.087	57.487
`Next()`	9.093 ± 0.113	1.330 ± 0.054	6.837
`Next(401)`	11.748 ± 0.169	3.272 ± 0.039	3.590
`Next(168, 401)`	11.473 ± 0.138	4.567 ± 0.063	2.512
`NextDouble()`	9.734 ± 0.125	2.376 ± 0.034	4.097
`NextBytes(Span<byte>[256])`	2254.480 ± 27.31	90.324 ± 1.177	24.960

雑にグラフにすると以下のようになりました。 (グラフガチ勢に刺されそうです…)

f:id:andantesoft:20210109131436p:plain

Next***() がつぶれているので拡大するとこのようになります。

f:id:andantesoft:20210109131439p:plain

上表を見ると、new Random() が予想以上に遅いです。シード指定のある new Random(401) の 3.7 倍も遅いところを見ると、前述したシードが重複しないようにする処理が思いのほか重いのでしょうか。暗号論的擬似乱数生成器による初期化より遥かに遅いとはいったい… .NET Framework 環境ではほぼ new Random(401) と同じになるとは思いますが、ビルド環境がなかったので試せていません。

Seiran と比べると、出力系メソッドでは 2 ～ 4 倍 (NextBytes は 25 倍ぐらい) 、new では 14 ～ 57 倍 (!) ほど遅いことになります。 Seiran.NextBytes が速いのは、 MemoryMarshal.Cast() を使って直接 ulong の値を書き込んでいる (一度に 8 byte 分書き込める) ためです。C 言語でいうと ((uint64_t *)bytes)[i] = Next(); の処理をしているイメージです。対して Random.NextBytes は 1 byte / 回なので、かなりの差が付きます。

メモリ

消費メモリの観点からも見てみましょう。ゲーム分野などではヒープアロケーションに敏感になっている場合があるので、知っておいて損はないでしょう。

System.Random は、.NET 5 環境において 1 インスタンスあたり 280 byte 消費します。これは Visual Studio の診断ツールで確認しました。加えて、一度でも new Random() を呼べば追加で 560 byte 消費します。これはちょうど 2 インスタンス分で、new Random() の項で述べた ThreadStatic なインスタンスと static なインスタンスによるものと思われます。

ちなみに、Seiran では 1 インスタンスあたり 32 byte で済みます。 (内部状態を配列で持つと 64 byte になります。) 本質的には 16 byte 分なのでワンチャン構造体にできるかもしれませんが、今回はそこまでしませんでした。

おわりに

調べれば調べるほど問題や変な性質が見つかるので、何か楽しくなって調べていたら 1 ヵ月が経っていました。誤差レベルのものもあれば、結構影響のあるものもあります。

「だから System.Random は使うな！！！！」といった強い言葉を使うつもりはないですが、ゲームの内部計算・科学シミュレーションといった繊細な用途に使用する場合は、問題が表出する可能性があるため注意が必要だと思います。特に、再現性が必要な場合は流石にやめておいたほうが良いかと思います (前言撤回) 。問題が起きても後で交換できなくなりますので……

対して、品質を気にする必要がなく、かつ再現性が不要な場合なら雑に使ってもよいかとも思います。ゲームで言えばパーティクルの飛ばし方などでしょうか。いくら品質が低いといえども、全力で偏ったりはしないのである程度の使用なら大丈夫です。また、他では真似できない最強の利点が「標準ライブラリなのでいつでもどこでも簡単に使えること」です。適切に使っていきましょう。

さて、 dis るだけ dis って何もしないのもアレなので、ほぼ上位互換の代替実装を作ってみました。 (NextInt(0) が例外を投げるなど、厳密に互換性はないです。) MIT License で公開します。テストは結構しましたが、何かバグがあったらごめんなさい。

Seiran128 sample implementation in C# (.NET 5)

最後の最後に免責事項です。それなりに調査したつもりではありますが、私は数学徒ではないので数学理論周りに誤りやずれがある可能性はあります。もし何かありましたら優しく指摘していただけると大変助かります。よろしくお願いします。

*1:全 0 などの周期が短い状態も含むため、実用的にはこれより小さくなります

*2:ラグの指定ミスは流石に意図したものではない、と信じているので…

*3: Brent, R. P. (1994). On the periods of generalized Fibonacci recurrences. Mathematics of Computation, 63(207), 389-401.

*4:Aviv Sinai. (2011) Pseudo Random Number Generators in Programming Languages. The Interdisciplinary Center, Herzlia Efi Arazi School of Computer Science.

*5:実際には Next(int minValue, int maxValue) があるためこのような操作はしないと思いますが

*6:厳密には「誤検知」や「テスト自身の妥当性」など若干難しいところはありますが、ここでは大目に見てください。

*7:Blackman, D., & Vigna, S. (2018). Scrambled linear pseudorandom number generators. arXiv preprint arXiv:1805.01407.

*8:Matsumoto, M., & Nishimura, T. (1998). Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation (TOMACS), 8(1), 3-30.

はじめに

JEP 356 の要約

インタフェースの追加

RandomGenerator

StreamableGenerator

SplittableGenerator

JumpableGenerator

LeapableGenerator / ArbitrarilyJumpableGenerator

JumpableGenerator シリーズの注意点

実装例

LXM アルゴリズムについて

LXM ファミリの品質について

速度について

内部状態復元攻撃

その他の改善点

nextDouble(double bound) / nextDouble(double origin, double bound)

nextExponential()

nextGaussian(double mean, double stddev)

RandomGeneratorFactory

余談・リリース以降の更新点について

アルゴリズムの選び方

均等分布性について

exactly equidistributed とは

k-equidistributed とは

おわりに

はじめに

テスト結果が合わない

JDK に報告してみる

バグじゃなかった？

おわりに

はじめに

テストに使える文字(列)

空文字列

空白文字

改行文字

RTL (Right-to-Left)

その他の制御文字・特殊な文字

その環境における制御文字(列)

長い文字列

大きなスペースをとる文字

大きなスペースをとる文字列

スペースをとらない・不可視の文字

複数の表現がある文字 (正規化)

UTF-16 において 2 バイトで表現できない (U+10000 以降の) 文字

フォントに含まれない文字

国と地域の旗の絵文字

外字

最近追加された文字

複数のコードポイントで表現される文字

色がある前提の絵文字・色を付ける絵文字

合字 (リガチャ)

非常に似ている文字

環境に依存して見た目が変わる文字

1 文字あたりのバイト数が大きい文字

不正な文字列・バイト列

余談

幽霊文字

Methematical Alphanumeric Symbols

実際に問題を起こした文字列

ひらがなは 2 バイト文字か？

おわりに

はじめに

発端

プランニング

自機

ステージ

ボス

アイテム

プロモーション

プログラミング

UniTask

初心者向け(?)逆引き

(m 秒後から) n 秒ごとに繰り返したい

一定回数の繰り返し

何回目のループか知りたい (for 文の i が欲しい)

投げっぱなしにする

キャンセル周りについて

DOTween の待機について

まとめ

Input System

`RandomGenerator`

`StreamableGenerator`

`SplittableGenerator`

`JumpableGenerator`

`LeapableGenerator` / `ArbitrarilyJumpableGenerator`

`JumpableGenerator` シリーズの注意点

`nextDouble(double bound)` / `nextDouble(double origin, double bound)`

`nextExponential()`

`nextGaussian(double mean, double stddev)`

`RandomGeneratorFactory`

`Input.GetKeyDown|Up()` 互換が (Stable 版には) ない

`Keyboard.current` は null になりうる

謎の `OnJointBreak2D` エラー

`xoshiro256**` 擬似乱数生成器の採用

`xoshiro256**` とは

`NextInt64()` シリーズ・ `NextSingle()` の追加

`Next(int maxValue)` の内部実装変更

`NextDouble()` の内部実装変更

`NextBytes()` の内部実装変更

- (公開されていたウェブサイトの内容を閉じる)