Factorioの乱数をリバースエンジニアリングして品質クラフトを予測する
Reversing Factorio's RNG
Factorioの品質システムは乱数に依存しているが、その中身はtaus88という3つのLFSRを組み合わせたPRNGだ。ゲームバイナリとデバッグシンボルを使ってアルゴリズムを特定し、内部状態を再現すれば、次にどのクラフトで高品質アイテムが得られるかを事前に知ることができる。線形代数の基礎があれば理解できる、実践的なリバースエンジニアリングの記録。
もし正確なアルゴリズムとその内部状態が分かれば、同じアルゴリズムをその状態に対して実行するだけで、ゲーム内部で見られるのと同じ出力が得られる。
HNでの議論
44- PennRobotics
Stardew Valleyには乱数シードが2つある。1つは通常のキャラクターシード。もう1つはマルチプレイヤーIDで、これはセーブファイルを解析することで特定できる。
ただし！Switchではセーブファイルに簡単にアクセスできない上に、乱数生成器がPCとは異なる。トラベリングカートのラインナップを見てキャラクターシードを計算するシードクラッカーは存在する。おそらく重要度が低く観察も難しいためだろうが、もう一方のシードをクラックするツールは見つかっていないし、自分で書いてみる時間もない。
クラックしたジオードの中身を調べれば、マルチプレイヤーIDを特定でき、PCプレイヤーがこの10年間セーブファイルへのアクセスでやってきたのと同じように、Nintendo上でもランダムイベントを予測できるはずだ。
ゲームのC#コードは公開されているし、Switchの乱数生成器も知られているので、闇雲に作業する必要はない。手順は3つ：Switchの乱数生成器実装が正しく動くことを通常シードでテストして確認し、ジオードの乱数生成器実装が正しく動くことをPCの乱数生成器でテストして確認し、そしてSwitchの乱数生成器をジオード関数に、観測した数列を生成しうるシードが1つだけになるまで十分な回数適用する。
-----
半ば関連する未解決の疑問が2つある：どのジオードから始めても、最初のジオードから解くのと同じ速さで解けるのか？乱数生成器は最終的に繰り返すのだから、ユニークな数列を観測さえすれば、その数列の続きは1つしかないので、マルチプレイヤーIDが何であれ実際には関係ないのではないか？
- renyicircle
私にとって一番クールなのは、乱数生成器をリバースエンジニアリングしてランダムロールを予測できるようになること——これはそのPRNGアルゴリズムにとっては比較的簡単だが——だけでなく、そのアルゴリズムをコンビネータネットワークを使ってゲーム内で実装できることだ。コンビネータでできる驚くべきことはすでにたくさんあるが、これはそのリストに加えるのにふさわしい素晴らしい例だ。
- cmovq
boostが嫌いな理由の1つは最初のコードサンプルにある。分解出力に示されているような、要するに10行の関数をこんな風に実装する意味がどこにあるのか
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;
- Aardwolf
> 我々がtaus88を選んだ主な理由は、boostの生成器の中で最速だからだ。
それは1996年の乱数生成器だ。最近のC++標準もboostも、テストスイートをよりよく通過しつつはるかに高速な現代のPRNGについて何も知らないようだ。
編集：ああ、上の引用は2014年のもので、boostは今ではいくつか知っているようだ！ https://www.boost.org/doc/libs/latest/doc/html/boost_random/...
- torvin92
Factorioが十分中毒的でなかったかのように、今では鉱石パッチまで予測できるのか！私の睡眠スケジュールはもう台無しだ。