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 です。とはいえシーケンスが十分に長いため、こういったことも起こりえます。