One Number Repeated Forever: RNG in NSMB (2020) | Hacker News Reader

One Number Repeated Forever: RNG in NSMB (2020)

roadrunnerwmc.github.io

78 pointssanqui21 comments

I was able to guess that it was the Mario game (but I was unsure since this is HN not gamefaqs), but I'd think there are probably other acronyms that people here might jump to - I think the acronym should probably be expanded in the title.

I am curious what went wrong during development here.

Was it an accident? Did someone think that it would be a waste to throw away all these fine higher bits and just did anything with them?

(It feels a bit like a self-designed crypto algorithm when someone adds complexity because that's sure better than not, isn't it?)

They might not have been too familiar with linear congruential generators (LCG) because then they would have known that casting the result to an unsigned 32bit integer was not an accident but the modulus operation of the LCG (here: "mod 2^32"). See [0] for details.

[0] https://en.wikipedia.org/wiki/Linear_congruential_generator

I wonder if it could have been done to shut up some static analysis tool?

That's my guess too. They were probably using ranqd1, then someone turned on a new warning, then someone else had to figure out what to do with the warning without really understanding the change they were making.

It'd be interesting to see if the same randomizer is used in other SMB games after NSMB and any ports.

I don't think this would make a warning go away. value + (value >> 32) is still a 64bit int value that gets then cast to a 32bit int.

Whoops, good point. Uh.. maybe there's a cast in the original source and the bit shift was added at the same time?

Speculating: Perhaps a feature for automated regression testing? Start the game with the "cursed" seed, run your script of inputs and compare the outputs against the results of your last production release. Versus the normal RNG, where a game difference which touches the RNG would alter ALL following output, hiding later game differences.

my thought exactly, its a feature not a bug. a way for a unit test to possibly "play" the game with RNG effectively "disabled"

That's far too subtle. If a developer were going to add a debugging mode like that, they'd just add a flag that's checked in the function and makes it return a constant.

That was my thought as well. Why bother with finding a fix point of your PRNG (and messing up its properties in the process) when one could use something like #ifdef ... return 4; instead.

It would be much, much simpler and much more robust to just have a flag that when set, makes RNG returns the same number, instead of depending on some very obscure behavior of specific hard coded constants chosen.

This was probably implemented in assembler, which makes it easy to make a mistake like this, and how are you going to check?

I doubt this was implemented in assembler. It's not performance critical, and 32-bit ARM is a friendly enough target for a compiler that a human won't be able to improve upon the compiler's output anyway.

Assembler? That seems very unlikely, as this was a DS game released in 2006. Ever since the Nintendo 64 and GameBoy Advance, compilers have been good enough and the hardware has been more than powerful enough that games have been typically implemented in C.

Am I having a moment or is the math off?

> Given a random starting seed, rand_nsmb will repeat an output after 1,820,529 calls, on average.

> Longest cycle: 1 cycle of length 1,708,724

I think the solution is that not every seed value is part of a cycle, but they might lead to a cycle.

If you look at all the listed cycles, their total length is 2,664,154 or only about 0.06% of all the 32 bit integers. So 99.94% of all the integers first follow some linear path before eventually entering into one of the cycles. Now depending on the exact structure of the graph - are there a few long paths or are there many short paths entering into the cycles and into a cycle of which length do the different paths enter - the average sequence length until the first repetition across all starting points can be very different including longer than the longest cycle in case there are relatively few but long paths entering into the cycles.

The article mentions that the seeding is sufficiently random so to make it unlikely to at the RNG will get fixed, but it would be cool to see more details about how you might be able to guarantee that seed so you can speed run or TAS the game.

Obligatory XKCD: https://xkcd.com/221/

Obligatory Dilbert: https://dilbert.com/strip/2001-10-25

Reply on news.ycombinator.com