A Random Number Generator doesn't exist! (somewhat technical)

[Karhgath]

Ok. This is a collateral to all the combat 'weirdness' everyone experienced. I want to dismiss a myth about computers and random numbers (ok, you will have to dust up your math a little=):

A Random Number Generator DOESN'T exist. Period. There is no known way for classical computer to generate truly random numbers. There is no equivalent to throwing some dice for a computer, because modern computer is based on logic, it is impossible for him to generate random number on the spot. Everytime you hear someone saying they got a hardware, or a software random generator is usually just trying to sell a product. EVERYTHING is based on variables and functions. You can use variables that seems more or less random, but, it still is possible to regenerate the same numbers doing the exact same steps.

The question now is, what does it actually do? And why is it called random number generator?

First, it is NOT called a random number generator. It is called a Pseudo-Random Number Generator(PRNG). The emphasive is on the Pseudo part. So, how does that work? Here we go =)

A PRNG algorithm is based on 2 things. A formula/function, that generates pseudo-random number, and a Seed. The formula is usually a linear congruential generator (LCG) or a non-linear congruential generator (NLCG). What is a LCG? It's a formula, that, given an input, will generator a LIST of pseudo-random numbers. The input is the seed. Here's the formula for a standard LCG, it is based on recurence to generate a list :

Xn+1=(Xn*b+a) mod max

where X0=seed, X1/X2/X3/X4/.../Xn/Xn+1 are the pseudo-random numbers, a and b are multipliers used by the function where 0 <= a and c < max, and max=the maximum number generated(and the longuest possible cycle, see below).

For example, lets take a = 2 and b = 11, seed = 127 and max 1024.

X1 = (127 * 11 + 2) mod 1024
X1 = 1399 mod 1024
X1 = 375

So, the first number in the list is 375. That means that, the first time you request a random number, it returns 375, and you usually do some operations to make it between X and Y to be used by your program, more often than not, between 0 and 99 or 1 and 100.

X2 = (375 * 11 + 2) mod 1024
X2 = 4127 mod 1024
X2 = 31

So, the second number in the list is 31. And it goes on like that.

Now, lets take the seed 49.

X1 = (49 * 11 + 1) mod 1024
X1 = 541 mod 1024
X1 = 541

X2 = (541 * 11 + 1) mod 1024
X2 = 5953 mod 1024
X2 = 833

...

As you can see, there it NOTHING random there. Given then exact seed, you can easely determine the EXACT numbers that will be generated. Furthermore, generating 2 PRN lists with the same seed always yields the same exact list, as you can see so well with the save/load quirks of Civ3, where, even if you reload, the same thing will happen, given the same order. This is because the seed is saved with the rest of the game.

So, why is that formula used? Well, LCG is NOT the best alrgorithm, but it's the most commun and 'easiest' one to implement. Also, statistically, it is viable and is 'correct' , if n is big enough (max <= n), where n is the number of generated numbers. So, how can you avoid having the same list over and over? Well, you usually use values that changes for the seed. The most commun one is the time, in miliseconds, since January 1970. Unless you generate your lists at the same exact milisecond, it will most likely be different. Or, you can keep a variable that keeps track of the mouse movement to really make it so it is even harder to predict. You can use the noise from your CPU fan as a seed, or any other thing like that, but it STILL is Pseudo-Random, even if the seed seems 'random'. Also, I will refrain from going to deep in math, but I want to point out that the 'mod' operator has a cycle that goes from 0 to N(non-inclusive), where N is the number after the 'mod'. That means that, even different seed can generate the same exact list. The smaller the cycle and 'max', the easier it is to generate the same list again.

So, why all this? To tell you that, NO, the combat is NOT broken, nor is the PRNG. Maybe, maybe the game relies too much on PRN and 'luck', it is up to you to decide for yourself on that. However, all the weirdness you see is based on the PRNG. That's why sometimes you have a warrior defeating a mech inf, or a stroke of bad OR good luck(I haven't seen anyone screaming for blood when they got a lucky stroke=).

Also, just to prove how 'sucky' PRNG is, have you ever used the 'random' function on a 5 CD disk changer? Or used the 'shuffle' function of programs like Winamp? If so, you probably already realised how sucky it is. For example, I just listened to music with the random function on my 5 CD changer. Here are the result :

(disk/song)
3/1
3/4
4/5
3/2
5/1
3/1
3/6
4/7
4/2
4/8
4/5
4/8
3/1
5/2
3/2

As you can see, i got 5!!! songs from the same disk IN A ROW, I got 2 and 3 times the same song in the list, and NEVER got any song from disk 1 or 2!! This is the 'randomness' Civ3 (and nearly all software programs) uses, so no wonder it yields the results you are all experiencing in combat.

This is just to clear the Myth about PRNG =)

I might be wrong on some account, but I think the gist of it remains true.

[Dis]

hey I remember my old commodore was able to generate random numbers. It must be superior to a PC!!

I do know a solution though. I suggest we build computers with a mechanized arm inside the casing. The arm would be capable of picking up and throwing dice within the computer casing. A laser sensor would then read the number of the side facing up. this would be used for all combat rolls.

[Karhgath]

IIRC and AFAIK, the commodore was using LCG like today's computer, and since it was 8-bit, it was even WORSE, because max was lower, so the cycle was lower, so it was easier to regenerate the same exact list. I could be wrong tho, it could have used another algorithm(there are a couple of other, less known formula/algorithm).

[sophist]

Someday all computers will have a quantum device within to allow true random number generation by measuring quantum properties that are effectively random.

[Karhgath]

Yeah, but until then, classical computers are unable to do it =) quantum computers are a LONG way ahead, and will change a LOT of things. Until then, we're stuck with classical science and classical computers =)

