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

[sophist]

Originally posted by Nagel
THERE IS NO SUCH THING AS RANDOM.

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

Er, what? The quantum states are random. That's a fundamental tenet of quantum mechanics. Truly random, not just approximately.

eclarkso, oops, right. Radioactive decay would be a lot simpler. That'd be easy. You just need some of that tritium like for watch dials or something.

[XPav]

Originally posted by 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 !!!!!!!!!!!!!

Its not random.

Run millions of test, graph them, and you'll see its not an even distribution.

[Rasputin]

which is waht makes it random, if you can graph it it isnt random,

[Hurry]

As I see it, people are complaining about two things about the PRNG:

A) That strange results occur in combat (i.e. the so called "the PRNG is broken"-school.
B) That the results are exactly the same if you reload and try again

Now, as many have shown, case A is not true. The one simple answer to "strange" results is due to the low number of hit points of units. Remember that units in Civ3 only have 2 to 5 hit points, while they in SMAC had 10-40. In Civ3, there is not time to get an even distribution of random numbers, since the number of die rolls is so low.

Case B, again, can be used in your favour just as much as against you.

[Pythagoras]

Originally posted by 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.

Your claim that 2 people generating the random number at the same time is correct, however with a "classical computer" (as you put it) it is imposible for 2 people to perform an operation (such as a random number operation) in the same clock cycle. Hence the two guys could not get the numbers simultaneously. What is ussually done is that if a series of random numbers is needed is that the time is used as a seed. From there random numbers are generated, and a program can reseed where nescesary.

So the random number generation is based on the time that this seed is placed into the random number generation. Think of all the factors that go into determining the time that this operation is conducted. If you consider that time T (and remember where talking absolute time) that the nth step in a program is going to execute on (ie the seed random number step) as a deterministic function, you got yourself a doozy. Because there are a million factors that go into this that might as well make it random, first you have when the user decided to execute the program and the whims of users brains (so a 100% accurate model of human behaviour is needed). Then once youve figured out at what time a user will initiate a program, you have to figure out at what time the computer will get to that command, and computers can be almost as complex and unpredictable as people. So good luck.

[Moraelin]

Actually, while re-seeding with the current time in milliseconds when the user clicks on something isn't strictly speaking Truly Random (TM), it is close enough for any practical purpose. Even if two users load the exact same saved game at the exact same time (which already is an improbability), the probability that they'll click on the enemy unit in the exact same millisecond is low enough to mean they'll likely get different dice rolls. Again, it's not Truly Random (TM), but it's a close enough illusion.

Either way, I think what most users complain about is Hurry's point B. Most users couldn't tell a LCG from a true die roll if it came and bit them on the rear -- and in all fairness, that's the whole point why pseudo-random number generators are OK -- but they can tell if reloading 10 times in a row produces the exact same result. If Firaxis didn't save the random seed, noone would even need to know how a random number generator works.

And his point A is actually the other half of the problem. That problem lies not as much in the generator, as in the combat model itself. This kind of weirdness would happen with real dice just as well. Try it.

But it's not only the hit points that are the problem. Attack and defense values change very very little through an upgrade, which means most of the time units that are 1000 years apart in the Real World, barely have a slight advantage in the game. If those units were called "generic offensive unit 4" and "generic offensive unit 5", I think noone would have a problem with it, but you do expect a company of Marines to be a lot more able to defend against a company of Longbowmen than is the case in the game. The squad support weapons alone of those marines would be perfectly able to either suppress or mow down those longbowmen (depending on if they're smart enough to take cover), before they get anywhere near the range to shoot a single arrow.

Or to take some actual historical example, in real world history, riflemen had a huge advantage over smoothbore musketmen. Not only they had 2-3 times the range, but also accuracy and the tactics they could use. If you tried the "walk up to 100 paces, shoot twice while standing, then charge with the bayonet" tactic, which was standard for smoothbore musket companies, against riflemen, you'd be dead. The huge numbers of casualties in the US secession war was precisely due to that kind of mistake.

Also the existance of different attack and defense values, and the TOTALLY UNINSPIRED use of it, makes it even worse. Things that are obvious for anyone who knows any history, or at least saw a movie, are exactly the opposite of what's in the game. Longbowmen are OFFENSIVE units? Hello? Care to tell the British that their use of longbowmen at Agincourt was all wrong? Unless I totally forgot history, the French got their rear handed to them, because they made the mistake of thinking longbowmen are defenseless against an attack. Throughout all history archers were excellent defensive units, not a case of 4-1-1. Most castles were defended by archers on the walls, not only by pikemen.

To make things worse, obvious combined arms tactics don't work. E.g., if you have archers and pikemen stacked together, you'd expect the archers to fire a volley before the melee starts. You know, like catapults do. Because that's how battles worked ever since mankind discovered missile combat. But guess what? In this game archers are a melee unit, so that doesn't happen.

[haderka]

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

Maybe this is not that future technology. I have such device in my lab here in Olomouc. It is based in splitting weak light beam on a fiber optic beamspliter and detecting single photons by sensitive detectors. We used it for generation of very high quality random numbers. It is much simpler and easier to use even than the radioactive decay thing. It is placed in a box 25x20x10 cm and connected through parallel cable to my computer. But in principle it can be placed even on a PCI board. I know about at least three other quantum optics groups in Europe that routinely use such devices.

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 =)

You can do a lot of things mixing quantum systems and classical computers even today (mainly quantum cryptography and related things). But I agree that quanutm computers will bring a whole new world. Hard to say how far it is, the progress is very fast but there is still a lot to resolve.