Semi-Scientific Study of the Civ3 Random Number Generator

[drmofe]

Originally posted by wervdon
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);
}

If you use integer arithmetic to generate your numbers, your implementation has a DRASTIC effect on the distribution of the results. If CivIII is implemented this way, it would explain a few things :-)
See here for an explanation of this effect with respect to Java:

http://developer.java.sun.com/developer/JDCTechTips/2001/tt0925.html

The same principle applies to your example above.

In essence, you must keep the result of rand() as a double-precision and base your outcome on the normalized distribution between 0 and 1. If you don't you skew the distribution and make it less random.

Not that I am making any connection between your sketched implementation above and the hypothetical implementation in Civ II, but games programmers are games programmers and all tend to read the same stuff :-)))

Summary: Truncation of rand() using % operator makes the resultant distribution LESS random.

Query: Any Firaxis programmers lurking out there, please tell me you didn't use the mod operator in the RNG :-))

DRM

[wervdon]

Interesting info drmofe, Ill certainely give that a read when I get time. However, its the exact function I use in an rpg Im currently working on (csc 370 project, not for profit at this point), and it seems to work just fine. The game basically generates a random world, and allows you to wander/fight with random encounters ala dragon warrior mixed with Diablo. Not much fun to do, but it was fun to make.

I could test your assertion easily enough though. The function I give generates a random integer between a lower and upper limit. Generally the game uses it in the range of 1 to 100 (as a random percentage for combat calculations). I could just write a small app that takes this function and uses it to generate about a million random numbers from 1 to 100, and keep track of how many times each one comes up. That would test one of the main tennants a random number generator should satisfy, and that each possible outcome is roughly equally likely to occur.

Testing for patterns is a bit harder to do of course.


Hmmm, just for kicks I wrote that test app. The results aren't conclusive to me, but they are interesting.

I scaled it back to numbers from 1 to 20 with 20*100 test numbers generated to make the results fit. If it was "perfecty" distributed (which wouldnt be very random) each result would of appeared 100 times.

I got this:
1 91
2 105
3 94
4 97
5 109
6 94
7 93
8 101
9 96
10 120
11 85
12 95
13 110
14 87
15 85
16 118
17 106
18 105
19 98
20 111

Range of 85 to 120.... Not too bad.



And back to excelsior, I won't promise but I am pretty sure that rand does re-seed itself with its own result each time. There's no real magic about it, it basically is just a set of complex equations that take in 1 number and spit out another. rand() doesnt take an argument, so basically it has to produce its own for the next call somehow. srand() just re-initializes this system.

And basically it does work like what you said.
Player starts game, seed is set by clock

