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

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

［動画］

Factorio 2.1で破損 – バージョン2.0のみ！

Factorio 2.1はRNGの使用方法を変更しました。

これにより、私のゲーム内実装は破損しました。RNGの理論的な側面は、同じRNGを使用しているため、依然として適用されます。詳細については、セクション6.1. Factorio 2.1を参照してください。

はじめに

FactorioのSpace-Age DLCのリリースに伴い、いくつかの新しいメカニクスが導入されました。その主要なメカニクスの一つが、アイテムや建物の新しい概念である「品質」でした。デフォルトでは、アイテムはコモン品質で作成されます。品質モジュールをクラフトマシンで使用すると、より高品質なアイテムを得られる小さなチャンスが得られます。

これは何を意味するのでしょうか？簡単に言うと、アイテムや建物のステータスが向上します。例えば、クラフト速度の向上、より強力なバフを提供するモジュール、範囲が拡大した電力ポール、より速くスイングするインサーターなどです。これは非常に便利なので、可能な限り最高の品質のアイテムや建物を入手することに興味があります。開発者は、このようなアイテムを大量に入手する方法について、「基本的に統計」1に集約されると述べています。つまり、高品質なアイテムの総数が十分に多ければ、観測される品質の分布は期待される分布に近くなるということです。

しかし、スケールアップする唯一の方法はこれだけでしょうか？考えてみると、人はこう疑問に思うかもしれません。

Factorioのような決定論的なゲームで、どのようにして「ランダム」なメカニクスが存在できるのか？

短い答えはこうです：ランダムではありません。

代わりに、コンピューティングでよくあるように、シミュレーションは疑似乱数生成器（PRNG）を使用します。PRNGは、あらゆる目的においてランダムに見える一連の数値を生成する決定論的なアルゴリズムです。特にこれは、出力が明確な分布に従い、識別可能なパターンを含まないという特性を持ちます。通常、コンピュータサイエンスでは、PRNGを単なるブラックボックス関数として扱い、その実際の動作を気にせずにランダムな数値を得ることができます。しかし、その内部を覗いてみると、何か面白いことができます。

面白いこと：アルゴリズムとその内部状態を正確に知っている場合、何が起こるでしょうか？

その場合、同じアルゴリズムを同じ状態で実行し、ゲーム内部でも認識される同じ出力を得ることができます。アルゴリズムが決定論的でなければ、それは必然的に常に同じ出力になります。そのため、ゲームと同時に同じ計算を実行し、PRNGの将来の出力を予測することで、品質の向上を伴うクラフトなど、ゲーム内の将来の「ランダム」なイベントを予測できます。

次のセクションでは、ゲームが使用するRNGから始め、それがどのように壊れるか、そしてゲーム内でどのように（誤って）利用できるかまで、段階的に説明していきます。線形代数の初歩的な理解があれば、背景全体を理解できるはずです。それが唯一の前提条件です。

何もないところから始める

さて、FactorioがどのPRNGアルゴリズムを使用しているかをどうやって突き止めるのでしょうか？結局のところ、いくつかの異なる実装が存在する可能性があり、それらから選択できたはずです。

これを突き止めるために、私の最初のステップは、インターネットでの基本的な調査でした。Factorioコミュニティは非常に大きく、多くの技術志向の個人で満ちているので、きっと誰かが以前にこの質問をしたことがあるはずです。少し調べてみると、Factorioフォーラムで私が知りたいこととほぼ同じことを尋ねている投稿を見つけましたが、それから11年が経過していました。そのスレッドでは、Wubeの元開発者であるCubeからの以下の回答も見つかりました。彼らは次のように書いています。

[…] 私たちは主にBoostのジェネレータの中で最も高速なtaus88を選択しました。3つのLFSRのうち1つを削除すること（これにより約40%（？）高速になるはずです）を考えていましたが、乱数（ran[d]om numbers）は私たちにとってボトルネックではないため、意味がありませんでした。

これは、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 = word size (e.g. 32 for 32 bit uint)
  // k = number of bits in the LFSR
  // q = feedback tap position
  // s = number of steps to do at once
  // wordmask() = 0b11...111; mask of w low bits set
  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つのシードを格納しているという事実は、それが同じジェネレータであることの最初の強い兆候です。同様に、状態は互いに独立して更新され、最終結果は3つの状態すべてのXORです。

2つの実装が同等であるかどうかについての残りの疑念をすべて払拭するために、両方のバリアントをPythonで書き直し、sympyという記号操作用のPythonライブラリを使用して実行できるようにしました。両方のバリアントを1ステップ進めることで、対応するレジスタのすべてのビットがまったく同じように更新されることを確認しました。ここではsympyを使用しました。なぜなら、これらの同等性チェックを手動で行う（3⋅32=96）のは非常に手間がかかるからです。対応するコードはこちらで見つけることができます。

さて、すべてが確立されたので、Factorioで使用されているRNGは実際にtaus88ジェネレータであり、それは3つのLFSRの組み合わせであることが確実です。これは非常に興味深い結果です。なぜなら、LFSRは非常に弱いPRNGとして知られており、文献では簡単に壊れる（trivially breakable）とさえ述べられています。2

それらが「弱い」理由と、この弱さを利用して将来のRNG呼び出しを予測する方法を理解するために、まずLFSRの基礎となる数学、次のセクションの主題を見てみましょう。

LFSR数学レビュー

まず、線形帰還シフトレジスタ（LFSR）が実際に何をモデル化しているかを理解する必要があります。まず、単純なレジスタを考えます。これは、単一の値xに集約されたビットのコレクションを表します。

x = x_{n-1} ... x_2 x_1 x_0

各個別のビットx_iはバイナリ変数と見なすことができ、x_i ∈ {0,1} = F_2です。このレジスタ値xを範囲[0, 2^n - 1] ⊆ Zの数値として扱うのが一般的ですが、この場合、レジスタを実際にはビットのベクトル、つまりx ∈ F_2^nとして扱う方が有用です。さらに、各個別のビットに作用する2つの演算を考慮します。

1. x_i ⊕ y_i: XOR演算は2つのビットを取り、ビットが異なる場合は1、同じ場合は0を返します。これは2を法とする加算と同等であることに注意してください。
2. x_i ⋅ y_i: AND演算は2つのビットを取り、両方のビットが1の場合は1を返し、それ以外の場合は0を返します。これは2を法とする乗算と同等です。

次に、そのレジスタの概念をシフトレジスタに拡張します。シフトするには、レジスタ内のすべてのビットを下方向に移動させます。各上位ビットを1位置下にシフトし、最下位ビットを破棄します。ここでは、最上位ビットを左端のビットx_{n-1}、最下位ビットを右端のビットx_0とする慣習に従います。

この種のレジスタは、以下のインタラクティブなデモで操作できます。個々のビットをタップして切り替え、コントロールを使用してレジスタを開始、停止、ステップします。

1000011

1x 2x 5x

まあ…これは退屈ですね！初期状態に関わらず、すぐにすべて0の値に収束します。これはまったくランダムに見えません！シフトレジスタが常にすべての情報を破棄するのを防ぐために、フィードバックという別のコンポーネントを追加します。最初のアイデアは、破棄された最下位ビットを最上位ビットにループバックさせることです。以前は、新しい情報から取得する先行ビットがなかったため、最下位ビットで情報を破棄していました。これを行うことで、ビットロール操作を実装しました。

0000011

1x 2x 5x

うーん…少なくとも常に空のレジスタに到達するわけではありません。しかし、最後のビットが点灯するときのシーケンスは非常に予測可能です。これは、現在のフィードバックシフトレジスタによって生成されるパターンがすぐに認識できるためです。これを回避するために、フィードバックを最初のビットだけでなく、中間ビットにも追加することで、線形フィードバックを挿入します。ここでの加算は、個々のビットで作業しているため、XORを意味します。

