源文档：https://docs.google.com/document/d/1stTJAjLmCXtqctdFOpuv4lylegcmfO8mFrptFtwqb78/edit

本机翻pdf版百度云链接: https://pan.baidu.com/s/1tqPu5A0oFCjNEB-4b3P2uA?pwd=1234

提取码: 1234

这个项目的目标是在Minecraft游戏中用红石完全逆转并模拟一个特定的随机器，即Math.random。

以下是使用Math.random的所有事物的完整列表，突出显示的部分是我们正在使用的重要部分：

以任何方式创建任何类型的生物实体，包括通过正常生成、加载或维度更改产生的玩家、怪物和盔甲架。（3次调用）

当实体受到攻击时，计算击退力。（可变次数的调用）

实体破坏物品时产生的粒子。（5次调用，每个粒子一次）

实体进食时产生的粒子。（可变次数的调用，每个粒子一次。如果完全吃掉一个普通食物物品，46次调用）

以任何方式创建物品实体。（4次调用）

以任何方式创建经验球实体。（4次调用）

TNT随机角度。（1次调用）

液体混合以生成石头、圆石或黑曜石。（16次调用，每个粒子两次）

用桶在下界尝试放置水。（24次调用，每个粒子三次）

当平均获得的经验值严格在0和1之间时，从熔炉输出槽中拿取物品。（1次调用）

在怪物生成算法中，生成怪物群的大小。（每个群1次调用）

逆转

这个过程的这一部分逆转了Math.random的当前种子，这样我们就可以预测所有未来（和过去，但谁在乎）的Math.random值。可以使用7个TNT实体的随机角度，这些实体已经从中心爆炸到半径为120个方块的圆上（以夸大角度），在那里角度可以被检测到大约1个方块的分辨率。

线性同余生成器（LCGs）背景知识

一般的LCG是一种随机数生成器（RNG），它具有与生成器当前输出相同的内部状态（“种子”），并在每次调用后按以下公式更新其种子：

其中a、b和m是精心选择的常数，用于产生类似随机的序列。在Java中，这些常数的值为a=25214903917,b = 11,m = 2^48，尽管输出被截断为最多只使用顶部32位。这使得Java LCG的内部状态长度为48位。

尽管Java选择了好的参数，但所有的LCG都不可避免地存在一些共同的弱点：

低位具有高周期性（即它们的序列倾向于更频繁地重复自身）；这就是为什么Java只返回高32位，但在某些情况下仍然可以利用（尽管我们不打算使用这个）。

如果你取一个n×n的矩阵，其行是模数为m的LCG的连续调用，并取其行列式，那么这个行列式总是具有k×m^(n-1)的形式，k属于整数集Z。如果k等于1，这些向量就生成了LCG可以生成的所有点（参见第3点）。

如果你用LCG在二维空间或更高维空间中绘制点，它会形成一个点的格子（像一个倾斜的网格），这看起来一点也不随机。正是这个格子，我们将在这次逆转中利用。

像我是本科生一样解释非正式的格子LCG逆转数学描述

（如果你不喜欢数学，可以跳过这部分，但如果你想了解Matthew说的任何事情，请阅读）。

这一部分需要一些线性代数的背景知识。如果你的线性代数基础不稳，我建议观看3blue1brown线性代数系列（译注：b站链接）的前几个视频。

以一个简单的LCG为例，我们将使用连续的两个伪随机数来逆转LCG的种子。实际上，我们使用的是一个更大的LCG的7个连续输出，但这很难可视化，所以我们将坚持这个简单的例子——它的工作原理是相同的。

我们的迷你LCG将具有参数a = 5,b = 3,m = 8。从种子0开始，我们的随机数序列是（如果你愿意，你可以自己验证这一点）：0,3,2,5,4,7,6,1,0,⋯ 因此，连续调用的对是：(0,3),(3,2),(2,5),(5,4),(4,7),(7,6),(6,1),(1,0)。我们将这些点绘制在一张图上：

这是一个格子，正如你所看到的，它一点也不随机。那么，假设我们想要找到一个种子，它可以产生两个连续的随机数大于或等于5。在图上，每个点的x坐标是第一个随机数，y坐标是第二个随机数。所以我们可以绘制一个框，表示我们想要在其中搜索的不等式：

从图中可以很明显地看出解决方案会是什么，但请记住，这只是一个在二维空间中过于简化的LCG。

在平面平移之后，使得这个格子上的一个点位于原点，这样一个格子可以由两个基向量来描述，这样任何在格子上的点都可以通过添加这两个向量的整数倍来到达。在这个例子中，我将把H点平移到原点，然后选择基向量(1,5)和(0,8)。见下图。

