hypothetical hypotheticals about hypothetical randomness

[doom_sheep]

assume that a hypothetical random generator is bad and gives some numbers more than it should.
if it was really bad and when asked for a number between 1-10 gave the number 2, 30% of the time. a person who didn't have access to a better one could just adjust it so that half of the time it adjusts the number up by 1 (and looping around so that 10 becomes 1, thanks pedants)
now hypothetically instead of really loving number 2 the generator would split the extras evenly between 2 and 3 and be less bad by about half.

maybe hypothetically the hypothetical random generator is not as noticeably garbage as the previous hypothetical example. hypothetically it could still give too much of a number, give them in hypothetically predictable sequences, etc, without it being obviously noticeable to a hypothetical observer. hypothetically, this could be bad for some reason. doing the same trick should hypothetically reduce this hypothetical problem.

anyway, this seems kind of bothersome. couldn't I just reset the random seed between each roll to get the same effect? I assume I can do that a thousand times a second without it affecting fps and I don't see how it would have any other adverse effects either.

hypothetically, what do I set it to? do I use it to randomize itself? adjust by 1? what's even the range for random seeds? is there some hypothetical reason not to hypothetically do this?

I've tried to be clear about this being theoretical but I'm not sure I got the message across. if you're confused you should ask if I actually wanted weighted random instead or demand a study about the quality of warcraft 3's random number generator.

 

[Lizreu]

hypothetically, what do I set it to? do I use it to randomize itself? adjust by 1?

There's not really much point in doing that. You're just going to be changing the pattern of the numbers generated, but the underlying issues will still be there.

If you're using the RNG itself as a source of entropy, well, you're not going to get any more entropy out of it.

If you really need a better RNG than what WC3 gives you, I think you're just going to have a better time implementing a known decent algorithm yourself instead. E.g. this: Xorshift - Wikipedia

EDIT:

Constantly re-seeding the stock WC3 RNG with output of a better RNG (e.g. the Xorshift thing I linked above) might actually produce decent results too, if you want to make sure that WC3 has better RNG internally, though I'm not 100% on this.

 

[doom_sheep]

If you're using the RNG itself as a source of entropy, well, you're not going to get any more entropy out of it.

if someone shuffles a deck of cards badly does shuffling it again get you an equally mana weaved result?

 

[Lizreu]

if someone shuffles a deck of cards badly does shuffling it again get you an equally mana weaved result?

This isn't really a comparable analogy, because RNGs aren't decks of cards, and you aren't "shuffling" them. It's just a bunch of deterministic operations layered on one another, trying to fool you into thinking the result is random.

If the underlying algorithm has biases and patterns, it won't matter much what input you're feeding into it. There's many reasons why so much research has been poured into producing quality RNGs, and why its such a hard problem.

EDIT:

Circling back to the deck shuffling analogy, if you're using a known and deterministic algorithm for shuffling your cards, its fairly easy to produce any sort of pattern as a result. There's many card tricks that involve doing something that looks "random", but produce 100% reproducible results. In the case of RNGs, you can only use deterministic steps to shuffle them, so that makes the problem kinda worse.

 

[doom_sheep]

If the underlying algorithm has biases and patterns, it won't matter much what input you're feeding into it.

if I frequently change the input based on a deterministic but unknown method that seems like it would make the patterns more chaotic. if you can coherently explain why it wouldn't be like this please do.

 

[Lizreu]

if I frequently change the input based on a deterministic but unknown method that seems like it would make the patterns more chaotic. if you can coherently explain why it wouldn't be like this please do.

So, I've actually thought about this for a bit and come up with an example.

Let's imagine a very bad RNG, that returns numbers in the range [0..2^32-1] (unsigned 32-bit integer):
1. Every 7th number is divisible by 5
2. Every 3rd number is divisible by 2
3. Other numbers have uniform distribution

It'll generate sequences of numbers like this:
x x 2 x x 2 5 x 2 x x 2 x 5 2 x x 2 x x 10

Where "10", "5", and "2" indicate numbers that are divisible by 10, 5, and 2 respectively.

Let's say we now reseed the RNG with itself 11 times (which is basically just generating a new random number and discarding it).
The pattern looks like this:
x 2 x x 2 5 x 2 x x 2 x 5 2 x x 2 x x 10 x

What about 13?
x 5 2 x x 2 x x 10 x x 2 x x 2 5 x 2 x x 2

What about 131?
x 2 x x 10 x x 2 x x 2 5 x 2 x x 2 x 5 2 x

What about 50123?
x 2 x x 10 x x 2 x x 2 5 x 2 x x 2 x 5 2 x

What about 21?
x x x x x x x x x x x x x x x x x x x x x x

Now we're getting somewhere. We've eliminated this statistical bias, but to do it we need to know the period of it - 21. Otherwise we're just throwing things at the wall to see what sticks.

This is a really simple, and perhaps unrealistic, example, but I think it illustrates why reseeding an RNG with itself doesn't necessarily make it better. It can, though, if you know the exact underlying faults, but its not straightforward.

The specific flaws I've used in this example aren't that important - the important part is that they're recurring, and most RNG flaws are, in one way or another, some kind of pattern that repeats itself, thus reducing the actual randomness of the output. You can substitute these flaws I used for something else, and chances are, you'll see new patterns emerge anyway.

Closing thoughts:

The reason why re-seeding (or skipping) an RNG doesn't make the output more "chaotic" is because RNG output isn't really chaotic in the first place. You're just swapping one pattern for another, but you're not completely eliminating it (unless you know what the pattern is and specifically compensating for it, but without the source code for the RNG this is pretty hard).

