一个数字永远重复：在NSMB中RNG（2020）

你好！已经有一段时间了，没有。抱歉耽搁了。这些帖子有时需要很长时间才能放在一起，因为这个博客不是我的最高优先级，我尝试向每个博客添加自定义多媒体。尽管如此，我已经有了一些未来的作品帖子，因此您可以在未来几个月期待更多。

反正！这是一种关于新的超级马里奥兄弟的绿色蟾蜍房子迷你ame的一个“部分0”。迷你游戏涉及随机性，因此在研究它时，我调查了NSMB的随机数发生器（RNG）。我的发现没有与迷你游戏非常相关，但他们自己的权利很有意思。

为了让这太长，我假设你已经知道了一个RNG是什么，以及播种一个的概念。如果没有，这里有一些很好的资源：youtube上的Pannenkoek2012（SM64），YouTube（SMW），维基百科解释了复古游戏机制。

要启动，这里是NSMB的随机数生成器的手动解答，我通过执行决策命名“rand_nsmb”：

UINT32_T RAND_NSMB（UINT32_T *状态）{UINT64_T值=（UINT64_T）（*状态）* 1664525 + 1013904223;返回*状态=值+（值＆gt;＆gt; 32）; }

想试试rand_nsmb？你可以在这里做到这一点：UINT32_T状态=;

一个RNG功能，其中下一个输出计算为先前的输出时间一些常数，另外常数，称为线性总体生成器。上面的功能几乎是LCG。唯一一个不合格的唯一部分是最后的+（值＆gt;＆gt; 32）。

每当你找到一个具有奇怪的大常量的未知代码时，你通常可以通过谷歌入他们来学习很多。如果您搜索1664525和1013904223，您会发现它们在LCG函数1中非常常用，最初发布在书数数字配方中。这本书根据这两个数字“RANQD1”（对于“随机快速和肮脏的生成器＃1”）命名LCG函数。我将在此处使用此LCG的该名称。

例如，这里的实施是RANQD1的实现（未直接从书中复制）与上面的RAND_NSMB的格式相匹配：

UINT32_T RANQD1（UINT32_T *状态）{UINT64_T值=（UINT64_T）（*状态）* 1664525 + 1013904223;返回*状态=值; }

据我所知，NSMB＆＃39;在游戏启动时播种RNG的程序是声音。它收集了各种来源的熵，包括在迄今为止加载游戏的时间，当前扫描线号，GPU状态，持有的任何按钮以及更多。然后它需要一个哈希1的哈希，并且XORS到32位整数。鉴于这一点，我认为它是安全的，安全地假设这种分析是均匀分布的种子值。

已知RANQD1具有在循环2（“完整周期”）之前每32位整数的非常好的属性（“完整周期”），并且通常（引用数值配方）“与任何32位线性总体发生器一样好”。

所以NSMB的RNG函数只是Ranqd1 - 一个体面的LCG - 具有较小的变化。 Nintendo在返回时添加否则将在隐式投用到UINT32_T期间将被截断的位。在表面上，这感觉就像它应该是一件好事 - 而不是失去某种随机的信息，现在正在循环回收！

但这是问题：随机数生成是你应该认真对待尝试和真正公式的那些事情之一，除非你真的知道你在做什么。随着我们很快看到的，这种变化最终会带来更多的问题而不是福利。

我之前提到过，在循环之前，每32位整数循环一次ranqd1周期。通过NSMB的修改，此属性并不一定仍然存在，因此我决定对Rand_NSMB的循环进行相当彻底的分析。

我写了一个C程序，它在每个32位整数上迭代，将每个1插入RAND_NSMB，然后遵循RNG值的结果跟踪，直到它达到重复。这种情况很好地借助动态编程，所以我有程序填写有关每种种子的信息（它最终循环，它需要多少步）进入相当庞大的20 GB数据表文件。即使文件在我的笔记本电脑内部SSD上存储过的文件，该程序也花了大约两周时间才能完成运行。一旦完成了，我就可以通过用Python线性读取（大约需要大约半小时3）和计算统计信息，通过线性读取来回答很多问题。

让我们先看看平均案例。给定随机开始种子，rand_nsmb平均将在1,820,529次呼叫后重复输出。虽然这是从4,294,967,296呼出的呼唤来获得RANQD1重复一个数字，但它仍然绝对充足了这样的视频游戏。

我发现更有趣的是检查最糟糕的情况。如果在启动NSMB之前在梯子下方打破了镜子，您可以最终进入一个循环的距离？嗯，这是所有1653个rand_nsmb周期的列表，按长度排序，以及显示进入它们的状态的饼图：

大约¾所有国家排队到最大的周期，这是170万州的州。以下是一堆逐渐更小的循环，具有类似地缩小的饼图。我不知道为什么为什么有这么多的周期恰好8个元素，但这并不重要。

看看列表的底部。有12个循环4州长（从此“4-循环”），2周期和......一个循环。

在这里，它是：1144735523.您可以使用早期的互动rand_nsmb小部件来检查它 - Rand_nsmb（1144735523）返回1144735523.4