现在，你应该能很容易地看到，可以应用一个逆线性变换，将这些基向量变成两个单位向量î和ĵ；我们将平面上的每个点向量v乘以行向量：

经过逆变换后，我们的格子变成了这个样子：

你可能会想，进行这个变换的意义是什么，问题看起来和以前一样困难。你是对的；这是因为我们一开始选择了较差的基向量。不过，你应该注意到，现在与之前不同的是，我们的不等式平行四边形内唯一的整数坐标是点F，这正是我们要寻找的点。这是因为我们已经将格子转换为整数坐标（两个新基向量的整数倍将我们带到整数坐标的任何地方）。

那么我们如何选择更好的基向量呢？让我们明确一下我们想要的。我们希望尽可能少地搜索整数坐标，所以我们希望我们的基向量在大小上大致相等，这样一切都会更加均匀地收缩。这对应于大致正交的基。有一个算法，LLL缩减，它接受我们的两个原始基向量，并对它们进行这样的处理。我不会在这里详细介绍，但维基百科有一篇很好的文章。经过LLL缩减后，我们的基向量变成了这样：

在应用逆变换后，它看起来是这样的：

你可以看到这使得问题变得容易得多，尤其是在更高的维度（更多的连续调用）和更复杂的LCG中。有足够好的基向量，在平行四边形上找到整数点可以简单到取点的地板值。

在找到这个平行四边形内的点F后，你只需重新应用基向量的变换，并平移回去，使H回到(1,0)而不是原点，然后，因为对于LCG，种子和输出是相同的，选择结果向量中的第一个数字，你就得到了你的种子。

我想提到的最后一件事是，调用不必是连续的，只要在你的两个值之间有一个已知的常数调用次数。这是因为，如果你取LCG的每一个其他调用，那相当于使用一个新的LCG：

因此，新的LCG具有参数(a^2  mod m,ab+b mod m,m)。对于任意数量n的连续调用，你可以继续形成一个LCG (a^n  mod m ,b×(a^n-1)/(a-1) mod m ,m)。

实践中的逆转

我们使用7个TNT的随机角度，通过半径为120的圆中的692个探测器进行检测。

一个探测器仅在TNT爆炸的tick被触发。探测器是一个触发器，TNT实体在爆炸前的砖块tick阶段与其相交。在此之前，围绕圆周的触发器将被物品实体触发，计时使得触发器在此砖块tick阶段检查相交实体，导致正确的触发器额外激活10个tick。在多个触发器仍然被激活的可能情况下（即TNT在两个探测器之间爆炸），我们取逆时针方向上的探测器，并说它被激活。

探测器对应于TNT可能被发射的角度范围。角度由Math.random() ×2π计算，Math.random的实现就像：

其中next(x)表示使LCG前进一位并取最高的x位。

因此，种子的最高26位与TNT发射的角度成离散比例，允许我们将探测器与种子范围对应起来。此外，探测器n的上限角度是探测器n+1的下限角度；如果给定的角度给出了next(26)的上限，那么上限种子值必须是具有那26位的最高种子值，即剩余的22位都是1。下一个探测器的下限具有相同的26个上限位，但是下限的22位都是0。

使用这些种子范围，我们可以形成一个表示这些范围的7维超立方体，并按照上述方法逆转种子。

Matthew在这里写了所有的东西

将LCG的n个连续种子作为n维空间中的点的坐标，揭示出一个晶格状结构，经过原点平移后，该结构在加法下与Z^n同构。通过用LLL-约化基向量表示这种同构关系的线性变换，我们可以有效地利用变换的逆矩阵将我们晶格的任何不等式系统表示为Z^n上的不等式系统。我们的机器产生7个值，它们的上限和下限是可能使TNT落在触发探测器上的种子，这些值可以转换为Z^n上的不等式系统。通过使用足够大的探测器并在射击之间有意调用LCG，我们可以在数学上保证只有一个Z^n元素能满足新转换的不等式系统（通过寻找正交程度足够的晶格，使与我们的不等式相对应的区域收缩到适合一个单位立方体内）。对Z^n这一点的变换进行反转并平移空间，再次与原始晶格对齐，揭示出每次射击时的7个种子。

具体而言，正在进行的计算如下所示：

请注意，通过樱桃挑选每个乘法的上限或下限，(v-b) M^(-1)可以得到一个点，其每个分量必然大于真实值。因为我们选择的晶格总是在每个维度上距离真实值小于1，所以只需对每个分量取地板值就可以得到所需的Z^n点。在实践中，所有可以预先计算的计算都已经完成，因此这个描述并不准确地表示机器实际上所做的计算。

校对：小灰灰

遵循知识共享协议CC-BY-NC-SA