Semi-Scientific Study of the Civ3 Random Number Generator

[Fake Boris]

Dan Baker appears to have a good point.
What I am saying is not scientific at all, but I have a STRONG impression that rolls are precomputed, i.e. that reloading a game and replaying the battles will yield the same results. For example, your elite unit A attacks regular 1 and get beaten by an "unfair" streak.
Reload.
Redo the same fight. Maybe the attack will succeed, but you can be sure you'll lose another one with overwhelming odds somewhere else in the turn.

[Rathgar1]

but I have a STRONG impression that rolls are precomputed

The rolls are precomputed, this makes it so you can't reload over and over again until youn win a battle. The precomputing is changed if you do things in a different order(ie you attack with different units, or against different targets.

[Excelsior]

Originally posted by Dan Baker
The numbers look right to me. However, I think it would be more usefull to encode the data in terms of number of 'dice rolls' won rather then streaks. It doesn' t really matter, I bet the distribution works out correctly anyway.

The reason I was looking at streaks specifically was to address the sentiment expressed by Venger and others that while the overall results might not be off, there were a larger number of long streaks than there should be by random chance. I believe these results disprove that hypothesis.

The real problem with the battle system has nothing to do with the probality distribution, its just a noise problem. With few units (i.e. early in the game), the amount of randomness in battles is huge. In modern times,with dozens of units even for a small war, the noise cancels out.

I think the problem is with the small number of hitpoints. It allows relatively short streaks of 2 or 3 in a row to be decisive. As it stands, with two three hitpoint warriors, the odds of the battle ending with one side completely undamaged is 25%! That's a lot! By comparison, in Civ2, the odds of such a thing occuring, with Civ3's 10% defense bonus, was slightly over 0.2%.

I believe this is also what causes a lot of the tank vs. pikeman angst. Assuming 3HP units, a pikeman fortified inside a metropolis on grassland has a fairly reasonable 16.5% chance of victory. With 10 HP units, this drops to 3.3%.

[wervdon]

As a programmer myself, I can guess how they accomplished the random numbers coming up with the same sequence after a reload based on how I would do it if I programmed it.

Id basically just use the last random number generated in someway to "reseed" the generator after each run.

Something like this:

srand(system time);

// utility function to return a random # between two limits
int number_range(int min, int max)
{
if (min > max) return min;
return ((rand() %(max-min+1)) + min);
}

Thats actual code from the game Im working on, and how I ussually handle random numbers. If I wanted it to always generate a sequence though, id just reseed the generator each call like this:

// utility function to return a random # between two limits
int number_range(int min, int max)
{
srand(next_seed);
next_seed = rand();
if (min > max) return min;
return ((rand() %(max-min+1)) + min);
}

Then all you'd have to do is initialize next_seed with the system time when a new game is made, and save next_seed along with a saved game file to be sure the game has a "locked" sequence of random numbers. It is a waste of effort though since all the player has to do is something meaningless that calls for a random number (like diplomacy) before he redoes an attack after a reload.

If that didnt make sense then don't worry about it, but I hope it sheds some light on how the random number generator more than likely works. I highly doubt they actually "pre-generate" a random sequence each turn and then save it. It'd be pointless anyways since all you need is a saved seed.

In fact a common trick in most games that generate random worlds and maps is to only save the random # seed that was used to generate that map/world to save space, since if you start with the same seed you'll get the same sequence of random numbers again (and thus the same map). Diablo for example does this, else the saved games would be many megs

[zapperio]

Excellent thread Excelsior, and thanks for the testing and the numbers.

Zap

[Excelsior]

Originally posted by wervdon
Thats actual code from the game Im working on, and how I ussually handle random numbers. If I wanted it to always generate a sequence though, id just reseed the generator each call like this:

// utility function to return a random # between two limits
int number_range(int min, int max)
{
srand(next_seed);
next_seed = rand();
if (min > max) return min;
return ((rand() %(max-min+1)) + min);
}