0000011

1x 2x 5x

最後のステップとは異なり、このステップがそのように名付けられた理由がすぐに明らかではないかもしれません。これは、内部ビットを結合するために使用するXOR ⊕ 演算により、ビット状態が前のビット状態の線形結合になるという事実から来ています。この線形性は、観測のみから内部RNG状態を再構築できる理由でもあり、スタンドアロンLFSRが暗号学的に弱いPRNGである理由でもあります。

上記すべてのケースで、最後のビットのみが出力と見なされることに注意してください。しかし、実際には、レジスタの状態全体をRNG呼び出しの結果として出力することがより一般的です。これにより、[0, 2^n - 1]の範囲の適切な整数として再解釈でき、ランダムに見える数値を生成できます。

これでLFSRがどのように構築されるかがわかりました。特に、時間tでの状態x(t)が与えられた場合、次のことを行う方法がわかりました。

1. 次の状態x(t+1)を生成する。
2. 対応する出力ビットを、1つずつ、または完全な整数値として生成する。

LFSRのサイクル長について

LFSRのサイクル長とは、状態が繰り返されるまでにかかるステップ数です。nビットのLFSRの場合、最大サイクル長は2^n - 1（すべてのゼロ状態を除くすべて）です。

LFSRのメカニクスは、実際にはF_2上の多項式によってもモデル化されます。1ステップは、現在の状態S(X) = Σ_{i=0}^{n-1} x_i X^iをXで乗算することに対応します（これはビットを1つ上にシフトします）。

最後に、次数nで原始的（したがって既約）なフィードバック多項式P(X)で割った余りを取ることで、サイクル長が最大（2^n - 1）であることを保証できます。P(X)は、フィードバックが挿入される空間、つまりXORされるビットを指定します。言い換えれば、すべてのフィードバック構成が等しく良いわけではなく、長いサイクル長を保証するためにはフィードバックタップの選択が重要です。

LFSRは線形である

上記の線形性の主張をもう一度見てみましょう。そのためには、xの任意のインスタンス、つまりすべてのビットが0または1に設定された状態を考慮する代わりに、LFSRのシンボリック表現を考慮できます。まだ任意の時点t=0から開始し、各個別のビットにシンボル変数x_iを追加でラベル付けします。次に、LFSRの遷移ルールを適用しながら、ビットが時間とともにどのように進化するかを追跡します。各シンボルは、LFSRが開始された時点の状態に応じて、オンまたはオフとして色付けされます。以前と同様に、個々のビットをクリックして切り替えることができます。ただし、ビットラベルが初期状態にある間のみです。

0001

1x 2x 5x

各ビットが常に初期ビット状態の組み合わせにすぎないことがわかります。シンボリック例でx_i ⊕ x_iが現れると、x_iがキャンセルされて方程式から削除できることに注意してください。ステップ中に、インスタンス化された各ビットは、ラベルを割り当てた時点の状態に応じて、シンボリック組み合わせの「オン」ビットのパリティに常に等しくなります。さらに、ビットは先行ビットの状態であるか、または先行ビットとフィードバック状態の組み合わせのいずれかであることがわかります。

では、これが線形性とどう関係するのでしょうか？

まず、ビットF_2 = {0,1}と演算⊕および⋅のセットが体（field）として知られる構造を形成することに注意してください。この体は、一般にガロア体 GF(2) = Z/2Z = F_2または2を法とする算術として知られています。体とは、特定のプロパティのセットを満たす演算と結合された値のセットに対する数学用語です（以下を参照）。

(F_2, ⊕, ⋅) の体プロパティ

(F_2, ⊕, ⋅) を体と宣言するために満たす必要があるプロパティは次のとおりです。

• 結合律（⊕および⋅の両方）：a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ cおよびa ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c。
• 可換律（⊕および⋅の両方）：a ⊕ b = b ⊕ aおよびa ⋅ b = b ⋅ a。
• 単位元：⊕の場合は0：0 ⊕ a = a、⋅の場合は1：1 ⋅ a = a。
• 加法逆元：任意のaに対して、a + (-a) = 0となる-aがあります。ここではa = -aであることに注意してください。
• 乗法逆元：任意のa ≠ 0に対して、a ⋅ a^{-1} = 1となるa^{-1}があります。これは、唯一の他の要素が1であるため自明です。
• 分配律：a ⋅ (b ⊕ c) = (a ⋅ b) ⊕ (a ⋅ c)。

これらのプロパティは、真理値表を使用してF_2で簡単に確認できることに注意してください。最大8行で十分です。

なぜこれが重要なのでしょうか？体構造を持つことは、ベクトル空間の前提条件となるためです。特にここでは、GF(2)上の長さnのすべてのベクトルのベクトル空間を考えます。これはGF(2)^nと表記されます。演算は、元の体GF(2)の演算を使用して、ベクトルの各座標にポイントワイズで適用されます。そして、ベクトル空間がある場所ならどこでも、ベクトルの線形結合について話すことができます。

個人的には、線形代数とベクトル空間の紹介を抽象的なフレームワークで受けた後、R^nまたは、スパイシーな場合はC^nにのみ適用されるのを見てきました。しかし、ベクトル空間の元の定義は意図的に非常に一般的です！これにより、必要なプロパティを満たす任意の構造を同じように操作でき、R^{m×n}行列に適用されたことのあるよく知られたアルゴリズムを、基盤となる体Fに関係なく、任意の行列に適用できるようになります。3そして幸運なことに、以前に定義されたXORとANDのビット演算は体 spanned します。

シンボリック例をもう一度見ると、各個別のビットの遷移を前のビット状態の線形結合として再定式化できます。

\begin{align*}
x_3^{(t+1)} &= x_0^{(t)} \
x_2^{(t+1)} &= x_3^{(t)} \oplus x_0^{(t)} \
x_1^{(t+1)} &= x_2^{(t)} \
x_0^{(t+1)} &= x_1^{(t)}
\end{align*}

状態全体をこれらのビットのベクトルとして書き出すことができ、各遷移自体が線形であるため、現在の状態s(t) ∈ GF(2)^nから次の状態s(t+1) ∈ GF(2)^nへの遷移を行列積として書くことができます。

s^{(t+1)} = T s^{(t)}

ここでT ∈ GF(2)^{n × n}です。状態ベクトル内のビットと同様に、行列の各エントリはGF(2)の値、つまり0または1です。特に、これは行列をビットマップとして視覚化することを可能にし、明るいエントリは1、暗いピクセルは0を表します。以前に見た6ビット幅のトイLFSRの場合、これは次のようになります。

この数学的表記により、いくつかの演算をよりコンパクトな方法で書き直すことができます。最も注目すべきは、LFSRを一度に複数ステップ進めることができることです。

s^{(t+k)} = T^k s^{(t)}

これで理論の多くを見てきたので、それを実際のコードスニペットに適用できます。単一のLFSRコンポーネントに焦点を当てると、次のようになります。

a = (a << 12 ^ a >> 6) & 0x1fff ^ a >> 19 ^ a << 12;

これは各個別のビットに対して展開して評価できます。次に、各LFSRがuint32_tワード（32ビット）で定義されているため、32個の方程式のシステムが得られます。LFSRの構築により、一部のビットが実際には冗長になっていることに注意してください。taus88ライブラリでは、k（LFSRサイズ）は常にw（ワードサイズ）よりも小さく選択されています。

\begin{array}{rrrrrrrrc}
a ext{'}{31} = \big((& a ext{}{19} &\oplus& 0 ) &\cdot 0\big) &\ \oplus& 0 & &\ \oplus& a ext{}{19} &=& & a ext{}{19} \
a ext{'}{30} = \big((& a ext{}{18} &\oplus& 0 ) &\cdot 0\big) &\ \oplus& 0 & &\ \oplus& a ext{}{18} &=& & a ext{}{18} \
\vdots
\end{array}

