FactorioのRNG（乱数生成器）をリバースエンジニアリングする

FactorioのRNG（乱数生成器）をリバースエンジニアリングする 2026年8月22日公開 #Factorio #RNG #reverse-engineering Factorio 2.1で壊れた – バージョン2.0のみ！ Factorio 2.1はRNGの使用方法を変更します。 これは私のゲーム内実装を壊します。RNGの理論的な側面は、同じRNGを使用しているため、依然として適用されます。詳細については、セクション6.1を参照してください。 Factorio 2.1。 はじめに FactorioのSpace-Age DLCのリリースに伴い、いくつかの新しいメカニクスが導入されました。1つの主要なメカニクスは、異なるアイテムと建物の品質という新しい概念でした。デフォルトでは、アイテムは一般的な品質で作成されます。品質モジュールがクラフトマシンで使用されている場合、より高品質のアイテムを入手する小さなチャンスが得られます。それは何を意味するのでしょうか？要するに、アイテムと建物は、より速いクラフト速度、より強力なバフを提供するモジュール、より広い範囲を持つ電力ポール、より速くスイングするインサーターなどの改善されたステータスを獲得します。それはかなり素晴らしいので、私たちのアイテムと建物の可能な限り最高の品質を入手することに興味があります。そのようなアイテムを大量に入手するために、開発者は本質的にこのランダム性が「基本的に統計」1に還元されると言いました。つまり、大量の高品質アイテムを入手した場合、観測された品質の分布は期待される分布に近くなります。しかし、スケーリングする唯一の方法はそれでしょうか？それを考えると、人は疑問に思うかもしれません：Factorioのような決定論的なゲームがランダムなメカニクスを持つことはどのように可能なのでしょうか？短い答えは次のとおりです。ランダムではありません。代わりに、コンピューティングで一般的なように、シミュレーションは擬似乱数生成器（PRNG）を使用します。PRNGは、あらゆる目的のためにランダムに見える一連の数値を生成する決定論的なアルゴリズムです。特に、これは出力の明確に定義された分布に従い、識別可能なパターンを含まないというプロパティを意味します。通常、コンピュータサイエンスでは、PRNGを単なるブラックボックス関数として扱い、それが実際にどのように機能するかを気にせずにランダムな数値を取得できます。しかし、内部を覗いてみると、面白いことができます。面白いこと：アルゴリズムとその内部状態を正確に知っている場合、どうなりますか？次に、同じアルゴリズムを同じ状態で実行して、ゲーム内部でも見られる同じ出力を取得できます。選択されたアルゴリズムが決定論的でない限り、それは必然的に常に同じ出力になります。したがって、ゲームと同時に同じ計算を実行し、PRNGの将来の出力を予測して、品質の向上を観察するクラフトなど、将来の「ランダム」イベントを予測できます。次のセクションでは、ゲームが使用するRNGから始まり、それがどのように壊れるか、そしてゲーム内でどのように悪用できるかまでを段階的に説明します。線形代数の初歩的な理解があれば、すべての背景を理解できるはずです。それが唯一の前提条件です。 ゼロから始める さて、FactorioがどのPRNGアルゴリズムを使用しているかをどのようにして知ることができるのでしょうか？結局のところ、彼らが選択できるさまざまな実装があります。それを知るために、私の最初のステップは初歩的なインターネットリサーチでした。Factorioコミュニティは非常に大きく、多くの技術志向の個人がいるため、誰かがこの質問をしたことがあるはずです。少し掘り下げた後、Factorioフォーラムで私が知りたいことと基本的に同じ質問をしている投稿を見つけましたが、それから11年が経過していました。そのスレッドでは、Wubeの元開発者であるCubeからの次の回答も見つかります。彼らは次のように書いています。 Cube – 2014年9月30日火曜日 – forums.factorio.com：トピック5995 […]私たちは、Boostのジェネレータの中で最も速いため、taus88を選択しました。LFSR（線形帰還シフトレジスタ）の3つのうちの1つを削除することを考えていました（これにより約40％（？）速くなるはずですが、乱数は私たちにとってボトルネックではないため、意味がありません）。これは、次にどこを探すべきかの手がかりを与えてくれます。Boost.Randomライブラリです。そこで、次の（省略された）taus88ジェネレータの実装を見つけます。 typedef xor_combine_engine< xor_combine_engine< linear_feedback_shift_engine<uint32_t, 32, 31, 13, 12>, 0, linear_feedback_shift_engine<uint32_t, 32, 29, 2, 4>, 0>, 0, linear_feedback_shift_engine<uint32_t, 32, 28, 3, 17>, 0> taus88; template<class UIntType, int w, int k, int q, int s> class linear_feedback_shift_engine { // w = ワードサイズ（例：32ビットuintの場合は32） // k = LFSRのビット数 // q = フィードバックタップの位置 // s = 一度に実行するステップ数 // wordmask() = 0b11...111; w個の低位ビットがセットされたマスク result_type operator()() { const UIntType b = (((value << q) ^ value) & wordmask()) >> (k-s); const UIntType mask = (wordmask() << (w-k)) & wordmask(); value = ((value & mask) << s) ^ b; return value; } } これは、taus88が互いにXORされた3つのlinear_feedback_shift_engineで構成されていることを意味します。この線形帰還シフトエンジンは、一般的に線形帰還シフトレジスタ（LFSR）として知られていることに注意してください。ただし、プロジェクトを開始したとき、その投稿はすでに8年前のものでした。したがって、フォーラムで提供された情報を、利用可能な最も正確なソースであるゲームバイナリと比較して確認したかったのです。ゲーム自体はクローズドソースですが、開発者はゲームバイナリと一緒にデバッグシンボルを含む.pdbファイルを親切に提供しています。これは、バイナリの注釈付きの逆コンパイルを生成してコードを検査し、内部で何が起こっているかを把握できることを意味します。この目的のために、オープンソースの逆コンパイルツールGhidraを使用し、プロジェクトの後半でBinary Ninjaに切り替えました。どちらのツールを使用しても、ゲームのコード内のRandomGeneratorクラスをかなり迅速に見つけることができ、getInt()は次のように実装されています。 uint RandomGenerator::getInt(RandomGenerator *this) { uint a = this->seed1; uint b = this->seed2; uint c = this->seed3; a = (a << 12 ^ a >> 6) & 0x1fff ^ a >> 19 ^ a << 12; b = (b << 4 ^ b >> 23) & 0x7f ^ b >> 25 ^ b << 4; c = (c << 17 ^ c >> 8) & 0x1fffff ^ c >> 11 ^ c << 17; this->seed1 = a; this->seed2 = b; this->seed3 = c; return a ^ b ^ c; } 最初に目につくのは、元のtaus88定義で使用されている定数のほとんどが残っていないことです。これは、コンパイラが定数畳み込みなどの最適化を実行して、必要な操作の数を減らすことによるものと考えられます。それでも、RNG状態の3つのシードを格納しているという事実は、それが実際に同じジェネレータであるという最初の強力な兆候です。同様に、状態は互いに独立して更新され、最終結果はすべて状態のXORです。2つの実装が同等であるかどうかについて、残りの疑念をすべて取り除くために、両方のバリアントをPythonで書き直して、シンボル操作用のPythonライブラリであるsympyを使用して実行できるようにしました。両方のバリアントを1ステップ進めることで、対応するレジスタのすべてのビットがまったく同じように更新されることが確認されます。sympyを使用した理由は、これらの同等性チェックを手動で行う（3⋅32=96）のは非常に手間がかかるためです。対応するコードはここにあります。 さて、すべてが確立されたので、Factorioで使用されているRNGは実際にtaus88ジェネレータであり、それ自体が3つのLFSRの組み合わせであることを確信しています。これは非常に興味深い結果です。LFSRは非常に弱いPRNGとして知られており、文献では「簡単に壊れる」という記述さえ見られます。2それらが「弱い」とはどういう意味で、この弱さを利用して将来のRNG呼び出しを予測できるかを理解するために、まず次のセクションの主題であるLFSRの基盤となる数学を見ていく必要があります。 LFSR数学レビュー まず、線形帰還シフトレジスタ（LFSR）が実際に何をモデル化しているかを理解する必要があります。まず、単純なレジスタを考えます。それはビットのコレクションを表し、単一の値xxxに集約されます。 x=xn−1…x2x1x0x = x_{n-1} is x_2 x_1 x_0x=xn−1​…x2​x1​x0​ 各個別のビット xix_ixi​は、xi∈{0,1}=F2x_i is {0,1}=F_2x_i∈{0,1}=F2​のバイナリ変数と見なすことができます。