darkpanda
Dark Prince
- Joined
- Oct 28, 2007
- Messages
- 823
Randomness in CIV
While looking at how CIV manages randomness (see this post), I discovered a design flaw that could be leveraged to bypass randomness.
To get started, let me re-state some initial findings on randomness, posted in the thread linked above:
If you are not familiar with such algorithms (which are very frequent in computer calculations), the basic idea you need to understand is that seed-based randomness is actually simulating randomness by selecting an initially hard to predict value - the seed - (system date and time, down to milliseconds if necessary), and then use complicated mathematical formulas applied to to this initial value to select the "next" random value.
The thing is, however complicated the mathematical formula can be, they are still deterministic, i.e. with the same input values, they will produce the same results. So, if the seed is initialized to the same value every time, then the sequence of "next" random values will always be the same!
Consequently, such algorithms are actually called pseudo-random in that they are good enough to look random, but they are essentially not random at all.
How can pseudo-randomness be exploited in CIV ?
In the case of CIV, the seeds are initialized based on system date&time during the opening credits. You would be right to think that, by controlling the system date and time when CIV starts, you may actually force the random algorithm to produce the same sequence of values every time. But a couple of issues come with this:
Fortunately, as part of the discussion in that previous thread, I discovered there is a place where CIV resets the seed during the course of game:
You can imagine how much this could simplify the control of randomness:
Discovering this, I was impatient to put it to the test... My first experiment is as follows:
For me, the results above are clear: displaying the City View forced the outcome of the tribal hut to be "metal deposits".
Since the new seed is computed using only the city name, I wanted to try changing the city name to control the outcome:
So the conclusion is that the outcome of the tribal hut visit can be controlled by the City name.
Now, looking at the City View code in CIV, there are plenty of calls to the random routine in order to select the positions of buildings. Obviously, the more citizens there are, the more houses to display, and also for every constructed improvement, there will be an additional random call to place it on the screen.
Those intermediate calls do not affect the seed itself, but it will affect the offset in the random sequence where CIV is when randomizing the tribal hut outcome.
I wanted to test this as well, so I re-did some series of test by modifying the city size and improvements"
Here are the results:
Moreover, if I sell the Barracks in the city size 3, then displaying the City View forces the hut outcome back to the previous situation (skilled mercenary - Legion).
Investigation is progressing but there are still more things to investigate:
TO BE CONTINUED...
While looking at how CIV manages randomness (see this post), I discovered a design flaw that could be leveraged to bypass randomness.
To get started, let me re-state some initial findings on randomness, posted in the thread linked above:
- CIV uses a very classic "seed"-based random algorithm:
- The algorithm is initialized with a pair of seed values S1 and S2, which are computed from the system date and time at CIV startup
- The random routine takes a single integer N as argument, and returns a value from 0 to N-1 included, computed using complicated mathematical formulas involving the input value N, and the seed values S1 and S2
- At the same time, every call to the random routine also re-updates the seed values S1 and S2
If you are not familiar with such algorithms (which are very frequent in computer calculations), the basic idea you need to understand is that seed-based randomness is actually simulating randomness by selecting an initially hard to predict value - the seed - (system date and time, down to milliseconds if necessary), and then use complicated mathematical formulas applied to to this initial value to select the "next" random value.
The thing is, however complicated the mathematical formula can be, they are still deterministic, i.e. with the same input values, they will produce the same results. So, if the seed is initialized to the same value every time, then the sequence of "next" random values will always be the same!
Consequently, such algorithms are actually called pseudo-random in that they are good enough to look random, but they are essentially not random at all.
How can pseudo-randomness be exploited in CIV ?
In the case of CIV, the seeds are initialized based on system date&time during the opening credits. You would be right to think that, by controlling the system date and time when CIV starts, you may actually force the random algorithm to produce the same sequence of values every time. But a couple of issues come with this:
- first, it is quite hard to control the date and time when CIV starts
- second it is even harder to make sure that the date and time when CIV initializes the seeds is always the same, as your CPU make take more or less time between the launch of CIV.EXE and the instruction that compute the seed.
Fortunately, as part of the discussion in that previous thread, I discovered there is a place where CIV resets the seed during the course of game:
darkpanda said:in addition, there are calls that, indeed, re-seed the randomness generator; typically, when displaying a City View, the random seed is re-initialized to the total sum of the city name's ASCII character codes (can you believe it! I just found this out 5 minutes ago...) while the 2nd variable is reset to 0; this ensures that a given city has always the same "random" - yet identical - streets and buildings layout
You can imagine how much this could simplify the control of randomness:
- you could control when the seed is initialized by displaying a City view
- moreover, you could control the value of the initial seed - and thus the sequence of random values! - by choosing a carefully crafted City (name, size, buildings)
Discovering this, I was impatient to put it to the test... My first experiment is as follows:
- The aim is to verify that randomness can be manipulated by displaying City View
- The initial condition: a newly started game, with just a 1-citizen capital city and a militia next to an unvisited tribal hut:
- I performed 3 series of tests: in each series, the test is run 10 times, and the outcome of the tribal hut visit by the militia is recorded:
- Series 1: the saved initial condition is re-loaded using the F10-hack, then the militia visits the tribal hut
- Series 2: the saved initial condition is re-loaded manually, by exiting then restarting CIV, then the militia visits the tribal hut
- Series 3: the saved initial condition is re-loaded using the F10-hack, then the City View is displayed, and finally the militia visits the tribal hut
- Hereunder are the outcomes of the 3 series of tests:
test # series 1 series 2 series 3 1 friendly tribe of skilled mercenaries (Cavalry) friendly tribe of skilled mercenaries (Cavalry) metal deposits of value 50 2 scrolls of ancient wisdom (Masonry) metal deposits of value 50 metal deposits of value 50 3 scrolls of ancient wisdom (Alphabet) friendly tribe of skilled mercenaries (Cavalry) metal deposits of value 50 4 scrolls of ancient wisdom (Horseback Riding) scrolls of ancient wisdom (Alphabet) metal deposits of value 50 5 metal deposits of value 50 metal deposits of value 50 metal deposits of value 50 6 metal deposits of value 50 friendly tribe of skilled mercenaries (Legion) metal deposits of value 50 7 metal deposits of value 50 scrolls of ancient wisdom (Masonry) metal deposits of value 50 8 metal deposits of value 50 scrolls of ancient wisdom (Alphabet) metal deposits of value 50 9 friendly tribe of skilled mercenaries (Legion) metal deposits of value 50 metal deposits of value 50 10 friendly tribe of skilled mercenaries (Cavalry) scrolls of ancient wisdom (Alphabet) metal deposits of value 50
For me, the results above are clear: displaying the City View forced the outcome of the tribal hut to be "metal deposits".
Since the new seed is computed using only the city name, I wanted to try changing the city name to control the outcome:
- Initially, the city name is Ulundi (I skipped Zimbabwe by mistake on pressing ESC on the first turn...). According to the seed formula, its value is computed as the sum of the name's ASCII character codes:
Code:U - 85 l - 108 u - 117 n - 110 d - 100 i - 105 ---------- [B]seed = [COLOR="Blue"]625[/COLOR][/B]
- I incremented the seed to 626 by changing the name to Uluodi
- Then I re-ran the series 3 and obtained the following results:
test # series 3 1 friendly tribe of skilled mercenaries (Cavalry) 2 friendly tribe of skilled mercenaries (Cavalry) 3 friendly tribe of skilled mercenaries (Cavalry) 4 friendly tribe of skilled mercenaries (Cavalry) 5 friendly tribe of skilled mercenaries (Cavalry) 6 friendly tribe of skilled mercenaries (Cavalry) 7 friendly tribe of skilled mercenaries (Cavalry) 8 friendly tribe of skilled mercenaries (Cavalry) 9 friendly tribe of skilled mercenaries (Cavalry) 10 friendly tribe of skilled mercenaries (Cavalry)
So the conclusion is that the outcome of the tribal hut visit can be controlled by the City name.
Now, looking at the City View code in CIV, there are plenty of calls to the random routine in order to select the positions of buildings. Obviously, the more citizens there are, the more houses to display, and also for every constructed improvement, there will be an additional random call to place it on the screen.
Those intermediate calls do not affect the seed itself, but it will affect the offset in the random sequence where CIV is when randomizing the tribal hut outcome.
I wanted to test this as well, so I re-did some series of test by modifying the city size and improvements"
- Series 4: the city size is 2
- Series 5: the city size is 2 and a Granary is built
- Series 6: the city size is 3
- Series 7: the city size is 3 and Barracks are built
Here are the results:
test # | series 4 | series 5 | series 6 | series 7 |
---|---|---|---|---|
1 | metal deposits of value 50 | friendly tribe of skilled mercenaries (Legion) | friendly tribe of skilled mercenaries (Legion) | scrolls of ancient wisdom (Masonry) |
2 | metal deposits of value 50 | friendly tribe of skilled mercenaries (Legion) | friendly tribe of skilled mercenaries (Legion) | scrolls of ancient wisdom (Masonry) |
3 | metal deposits of value 50 | friendly tribe of skilled mercenaries (Legion) | friendly tribe of skilled mercenaries (Legion) | scrolls of ancient wisdom (Masonry) |
4 | metal deposits of value 50 | friendly tribe of skilled mercenaries (Legion) | friendly tribe of skilled mercenaries (Legion) | scrolls of ancient wisdom (Masonry) |
5 | metal deposits of value 50 | friendly tribe of skilled mercenaries (Legion) | friendly tribe of skilled mercenaries (Legion) | scrolls of ancient wisdom (Masonry) |
6 | metal deposits of value 50 | friendly tribe of skilled mercenaries (Legion) | friendly tribe of skilled mercenaries (Legion) | scrolls of ancient wisdom (Masonry) |
7 | metal deposits of value 50 | friendly tribe of skilled mercenaries (Legion) | friendly tribe of skilled mercenaries (Legion) | scrolls of ancient wisdom (Masonry) |
8 | metal deposits of value 50 | friendly tribe of skilled mercenaries (Legion) | friendly tribe of skilled mercenaries (Legion) | scrolls of ancient wisdom (Masonry) |
9 | metal deposits of value 50 | friendly tribe of skilled mercenaries (Legion) | friendly tribe of skilled mercenaries (Legion) | scrolls of ancient wisdom (Masonry) |
10 | metal deposits of value 50 | friendly tribe of skilled mercenaries (Legion) | friendly tribe of skilled mercenaries (Legion) | scrolls of ancient wisdom (Masonry) |
Moreover, if I sell the Barracks in the city size 3, then displaying the City View forces the hut outcome back to the previous situation (skilled mercenary - Legion).
Investigation is progressing but there are still more things to investigate:
- Will it work for a series of huts ? i.e. if I have several huts that can be visisted, and I display the city before each hut, will I get the same outcomes every time ?
- Can I force battles to be victorious, even if a militia attacks a fortified Mech. Inf. ?
TO BE CONTINUED...
Last edited: