背景
对于以撒的随机机制（特别是伊甸生成机制）的研究历史悠久，最早可以追溯到十年前以撒尚处于Rebirth版本时BLouBLue的这三篇Reddit文章：
- The Birth of Eden - In-depth analysis
- RNJesus : An introduction on how RNGs are used and work in BoI:R
- RNJesus : Secrets behind pedestal item generation
这些知识是BLouBLue通过逆向以撒的代码获取的。虽然已经过去了十年，以撒的程序在Rebirth之后并没有重写过，因此这些知识对于最新版也基本适用。我对于伊甸和道具生成机制的研究就是在这几篇文章的基础上进行的。
我对以撒种子的研究是从高考前几天寻找里叁孙血权速通种子开始的。当时我还只会编写lua mod不断重开游戏来寻找种子，mod代码是根据Seed Finder改的。现在的找种子程序eden-seed-finder和四年前比起来已经可以说是天翻地覆了。
基础知识
虽然表面上看以撒的种子是8个字母/数字组成的字符串，去掉I/1，O/0，U/V，S/5这四组重复的组合，共能表达$32^8=2^{40}$个种子；然而其中有二进制8位是checksum，因此不是所有字符串都是合法的种子。实际上以撒的种子共有$2^{32}-1$个，用较少的算力即可全部遍历。
以撒里的每个玩家、楼层、房间、敌人、道具、饰品、基础掉落等等都有自己的种子。这些种子是从游戏的初始种子经过一系列计算得到，完全由初始种子决定；而且它们之间是相互独立的，基本不会有重复使用的随机数。游戏内绝大部分事件结果是由种子决定的。
研究方法
在Afterbirth+版本之后，以撒拥有了一套功能极为丰富的mod API，我们可以通过执行lua代码直接获取游戏中任何物体的种子。不仅如此，以撒的Rng（随机数生成器）也是完全公开的，是采用的XORShift算法，共有81套可能的Shift参数。这就让摸清这些种子之间的联系变得格外简单：只需要枚举Shift参数和Rng调用的次数，看看哪一套Rng调用结果会从一个种子生成另一个种子即可。比如从一层的StageSeed生成一个房间的SpawnSeed，可能是调用了4次第35号Rng，然后调用了2次第12号Rng。
而从这些种子产生随机事件结果的机制也并不复杂。根据已有的老版本Eden生成代码，容易看出以撒的随机事件结果就是某些Rng调用结果取模产生的。只需要随便开几局游戏，记录一下种子和随机事件的结果（比如记录Deck of Cards(卡牌盒)的种子和每次使用时产生的卡牌），通过枚举即可判断出到底是哪个随机数对几取模导致的。当然由于条件逻辑的存在，实际上搞清楚这些机制并没有上面说的这么简单，还需要在脑海里想象一下：如果你是以撒的程序员，你会怎么实现这个功能？往往直觉产生的答案就是以撒程序里实际发生的！
这些方法尽管威力强大，但并非万能。一个失效的例子是Baby Plum的爆炸动画：在忏悔V1.7.9a之后，该爆炸动画的出现概率被调整为了百万分之一。我们能通过实验和枚举获知爆炸动画出现的条件吗？当然是不能的，因为通过人肉重开游戏压根就不可能找到出现爆炸动画的种子，自然就无法进行判断。为了解决这些问题，我们别无选择，只能逆向工程以撒的源码。我使用开源软件Ghidra做到这一点。
由于以撒由C++编写，反编译代码的可读性要比杀戮尖塔的Java代码和其他一些游戏的C#代码低非常多。关键的突破口是以撒的日志文件log.txt，通过阅读日志可以将游戏中发生的事件与输出的字符串建立联系，而这些字符串是被明文存放在以撒的二进制文件里的（还好没有混淆），搜索调用这些字符串的地址就能把游戏事件和代码中的函数对应起来了。有些用实验方法难以获取的信息在反编译下变得极为显然，比如通过搜索Baby Plum爆炸动画的文件名gfx/promo/gfuel/effects/explosion_delayed.anm2，可以在附近的代码中立即发现判断条件：Baby Plum的InitSeed二进制后20位为0xdedbb时播放爆炸动画。
然而并非所有问题都是这么容易解决的。有一些很基本的游戏环节不仅不能通过实验理解，还需要阅读和理解大量的反编译代码才能完全复现，比如从道具的InitSeed产生道具编号的过程。由于道具池和权重的存在，这并非是简单的取模就能解决的。虽然有着BLouBLue研究的基础，我仍然用了数天的时间才破解了这个过程。
Rng
前面提到过，以撒用的Rng为XORShift（极少数情况为mt19937，如每个种子开始时shuffle道具池的过程，可能是由于使用了std::shuffle，Rng为mt19937）。81组可能的shift参数中，BLouBLue已经发现第60组是唯一一个周期不为$2^{32}-1$的；这个Rng甚至有0之外的不动点和2-周期点。可想而知，一旦使用这第60号Rng，对于恶意构造出的种子，产生的结果将会无法有效均匀随机。所幸，通过对于以撒二进制程序的搜索，目前完全没有发现第60号Rng的使用痕迹。
周期为$2^{32}-1$只意味着产生的结果足够均匀随机，并不代表Rng足够安全。实际上，如果把种子视为$\mathbb{F}_2$上的32维向量，XORShift就是一个可逆线性变换，可以使用$32\times 32$的矩阵表示。因此，以撒Rng的输出$\bmod 2$的结果线性递推长度仅为32，比标准库的rand()还要劣质。但毕竟我们是来玩游戏的，不是来研究密码学的，Rng的这一性质会带来许多有利的影响：
- Rng是线性变换，因此
Rng(a^b)=Rng(a)^Rng(b)。这导致忏悔版本的弯币（Crooked Penny）仅存在两套不同的结果序列（每个房间内结果是两个序列之一），而且这两套序列间还是存在关联的。这并非以撒里弯币代码的本意，而是Rng带来的问题：如果将Rng替换为mt19937等，弯币的结果将会随着房间和使用次数不可预测地改变。 - 从游戏的初始种子到每个道具、每层、每个房间、每个实体的Rng调用路径基本是固定的，因此可以预处理出初始种子到Baby Plum的种子的变换矩阵，对于每个游戏种子只需要计算一次矩阵乘向量。相比于大量的Rng调用，这样做让种子搜索速度提升了许多。
- 由于这一变换矩阵是一系列可逆矩阵的乘积，也是可逆的。我们直接预处理出变换矩阵的逆，乘上
0xdedbb，就得到了会让Baby Plum爆炸的游戏种子！避免了遍历$2^{32}$个种子。（这里只是一个简化版的描述，其实由于地形问题变换矩阵并非固定的，一层boss也并非一定是大可爱，但还是只需要枚举几十个种子就能找到一个） - 使用矩阵快速幂，通过$O(\log n)$次操作即可预知$n$次Rng调用之后的结果。如黄针（Experimental Treatment）为第240号道具，本来需要241次Rng操作才能生成黄针的道具种子，矩阵快速幂会大大降低用时。由于都是位运算，矩阵运算也极为高效。
伊甸生成
wiki上的Eden Generation页面有一个详尽的描述，其中有一部分是我编写的，此处就不再赘述了。
- 伊甸初始携带饰品的话就不会携带卡牌或者药丸；有2/3概率没有任何的金币/钥匙/炸弹，就算有的话也只有其中一种。
- 伊甸初始携带的卡牌已经被研究清楚了，可饰品和药丸没有。这一方面是由于饰品和药丸对速通的影响远小于卡牌，一方面是由于饰品和药丸的生成机制比卡牌复杂得多。其实饰品和药丸是与道具一样在道具池的逻辑中被处理的，而道具池是个很复杂的东西。
- 忏悔及忏悔+中，伊甸的攻速属性其实还没有被研究清楚。在AB+中常常出现攻速非常低的伊甸，而从忏悔开始攻速太低的伊甸受到了某种提升攻速的修改。这个修改目前还是未知的，由于我还没找到计算属性的代码。但这其实不是什么本质问题，大不了多开几局伊甸记录一下真正的攻速，然后用插值就能以够用的精度近似算出任何一个种子的攻速了。
- 在找毒种的过程中常常要求伊甸没有炸弹，且携带某个特定的道具。其实二者不是独立的，以某些道具开局的伊甸有炸弹的概率会远高于另一些！这本质上是由于忏悔的道具数量732是2和3的倍数，而确定伊甸基础数量的函数和确定伊甸初始道具的函数复用了同一个Rng。这是以撒中极为罕见的Rng复用导致的问题。
TMTRAINER
TMTRAINER在速通种子中扮演了极度关键的地位，因为错误道具可以拥有任何普通道具都无法达成的强力效果，如直接生成通关宝箱、永续超大蘑菇、无限giga bomb之类。实际上TMTRAINER道具一共只有$2^{32}-1$个，效果是由道具的InitSeed完全决定的，在不同局之中同一个InitSeed的错误道具效果完全相同。虽然我目前还不能从种子确定错误道具的效果，但REPENTOGON拥有确定错误道具效果的能力，在Lua脚本筛选TMTRAINER种子时可以使用REPENTOGON帮助。
未解之谜：地形
生成地形的代码已经被Blade研究过了，见Level Generation。可惜这些给出的信息都只是伪代码，并没有解释用到的Rng是怎么从游戏种子中产生出来的，因此对于我而言地形生成仍是一个未解之谜。不仅如此，对于找种子的人来说最重要的部分不是每层的布局，而是每个房间到底是什么房间，而这个页面里也完全没有解释。几个需要判断地形才能完成的找种子任务：
- Henry。出现概率极低，而且由于选择具体房间的机制不明，目前只能使用Lua脚本不断重开游戏来寻找，效率极低。
- 宝物房、boss房道具。各层的boss房道具基本固定，无论是走什么路线；然而有小概率会发现三层和水二的boss房道具不同，这是由于生成地图所使用的尝试次数不同。想要精准算出boss房道具，就需要获取生成地图用的循环次数，否则只能大概率算对boss房道具。宝物房道具则不仅受到生成地图所需循环次数的影响，还受到具体宝物房种类的影响，不同的宝物房地形大概率过的随机数个数不同。这就是为什么alt path和主线的宝物房道具大概率不同，但也有远超理论值的相同概率，因为不同地形过的随机数个数也偶尔是相同的。
- 星象房。虽然只有1%的概率开启，可根据以撒的种子总数，极大概率能找到一个6层至少开了5个星象房的种子。一层就拿到Telescope Lens饰品并且后面七层全都开了星象房的种子也基本上是存在的。但由于地形还没法判断，目前这些都只是妄想。
他山之石：杀戮尖塔
杀戮尖塔作为另一款相当受欢迎的Roguelike游戏，和以撒一样有发达的筛种子现象。杀戮尖塔是用Java写的，反编译极为简单，和直接看源代码没啥区别。正因如此，虽然杀戮尖塔是个比以撒年轻的游戏，但代码中的机制基本都已经被研究透了。
由于广泛存在的Rng复用机制，和以撒不一样，杀戮尖塔的随机数并不是那么随机。虽然尖塔很多地方代码写的是一坨，但并非完全没有可取之处：尖塔使用的Rng是xorshift128p，这虽然也不是什么密码学安全的玩意，但比起以撒的32位线性xorshift还是高到不知道哪里去了。这导致杀戮尖塔的找种子代码无法从随机事件的结果直接反推出游戏种子，只能老实地挨个枚举种子；不仅如此，杀戮尖塔的种子还是64位的，枚举全部的种子是目前人类算力无法实现的，故无法像以撒一样从一局游戏的视频里算出游戏种子是什么。
由于这些和以撒不同的特点，杀戮尖塔的roll种器和以撒长得完全不一样：cuda-the-spire使用GPU的算力帮助加速枚举种子这一天生高度并行化的过程，从而能够处理远超过以撒种子总量的种子。尖塔的开局选项、地图、战斗选牌、遗物等等全部信息都可以在roll种器里完成判断，因此不需要在游戏里写mod筛选。各个筛选条件还根据通过概率和筛选所需时间被按照最优的次序排列。作为大规模的整数运算暴力搜索，说句实话这完全就是不赚钱的GPU挖矿。
所以以撒的roll种需要GPU吗？目前暂时还是不需要的，因为普通CPU上的多进程计算足以在短时间内遍历完全部种子。然而随着道具池、地形生成等高耗时环节被逐渐加入roll种器中，可能将来以撒也会需要GPU筛选种子。