以前のLFSRダイアグラムからほとんどすべての矢印を反転させることで、次の「逆モード」LFSRを得ることで、これは単純に私たちが行ったことになります。

110000

1x 2x 5x

数学的には、これは、単一の前進ステップに対応する行列Tが存在する場合、前のステップを完全に逆転させる別の行列T^{-1}を常に構築できることを示しています。つまり、逆行列を見つけました。

T^{-1} T = I

したがって、LFSRから派生した任意のTに対して、T^{-1}が存在することを知っています。これは、上記の構築によって生成されるか、またはガウスの消去法などの代替方法によって生成できます。通常、ガウスの消去法では行列を上三角行列に変換するだけです。しかし、GF(2)では数値的な問題なしに、次の疑似コードを使用して逆行列を直接解くことができます。

def invert(M):
  # Extend with the identity matrix on the right
  system = [M | I]
  # Iterate over all columns in the original M
  col = 0
  for row in M.num_rows:
    # Find pivot row, which hasn't previously been applied
    for pivot_row in range(row, M.num_rows):
      if system[pivot_row][col] == 1:
        break
    # Move the pivot to the current row
    system.swap_row(pivot_row, row)
    # Cancel all other rows with a 1 in the current column
    for cancel_row in range(M.num_rows):
      if system[cancel_row][col] == 1 and cancel_row != row:
        system[cancel_row] += system[row]
    # Move to the next column
    col += 1
  # Return the part which was previously the identity
  return system.I

T_iの可逆性について

Boostライブラリで与えられたLFSRとそれらをインスタンス化するために使用されるパラメータを考慮すると、それらはn=32ビットワードで動作しますが、実際のLFSRサイズはそれぞれ31、29、28であることがわかります。これは、いくつかのビットが考慮されていないことを意味します。この場合、これらは最下位ビットであり、LFSRが以前に出力したビットのコピーにすぎません。線形方程式の観点からは、最下位ビットは上位ビットに線形従属です。

これにより、T_i行列のランクがrank(T_i) < 32 = nとなり、厳密には非可逆となります。これも、上記の図で最下位ビットに空の列が表示されている理由です。

しかし：下位ビットは常に上位ビットの線形結合にすぎないことを知っているので、個々のLFSRの遷移行列をそれぞれ31×31、29×29、28×28に縮小できます。これにより、完全なランクが回復し、したがって遷移行列が構築によって可逆であるという私の主張は有効になります。これらの縮小された行列を使用して観測された出力から内部状態を計算することにより、上位ビットの値から残りの下位ビットを計算でき、完全な状態復元が可能になります。ただし、これは厳密には追加のステップではありません。計算された状態がそのまま（例えば、線形従属ビットが0に埋められた状態で）進められると、単一の前進ステップの後、すべてのビットの完全な状態が利用可能になります。なぜなら、単一のステップには、上位ビットの線形結合によって下位ビットを計算することが含まれるからです。

複数のLFSRの結合

単一のLFSRの状態をAx=bという形式の線形方程式として解くことができることを見てきました。ここで、すべてのコンポーネントは2を法として計算されます。ただし、完全なRNG結果は、出力がXORで結合される3つの独立したLFSRによって決定されることを思い出してください。これを、それぞれ対応する遷移行列T1, T2, T3を持つ3つの異なる状態s1, s2, s3 ∈ GF(2)^nを持つとモデル化できます。次に、これらのすべての状態ベクトルをスタックすると、一度の全体の状態を表す大きなベクトルs = [s1 s2 s3]^Tが得られます。この新しい状態ベクトルに対して、可逆であることがわかっている遷移行列を再び導出できます。

s^{(t+1)} = \begin{bmatrix} T_1 & 0 & 0 \\ 0 & T_2 & 0 \\ 0 & 0 & T_3 \end{bmatrix} s^{(t)} = T s^{(t)}

現在のRNGの「隠れ状態」s(t)から最終結果o(t) ∈ GF(2)^nを得るには、次のように単純に計算できます。

o^{(t)} = [I I I] s^{(t)}

ここでI ∈ GF(2)^{n × n}は対応する単位行列です。これを単に見ると、全体が再び非可逆になったと思うかもしれません。そして、これは単一の出力を調べるだけであれば真実です。しかし、乱数ジェネレータを複数回ステップするとどうなるでしょうか？最初の出力はそのままですが、次の出力は次のようになります。

o^{(t+1)} = [I I I] s^{(t+1)} = [I I I] T s^{(t)} = [T_1 T_2 T_3] s^{(t)}

同様に、次のようになります。

o^{(t+2)} = [T_1^2 T_2^2 T_3^2] s^{(t)}

したがって、3つの連続した出力を連続して観測すると、次の連立方程式が得られることがわかります。

\begin{bmatrix}o^{(t)} \\ o^{(t+1)} \\ o^{(t+2)}\end{bmatrix} = \underbrace{\begin{bmatrix}I & I & I \\ T_1 & T_2 & T_3 \\ T_1^2 & T_2^2 & T_3^2\end{bmatrix}}\_A s^{(t)}

言い換えれば、任意の時点tでのPRNGレジスタの状態を把握するには、3つの連続した呼び出しの結果を観測し、次の連立方程式を解く必要があります。

s^{(t)} = A^{-1} \begin{bmatrix}o^{(t)} \\ o^{(t+1)} \\ o^{(t+2)}\end{bmatrix}

実装上のハードル

観測行列Aを反転するという以前の結果はすでに機能しています。実際、それは私がPythonで最初に構築したソルバー実装でした。観測には、Factorio Lua APIを使用して3つの連続した乱数を生成しました。これにより、内部状態を復元し、将来のRNG出力を予測するのに十分でした。以下を参照してください。方法が機能する最初の記録

ゲーム内で利用可能なリソースのみを使用して実装しようとする前に、2つの理論的なハードルを調べる必要があります。

1. 現在、連続した呼び出しの結果が必要です。これらは私たちには利用できない場合があります。
2. さらに、完全な結果幅、つまりPRNG呼び出しのすべての32ビットを一度に取得する必要があります。純粋なゲームメカニクスでは、これらは必ずしも観測可能ではありません。

したがって、これらの問題の両方と、それらをどのように対処できるかを見てみましょう。

連続した呼び出し

以前の導出では、3つの連続した呼び出しの完全な幅を使用した状態s(t), s(t+1), s(t+2)を利用しました。私たちが要求しているRNG値以外のシミュレーション内の他のシステムが同時に存在しないとは限らないため、非分離ケースを考慮する必要があります。これに対処するにはいくつかの方法があります。

1. 観測の間の呼び出し回数をカウントする方法があれば、以前の結果を一般化してo^{(t+n)} = T^n s^{(t)}を使用することで、観測されなかった結果をスキップできます。ここでnは、次の測定までスキップした呼び出しの数です。
2. あるいは、測定が連続して発生するように強制しようとします。これは、測定したい呼び出しに干渉できる他のすべてのゲーム内ソースを無効にし、順序で必要な呼び出しを行い、そこから計算/操作することによって行うことができます。
3. 後者は、サブティックメカニクスの領域にさらに拡張できます。毎秒1/60秒ごとに、ゲームは更新ステップ、つまりティックを実行します。このティック内ですべてのシミュレーションメカニクスが固定順序で実行されます。トリガーされるメカニズムの1つは、もちろん、すべてのマシンがアイテムクラフトサイクルを完了した後のクラフト結果の作成です。もし私たちがアイテム作成イベントをキューに入れるマシンの順序を制御できれば、エントロピー生成器をこのキュー内の連続したブロックに配置することで、RNG呼び出しがギャップレスになるように強制し、適切な状態再構築が可能になります。

