Thoughts as to why the RNG may appear "streaky"

[etj4Eagle]

I have been thinking about why for some the RNG appears "streaky." A post from someone complaining that my examinations of the combat is useless because I have too large of a sample size got me thinking. What if the required sample size for statistical significance is larger than what a player will see in the course of one game. Hence the cause of the "streakyness" may be nothing more than an artifact of the size of the population that the random number is being returned from.

From a post in Dan's combat test map thread, we know that the RNG returns a 10 bit number (0-1023). That gives a population size of 1024 of possible numbers that can be returned. Now I assume that required size of a sample to be statistically significant is depent on the population size that you are pulling from. Ie you need to roll a 6 sided dice less times than a 20 sided one to see a normal distribution.

Now someone with formal statistical training should be able to give the rule of thumb formula that is used. However, from experience with rolling dice I would say that I would not expect to see an even distribution till on average each side had come up at least 4 times. Now for a population size of six this means you would need a sample size of 24 to expect an even distribution.

Now extend that to a population size of 1024 and well that gives 4096 sample events. For combat lets assume an average of 6 rounds for each engagement, well that is 682 2/3 engagements. Quite a bit.

Or for a different way of looking at it. The poster who reported 100 elite victories with no leaders. Well that is only 9.77% of the population, somehow I don't see that as a statistically significant sample size.

What this means is that for combat engagements and especially leader creation we are not working with a statistically significant sample size over the course of a game. Consequently statisics and the rules of randomness have no effect with the sample size that we are looking at.

The only way I really see to "fix" this problem is to reduce the size of the source population. If a 7-bit number is used instead that would reduce the possible numbers being returned by almost a factor of 10 and would at the same time still hopefully retain enough information to avoid negating the modifiers.

I hope that made enough sense. If not I will try to explain my thinking another way. BTW this is also why upping the number of hitpoints removes the "streaky" results as well, since it increases the sample size.

 

[Zouave]

 

[Rooker]

RNG?

Random Number Generator - or at least, that's what I think it is

 

[Lt. 'Killer' M.]

Wow, why is it always the simple things I never think about????

etj4Eagle, thanx a bunch!!!!

It may very well have something to do with it. I have long felt that the RNG is too streaky for the game, even if it is streaky within statistical limits!

 

[etj4Eagle]

Originally posted by Rooker
RNG?

Random Number Generator - or at least, that's what I think it is

Yep that is what RNG stands for, sorry should have used the long name once and put the short hand in ().

 

[Akka]

Good thinking, etj4eagle.
I would never have though about it myself, though as soon as you talked about it, it seemed obvious

Still, a 0,5 probability stay 0,5 whatever the sample size, it being 1 of 2 or 1 to 500 of 1000.
So I think there will tests to do with the RNG

 

[Zachriel]

Originally posted by etj4Eagle
I have been thinking about why for some the RNG appears "streaky."

A 1/16 chance per trial with 1000 trials is a virtual certainty (99.999999%), regardless of the other considerations. From what I understand, there is reloading occurring in the reported instance, so it is apparent that the random seed is being saved and reused. In other words, cards are being drawn from the deck, then the cards are returned to the top of the deck, then drawn again, over and over again. Or there is some other bug involved that apparently does not effect my own games.

Here is an online binomial calculator. Pay special attention to the "at least one", "exactly one" modifiers. For this calculation, we would use "at least one" leader per number of instances.
http://www.stat.sc.edu/~west/applets/binomialdemo.html

The RNG has passed every test for "randomness" performed thus far.

 

[etj4Eagle]

Originally posted by Akka
Good thinking, etj4eagle.
I would never have though about it myself, though as soon as you talked about it, it seemed obvious

Still, a 0,5 probability stay 0,5 whatever the sample size, it being 1 of 2 or 1 to 500 of 1000.
So I think there will tests to do with the RNG

Yep a 0.5 probability is the same for whatever the population size. However, you would expect to have to roll a 4 sided dice less to see the 50% probability than say a 100 sided dice.

Since the string 1, 2, 1, 2, 2, 1, 3 seems off

however the comparable string on a 100 sided die:
8, 39, 13, 41, 26, 19, 73 does not seem so off.

In one you have a sample size that is 175% the population size and the other only 7%.

And the RNG has been run through a statistical analyis suite (the DIEHARD tests) and passed them. See Dan's Combat Test Map Theard And scroll down the bottom of the second page for the post by hwinkels.

 

[Sanaz]

