逆向Factorio的RNG，预测未来
Reversing Factorio's RNG
Factorio引入物品品质机制后，官方称其本质是统计学问题。但我发现，作为确定性游戏，它使用的伪随机数生成器（PRNG）并非真正的随机。通过逆向工程，我确认游戏底层使用的是Boost库中的taus88生成器，它由三个线性反馈移位寄存器（LFSR）组合而成。LFSR在数学上具有线性特性，这意味着只要掌握其算法和内部状态，就能精确预测未来的随机输出。我利用Ghidra和Binary Ninja反编译游戏二进制文件，验证了这一猜想，并成功在Python中复现了状态更新逻辑。现在，我们可以在游戏运行时同步计算，提前预知哪些物品会获得高品质。
如果我们知道确切的算法及其内部状态，就可以运行相同的算法并获得相同的输出，从而预测游戏中即将发生的“随机”事件。
HN 评论区
48- PennRobotics
Stardew Valley 有两个随机数种子。一个是普通的角色种子。另一个是你的多人游戏 ID，可以通过分析存档文件来确定。
不过！在 Switch 上，你无法轻易访问存档文件，而且其随机数生成器（RNG）也与 PC 版不同。有一个种子破解工具会查看你的旅行商列表并计算出角色种子。也许是因为它没那么重要且更难观察，我还没找到能破解另一个种子的工具，也没时间自己尝试编写。
通过检查已破解的晶洞内容，你应该能够分离出你的多人游戏 ID，然后像 PC 玩家过去十年通过访问存档文件所做的那样，在 Nintendo 上预测随机事件。
游戏的 C# 代码在线可查，且 Switch 的 RNG 机制已知，所以你永远不必在黑暗中摸索。只需三步：首先通过测试常规种子来确保你的 Switch RNG 实现有效；其次通过测试 PC RNG 来确保你的晶洞 RNG 实现有效；最后将 Switch RNG 应用到晶洞函数上足够多次，直到只有一个种子能生成你观察到的序列。
-----
两个半相关的开放性问题：你是否能像从第一个晶洞开始破解那样，从任意晶洞开始同样快速地解决？RNG 最终是否会循环，以至于你的多人游戏 ID 其实并不重要，只要你观察到一个独特的序列，因为该序列只有一种可能的延续？
- Aardwolf
> We chose taus88 mainly because it is the fastest from boost’s generators.
这是一个 1996 年的 RNG。看来无论是最近的 C++ 标准还是 boost，似乎都不知道那些既快得多又能更好通过测试套件的现代 PRNG。
编辑：好吧，上面的引文是 2014 年的，而且 boost 现在似乎知道一些了！https://www.boost.org/doc/libs/latest/doc/html/boost_random/...
- cmovq
我不喜欢 boost 的原因之一就在第一个代码示例中。把本质上只是一个 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;
- renyicircle
对我来说最酷的一点是，这不仅仅是逆向工程 RNG 并能够预测随机投掷结果（对于该 PRNG 算法来说相对简单），而是能够利用组合器网络（combinator networks）在游戏中实现该算法。组合器本身已经能做出很多惊人的事情，这是一个绝佳的例子，值得加入清单。
- torvin92
Factorio 已经够让人上瘾了，现在我们居然能预测矿脉分布了！我的睡眠时间表已经彻底毁了。