Random number generator

From NetHackWiki
Jump to navigation Jump to search

NetHack uses a random number generator (RNG) to determine the outcome of in-game events. Probabilities are expressed in d notation, a homage to Dungeons and Dragons.

Deification

The RNG is sometimes referred to as the Random Number God. The RNG plays a pivotal role in determining the fate of all characters, and is sometimes considered the deadliest enemy in the game, despite the fact that expert players such as marvin have demonstrated that nearly every game is ascendable.

Technical details

Although NetHack relies on the C rand() function, random number generation is not as straightforward as picking a number between 0 and n. Rnd.c holds all of the game's RNG functions, which can return results that depend on your Luck or experience level. Source divers might profit from examining these functions.

Misuse

A user has suggested improving this page or section as follows:

"What's the current state of this in vanilla NetHack rather than NAO? Did the devs ever just implement a Mersenne Twister? Also did they patch the actions that reveal/advance the RNG but take no time?"

Like most computer programs, in place of a true random number generator, NetHack uses a pseudo-random number generator. This is a mathematical function that generates a set sequence of numbers intended to approximate randomness; in particular, good PRNGs have the following qualities:

  • They have a very long period, i.e. it takes a long time before the sequence repeats
  • The numbers in the sequence are randomly and evenly distributed throughout their range

Unfortunately, NetHack's use of the standard C library's rand() function means that its PRNG is generally weak on the first quality: while implementation-dependent, the period of that PRNG is usually 2^32, or approximately 4 billion. While sufficient for everyday use, a sequence of that size can easily be handled by a modern desktop computer. More modern PRNG implementations, in particular Mersenne Twisters, have periods that are far longer than any computer can generate or search.

Given the short period of NetHack's PRNG, a determined player who knows their location in the sequence can use it to predict the outcome of subsequent events. Moreover, there are in-game actions that take no in-game time, but still advance the RNG, giving the player the ability to control events as well as predict them.

On a local copy of NetHack, determining one's place in the sequence is generally easy: the "seed" (starting point) is predictable, if OS-dependent. On a public server, this is more difficult, but because the period of rand() is so short, a player who observes a sufficient number of random events can use those observations to find their location within the sequence by exploiting actions that take no in-game time but still cause a random effect.

3.4.3

It was found by Adeon that a sufficiently determined player can find the seed of RNG after starting the game and then use it to his or her advantage - for example to gain unlimited number of wishes from a fountain. For demonstration see his ttyrecs on NAO from 2009-02-28 (starting with http://alt.org/nethack/trd/?file=http://alt.org/nethack/userdata/A/Adeon/ttyrec/2009-02-28.10:31:15.ttyrec.bz2#). See also Sartak's blog entry Predicting and controlling NetHack's randomness and ais523's description of a game relying on extreme RNG manipulation.

Instead of taking the current time in seconds as seed, NAO has after this exploit been changed to read the seed from the operating system's own pseudorandom number generator '/dev/urandom'. This way the seed has become unpredictable.

To also complicate the deducing of the random number generator's internal state, periodic reseeding has been implemented. This makes it so that a player is unlikely to be able to "collect" a sufficient quantity of random numbers before the seed changes. The reseeding is done using a truly random number (computers periodically "collect" these from events such as CPU temperatures and keystroke timings).

UnNetHack

The player nht produced a 363 turns, 16 seconds set seed UnNetHack ascension by exploiting a known bug. Nht gave detailed report on this ascension in a reddit post.

3.6.1

A tool assisted speedrun exploiting the RNG has been done NetHack 3.6.1 by pellsson on NAO in 7 minutes and 15 seconds and 2087 turns.

This page may need to be updated for the current version of NetHack.

It may contain text specific to NetHack 3.4.3. Information on this page may be out of date.

Editors: After reviewing this page and making necessary edits, please change the {{nethack-343}} tag to the current version's tag or {{noversion}} as appropriate.