In a different thread (sorry, I forget who posted it), the idea was proposed that a single Elite unit can produce only one GL in a game. So, say a unit produces a GL. Then this same unit is set up and ready to fight, trying to produce another GL. It is tried, and no GL is produced. The game is reset with a NEW seed, and the battle is fought again. This is repeaated 1000 times, with no new GL. This looks streaky, but the battle being tested in reality may have had 0% chance of producing the GL. So, a DIFFERENT Elite unit is brought in for the same tests (one that has never produced a GL in this game). The same tests are run, and the statistical norm is seen - a GL is produced after a number of battles.

This explains a lot, since we don't generally keep track of which unit produced our GL, and may fight again and again with the same unit. This doesn't explain everything, but it's a great hypothesis for a lot of situations. Not as fancy as some, but easy on my simple brain at least!

 

[Akka]

Originally posted by etj4Eagle
Yep a 0.5 probability is the same for whatever the population size. However, you would expect to have to roll a 4 sided dice less to see the 50% probability than say a 100 sided dice.

Here I don't agree with you
The number of sides on a die does not change the numbers of tests you need to do to see a pattern appearing. Because what does count is not the total number of possibilities, but the chances that each events has to appear.

Well I'm not clear. Let's take an example. Imagine a 6 sided die and a 12 sided die. If the number of sides count, then you should say that you need twice more rolls to see the same probability on the 12-sides than on the 6 sided. That is true only if you want to see the equal chances of ALL the sides to show. Now if you're only willing to test a "1 out of 3" or "1 out of 2" chances, you can use one die or another without any change.
If you want to see a 50 % chance test, then the results 1, 2 and 3 on the 6-sides die are in fact the SAME event, not three different events. On the 12 sides die, it's the results 1 to 6 that are considered as the event "1".
So whichever die you roll, there is still two events, not 6 or 12.

I hope I was understandable, because I'm feel I'm somehow messy

 

[etj4Eagle]

Akka you may be right. All I am working with is conjecture in my mind and don't have any good stat books/pages available to help me think this through. Of course the algorithm's design could effect this hypothesis of mind greatly as well. Since if say every bit is generated independently, then the increased size would have no effect. It is also possible that the required sample size does not scale linearly with the increased population size.

Of course at the same time, maybe I am just suffering from the human mind's incapability of truly grasping random numbers. Since out of a thousand the string 2, 58, 96, 21, 37, 46, 88 is no different than the string 1, 1, 1, 1, 1, 1, 1 out of 10. But the first string looks a whole lot more reasonable to the humand mind, however they both have the same chance of occuring.

Though what I am curious to know is what is a statistically significant sample size? How many events do I need to be able to draw a conclusion on the resulting probability?

 

[sgrig]

etj4eagle, you are absolutely right that the sample mean gets closer to the population mean as the sample size increases. (I think that's what you were actually saying!)

This is basically what is called the Law of large numbers in probability theory.

Also there is an inequality, called Chebyshev inequality which states that for a random variable X, and for a positive number a,

P(|X-E(X)|>=a) <= Var(X)/a^2. (note P is probability, E expectation, Var is variance)

Applying this to the case where the X is the random variable M, the sample mean, with some rearrangement we get that

P(|M-m|<=a) >= 1- Var(Y)/(a^2 * n)

Where n is the sample size, and Var(V) is the variance of an individual sample point Y (a single 'die roll'). In this case each individual outcome has a uniform distribution from 0 to 1023, ie it is equally likely that Y will be any number from 0 to 1023. For a uniform distribution from 0 to N, variance = N*(N+2)/12. m is the population mean, ie in our case 511.5 (ie 1023/2).

Let S=Var(Y), then we have a simple relation:

n*a^2 = S/(1-p) Where p is such that the probability that M and m differ by less than a, is greater than p.

Sorry, this probably sounded like Martian, especially since it is very inconvinient to type maths in plain text!

But now we can apply the relation which we got:

It's easy to calculate that S=87381.25
Set p=0.8 and we have a sample size of 6 (an average combat in Civ3), then a =270. Now this result means that in a sample size of 6, the probability is more than 80% that the sample mean and population mean will differ by no more than 270.

For a sample size of 30, we get a=120. For n=1000, we get a=20.

Suppose we now want M to lie within about 10% of m, ie we want a to be about 50, p =0.9. Then n=350 - ie. in this case with probability greater than 90%, difference between M and m will be at most 50.

From these calculations it seems that the hitpower in Civ3 was chosen such that in combat the sample size is about the same as which is needed for the difference between M an m not to be exceeded by the standard deviation with a high probability. Because if a=Root(S) (ie std deviation), n= 1/(1-p), so is about 5-7 when p is 0.8 to 0.85.

Hopefully this post has shown something useful and that it is not too incomprehensible. Ask me in case something is not clear.

I also hope I haven't made any mistakes, but the results are reasonable so there is a high chance that it is more or less correct.

This was actually a useful bit of revision for exams for me! I am a first-year university maths student and I have exams in less than 3 weeks' time, and probability is one the examinable topics!

Oh yeah, I almost forgot: if the RNG range is reduced (ie from 1023 to something smaller), it won't affect much the results, because although S will be reduced and hence a, but a has to be compared relative to N (the RNG range), so after plugging in the value of S int terms of N and rearranging the formula above, we get:

a/N = Root((1-2/N)/(12(1-p)n)) so changing N will only change the term 1-2/N, but the change in it will be tiny because 1/N will still be very small.

For comparison, if p=0.9, n=10, N=1023, then a/N = 0.288. If N=127, as etj4Eagle suggested, a/N = 0.286. Ok it is smaller, but hardly noticeably smaller! Even drastically lowering N to 5 say, will only keep a/N at 0.223.

It seems therefore that the only way to defeat "streakyness" is too increase the sample size - ie increasing hit points of units.

There were no complaints about combat in Civ2, because there an average battle had at least 10-20 rounds, and even more in modern era (upto 60), so the greater sample size and hence fewer 'freak' results.

So Akka is right about the 6 and 12-sided dies.

 

[etj4Eagle]

Thanks sgrig, I was hoping that someone with some real statistical background would enter the thread and give an expert opinion (and hopefully math to back it up as well). I was wrestling with the idea in my head, but could not really disprove my conjuncture and decided to through it out (heck there have been more wild assertions) and let those with know how correct my conjecture).

