[HN Gopher] One Number Repeated Forever: RNG in NSMB (2020)
___________________________________________________________________
One Number Repeated Forever: RNG in NSMB (2020)
Author : sanqui
Score : 71 points
Date : 2021-05-03 08:32 UTC (1 days ago)
(HTM) web link (roadrunnerwmc.github.io)
(TXT) w3m dump (roadrunnerwmc.github.io)
| coolreader18 wrote:
| 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.
| twic wrote:
| I also initially guessed that the number was 1488.
| dang wrote:
| Please don't do this here.
| blackboxlogic wrote:
| 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
| danbruc wrote:
| 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.
| steerablesafe wrote:
| I think the solution is that not every seed value is part of a
| cycle, but they might lead to a cycle.
| _Microft wrote:
| 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
| blackboxlogic wrote:
| 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.
| pcwalton wrote:
| 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.
| _Microft wrote:
| 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.
| xyzzyz wrote:
| 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.
| flatiron wrote:
| my thought exactly, its a feature not a bug. a way for a unit
| test to possibly "play" the game with RNG effectively
| "disabled"
| no_multitudes wrote:
| I wonder if it could have been done to shut up some static
| analysis tool?
| bentcorner wrote:
| 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.
| _Microft wrote:
| 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.
| tinus_hn wrote:
| This was probably implemented in assembler, which makes it easy
| to make a mistake like this, and how are you going to check?
| pcwalton wrote:
| 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.
| NobodyNada wrote:
| 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.
| azundo wrote:
| Obligatory XKCD: https://xkcd.com/221/
| pavel_lishin wrote:
| Obligatory Dilbert: https://dilbert.com/strip/2001-10-25
| memco wrote:
| 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.
___________________________________________________________________
(page generated 2021-05-04 23:02 UTC)