私の実装では、オプション2と3の両方を追求することを選択しました。前者は内部更新順序に依存しないため、常に機能するはずのフォールバックメソッドです（開発者がRNGをtaus88から変更しない限り）。一方、理論的には、後者のアプローチははるかに高速な状態読み出しと、外部からの余分な呼び出しに対するより高い堅牢性を可能にします。しかし、実際には、それはやや不安定に見え、無作為な時間に壊れることがあります。その場合、配線を再構築するだけで再び機能します。

完全な結果幅

エントロピー生成器には、出力にランダム性が含まれるクラフトレシピを使用します。これは、そのような出力を測定するたびに、PRNG呼び出し全体に関する情報が得られないという欠点があります。代わりに、私たちが測定できるのは、選択した方法に応じて、出力に関するいくつかの単純な質問だけです。例をいくつか挙げます。

• 出力アイテムの数。レシピが非整数スタックのアイテムを生成する場合（例：リサイクルレシピ、単一の入力アイテムをクラフトするために必要なアイテムの25%またはアイテム自体を返す場合）、または本質的にランダムな出力を持つレシピの場合（例：ウラン処理、U-235が生成される確率が0.7%、U-238が生成されない確率が0.7%の場合）にランダム性が関わります。
• 出力の品質レベル。レベルが上昇したかどうか、そしてもしそうなら一度にどれだけ上昇したかを測定できます。

私は、最初の2つの方法のうち、生産されたアイテムの量のみを観測することに焦点を当てます。これは、このプロジェクトを開始したときに利用できた唯一の情報源でした。理解すべきことは、これらの質問のいずれかに答えることで、RNGロールの最上位ビットに関する情報しか得られないということです。

ウラン鉱石をU-235とU-238に精製する例を考えてみましょう。これには2つの生産結果があります。

• U238は99.3%の確率で結果として発生し、
• U235は0.7%の確率で発生します。

両方の出力を生成するために、RNGは1回のクラフトサイクルごとに2回クエリされます。アイテムごとに2つの連続したRNG呼び出しが生成されます。これらの確率は非常に極端であるため、低確率イベントが発生するたびに重要な知識が得られます。結果のアイテムは、それぞれの不等式が成り立つ場合に生成されます。ここでr_i ∈ [0, 2^{32}-1]は計算されたRNGロールです。

r_1 \leq \left\lfloor 0.993 \cdot 2^{32} \right\rfloor = 4,264,902,524_{10} = 11111110\ 00110101\ 00111111\ 01111100_2
r_2 \leq \left\lfloor 0.007 \cdot 2^{32} \right\rfloor = 30,064,771_{10} = 00000001\ 11001010\ 11000000\ 10000011_2

特に：

• U238が生成されなかった場合、つまりr_1が指定されたしきい値より大きい場合、最初の7ビットが1であることがわかります。
• 同様に、U235が生成された場合、r_2の最初の7ビットは0である必要があります。

それ以外の場合、ロールされたビットに関する意味のある情報は得られません。

クール！しかし、各クラフトサイクルが完了するたびに、最も多くの情報が得られるレシピはどれでしょうか？クラフトサイクルごとに得られる情報が多いほど、必要なクラフト数が少なくなり、内部状態をより迅速かつ効率的に決定できます。

上で見たように、観測できる唯一の情報は最上位ビットによって決定され、アイテムが得られたかどうかです。ロールが実際には均等に分布していると推定する場合、各ロールと観測で得られる情報の期待値を計算できます。

\underbrace{0.007 \cdot 7\,\text{bit}}\_\text{no U238} + \underbrace{0.993 \cdot 0\,\text{bit}}\_\text{U238} = 0.049\,\text{bit}
\underbrace{0.993 \cdot 0\,\text{bit}}\_\text{no U235} + \underbrace{0.007 \cdot 7\,\text{bit}}\_\text{U235} = 0.049\,\text{bit}

これは、1回のクラフトサイクルあたり合計0.098ビットを期待できることを意味します。上記のパターンをもう少し長く調べると、各成功ケース（確率が0.7%の場合）で得られる先頭ビットの数は、⌊-log_2(p)⌋であることがわかるかもしれません。同様のことがp > 0.5の場合にも当てはまり、結果は代わりに先頭の0ビットが観測されます。これにより、確率pのイベントで測定される期待ビット数を計算できます。全体として、次のように書くことができます。

E[bits] = p ⌊-log_2(p)⌋ + (1-p) ⌊-log_2(1-p)⌋

この関数は以下にも示されています。そのプロットは次のことを示しています。

• 観測される期待ビット数が最も多いイベントは、50%の分割にあります。その時点で、最上位ビットを常に観測できます。
• 0/1に近いイベントは、成功した場合により多くのビットを推測できますが、イベントが発生する可能性が速すぎるため、イベントあたりの期待観測ビットの総数が減少します。

2025-10-07T19:10:49.360938 image/svg+xml Matplotlib v3.8.4, https://matplotlib.org/ 0 312 116 18 14 12 3312 1156 78 34 1 Event likelihood p 0.0 0.2 0.4 0.6 0.8 1.0 Expected #Bits () Ep Expected Bits observed for Events of Probability p

私たちが計算したものは、シャノンエントロピーの離散化バージョンと見なすことができます。したがって、利用可能なすべてのレシピに適用できる尺度があり、クラフトあたりの情報量が最も多いレシピを特定できます。生のゲームダンプ4から関連するレシピデータを抽出することで、各レシピのエントロピーをプログラムで計算できます。

そうすると、クラフトあたりの期待ビット数と各クラフトにかかる時間を含むレシピのテーブルが得られます。以下は、ランダムな出力を持つレシピの小さな選択を示しています。すべてのランダム出力を持つレシピのテーブルについては、こちらを参照してください。

ビット観測を生成するランダム結果を持つレシピの抜粋。

ご覧のとおり、情報抽出にははるかに優れたレシピがあります。スクラップリサイクルは、生成されるアイテムが多数あるため、多くの情報が得られると考えるかもしれません。しかし、合計エントロピー2.05は、2のエントロピーを持つ修理パックのリサイクルなどのレシピをわずかに上回るだけです。これは、修理パックのリサイクル（および同様の材料数が4n+2のレシピ）が、追加アイテムが作成されるかどうかの50/50の分割を正確に生成するため、どちらの場合も1ビットの情報しか得られないためです。明らかに、石油精製所のような4.5のエントロピーを持つ代替レシピもあります。しかし、これらははるかに高価で遅いです。

したがって、修理パックのリサイクル方法を使用して状態読み出しを実装することを選択しました。修理パックは安価で、クラフトが速く、ゲーム序盤でアンロックされるためです。

実際のインプリメンテーション

RNGの逆転と操作を実際に実装するために、計算を次のステップに分割しました。

1. サンプリング：観測による現在のRNG。
2. 現在の内部RNG状態の計算。
3. 将来の内部状態の予測。
4. 各呼び出しに対応する品質レベルの計算。
5. 最後に、アダプターを使用した予測レベルの活用。

LFSRの反転で既に示唆したように、これらのステップの両方で行列ベクトル積を計算する必要があります。さて、行列をどこから取得し、ベクトルをどこから取得するのかという問題です。

RNGのサンプリング

現在の状態は、修理パックをリサイクルする際に作成された観測から計算されます。各リサイクル操作は正確に2ビットの情報（各結果アイテムに対して1ビット）を生成します。これは、状態を完全に再構築するために88/2 = 44回の再リサイクル操作が必要であることを意味します。各結果は正確に1ビットの情報（RNGロールの最上位ビット）を提供するので、88回の観測は次のように書くことができます。

o^{(t)}, o^{(t+1)}, ..., o^{(t+87)} ∈ GF(2)