[barefootbadass]

The only way you could get a truly random generator would to be to write a function that uses a different seed based on the precise time each time a number is needed. Most good generators do this, you create the Random object and the seed is set(the seed is random since it is based on the time). The next number is not random because it has the same seed and follows some kind of formula. But if you have another Random object for the next number, the seed will be different and therefore the next number is random with respect to the first number.

But of course this isn't how the generator in civ 3 works(not that I am one who has a problem with it).

[Karhgath]

Time is NOT random, as 2 people generating the number at the exacte same time will have the same random number. For the same person tho, it looks like random, but remember, it has a cycle, so it is still not random. However, 2 people using dice at the exact same time will most likely not get the same result(although it is probably quite hard to achieve, hehe, if not impossible, so my point could not old). In fact, in the world, true randomness could even not exist at all, as there is SO much variables in the world that there could be a big unified formula that governs everything =) However, I disgress.

[eclarkso]

Originally posted by barefootbadass
The only way you could get a truly random generator would to be to write a function that uses a different seed based on the precise time each time a number is needed. Most good generators do this, you create the Random object and the seed is set(the seed is random since it is based on the time). The next number is not random because it has the same seed and follows some kind of formula. But if you have another Random object for the next number, the seed will be different and therefore the next number is random with respect to the first number.

But of course this isn't how the generator in civ 3 works(not that I am one who has a problem with it).

This is not really correct--as the original poster said, a 'classical' (which I assume means deterministic) computer cannot itself generate truly random data. Even though a PRNG based on the system clock has a changing seed, it's still fully deterministic based on that seed, and that's not considered -really- random.

However, I believe the original poster is incorrect in stating that there are no hardware solutions for generating random data. There are a number of ways to generate -real- random data by extracting real-life random events--the most often cited of which is radioactive decay. See the link below for one example.

http://valley.interact.nl/av/com/orion/rng/home.html

FWIW, there are much better software PRNG available as well, such as the /dev/random/ facility in the Linux (and other UNIX-like) operating system, which use very dynamic data from the computer other than the system clock, such as keyboard interrupt timings, etc.

[sophist]

Oh, I didn't mean the whole processor would be based on quantum mechanics. That's a looong time from now. But it should be easy to get a small device made that has a couple dozen structures in it that each randomly selects either a 0 or 1 based on some quantum property. A couple dozen makes for some pretty big numbers, and if they aren't big enough, well, you can just do it a bunch of times and concatenate them all together. Heck, if you want your computer generating random signals, just overclock it . This specialized case is very much in reach; it wouldn't surprise me if those fancy dancy special hardware deals that governments are so fond of use something like this.

Originally posted by Karhgath
Yeah, but until then, classical computers are unable to do it =) quantum computers are a LONG way ahead, and will change a LOT of things. Until then, we're stuck with classical science and classical computers =)

[Karhgath]

Yeah, you are right. You can build hardware that can create truly random numbers. However, it is beyond the reach of this discussion, and I think you will agree. Buying a little blackbox with plutonium in it to play Civ3 qith truly random numbers is quite extreme =) (yeah, I'm exagerating, but still) Those kind of random generator are use for extreme case, usually, PRNG are statistically correct and are enough for most tasks.

[Trifna]

Originally posted by Dissident
hey I remember my old commodore was able to generate random numbers. It must be superior to a PC!!

Your Commodore wasn't logical. I never understood mine

[sophist]

Heh, it sounds like some other people would need a device like that to be satisfied. And maybe not even then.

Originally posted by Karhgath
Yeah, you are right. You can build hardware that can create truly random numbers. However, it is beyond the reach of this discussion, and I think you will agree. Buying a little blackbox with plutonium in it to play Civ3 qith truly random numbers is quite extreme =) (yeah, I'm exagerating, but still) Those kind of random generator are use for extreme case, usually, PRNG are statistically correct and are enough for most tasks.

[eclarkso]

Originally posted by sophist
Oh, I didn't mean the whole processor would be based on quantum mechanics. That's a looong time from now. But it should be easy to get a small device made that has a couple dozen structures in it that each randomly selects either a 0 or 1 based on some quantum property. A couple dozen makes for some pretty big numbers, and if they aren't big enough, well, you can just do it a bunch of times and concatenate them all together. Heck, if you want your computer generating random signals, just overclock it . This specialized case is very much in reach; it wouldn't surprise me if those fancy dancy special hardware deals that governments are so fond of use something like this.

Perhaps, but I'm not sure how this would be better than using much simpler, much less expensive, and still very random radioactive decay. Though I don't have super sekrit access to the NSA's facilties or anything, I'm going to guess most security-concious organizations (gov't and otherwise) use something like what's advertised here, for the most part:

http://www-3.ibm.com/security/cryptocards/index.shtml

[Rasputin]

well my excel program certainly generates a random number simply enough, just type in to any cell =RND() then hit F9 and see it give different numbers each time !!!!!!!!!!!!!

[Nagel]

THERE IS NO SUCH THING AS RANDOM.


Karhgath wrote:

"A Random Number Generator DOESN'T exist. Period. There is no known way for classical computer to generate truly random numbers. There is no equivalent to throwing some dice for a computer, because modern computer is based on logic, it is impossible for him to generate random number on the spot."

If you throw a dice in EXACTLY the same way, on exactly the same place and with all other factors exactly the same - you will get the same number over and over again.

Even if you have a quantum device, it won't be random. You put something in, and you can predict what will come out. It's as simple as that. The only thing that COULD be "random", eg unpredictable is the free will. But that is debatable.

Hope I didn't blow your philosophical shells now