 |
| |
|
|
Excelsior
|
 |
Alabama
Nov 2001
time: 23:16
|
|
The following are the results of tests I have performed to help determine whether or not the random number generator used by Civ3 is in fact faulty. Many have alleged, including myself, that the random number generator is too "streaky." The following numbers are the results of 10,000,000 simulated encounters* between common ancient attackers and defenders. All combat is assumed to transpire on level ground with a 10% combat modifier to the defender. Each column displays the total number of each type of streak that occurred during all of simulated combat.
Now, in order to determine whether Civ3's random number generator is delivering an appropriately random result we will need results taken from the game. As yet, I do not have these results. It would be a lot easier if it had a cheat mode with which I could instantly put down 1,000 test subjects, but it doesn't. So, I call on the collective data gathering power of this entire forum to help collect the necessary data.
I would ask each of you to go fight an ancient era war and return the results of each combat. We want to know the exact number of each type of streak that occurred during combat. Once we have enough results, we can compare them to expected results. This will, hopefully, either prove that there is indeed something wrong with the random number generator, or that there is indeed nothing wrong with the random number generator.
Sorry about this PHP stuff, but it was the only way I could figure out to make the board not delete all of my tabs. It totally destroyed my tables. I don't know what PHP is supposed to do, and so I can't predict if it will show up properly, but it looks like it works on my end. It is still a big mess, but it is better than not having any spaces at all!
PHP:
The following is an example of what the data means. If a battle follows the pattern,
Attacker Defender
X
X
X
X
X
X
X
Defender Dies
, then the results of this combat are:
One Two Three Four
Attacker 1 0 1 0
Defender 1 1 0 0
4HP vs. 4HP
Results from 10,000,000 Confrontations
Attacker One Two Three Four
Archer 8,964,266 4,360,764 2,011,396 1,000,836
Defender One Two Three Four
Spearman 9,730,149 4,518,276 2,041,995 1,361,879
Results from 10,000,000 Confrontations
Attacker One Two Three Four
Archer 10,462,044 4,287,162 1,954,495 2,641,432
Defender One Two Three Four
Warrior 6,337,550 3,517,345 1,813,553 369,421
Results from 10,000,000 Confrontations
Attacker One Two Three Four
Swordsman 10,300,304 4,533,003 2,034,088 1,859,570
Defender One Two Three Four
Spearman 7,885,837 4,052,129 1,947,714 673,142
Results from 10,000,000 Confrontations
Attacker One Two Three Four
Swordsman 9,597,199 3,542,791 1,723,552 3,897,640
Defender One Two Three Four
Warrior 4,326,225 2,690,371 1,581,916 137,632
3HP vs. 3HP
Results from 10,000,000 Confrontations
Attacker One Two Three
Archer 6,918,570 3,383,259 1,943,113
Defender One Two Three
Spearman 7,422,891 3,470,202 2,445,965
Results from 10,000,000 Confrontations
Attacker One Two Three
Archer 7,884,940 3,306,257 3,976,614
Defender One Two Three
Warrior 5,131,003 2,843,250 921,083
Results from 10,000,000 Confrontations
Attacker One Two Three
Swordsman 7,784,038 3,471,340 3,080,190
Defender One Two Three
Spearman 6,197,744 3,195,090 1,445,633
Results from 10,000,000 Confrontations
Attacker One Two Three
Swordsman 7,294,638 2,806,963 5,253,033
Defender One Two Three
Warrior 3,674,535 2,273,300 436,849
*These numbers were generated using the srand() and rand() functions of C++ using the Visual C++ 6.0 compiler. The results were found to be consistent with minor random variation between multiple computers. The srand() function was seed with the current time using the time() function.
|
|
| |
|
|
|
Xerxes314
|
|
New York, NY
Nov 2001
time: 05:16
|
|
Why not make your life easier by eliminating all units from the game except the warrior and the galley and paving the world with grassland? Then you only have one kind of battle: 1 vs 1.1
You can also simplify things by giving everything 1hp, so that you don't have injured units running around.
Xerxes
Last edited by Xerxes314 on 25-11-2001 at 09:56
|
|
| |
|
|
|
Excelsior
|
|
Alabama
Nov 2001
time: 23:16
|
|
quote:
Originally posted by Xerxes314
Why not make your life easier by eliminating all units from the game except the warrior and the galley and paving the world with grassland? Then you only have one kind of battle: 1 vs 1.1
|
Good idea, I've put together a scenario that makes testing it easier. The entire map is grassland, still affording a 10% terrain bonus since I couldn't figure out how to change that. Cities, fortifications, forts, etc., however, now provide no defensive bonus at all. The only units available in the game are the worker, settler, explorer, scout, and warrior. Conscripts and regulars have 3 HP, while veterans and elites have 4 HP.
Keeping track of the streaks when the AI attacks is a little bit like a maddening game of "Simon," but it is managable if you only try to remember the first battle of every AI turn.
quote:
Originally posted by Xerxes314 You can also simplify things by giving everything 1hp, so that you don't have injured units running around.
Xerxes |
Wouldn't that invalidate the entire point of the data collection? I'm testing to determine whether or not the streaks in combat are more than one would expect from random chance. If there is only one hitpoint, there are no streaks.
Currently my policy is to not count any combat in which either combatant has less than 3 HP. If a 4HP unit is damaged 1 HP before combat, it counts in the results as being a 3HP unit.
Thus, there are four valid combinations:
3HP vs. 3HP
4HP vs. 4HP
3HP vs. 4HP
4HP vs. 3HP
So far, from the small amount of testing I've done today, these are the current results.
3HP vs. 3HP
3HP Attacker
One hit streaks: 37
Two hit streaks: 16
Three hit streaks: 6
3HP Defender
One hit streaks: 37
Two hit streaks: 13
Three hit Streaks: 15
4HP vs. 4HP
4HP Attacker
One hit streaks: 1
Two hit streaks: 0
Three hit streaks: 1
4HP Defender
One hit streaks: 0
Two hit streaks: 1
Three hit streaks: 0
3HP vs. 4HP
3HP Attacker
One hit streaks: 5
Two hit streaks: 2
Three hit streaks: 0
Four hit streaks: 1
4HP Defender
One hit streaks: 10
Two hit streaks: 2
Three hit streaks: 0
4HP vs. 3HP
4HP Attacker
One hit streaks: 7
Two hit streaks: 3
Three hit streaks: 0
3HP Defender
One hit streaks: 7
Two hit streaks: 3
Three hit streaks: 0
Four hit streaks: 0
I tried to upload the scenario that I used for testing, but the board wouldn't allow that file extension. Does anyone know if I could just rename the file with a different extension, or would the board just scramble the file?
|
|
| |
|
|
|
Excelsior
|
|
Alabama
Nov 2001
time: 23:16
|
|
quote:
Originally posted by GP
It seems like the statistics are behaving normally. You could come up[ with some type of confidence test. But It looks ok to me. (looks like a normal distribution) |
I'd agree, except for this:
"3HP Attacker
One hit streaks: 37
Two hit streaks: 16
Three hit streaks: 6
3HP Defender
One hit streaks: 37
Two hit streaks: 13
Three hit Streaks: 15"
Why are there more three hit streaks for the defender than two hit streaks?
- Is it simply the result of small sample size?
- Is that what a random distribution of streaks for two warriors should look like?
- Is it a bug in the Civ3 random number generator?
I just simulated 10,000,000 warrior vs. warrior encounters using the program I wrote. The results were as follows:
3HP Attacker
One hit streaks: 6,918,029
Two hit streaks: 3,386,429
Three hit streaks: 1,943,773
3HP Defender
One hit streaks: 7,420,790
Two hit streaks: 3,471,117
Three hit Streaks: 2,444,853
As you can see, there is no corresponding increase in the number of three hit streaks for the defender. Thus, I'm rather inclined to rule out #2.
|
|
| |
|
|
|
Zurai001
|
|
I'm inclined to say that's a combination of small sample size and the 10% defensive bonus for grasslands. BTW, you can remove that on the terrain tab of the editor.
|
|
| |
|
|
|
Excelsior
|
|
Alabama
Nov 2001
time: 23:16
|
|
These are the results,
3HP Attacker
One hit streaks: 6,918,029
Two hit streaks: 3,386,429
Three hit streaks: 1,943,773
3HP Defender
One hit streaks: 7,420,790
Two hit streaks: 3,471,117
Three hit Streaks: 2,444,853
of 10,000,000 warrior vs. warrior encounters that I simulated using a C++ program I wrote for the purpose. The idea is that this is the ratio that the streaks should occur within the game if the random number generator is functioning properly.
Streaks are considered to have stopped at the end of a battle, that is why the maximum length of a streak is 3. This is taken into account in the simulation. The 10% grassland bonus is accounted for in this simulation, that is why the defender has more of every type of streak.
My point was that from the defender in the 3HP vs. 3HP battles I have recorded actually had more 3 hit streaks than 2 hit streaks. This is not what one would expect based on these simulated battles. This may very well be the result of small sample size. It could also be the result of something screwy with the random number generator in civ3.
Either way, we still need more results from the game to reach a conclusion.
This is a screenshot from the scenario I used to create the results from the game.
 Attachment: lotofwar.jpg
This has been downloaded 891 time(s).
|
|
| |
|
|
|
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.
My current guess on how the random number generator works, (and ways around it)
Dice rolls are precomputed (or seeded) somehow at the beginning of every turn.
Some value between 0 and 1 is chosen for the defense and offsense - the value is then multiplied times the corrisponding defending and offensive strengths. Defender gets some bonus.
Thus, if it is important to win a battle it appears effective to use junk units - that is, one that is sure to be beaten, if you know that the first 'n' seed values are so low that the computer is going to win regardless.
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.
|
|
| |
|
|
|
Excelsior
|
|
Alabama
Nov 2001
time: 23:16
|
|
quote:
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.
quote:
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%.
|
|
| |
|
|
|
zapperio
|
|
Halifax, NS
Nov 2001
time: 05:16
|
|
Excellent thread Excelsior, and thanks for the testing and the numbers.
Zap
|
|
| |
|
|
|
Hurry
|
|
There is definately a queue of seeds at all times. Check my results in this thread (bottom of page): http://apolyton.net/forums/showthre...&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
Last edited by Hurry on 27-11-2001 at 20:39
|
|
| |
|
|
|
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.
|
|
| |
|
|
|
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
|
|
| |
|
|
|
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.
|
|
| |
|
| |
All times are GMT. The time now is 05:16.
Apolyton Time is 00:16. |
top of page
|
|
|
Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
|
HTML code is ON
vB code is ON
Smilies are ON
[IMG] code is ON
|
|
|
|
|
|
25-11-2001 07:00
Attachment: 
|