単一の測定ユニット（o(t+2k)およびo(t+2k+1)を測定する）は次のようになります。

［画像: 単一のエントロピー測定ユニットのスクリーンショット。］

単一のエントロピー測定ユニット。

次の手順を実行します。

1. インサーターは正確に1つの修理パックをリサイクラーに移動させます。
2. リサイクラーはアイテムをリサイクルし、完了時にRNGに2つの新しい整数をクエリして、追加アイテム（0または1）が生成されるかどうかを決定します。
3. アイテムが生成されたかどうかに応じて、それらはプロバイダーチェストに配置されます。このチェストは内容を読み取るように設定されており、観測を赤線に提供します。
4. これらの観測は、50%の出力確率のため、最上位ビットo^{(t+k)}に直接対応します。デサイダーコンビネータでさらに処理が行われます。
5. 次の呼び出しが発生する前に、要求されていないゴミオプションと、リクエスターチェストが無効になっているときに自動ゴミ処理動作を一時的に一時停止できるグリーンワイヤ経由で送信できる有効/無効信号を利用して、プロバイダーチェストをクリアします。それ以外の場合は、アイテムを要求しません。

したがって、上記のユニットは常に2ビットの情報を提供します。完全な状態を迅速に再構築するために、このユニットを44回コピーすると、合計88ビットになります。これは次のようになります。

［画像: すべてのエントロピーユニットが結合されたもの。］

すべてのアントロピーユニットが結合されたもの。

個々のユニットがどのようにクエリされるかについて言及する価値があります。2つのアプローチがあります。

1. 各ユニットを1ティック遅延でトリガーすると、常に同じ順序でクエリされることが保証されます。ただし、その間に他のRNGが実行されていない必要があります。なぜなら、途中で発生するRNG呼び出しは、期待される順序を乱す可能性があるからです。
2. あるいは、同じティックの動作を使用できます。インサーターを接続する赤線を、各インサーターの前に1ティック遅延コンビネータで分割することにより、これを実現できます。遅延の入力に接続してから各インサーターに接続すると、各インサーター用のスタンドアロンネットワークが作成されます。ゲームはネットワークを何らかの方法で更新する必要があるため、ネットワークIDでソートされたリストを反復処理すると仮定します。これにより、RNG呼び出しがすべて同じティックで発生し、ティックが干渉しないことが保証されます。ワイヤの構築は、2段階のブループリントを使用しても実行できることに注意してください。

注 - 同じティックの動作について

同じティックの動作は実際には機能するように見えますが、ゲームが内部でどのように動作するかを実際に確認したわけではありません。時々壊れることがあるようです。その場合、配線を再構築するだけで再び機能します。

現在の状態の決定

各ユニットは単一ビットの観測結果しか生成しないため、以前と同様の戦略を適用する必要があります。ただし、今回は、観測から計算するために上記で定義された線形方程式の最初の行のみを使用します。

o^{(t+k)} = P_1 T^k s^{(t)}

ここでP_1 = [I I I]の最初の行です。A_k = P_1 T^kをk回のRNGステップを実行してから最上位ビットを観測することを示す行列とすると、観測は次の式に従うと書くことができます。

A s^{(t)} = \begin{bmatrix}o^{(t)} \\ \vdots \\ o^{(t+87)}\end{bmatrix}

ここでAはA_0からA_87までのすべてのA_kを積み重ねたものです。88回の呼び出しを消費するため、観測を開始した時点ではなく、観測後のRNGの状態を直接計算する方が有益です。これは、逆遷移行列T^{-1}を使用して時間インデックスをシフトすることで実現でき、新しい行列\tilde Aが作成されます。

A s^{(t)} = A T^{-88} s^{(t+88)} = \tilde A s^{(t+88)}

tを次のRNG呼び出しに対して相対的にシフトするために\tilde t = t + 88と置換すると、次の式が得られます。

\tilde A s^{(\tilde t)} = o^{(\tilde t-88, ..., \tilde t-1)}

これは、以前に行った観測から次の内部RNG状態を計算していると読むことができます。88ビットしか線形独立ではないため、完全な逆行列を計算することはできません。しかし、擬似逆行列で十分です。特に、私たちは後続の状態に興味があるので、その下位ビットは最上位ビットによって完全に記述されます。これは、単一のステップの前進でも、以前は未知だったビットが決定論的に設定されることを意味するため、すべて問題ありません。

このすべてにおいて本当に素晴らしいのは、行列Aおよび同様に\tilde Aが動的な状態に依存しないことです。したがって、\tilde A^{-1} ∈ GF(2)^{88 × 96}はPythonで事前に計算でき、その後Factorioで使用できます。

したがって、GF(2)での行列ベクトル乗算をゲーム内に実装するだけで済みます。これを行うには、任意の行列ベクトル積が、ベクトルによって重み付けされた行列の列の合計と見なせることを思い出してください。

Ax = \sum\_k=1^n x_k [A]_k = x_1 a→1 + ... + x_n a→n

この場合、GF(2)で計算しているため、各エントリは0または1であり、乗算は単純な条件付きで表すことができ、合計は重み付けされたすべてのベクトルのXORに置き換えられます。

s^{(t+88)} = \bigoplusromi=0^{87} o^{(t+i)} \cdot [\tilde A^{-1}]_i

ここで[\tilde A^{-1}]_iは\tilde A^{-1}のi番目の列であり、o^{(t+i)}は実行されたi番目のビット観測です。実際には、この方程式は2つの部分で計算されます。

まず、各測定ユニットは、o^{(t+i)} ∈ {0,1}とベクトル[\tilde A^{-1}]_iのポイントワイズスカラーベクトル乗算を実行します。これは、上記で言及したデサイダーコンビネータが「さらなる処理」を行うことによって行われます。結果のアイテムが観測されなかった場合（=0）、ロールはしきい値を超えており、o^{(t+i)}=1となるため、この列を累積する必要があります。それ以外の場合は累積しません。ベクトル[\tilde A^{-1}]_iは、デサイダーコンビネータの定数出力に格納されており、1であるビットのみが出力されます。したがって、ベクトルは96個の異なる信号で表されます。

［画像: 単一のデサイダーコンビネータが単一のスカラーベクトル乗算を計算している様子。］

単一のデサイダーコンビネータが単一のスカラーベクトル乗算を計算している様子。

最後に、これらのすべてのベクトルのXORを取得して最終状態を得る必要があります。これは暗黙の加算5を使用して達成できます。単一信号の値の合計を取り、その合計の最後のビットのみを抽出することは、それらすべてをXORすることと同等です。したがって、すべてのデサイダー出力を配線することで、単一の算術コンビネータが1とのポイントワイズ合計をANDingすることによってビット抽出を実行できます。

各信号が3つの32ビットLFSR状態の単一ビットに対応するようになったので、デサイダーコンビネータのセットを使用して、各アクティブ信号の対応するビットの合計を取ることができます。したがって、3つの信号があり、それぞれがゲームのRNGの現在の状態を含んでいます。

［画像: スカラーベクトル乗算の最終的なXOR削減。］

最終的なXOR削減。

未来を見る

個々のLFSRの将来の状態を計算するために同様のアクションを実行します。ただし、すべてのLFSR状態は32ビット未満を必要とするため、ルックアップテーブルをよりコンパクトな形式で格納できます。各LFSRについて、次の計算が必要です。

s^{(t+k)} = T^k s^{(t)}

これはk=1,2,...,Nについて計算されます。ここでTとsは3つのサブLFSR間で異なります。ここから、これらの行列ベクトル乗算を次のように書き直すことができます。

s^{(t+k)} = \bigoplusromi=1^{32} s^{(t)}_j \cdot [T^k]_j