Player does things using up 5 (or any # of) random #'s

Player saves game, the entire game state along with the seed to pick the random # sequence where it left off last is saved too.

Player loads game. The game state is entirely restored, including the seed. He'll get the same results from rand() as before because it was reseeded by what should of been next when he saved.


Edit:
I also read through your article, and run a similar test to the one they did where they computed the average of all numbers generated over a large sample. With the expected result to be very near the mid-point of the range. Their results showed consistantly below the mid-point by significant amounts. My results did not repeat that, instead I always got reasonably close to the mid-point and on either side of it. For example 100*1000 runs of 1 to 1000 number_ranges would produce a result ranging from 480.something to 510.something. I ran it several times to be sure.

Perhaps their results can only be applied when working with Java? Im working with C++. (MS visual C 6.0 to be exact)

[Excelsior]

Originally posted by wervdon And back to excelsior, I won't promise but I am pretty sure that rand does re-seed itself with its own result each time. There's no real magic about it, it basically is just a set of complex equations that take in 1 number and spit out another. rand() doesnt take an argument, so basically it has to produce its own for the next call somehow. srand() just re-initializes this system.

Nope. You are probably right that rand() reseeds itself, but not with its own result. I tested it and it is not the case. I don't know what it is reseeding itself with, though. I wrote a program that determines the what seed is necessary to generate the same number after the first with a specific seed, and it seems to be, well, random.

For example, with the seed 1007091906, the random number generated is 10891. If you call rand() immediately thereafter, you get 25517. Now, if you reseed the generator with 1007091906 you again get 10891. If you then reseed with 10891 you get a different number, 2036. The seed needed to produce 25517 is 27871. It's an interesting thing.

[wervdon]

I actually wasn't too sure if that was the exact case Thats why when I orignally give an example I had it compute its own next_seed each time in a global variable that could be saved.

rand() does have to reseed itself each run somehow, but your probally right. It most likely does not use its own result to do the reseeding. I do know that rand() is basically a really complicated
f(x) function, where x does in some way depend on on the last calculation though, thus you can produce a repeatable sequence with a known seed value. I just don't know exactly what the f(x) is or how it uses results from the last run.

[cousLee]

I am not a programmer, nor do I have a clue about RNGs. But, if it helps, this is what my in game testing showed. (done long before reading this thread).

I wanted to see if each battle was a random determination. it is not. And some of the things I read here don't match what I found. Here is the in game, playtest set-up.

I had 5 catapults, and assorted warriors, spearmen, archers, charriots. After moving all non test units and saving the game, I would use the catapults to attack first. In example, the results would be. (win=defender lost hit point, or -1 population,ect. lose=arty failed, or no message with no apparent effect)

win, lose, lose, win, lose.

Then i reloaded the game, and didn't use the catapults, but attacked with the other ground units. I got the same victory order. w,l,l,w,l. As the ground units each had more than just one battle action, then it should have had a different outcome, as the # taken from the rng sequence would have moved farther down the line. But it didn't.

So I reloaded, and tried diffrent non-bombard units against diffrent defenders on assorted terrains (some in towns, some on mountains) got the same win/lose sequence.

Reloaded again, and tried it with diffrent units with varrying damage before battle, got the same result. So I pushed it the max, and used the current win/loss order to try attempt a phalanx vs tank type of scenario. got the same results. Using the sequence, I was able to win "important" battles, and use the "lose" slots for unimportant one. I was able to use a 1 hp warrior to destroy a full HP vet spearman in city, if I used that damaged warrior in a win slot. Affacking the same defender in a lose slot with a full HP elite archer I would still lose. EVEN if I used the previous win slots for the catapults to bring the defender down to one HP. the archer would still lose if used in a lose slot. So, using the above example, i could (and did), once I had the win/loss order, use the lose slots for the catapults, and the win slots to destroy the defender. so..
2/4 HP spearman defeats 4/4 HP spearman in city.
catapult failed
catapult failed
1/3 HP warrior defeats 4/4 HP spearman in city
catapult failed.

It did not matter what units I attacked with, what kind of damage either side had, whether or not the unit was in a city, on flat terrain, or mountain. The win/lose order set at the save point never changed.

Using the same type of determination, I was able to use a spearman (1 attack value) to destroy a spearman (2 defense value) sitting on a mountain tile. Even without adding terrain values, this should not have happened no matter when I did the attack. If I did the attack on a "lose" slot, i would lose, if done on a "win" slot, I would win. It didn't matter how many battles were fought in the turn. iirc, I had about 11 battles to do that test turn. My spearman won every time it was used during every win slot.

So I concluded it don't matter if you build better units, and whether you win or lose any given battler is pre-determined.

A couple of times, I did the save right before hitting end turn, and after the new turn generated, I would get the same win/lose order time and time again. So it may not be a new generation each turn either. I think it does have something to do with the accumulated power for all units in your civ. IE, if you want to win more often, have more units civ-wide. put 2 or3 defenders in each town, instead of only one. However, that is very hard to get a test done using actual game reloading. save, end turn, determine sequence VS save, disband units, end turn, determine sequence.

Hope this helps determine the extent of how broke the combat is. I prolly wont re-visit this thread, so if you had any questions, feel free to email me. (realpissed_2000@yahoo.com)

[Excelsior]

Originally posted by drmofe
If you use integer arithmetic to generate your numbers, your implementation has a DRASTIC effect on the distribution of the results. If CivIII is implemented this way, it would explain a few things :-)
See here for an explanation of this effect with respect to Java:

