Missing mushroom and object generation question

[zaimoni]

Originally Posted by Tiburon Silverflame

What RNG is being used? Don't feel like digging through the code to find out.

It's a reimplementation of a fairly standard addition-shift RNG; no in-source documentation of where the coefficients are from, but as it's very easy to get these things wrong I assume there is a properly documented source "out there".

My testing suggests it's naked-eye random for events with probability greater than about 1/27. (Below that point, save-scumming enchant __ scrolls starts hitting excessively many long runs of non-occurrence: the empirical chance of a 1 in n event having a run of 3n failures ideally is about 5% for moderately large n. Hardly a major failing.)

[Tiburon Silverflame]

That sounds like it's a simple linear congruential generator. Those are seriously NOT random; they have major sub-cycles in them. Yes, they're god-awful if you pick the parameters wrong...but we're talking TOTAL cycle lengths of, like, 10 when you do that. But even if the coefficients are set up to give properly total cycle length, these generators inherently produce

R(n+k) ~= R(n)

where k is the sub-cycle length.

[Pete Mack]

@Tiburon: so what's your point?
Poor pseudo-randomness matters a lot when all you have is an array of random numbers, but composed with some complex state machine (like Angband), cycles aren't likely to be obvious to the end user.
They sure aren't obvious to me; if they were, I'd win every game in very small number of turns...

[LostTemplar]

For such a complex thing like andband you do not need random numbers, any uniformly distributed numbers will be OK.

[ekolis]

So the first time I attack the monster, I hit him for one damage... then I hit him for two... then I hit him for three... :P

[buzzkill]

Originally Posted by ekolis

So the first time I attack the monster, I hit him for one damage... then I hit him for two... then I hit him for three... :P

I've a better idea... mechanical hands, real dice, and an optical scanner. No more getting screwed over by the RNG.

[zaimoni]

Originally Posted by Tiburon Silverflame

That sounds like it's a simple linear congruential generator.

It is not: there's way too many slots. There is also a linear congruential generator, but it's used only to initialize the main RNG and compact the town and flavors into a 4-byte seed.

Originally Posted by Tiburon Silverflame

Those are seriously NOT random; they have major sub-cycles in them. ... But even if the coefficients are set up to give properly total cycle length, these generators inherently produce

R(n+k) ~= R(n)

where k is the sub-cycle length.

That is...elegant. (I'm not specialized in this literature, but that's not something I've seen in 200+ reasonably technical-looking web pages.)

[Pete Mack]

I would be happy to rewrite the random number provider to use an optional secure random number generator, like /dev/random on *NIX or CryptGenRandom on Windows. But I would be shocked, shocked, if you could tell the difference vs even a bad RNG like a linear congruential generator. Angband runs as the composition of the RNG with a really complicated finite state machine. So long as it can't get stuck in a cycle (like the borg), the lack of "randomness"* of the random numbers is not likely to be an issue.

* I put "randomness" in quotes, because even a secure RNG isn't necessarily truly random. It's just very, very hard to second guess. For true randomness, you need an ergodic (physically random) source like rolling dice or shuffling cards. This is surprisingly hard to come across on a purely digital system. The references above are to (mostly) ergodic RNGs. They use things like disk drive latency, mouse movement, keyboard delays, and WIFI signal strength as entropy sources. For the tinfoil hat set, you can buy true hardware RNGs for $100-$200. I suspect this won't fly with the angband crowd...

edited for broken link, /dev/random reference, and completeness

[zaimoni]

Originally Posted by Pete Mack

I would be happy to rewrite the random number provider to use an optional secure random number generator, like /dev/random on *NIX or CryptGenRandom on Windows.

Goodbye, RNG state within savegame. Reintroducing the V2.7.9- (?) behavior of just being able to reload ad-nauseum and get potentially different results every time sounds like a large step backwards.

[nobody]

does it?

i guess it might induce people to 'loadscum' but is there any other reason this is bad?