为了使它有温和，可以吐出一遍又一遍地的随机数发生器并不理想。 将NSMB与其RNG功能卡在一个号码上粘在一起？ 虽然你只需要启动的比赛，但是通过黑客攻击实现它的90％才能获得90％的击中rand_nsmb的概率，这是一个微小的比特。 您可以使用此NSMBE代码修补程序来执行此操作。 我像这样踢过整个游戏。 以下是我发现的一些亮点： 您的浏览器并不支持HTML5＆lt;视频＆gt; 标签。 :(要查看我的动画，请尝试在浏览器中查看此页面！ 瓷砖不是随机（最左边的动画）。 这影响了大多数层次，但在1-2开始时尤为明显。 某些声音效果不是随机化的。 Mario将始终使用相同的语音夹，而不是跳跃时，而不是从几个中随机选择。

绿色蟾蜍房屋的解决方案总是相同的。并巧合5恰好匹配Toadsworth将卡片放入块的顺序。

管泡从单点排出（中间动画）。通常，它们沿着管边缘的各个点排放。

一些具有不可预测的攻击模式的敌人变得可预测。具体而言，Skeeters，Hammer Bros和Sledge Bros - 谁在谁永远不会再次完成。

大动物园植物，当用火杀死时，以不自然的方式发出硬币（最右边的动画）。他们都像喷泉一样在各种方向上喷出硬币，而不是喷出硬币。

...尽管在其代码中有超过600个不同的RNG呼叫，但NSMB不能以直接影响游戏的方式非常大量使用随机性。所有的事情都考虑，这可能是最好的。

我想提醒您，虽然通过黑客攻击游戏获得以上素材和信息，但这是一个非常真实的错误，因为非零概率可以自然地发生。这让我想知道......我们可以估计实际经历过的玩家的数量吗？

总共5种种子值6导致Rand_NSMB的定点，这意味着您在任何给定的游戏启动上遇到它的几率（5 / 0x100000000）≈0.0000001164％。

截至2020年3月，新的超级马里奥兄弟已售出30.80万份副本7.作为粗略估计，让我们平均地说，购买游戏的每个人都推出了10次。然后，总的来说，NSMB已经启动了...让我们绕过3亿次。

没有人经历过这种定点的可能性是（1 - 0.0000001164％）300,000,000≈00％，这意味着至少有一个人遇到的30％的几率。

有人不幸的是30％的几率足以获得固定点并不是那么高的。但是，如果您还计算了导致2周期的10种种子（您应该 - 在两个值之间循环几乎是可怕的），那么至少有一个人经历了65％的机会。如果您进一步包含导致4周期的240种种子......它有效地保证（99.99998％）某人，某个地方，已经出现了一个异常糟糕的rng种子。

这种手动分析是有效和有趣，我甚至注意到了与可分性有关的一些违规行为，但专业人士通常不会分析这样的随机数发生器。专家使用统计测试检查大量不同的东西。为了获得一些更严格的结果，我通过Dieharder自动化RNG测试套件ran Rand_NSMB。

现在，线性总体发电机旨在快速，而不是通过每个统计测试，因此只需查看测试套件兰德_NSMB通过的百分比而不将其与某事物进行比较。为此，我正在使用原始的ranqd1函数，它是基于的。这让我们直接衡量了任天堂代码变更的影响。

所有测试都基于单个初始种子（0），因此我讨论的小周期问题并没有反映在结果中。 0进入最大的rand_nsmb优惠，因此这种选择尽可能慷慨。

在我的笔记本电脑上运行测试花了一点点。完整的结果可在此处提供。左侧的图表总结了通过的测试数量。你可以将悬停在它上面看数字。

对于Rand_NSMB的信用，它以114个测试中的35个（31％）优于Ranqd1（31％），因此函数似乎以某种方式对原始的改进。但仍然，看着整个结果......似乎很明显它通常表现更糟。

没有人玩新的超级马里奥兄弟。将注意或关心其随机数发生器失败一些模糊的统计测试，也不应该是它们。 Rand_NSMB显然不需要加密强烈，而且超过99％的时间，这对于其目的来说是完全可以接受的。它主要困扰我，开发人员莫名其妙地改变了这种功能，以一种在某些情况下触发可怕的行为，这在正常播放期间遇到了完全可能的（虽然不太可能）。

如果它不是破产（如果是由人们发明的经验超过你的经历了很多），请不要解决它。

“线性总体生成器”（“常用参数”） - 维基百科。检索到4月18日，2020年4月18日。↩

“随机数信息 - 随机性的性质” - randomnumbergenerator.com。检索到4月18日，2020年4月18日。↩

如果您正在考虑这一点，我必须有一个缓慢的SSD ......没有，我一旦完全生成，我就会将文件移动到另一个驱动器。 ↩

以下是一些其他有趣的输入，您可以尝试在交互式小部件中，如果您想要：2576391288（2周期），49939938（前4个周期），459503（前8个周期）。 ↩

如果固定点是其他一些数字，这不一定仍然是真的。 ↩