Then all you'd have to do is initialize next_seed with the system time when a new game is made, and save next_seed along with a saved game file to be sure the game has a "locked" sequence of random numbers. It is a waste of effort though since all the player has to do is something meaningless that calls for a random number (like diplomacy) before he redoes an attack after a reload.

You should take a look at Zapperio's thread where he was testing what things change the outcomes of subsequent battles. It looks like the generator is not reseeded every time it is called. If everything is done in exactly the same way, the turn will come out exactly the same no matter how many times you reload.

Through my own experience, though, I am pretty sure that it is reseeded at the beginning of each turn of both the AIs and the player. If you reload a game from before an AI attack and fight it again, it will have an entirely different outcome.

[Hurry]

There is definately a queue of seeds at all times. Check my results in this thread (bottom of page): http://apolyton.net/forums/showthrea...threadid=35475

This clearly shows that the queue includes at least 5 prerolled random numbers (and most probably much more than that).

I have not seen anything proving that the queue would be reset at the beginning of each round, rather I would suggest that the queue is of a fixed size (for example, 100), and each time a random number is needed, the first one in the queue is picked, and a new one is generated at the end of the queue.

Hurry

EDIT: Edited for clarity

[Oho]

Ave !!!

The pre generated "random numbers" aside, the basic idea of determining randomness in terms of statistical frequency is in my opinion flawed. To do it correctly you would have to look at the sequence of events as they are and to determine whether the sequence was genrated by random (stochastic?) sampling of some dsitribution.

(Hack follows)
This you could do by genrating a guaranteed (pseudo)random seqeunce from the same ditsribution and computing some measure of complexity for the sequence (compress it and look how long the compressed sequence is) and compare the result with one obtained form the observed seqeunce of events. If the compressed code for the real sequence is shorter you know the samples of the sequence are not as random as the samples of the guaranteed random sequence. The process may still be "stochastic" but the samples are no longer i.i.d.
(Hack ends)

- Oho -

[Kokuei]

[Not Civ3, but still on-topic]

Back in my Univ days, I did a study on random variable generators. I tested the pre-built generator on Excel (early version).

If you called for a random seed, you would get a distribution of numbers. If I went to a completely different machine in the lab, and repeated the same process, I would get the same set of numbers!

I realised this because when I asked for a Uniform Distribution Sample - (using a random seed) & then came back later on to another machine and asked for a Normal Distribution Sample (again using a random seed), the results from the Normal Sample when converted to Uniform were the same!

So the random seed was not actually random at all! I'm assuming that it must have had a seed look up table, much like the one described above, only the table was always the same when you started up the machine.

Funny old world.

[wervdon]

My point was just that you don't have to pre-generate a list of the next random numbers per say, or save them at the beginning of a turn. You just generate the next seed for the random number generator and save that with the save game file, then when you reload, use what would of been the next seed as the starting one.

In effect, that creates an infinite list of pre-determined random numbers, since if you start with a given seed you'll get the same exact results out of the next trillion+ calls to rand()% (actually until you recall srand() :P )

I don't know that they do it like this of course, but it'd make the most sense.

[Excelsior]

OK, after some thought, here is a test that might answer some questions. We need to determine whether the third battle in this sequence is different,

1st Attack: Horseman vs. Pikeman (Constant X rounds of combat)
2nd Attack: Horseman vs. Spearman (Y rounds of combat)
3rd Attack: Horseman vs. Warrior

if we substitute this for the second battle:

2nd Attack: Swordsman vs. Pikeman (Y rounds of combat)

where Y is the same as the other Y.

This would determine whether or not the queue is being changed by the combat, or a difference in the number of rounds fought. The idea is that we determine whether srand() is being called after certain events or whether the queue appears different because a specific battle uses up more or less random numbers. Zapperio, could you test this?

[wervdon]

I dont think Im being clear

If you call srand(12)
and then you call rand() 6 times and get:
21
14
6
7
12
2
then call srand(12) again, and rand() 6 more times you'd get the same string of numbers again. Obviously the #'s srand takes and rand gives are much larger though :P

There is nothing *random* about it for real. rand() is in fact a pre-determined sequence of numbers based on what # was passed to srand() to start it. Its unpredictable because srand() is ussually used with the system time