ここで[T^k]_jはT^kのj番目の列です。これらの列は32ビット整数として格納できます。なぜならT^k ∈ GF(2)^{32 × 32}だからです。したがって、スキップアヘッド方程式は、すべてのkステップに対して次のように並列に実装できます。

1. パックされた状態s^{(t)}を個々のビットs^{(t)}_jに分割します。これらを再び個別の信号として表します（左側の算術コンビネータ）。
2. 各s^{(t)}_jとすべての異なるベクトル[T^k]_jのポイントワイズスカラーベクトル乗算は、対応するk番目の状態のすべてのベクトルを含めるか、または含めないかのいずれかであるため、デサイダーコンビネータを使用して実装できます。ただし、今回は定数を別の定数コンビネータに格納します。これは一度に複数の信号を出力できます。1000ステップ先まで並列に予測することを選択しました。

［画像: 異なるT^k遷移行列からの同じ列。］

異なるT^k遷移行列からの同じ列。

3. これで、XORする必要がある32個のネットがあり、それぞれが32ビット幅の値k個で満たされています。以前とは異なり、ここでは暗黙の加算を使用できません。なぜなら、ベクトルは32個の異なる信号ではなく、単一の32ビット信号値で表されるからです。したがって、より多くの算術コンビネータを使用する必要があります。ここでは、ペアワイズでベクトルのXORを取るバイナリツリーを使用することを選択しました。これは、プレフィックスサム（これが該当します）の既知の高速削減戦略です。

［画像: 単一LFSRの並列ルックアヘッド］

単一LFSRの並列ルックアヘッド。

品質予測

これで、ゲーム内の実際の呼び出しが発生する前に次のRNG呼び出し結果を計算できるようになりました。これを目的のために使用可能にする必要があります。これは基本的に、ゲームのrollQuality関数の何らかの形式を実装することを意味します。以下に、擬似C++で実装された逆エンジニアリングされた関数のバージョンを示します。

// Fixedpoint value of the module effect from -32.768 to 32.767
// e.g. 10% quality would be a value of 100
typedef EffectValue int16_t;

// Stub of relevant quality prototype fields
struct QualityPrototype {
    ID<QualityPrototype, uint8_t> id;
    ID<QualityPrototype, uint8_t> next;
    double nextProbability;
}

// Mapping from the ID<...> to QualityPrototype
PrototypeList<QualityPrototype>::indexToPrototype;

// Function which determines crafting result quality
ID<QualityPrototype, uint8_t>* QualityPrototype::rollQuality(
  ID<QualityPrototype, uint8_t> qualityID,
  EffectValue bonus, 
  RandomGenerator* generator,
  IDIndexedData<uint8_t, ID<QualityPrototype, uint8_t>> 
    const* unlockedQualities
) {
  // If no bonus, do early return -> no RNG call!
  if (bonus == 0)
    return qualityID.copy();
  
  QualityPrototype* quality = indexToPrototype[qualityID];

  // Roll the RNG exactly once
  double roll = RandomGenerator::uniformDouble(generator);

  // If roll < threshold we upgrade to the next quality
  double threshold = (double)((float)(bonus) / 100f);

  // Find highest quality which beats the threshold
  uint8_t nextIndex;
  while ((nextIndex = quality->next.id.index) != 0) {
    if (!unlockedQualities->data[nextIndex])
      break;

    // Scale by next upgrade probability, base game = 0.1
    threshold *= quality->nextProbability;
    if (roll > threshold)
      break;

    quality = indexToPrototype[nextIndex];
  }
  return quality->id.copy();
}

ゲームでの関数の実装方法を見ると、基本的にRNGロールを取得し、いくつかのしきい値と比較しています。しきい値が超えられなくなるまで停止します。

これは、品質ロールを伴う各クラフトが正確に1回のRNG呼び出しを必要とすることを意味します。そして、各呼び出しについて、しきい値はゲーム中に一定であるため、期待される品質レベルを計算できます。したがって、算術コンビネータを使用してゲーム内で事前に計算できます。

［画像: ゲーム内でRNG状態から品質レベルを計算している様子。］

ゲーム内でRNG状態から品質レベルを計算している様子。

以下の計算機は、各品質レベルに必要なしきい値、および指定されたボーナスに対する各品質レベルの期待値を示しています。しきい値が2^{32}-1（uint32_tの最大値）を超えると、常にアップグレードされることに注意してください。これは、しきい値を括弧で囲んで示されています。

開始品質：

品質ボーナス（%）：

アダプター

やった！対応するゲーム内呼び出しが発生する前に、次のRNG呼び出し結果を計算できるようになりました。さて、それで何ができるでしょうか？私はすでに、これらの予測を取り込み、いくつかの面白いことをする、私が「アダプター」と呼ぶいくつかのものを実験しました。

最初に実装したものから始めます。

［動画］

クラフト前に品質レベルを予測します。

これは、将来の出力品質のシーケンスを取得し、テトリスの「次のピース」キューのように、アセンブラの隣に表示します。クラフトが完了するたびに、将来の出力のウィンドウを1つ進め、常に表示を関連性の高い状態に保ちます。

次に実装したのは次のものです。

［動画］

次のアップ品質によってアセンブラを選択します。

これは同じリストを取得しますが、次のアイテムを製造するために1つのクラフターのみを割り当てます。選択されるアセンブラは、次の出力品質によって異なります。これにより、5つのアセンブラがアイテムをソートされた順序で出力し、各ベルトは左から右に向かって品質が上昇する単一タイプの品質のみを運びます。

最後に、最初から興味があった目標、そしてこの投稿の冒頭で見られたフックです。

［動画］

伝説のアイテムの完全自動化。

この方法は、予測とクラフトループ全体を閉じたシステムにカプセル化しており、すべて（予測とクラフト）を自律的に実行できます。現在の状態を計算し、次のNN状態を予測する方法を見てきました。しかし、これがどのようにして望むRNG値を強制できるのでしょうか？

答えは最も単純です：直接はできません。

代わりに、RNG出力のシーケンスが決定論的であるという事実を利用できます。望むものより前に発生する必要のある悪いRNG呼び出しを消費することで、RNGを「強制」して、たとえば品質ロールコードで使用したときにコモンからレジェンダリー品質に即座にアップグレードするような値を次に出力させることができます。これには、呼び出しを消費する何かが必要です。

自動化可能な側面は、部分的なアイテムスタックの作成です。ただし、以前とは異なり、これらのクラフトの出力を観測することには関心がなく、各クラフトサイクルが生成する呼び出し数のみに関心があります。さらに、高速なクラフトサイクルは、秒あたりの呼び出し数を最大化します。

幸いなことに、多くの呼び出しを消費し、非常に高速なクラフト速度を持つレシピをすでに見てきました。スクラップリサイクルです。1回のクラフトあたり12回の呼び出しを消費し、基本速度は0.2秒です。これは完了したクラフトの数に適用されることに注意してください。生産性による完了したクラフトも同様です。これは、各リサイクラーの呼び出し消費率を無限のスクラップリサイクル生産性でスケーリングできる一方で、生産性の追加処理も必要とします。

［画像: ギアとスクラップを投入してRNG呼び出しをスキップするように制御された10台のリサイクラーのアレイ。］

スクラップとギアを消費して悪い呼び出しをスキップします。

スクラップの使用は、次の考慮事項により複雑さをもたらします。

• 複数のリサイクラーがあるため、各リサイクラーがどれだけスクラップを受け取るか、そして何台が追加のスクラップを受け取るかを把握する必要がありますか？後者は、最後のステージのアイテム数を減らすのに役立ちます。
• スクラップのリサイクルは、クラフトあたり12回のRNG呼び出しをステップしますが、これは正確な状態を解決するには十分な細かさではありません。必要な追加呼び出しの残りの数は、1回の呼び出しのみを消費するクラフトで埋められます。ここでは、これらはギアです。
• スクラップリサイクルの生産性により、単一の入力アイテムに対して複数のクラフトが完了することがあります。これにより、RNGは複数のレシピ結果、つまり12回の呼び出しの倍数に対してクエリされます。
• 各リサイクラーは、以前の生産性の進行状況をリセットするために、少なくとも1つのギアを最初に消費して開始します。これにより、それも追跡する必要がなくなります。