http://developer.java.sun.com/developer/JDCTechTips/2001/tt0925.html

The same principle applies to your example above.

In essence, you must keep the result of rand() as a double-precision and base your outcome on the normalized distribution between 0 and 1. If you don't you skew the distribution and make it less random.

I rewrote all the test programs I made to use a floating point generator rather than an integer generator. THe generator I used was the "Mersenne twister." I found it at http://www.agner.org/random/randomc.htm. The website claimed that "The random number generators found in standard libraries are often of a poor quality, insufficient for large Monte Carlo calculations. This library provides random number generators of a much better quality: Better randomness, higher resolution, and longer cycle lengths."

I then performed the tests again using the floating point function of the "Mersenne twister" and found that the results did not differ from those obtained from the integer generator by a particuarly large amount.

The results from the integer generator:
Attacker
One hit Streaks: 6,918,029
Two hit Streaks: 3,386,429
Three hit Streaks: 1,943,773

Defender
One hit Streaks: 7,420,790
Two hit Streaks: 3,471,117
Three hit Streaks: 2,444,853

The results from the floating point generator:
Attacker
One hit Streaks: 6,915,994
Two hit Streaks: 3,383,324
Three hit Streaks: 1,941,721

Defender
One hit Streaks: 7,421,830
Two hit Streaks: 3,473,021
Three hit Streaks: 2,446,943

Either way you generate the numbers, though, the results from the actual RNG in the game are not significantly different.

[Panag]

hi ,

bump

have a nice day

[Cyclotron]

You got that through my link, didn't you?

[Panag]

Originally posted by cyclotron7
You got that through my link, didn't you?

hi ,

yes , and now its no longer out of eyesight

have a nice day

[Excelsior84]

I haven't been to Apolyton in months, and what's the first thing I notice when I return? A thread I started over a year ago... So I searched up to find where you posted the link to it, and there it was. 9 pages of argument about the combat system. It's good to see nothing's changed while I was gone.

[Cyclotron]

Hmm, you should get your old profile back then...

Excecllent study, by the way. All the combat naysayers just need to look here.

[Excelsior84]

Originally posted by cyclotron7
Hmm, you should get your old profile back then...

Excecllent study, by the way. All the combat naysayers just need to look here.

Thanks.

I'm actually not quite sure what happened to my old account. I came back after being gone a couple of months early this year and discovered it no longer functioned. I can still log in, but it won't let me post. I thought maybe inactive accounts were disabled after a certain period (but I don't think that's it), because I know I didn't do anything to get banned!

[Excelsior84]

Originally posted by Tassadar5000
Too busy to read the study though I know the general message. All I have to say is: I've just given it another chance. No change in what's happend before. And no piece of paper or HTML page can prove me wrong there

Of course there's no change. The whole point is that the RNG is working randomly, and not producing more streaks or odd results than would be expected by random chance.

Are you still using the default hitpoints? I myself find the combat rather infuriating with the standard 3-5 hp, and find it to be much more reasonable at double or even triple that number. The combat results are thus more predictable, while still maintaining an element of randomness.

[Excelsior84]

Originally posted by Tassadar5000
No, of course not. I find that whenever I take the time to do ANYTHING in the editor to make the game to my liking, when I start it up either something is wrong, or (most of the time) the game crashes.

I've moved on and seen the light....

Suit yourself. I've never had such difficulties, though the modifications I've made weren't extensive.

[Cyclotron]

Tassadar, I wasn't implying that people who don't like the game will suddenly like it after reading this thread... only that it should put to rest any suspicions of irregularities on the part of the RNG.