The reason taking an action in combat can change the results is you cause an extra call to rand() which will "eat" one of the random numbers up that wasnt used before.

For example:
unit a attacks b (uses 21, 14, and 6 up)
unit b attacks c (uses 7 12 2 up)

Say you reloaded, it'd reseed srand with the saved seed it stopped on. And reset the sequence to the 21. If you did something different that used a random number up, it'd change the use of the results, but not the order.

Example
unit a attacks b (uses 21 14 6 again)
You bombard (uses 7, which may of caused you to lose or something)
b attacks c again (now it'd be 12 2 ?) Outcome could be different even though the random sequence of #'s was the same, because you took a different action.

My point in the first place though was that there probally isn't some list of pre-generated #s, cause all they'd have to do is save 1 #, and thats the seed that was to be used next when the game was saved. Chances are if save files are disected, that seed # will be found in them somewhere :P

[Excelsior]

Originally posted by wervdon My point in the first place though was that there probally isn't some list of pre-generated #s, cause all they'd have to do is save 1 #, and thats the seed that was to be used next when the game was saved. Chances are if save files are disected, that seed # will be found in them somewhere :P

I understand that there is not a pre-generated list of random numbers, but I would like to know whether or not the initial seed is the only factor at play, or whether certain things might cause the game to reseed the generator.

Alright, here's a question. Does the save file save the position in the seed? Might it save the number of random numbers used since the seed was generated? Then would it burn those numbers before proceeding with the turn?

Now my point is, if it doesn't save the position in the seed, would it not be neccessary to generate a new seed after each event that uses a random number? This seed would have to be non-random since the combat is predetermined no matter how many random number using events occur. Is there any way to determine which is occuring inside the game?

[wervdon]

You mean something like this?

game_startup()
{
...srand(timer)
number_of_rand_calls = 0
....
}

save_game()
{
....
write initial seed
write number_of_rand_calls
.....
}

number_range()
{
number_of_rand_calls += 1
generate and return a random #
}

load_game()
{
.....
load initial seed from file
srand(initial seed)
load number_of_rand_calls from file
for (counter = 0; count < number_of_rand_calls; counter++)
rand()
....
}

Yeah that'd work out, but its alot of extra work, and you'd still have to save the initial seed so you didn't gain anything really.

I _suspect_ their number range function actually looks something like this though:

game_startup()
{
.....
seed = current time;
srand(seed)
......
}

save_game()
{
....
write seed to file
.....
}

load_game()
{
.....
Load seed from file
srand(seed)
.....
}

get_random_number()
{
seed = rand()
return (seed%max + min + 1) (roughly anyways)
}

-----
You don't actually need more than that, the way rand() works anyways is it reseeds _itself_ each time you call it with what it generates that run.

Basically this:
seed = rand()
srand(seed)
result = rand()

should give you the exact same thing as this
rand()
result = rand()

Because rand reseeds itself with its own result, thus you get a predictable string of #s if you know the starting seed.

It could be either way though, but I imagine when someone fully disects the save game file there will have to be at least 1 seed value in there somewhere in any case.

[Excelsior]

I _suspect_ their number range function actually looks something like this though:

game_startup()
{
.....
seed = current time;
srand(seed)
......
}

save_game()
{
....
write seed to file
.....
}

load_game()
{
.....
Load seed from file
srand(seed)
.....
}

get_random_number()
{
seed = rand()
return (seed%max + min + 1) (roughly anyways)
}

But with this system, if you save during the turn and then reload, you'll get the same random numbers you got up until the point where you saved.

Example:
Game seed = current time
player uses first 5 numbers from seed
player saves
saves game seed to file
player reloads
player gets same first 5 numbers he got last time

You say that rand() reseeds itself with the result? i.e., rand() returns 506021, whatever, then that number becomes the seed? If this is the case, then all the game would need to do is save the most recent result to file and when it reloads, use that as the seed, right?

EDIT: Oh, never mind. That is what this does...sorry. I see now.