実装された正確な関数

正確な関数を実装するために、まずシミュレーションコードを記述し、次にAIに閉じた式を導出させ、それを簡略化してコンビネータに変換しました。関連するノートブックはこちらで見つけることができます。要するに、F(R, P, C) = (N_base, R_extra, C_rem)という関数が必要です。これは、R台のリサイクラーと生産性レベルPが与えられた場合に、任意の望ましい呼び出し数Cに対して、各リサイクラーが受け取るスクラップN_base、R_extra台が追加のスクラップを受け取る、C_remが消費される追加ギアの数、を計算します。

方程式は次のように書くことができます。

K_{target} = \lfloor C / (12R) \rfloor
N_{base} = \lfloor (10 K_{target} + 9) / (10 + P) \rfloor
K_{base} = \lfloor N_{base} (10 + P) / 10 \rfloor
\Delta K = \lfloor (N_{base} + 1) (10 + P) / 10 \rfloor - K_{base}
C_{gap} = C - 12 R K_{base}
R_{extra} = \lfloor C_{gap} / (12 \Delta K) \rfloor
C_{rem} = C_{gap} \bmod (12 \Delta K)

ここでKはクラフト完了数、\Delta Kは1回のクラフトが完了した場合のステップサイズ、Rはリサイクラーの数、C_{gap}/C_{rem}はRNG呼び出し数です。

考慮すべき追加の点が2つあります。まず、フォワードパスで同時に予測される呼び出しの数を増やすことはできますが、これはセーブ/ブループリントを肥大化させ、数千回の呼び出しを超えるとスケーリングしません。代わりに、最後の計算されたRNG状態の出力をRNGフォワーダーにフィードバックループで供給するだけで済みます。

［画像: シミュレータ入力にシミュレーションの出力をフィードバックしている2つのコンビネータ（右）。］

フォワードシミュレートされたRNGレジスタ（右）をシミュレータ（上）にフィードバックします。

最初の2つのアダプターは、品質予測モジュールの出力を単純に摂取できます。予測とスキップをある程度分離するために、2つのシステムを分離することにしました。既知の良いオフセットをバッファリングします。

これを行うために、以前と同様にしきい値を計算し、今度は異なります：関連する呼び出しインデックス/オフセットをフィルタリングし、それらのみを格納します。これは、合格した信号を新しい信号のシーケンスにマッピングすることによって行われます。各良好なオフセットに対して1つの信号/ティックで実行されます。この反復のすべての合格信号が消費されると、上記のフィードバックループがトリガーされ、次の1000ステップに進みます。

［画像: フィルタリングされた良好な品質呼び出しオフセットで満たされたバッファコンビネータのビュー。］

バッファはすべての「良好な」RNGオフセットを格納します。約1分後の予測状態。

このバッファは、RNGを最初に測定した時点からの絶対オフセットを格納するため、次のインデックスに到達するために実際にスキップする必要のある呼び出し数を計算する必要があります。これを行うために、バッファから現在のインデックスと次のインデックスを取得し、それらのオフセットを減算してデルタを取得します。このデルタは、実際にスキッパーに供給されるものです。スキッパーが現在のスキップサイクルを完了し、次のアイテムを作成した後でのみ、次のステップ数が取得されます。

［画像: バッファをインデックス付けする2つのセレクターコンビネータが、2つの隣接する呼び出しの差を計算しています。］

2つの隣接するバッファオフセットを減算して、スキップする呼び出し数を計算します。

最後に、シミュレートされたレジスタが実際のゲームRNG状態から逸脱する可能性があるという問題があります。例えば、私たちに知られずに他のプロセスがRNG呼び出しを消費した場合です。このような断続的な呼び出しを防ぐことはできませんが、少なくとも検出することはできます。この場合、予測は実際に観測可能なクラフト結果から逸脱します。したがって、結果が多すぎる（2つ）場合、マシンを自動的に再起動し、そこから将来の状態を転送することができます。

［画像: アセンブラ出力インサーターが右側のしきい値処理回路に接続されています。］

逸脱検出器と自動リセッター。

以下に、完全な状態での機械全体を示します。以前のセグメントに対応するさまざまなモジュールをハイライトしました。一般的なデータフローは、左下（アセンブラ）から時計回りに読むことができます。読み出し（ライム）、予測（青）、フィルタリング（黄）、バッファリング（紫）、スキップ（黒）。

［動画］

最終的な全体像、完全に自動化されたクラフター。

制限事項

さて、重要な部分です。あなたは疑問に思っているかもしれません。

素晴らしい！これで、私のセーブゲームで<insert RNG manipulation target>を実行できますか？

短い答えは次のとおりです。可能性は非常に低いです。

しかし、なぜでしょうか？私がこの技術を自分のために取っておきたいわけではありません。実際、ここにワールドダウンロード、ブループリント文字列、および関連するクリーンアップされたPythonコードがあります。いいえ、むしろFactorioが現在ランダムジェネレータを処理する方法に関係しています。

これについては、ゲームバイナリをもう一度見てみましょう。少し閲覧すると、Mapオブジェクトに遭遇します。これは、他のものの中でも、個々のサーフェス（つまり、Nauvis、Fulgoraなどの惑星のような世界のさまざまなレイヤー）への参照を含んでいます。しかし、RNGの状態はサーフェスごとに保存されるのではなく、マップ全体でグローバルに保存されます。そして、状態（複数形）について話していることに注意してください。なぜなら、ゲームには実際には複数のRNGがあり、それぞれがゲームのロジックの一部を担当しているからです。

Mapは特に次の6つのRNGを格納しています（pdbからの名前）。それぞれが何を担当しているか推測してみてください。

• Map.aiRandomGenerator
• Map.entitiesRandomGenerator
• Map.generalRandomGenerator
• Map.mapRandomGenerator
• Map.triggerRandomGenerator
• Map.unsafeRandom

正直に言うと、私はまだそれらのいくつかが何をするのか知りませんが、アイテムクラフト手順に関連するものだけに関心がありました。

追加のRNG

バイナリにはさらに多くのジェネレータがあります。現在見つけた上記以外の完全なリストは次のとおりです。

• GlobalContext.randomGenerator
• LightningMeshGenerator.random
• SelectorCombinatorControlBehavior.random
• SoundRandomizer.randomGenerator
• SpacePlatform.asteroidsRandomGenerator

すべてのRNGと、乱数呼び出しにつながる可能性のある呼び出しパスを追跡しようとして、バイナリニンジャとそのPythonスクリプトを使用して、RandomNumberGenerator::getInt呼び出しとその派生から始まる呼び出しツリーを抽出しました。スクレイピングに対応するスクリプトはこちらで入手できます。

ここでは、RNG操作の救いが見えます。すべてのランダム効果が同じRNGによって処理されているわけではないため、少なくとも一部をゲームロジックの残りの部分から分離できます。たとえば、バイターのスポーンと経路指定を担当するRNGは、私たちが関心のあるRNGとは別です。

特に、これはアイテム作成を担当するgeneralRandomGeneratorです。名前が示すように、これは一般的なランダムジェネレータであり、他のゲームロジックとの間にいくらかの重複があることを意味します。アイテム作成とは完全に無関係であるか、または確率的な出力を持つ他のレシピを介しています。これは、以前に話した非分離ケースの問題とまったく同じです。

まず、品質ロールに関連しないインスタンスの非網羅的なリストを次に示します。