I had a feeling that everything probably fell down to the number of combat rounds, and that increasing those would help alleviate the "wierd" results. SMAC base hit points were 10 and with singularity engines you got up to 60 hit points.

Next game I play I may try upping those values a fair bit and see what happens. And turning off "animate battles" should help avoid making battles take too long when I do that.

 

[sgrig]

Originally posted by etj4Eagle
Thanks sgrig, I was hoping that someone with some real statistical background would enter the thread and give an expert opinion (and hopefully math to back it up as well). I was wrestling with the idea in my head, but could not really disprove my conjuncture and decided to through it out (heck there have been more wild assertions) and let those with know how correct my conjecture).

I had a feeling that everything probably fell down to the number of combat rounds, and that increasing those would help alleviate the "wierd" results. SMAC base hit points were 10 and with singularity engines you got up to 60 hit points.

Next game I play I may try upping those values a fair bit and see what happens. And turning off "animate battles" should help avoid making battles take too long when I do that.

Unfortunately you can't set the HP values in Civ3 too high up, because the max RoF for bombard units is only 10, so giving somthing like 20 HP to a unit will render bombardment useless...

A good idea is also giving extra HP to more modern units, so that they have a greater edge over the obsolete unit.

 

[sumthinelse]

Originally posted by Sanaz
In a different thread (sorry, I forget who posted it), the idea was proposed that a single Elite unit can produce only one GL in a game. So, say a unit produces a GL. Then this same unit is set up and ready to fight, trying to produce another GL. It is tried, and no GL is produced. The game is reset with a NEW seed, and the battle is fought again. This is repeaated 1000 times, with no new GL. This looks streaky, but the battle being tested in reality may have had 0% chance of producing the GL. So, a DIFFERENT Elite unit is brought in for the same tests (one that has never produced a GL in this game). The same tests are run, and the statistical norm is seen - a GL is produced after a number of battles.

This explains a lot, since we don't generally keep track of which unit produced our GL, and may fight again and again with the same unit. This doesn't explain everything, but it's a great hypothesis for a lot of situations. Not as fancy as some, but easy on my simple brain at least!

Yes, in fact that is the cause of the "leader drought" of almost 300 elite victories without a leader being produced. I tested with new elite units many times and the leaders always appeared more or less within 30 tries. The random number generator did not have anything to do with the long "no leader" sequences, because the RNG was never even applied when it was simply impossible to create a leader.

 

[Quiet Sound]

Speaking of streaks I just experienced one.
The setup:
A fortified regular pikeman in a size 8 city built on grassland. There was no river between the city and the attacking units.
vs.
An attacking army of 3 vertran calvary modded with double A/D values (12/6).

The pikeman lost one hitpoint, then the army was reduced to one hitpoint per unit, i.e. each calavry attacked until it was reduced to one hitpoint and then retreated.
Back to the editor I go...

 

[Zouave]

Originally posted by Rooker
RNG?

Random Number Generator - or at least, that's what I think it is

Ahhhh.

I thought it was something like LNG - Liquid Natural Gas.

We really need a Glossary of Arcane Abbreviations on this site. I'm serious.