「Factorio」の乱数生成器を解析して「レジェンド品質のアイテム」が出る未来を予測する試み

工場建設ゲーム「Factorio」の拡張コンテンツ「Factorio: Space Age」には、製造したアイテムの性能がランダムで上昇する「品質」という仕組みがあります。コンピューター科学を専攻する大学院生のGegell氏はFactorioが使う疑似乱数生成器をリバースエンジニアリングし、ゲーム内の回路だけで乱数の内部状態を割り出して将来どのタイミングで高品質アイテムが完成するのかを予測する仕組みを構築しました。さらに不利な乱数を意図的に消費し、最高品質の「レジェンド」が出るタイミングまで乱数列を進める自動化にも成功したとのことです。

Reversing Factorio's RNG
https://gegell.github.io/posts/factorio-rng/

Factorioの品質システムではアイテムや設備にノーマル、アンコモン、レア、エピック、レジェンドという5段階の品質が用意されています。品質が上がると組立機の製造速度が向上したり、インサーターの動作が高速化したりと性能が強化されます。製造設備に「品質モジュール」を取り付けると一定確率で材料より高品質な製品が作られ、さらに上の品質へ一気に上昇する可能性もあります。

高品質アイテムを大量に入手したければ、品質モジュールを搭載した設備で製造を続け、目的の品質にならなかった製品をリサイクラーに投入するのが基本です。Factorio公式も大量生産では品質の出現が「統計」の問題になると説明しており、通常は大量の資源と時間を投入することでレジェンド品質を狙うことになります。

Factorioで使われる「乱数」は完全に予測不能な値ではなく、一定の計算規則から乱数らしい数字を作る「疑似乱数生成器(PRNG)」によって生み出されています。つまりアルゴリズムと内部状態の両方が分かれば、今後出力される乱数を計算できるというわけです。

Gegell氏はまずFactorioの元開発者が2014年に投稿した情報から「taus88」という疑似乱数生成器が使われている可能性に着目しました。さらにFactorioに付属するデバッグ情報を利用してゲーム本体を解析。GhidraやBinary Ninjaといった逆コンパイルツールでコードを調べた結果、Factorioの乱数生成器が3つの「線形フィードバックシフトレジスタ(LFSR)」を組み合わせたtaus88であることを確認しました。LFSRはビット列を一定の規則で移動させながら新しい値を作る仕組みで、処理が非常に高速な一方、十分な出力を観測すると内部状態を数学的に逆算できる特徴があります。

そこで問題になるのが、ゲーム画面からどうやって乱数の出力を観測するのかという点です。Gegell氏が選んだのは「リペアキットのリサイクル」でした。Factorio 2.0ではリペアキットをリサイクルした際の結果から乱数について効率よく情報を取り出すことが可能で、1回のリサイクルから2ビット分を観測可能とのこと。44回リサイクルして88ビット分の観測結果を集めれば、乱数生成器の有効な内部状態を再構成できるそうです。

内部状態を取得した後は、あらかじめPythonで計算しておいた行列をFactorioの回路に組み込み、Factorioの回路部品を使って未来の乱数を計算します。Factorio 2.0の品質判定は製造1回につき乱数を1回取得し、乱数を品質ごとに設定された基準値と比較することで完成品の品質を決めていました。そのため未来の乱数が分かれば「次の製造はノーマル」「数回後にはレア」「さらに先でレジェンド」といった予測も可能になります。

Gegell氏は予測結果を実際の工場で利用する仕組みも作りました。以下の画像では予測された品質に応じて使用する組立機を切り替え、品質ごとに異なるベルトへ製品を送り出しています。

そして最終的に作られたのがレジェンド品質のアイテムを自動生産する設備です。予測した乱数列の中からレジェンド品質になる位置を探し、それ以前に並んでいる不要な乱数を別の処理で消費します。Factorio 2.0では廃材のリサイクルが短時間に多数の乱数を消費できるため大まかに乱数列を進め、残りを鉄の歯車のリサイクルなどで調整。狙った乱数が次に来た瞬間、本命のアイテムを製造する仕組みとなっています。

なお、実験版として公開されているFactorio 2.1ではアイテム生成時の乱数処理そのものが変更されてFactorio 2.0向けに作られたGegell氏の装置は使用できなくなっています。Gegell氏によると基礎となるtaus88は引き続き使われているものの、1回取得した乱数を複数の出力で共有するようになり、品質に関係しない通常の製造でも乱数が消費されるようになったとのこと。

Gegell氏はFactorio 2.1について、新たに追加された惑星間の信号を利用して別の惑星で不要な乱数を消費し、狙ったタイミングで高品質アイテムを作る構成も考えられると述べています。ただし、Gegell氏はFactorio 2.1が今後さらに変更される可能性もあるため、乱数予測装置の更新についてはひとまず様子を見るとのことです。