EDIT:

I've kinda gotten interested in this myself, and decided to run some tests. I made a very simple, and very bad RNG:

(this is Rust, but should give the general idea)

    fn generate(&mut self) -> u32 {
        self.state = self.state % 16255027;
        self.state = self.state.wrapping_mul(self.state % 4256233);
        return self.state;
    }

If asked to generate numbers in the [0..9] range, the result is abysmal:

0 - 14%
1 - 4%
2 - 15%
3 - 7%
4 - 14%
5 - 5%
6 - 15%
7 - 5%
8 - 15%
9 - 6%

Let's try fixing it.

Variant A: Skip 1000 numbers each time.

0 - 13%
1 - 5%
2 - 16%
3 - 5%
4 - 14%
5 - 6%
6 - 16%
7 - 5%
8 - 14%
9 - 4%

Still bad.

Let's try re-seeding it each step with "random() * 80123"

0 - 17%
1 - 3%
2 - 15%
3 - 5%
4 - 15%
5 - 5%
6 - 15%
7 - 6%
8 - 13%
9 - 5%

Re-seed with "random() + random() % 15485863" (15485863 is a prime number, and primes are good for this kinda stuff).

0 - 15%
1 - 6%
2 - 13%
3 - 5%
4 - 15%
5 - 5%
6 - 17%
7 - 5%
8 - 14%
9 - 5%

Still bad.

Finally, let's try reseeding it each step with a number from an actually good RNG.

0 - 15%
1 - 5%
2 - 15%
3 - 5%
4 - 14%
5 - 5%
6 - 15%
7 - 5%
8 - 15%
9 - 5%

Doesn't help at all. It isn't fixable.

Let's try a slightly better RNG:

    fn generate(&mut self) -> u32 {
        self.state = self.state % 16255025;
        self.state = self.state.wrapping_mul(910385619);
        return self.state;
    }

This one, when seeded with a good RNG at each step, produces numbers in uniform distribution. So that's a start.

But, let's remove the good RNG from the equation:

0 - 13%
1 - 9%
2 - 15%
3 - 13%
4 - 10%
5 - 11%
6 - 9%
7 - 9%
8 - 4%
9 - 9%

Welp.

Let's re-seed it with itself 100 times:

// first run
0 - 13%
1 - 9%
2 - 16%
3 - 13%
4 - 10%
5 - 11%
6 - 8%
7 - 8%
8 - 3%
9 - 8%

// second run
0 - 10%
1 - 10%
2 - 9%
3 - 9%
4 - 11%
5 - 10%
6 - 11%
7 - 10%
8 - 11%
9 - 10%

Why are the 2 runs different? They each started with a different initial seed value. In fact, this algorithm is highly dependent on having a quality seed available at the start.

Let's try re-seeding it with this each run: "((rng.generate() ^ 3279046249) ^ 273646861) ^ 1939583911" (all of these are primes, too)

0 - 9%
1 - 11%
2 - 10%
3 - 9%
4 - 11%
5 - 10%
6 - 10%
7 - 9%
8 - 9%
9 - 11%

Still some bias, and occasionally with some seeds some numbers have only a 7% chance of appearing. But it seems to be much less dependent on the initial seed now, so that's a plus.

So, what I think you can do is regularly re-seed the WC3 RNG with a better RNG and you'll actually have better output, though it won't be as good as if you used a good RNG to begin with, and it still might depend on how good/bad the initial seed is.

My own conclusion from this, is that this whole topic is rather complicated. Some RNGs marginally improved with the techniques you were proposing, others were just unfixable. It depends a lot on the technique you're using and the nature of the bias. But, you can try throwing a xorshift into WC3's RNG once in a while - might make it better?

 

[doom_sheep]

I don't have to just use GetRandomInt, though. I can combine it with an incrementing counter, derive something from elapsed game time or whatever.

EDIT: also I'm pretty sure wc3's rng atleast over long periods produces reasonable amounts of each number. if there is an issue it's patterns or bias within short sequences.

 

[Lizreu]

I don't have to just use GetRandomInt, though. I can combine it with an incrementing counter, derive something from elapsed game time or whatever.

EDIT: also I'm pretty sure wc3's rng atleast over long periods produces reasonable amounts of each number. if there is an issue it's patterns or bias within short sequences.

I wish someone'd reverse-engineered WC3's RNG. I remember seeing decompiled WC3 sources around the time memhack was being hyped, but can't find them anywhere. If we knew the algorithm we could figure out how to fix it exactly.

 

[maddeem]

here is a random  number generator library RandomNumber
    globals
        integer RANDOM_SEED
        integer RANDOM_MULT = 8121
        integer RANDOM_MOD = 134456
        integer RANDOM_INC = 28411
    endglobals

    //RETURNS A VALUE BETWEEN 0 - 1
    function GetRandom takes nothing returns real 
        local integer d = RANDOM_SEED * RANDOM_MULT + RANDOM_INC
        local integer m = d - (d / RANDOM_MOD) * RANDOM_MOD
        if m < 0 then
            set m = m + RANDOM_MOD
        endif
        set RANDOM_SEED = m
        return I2R(RANDOM_SEED) / I2R(RANDOM_MOD)
    endfunction

    function RandomReal takes real lowBound, real highBound returns real
        return GetRandom() * (highBound - lowBound) + lowBound
    endfunction

    function RandomInt takes integer lowBound, integer highBound returns integer
        return MathRound(RandomReal(lowBound,highBound))
    endfunction

endlibrary

I've implemented this and it is pretty solid RNG. It only repeats after every 134456 uses. The numbers are very specific so only change them if you know what you are doing.