• 床タイルの変更：MapGenerator::clearEntitiesAndSetTile関数は、バリアントからランダムに選択します。これは、エディターによる手動編集、凍結ロジックによるタイルの変更、タイルゴーストの構築、または宇宙プラットフォームによる床材の構築によって発生する可能性があります。
• 実験室や列車停止などのエンティティの名前のランダム化。
• プレイヤーが手動で鉱石を採掘（粒子生成）したり、ほこりの多い地面を歩いたり（ほこりの粒子を作成）。
• 一般的な粒子、つまりParticlePrototype::getRandomVariationとSmokeコンストラクタ。
• セレクターコンビネータは、ランダムなシードで独自のRNGを初期化します。
• 単一の鉱石タイルを持つ採掘ドリルは、残りのタイルをランダムにシャッフルして採掘します。
• Fulgoraへの稲妻。
• スパイダートロンが歩行時に脚を配置する。

次に、あらゆる種類のランダム性を必要とするすべてのマシンが同じRNGを共有します。私のマシンが予期しない他のレシピがRNGを使用するたびに（たとえば、Fulgoraのスクラップリサイクルライン、Nauvisのウラン処理、または他の品質ロールなど）、RNGの状態が変更され、予測が実際のゲーム状態から逸脱し、信頼性の高い操作が不可能になります。さらに、自動化に関するゲームでは、通常、大量のアイテムを生産するためにスケールアップするため、1秒あたり数千回の呼び出しが発生する可能性があり、RNGを十分に速く事前計算する私の能力を超えています。

上記のすべての/多くのランダムソースを考慮に入れることは可能かもしれませんが（たとえば、ロジスティクスグループなどを使用してランダムな呼び出しを行う他のすべての生産ラインを動的に無効にし、Fulgoraの昼間まで待つなど）、実際のゲームセーブに適用できる可能性があります。既存のセーブに後付けするのではなく、最初から考慮する必要があります。

誰かが試してみたい場合は、自由に試して、どのように/それが機能するか教えてください。

Factorio 2.1

Factorioの最後のメジャーアップデートでは、RNGの使用方法が変更されました。依然としてtaus88を基盤となるジェネレータとして使用していますが、アイテム作成ロジックの主要部分が根本的に書き直され、単一の呼び出しが複数のアイテム出力に再利用されています。

さらに、現在わかっている限りでは、決定論的であっても、後で必要になる可能性のある共有呼び出しフィールドを埋めるために、すべてのクラフト操作がRNGを使用するようになりました。これは、他のマシンが並列で実行できないことを意味します。なぜなら、それは常にRNG状態に干渉するからです。

さらに、ロールの共有のため、RNGを前方にスキップするためにスクラップリサイクルを使用することはもはや有用ではありません。なぜなら、リサイクルされたアイテムごとにRNGが同じ量だけクエリされ、スクラップリサイクルの生産性と多数の出力の処理がオーバーヘッドを大幅に増加させるからです。したがって、これは少なくともFulgoraに直接バインドされなくなった、より単純/安価なアイテムのリサイクルに置き換えることができます。

最後に、アップデートはまだ実験ブランチにありますが、RNGシステムに対するさまざまな変更を見て、ジェットコースターに乗っているような気分でした。ある時点で、Map::generalRandomGeneratorがFISHの動きを制御するために使用されていました。もちろん、これは大きな問題でした。なぜなら、マップ上のすべての魚が未知数のRNG呼び出しを生成することを意味し、新しい魚で新しいチャンクを生成することなく、すべての魚をマップから削除する（魚をすべて削除する）以外に、RNG状態が予測と継続的に同期しなくなるためです。幸いなことに、これは後のアップデート（バージョン2.1.13では削除されています）で、Mapオブジェクトに新しい7番目のRNG、Map::fishRandomGeneratorと呼ばれるものが追加されたことで解決されました。それが何をする仕事だと思いますか？:)

しかし、すべてが悪かったわけではありません。たとえば、スクラップリサイクルからの強制的な移行、および宇宙全体の信号の追加（Fulgoraの雷雨が他の惑星に開始されるのを送信できるようにする）により、特定の惑星に縛られることはなくなり、代わりにVulcanusにマニピュレーターを構築し、スキップに必要なリソースをどれだけ消費しても、RNGが正しい状態になったときに他の惑星にローカルレジェンダリーをクラフトするように信号を送信できるようになりました。

現時点では、ゲームはまだ実験段階であり、変更される可能性があるため、ここで終了します。次のアップデートで予告なくクラッカーの更新が壊れる可能性があります。

結論

これは2年以上続いたプロジェクトの完了であり、当初望んでいた完全に自律的なギャンブルなしの状態にようやく到達しました。もっとも、後半のほとんどは、この投稿を書き、公開するのを先延ばしにしていただけでした。その間に（私が足を引っ張っていた間）、他の人々もRNGを調査しており、参考のためにここにリンクします。

• @kovaxis：Factorioフォーラムで、観測されたゲーム内メカニクスからPythonスクリプトで状態が計算されるという、私が最初に到達したのと似た地点で停止しました。
• @d4s_over_dt4：Factorio Discordで、3つのセレクターコンビネータ（それぞれが一般RNGをクエリして独自のコンビネータ状態をシードする）から読み取られたRNG状態を計算するコンビネータ回路を構築しましたが、さらなる統合や検証はありませんでした。

この投稿には含まれていなかった多くの脇道がありました。たとえば、サブネットの処理を改善したcnideを、VSCodeのシンタックスハイライトと同様に、ドキュメントとシミュレーション目的で部分的に再現したり、行列計算のすべてをゲーム内で行った最初の実装試行（行列の作成とガウスの消去法を含む）6などです。

感謝の意を表します。

• @earthkenと共同で：彼らの「メス検出器」は、ゲーム内メカニクスのみを使用してMinecraftのRNG状態を読み取るという、このプロジェクトの知らぬ間にインスピレーションを与えてくれました。
• @redruin1：factorio-draftsmanライブラリにより、簡単な手続き型ブループリント作成が可能になりました。
• Binary Ninjaチーム：比較的巨大なfactorio.exeを処理するときに実際に機能する（Ghidraを見ているあなたへ）逆コンパイラを提供してくれました。
• 過去2年間、RNGについて私に繰り返し話を聞かせてくれた、私をこの執筆の完了に追い込んでくれた私の近くのすべての人々：)

---

1. Factorio Friday Facts #375↩
2. セキュリティ研究者にとっての「簡単に壊れる」とは、彼らがそれを壊す方法を知っていることを意味します。したがって、セットアップに時間がかかっても、それは簡単です。↩
3. このプロジェクトの部分で、体、環、モノイドなどが、ジェネリクスを使用したプログラミングの数学的バリアントにすぎないことを実感しました。これにより、必要なプロパティを満たす任意の型で動作するアルゴリズムを記述でき、プログラミングと同様に、名前はしばしばひどいですが…しかし、定着します：）↩
4. Factorioは、コマンドライン引数付きで実行することでデータをダンプする方法を提供しています。そのうちの1つは--dump-dataで、ゲーム内でロードされたプロトタイプを処理したJSONファイルを出力します。これは、さまざまなレシピを抽出するためなどのさらなる処理のために解析できます。ただし、draftsmanにバンドルされているデータを使用しました。↩
5. Factorioでは、複数のデバイスがワイヤに信号を書き込むと、ワイヤ上の結果の信号値は個々の信号の合計になります。これは、任意の合計が暗黙的に実行できることを意味します。↩
6. ゲーム内のガウスの消去法は、ワールドダウンロードにも含まれており、使用方法に関する指示があります。↩
7. Ghidraとは異なり、64GBのRAMでもゲームexeを正常に逆コンパイルするには十分ではありませんでした。↩