.com.unity Forums
  The Official e-Store of Shrapnel Games

This Month's Specials

Air Assault Task Force- Save $8.00
Bronze- Save $10.00

   







Go Back   .com.unity Forums > Illwinter Game Design > Dominions 2: The Ascension Wars

Reply
 
Thread Tools Display Modes
  #1  
Old February 5th, 2005, 12:55 AM

alexti alexti is offline
First Lieutenant
 
Join Date: Dec 2003
Location: Calgary, Canada
Posts: 762
Thanks: 0
Thanked 0 Times in 0 Posts
alexti is on a distinguished road
Default Re: Random Magic Paths - is it truly random?

Quote:
Ivan Pedroso said:
In fact you could choose any two small positive numbers, epsilon >0 and delta >0, (could be 0.00000001 and 0.000000001) and it will then be possible to find a laaaarge number N that insures that:

If N dies are rolled then the probability of getting an observed frequency that deviates from 1/8 with more than the small number epsilon, is smaller than delta.

That is:
Probability( |"observed frequency" - 1/8| > epsilon ) < delta

Do you know how to proof it? I don't see any obvious one. Let us consider frequency of death picks.
Code:

Probability to roll exactly k out of n P(k,n) = C(k,n)*p0^k*(1-p0)^(n-k). (p0 = 1/8)

For simplicity, let's consider overrunning your range up. Probability of that P(m+,n) = sum[k=m..n]{P(k,n)},
where m is smallest that satisfy m/n > p0 + epsilon.
Ignoring rounding effects we can write m=a*n, where a = p0 + epsilon.
Then P(m+,n) = sum[k=m..n]{P(k,n)}
= p0^(a*n) * sum[k=a*n..n]{C(k,n)*p0^(k-a*n)*(1-p0)^(n-k)}.

And that's where I'm getting stuck. p0^(a*n) quickly goes to 0 when n grows,
but the sum part has number of elements proportional to n,
with the dominant n! on the top, so it will grow very quickly.
Does this P(m+,n) converge to anything? And if it does, to what value?



I have tried to run a test program to see what is happening.
I didn't have few billion years to wait until the probability to get within the epsilon = 0.00000001 will become distinguishable from 0, so I took 0.002 as epsilon. Unfortunately, at around n=3000 my program is running out of precision of double. At that moment P(m+,n) is around 40%. Until then it was slowly going down, but the rate of descend was decrementing. So, the experiment didn't suggest any conclusion

Quote:
Ivan Pedroso said:
And then adding up the three largest observed frequencies will then result in a value that is in the interval
[3/8 - 3*epsilon ; 3/8 + 3*epsilon]

That looks wrong. You could do this if your frequencies were independent random processes. However, in our case they are dependent from each other, because the total of all frequencies is always 1. And of course, sum of three largest frequencies is always >= 3/8, but that isn't a problem.

I'm still unsure if your theorem is right or not, but your proof needs fixing.
Reply With Quote
  #2  
Old February 5th, 2005, 12:58 AM

alexti alexti is offline
First Lieutenant
 
Join Date: Dec 2003
Location: Calgary, Canada
Posts: 762
Thanks: 0
Thanked 0 Times in 0 Posts
alexti is on a distinguished road
Default Re: Random Magic Paths - is it truly random?

To everybody who submits statistics from the real games. Please make sure that you were not conducting any particular strategy with those random mages (meaning that you sure that some of them couldn't have been killed in the battles or by assasins, remote spells etc). Also if you were buying those mages until you got some particular pick, your statistics is also invalid (because it's guaranteed that it doesn't contain more than once instance of that pick)
Reply With Quote
  #3  
Old February 5th, 2005, 07:12 AM
Kristoffer O's Avatar

Kristoffer O Kristoffer O is offline
General
 
Join Date: Aug 2003
Location: Sweden
Posts: 4,463
Thanks: 25
Thanked 92 Times in 43 Posts
Kristoffer O is on a distinguished road
Default Re: Random Magic Paths - is it truly random?

Hmm, strangest thread I've seen in a while. I have a feeling it tells us something. Perhaps not about the topic of the thread. Interesting reading anyway
__________________
www.illwinter.com
Reply With Quote
  #4  
Old February 5th, 2005, 09:29 AM
bone_daddy's Avatar

bone_daddy bone_daddy is offline
Private
 
Join Date: Jan 2005
Location: Indiana, USA
Posts: 36
Thanks: 0
Thanked 0 Times in 0 Posts
bone_daddy is on a distinguished road
Default Re: Random Magic Paths - is it truly random?

Yeah. It tells us that we're all a bunch of nerds. :-)
Not that that's a bad thing. I'm a nerd, my wife's a nerd, and hopefully my son will grow up to be nerd.
Reply With Quote
  #5  
Old February 6th, 2005, 11:58 PM

Ivan Pedroso Ivan Pedroso is offline
Corporal
 
Join Date: Feb 2004
Location: Denmark
Posts: 67
Thanks: 0
Thanked 0 Times in 0 Posts
Ivan Pedroso is on a distinguished road
Default Re: Random Magic Paths - is it truly random?

Quote:
alexti said:
Quote:
Ivan Pedroso said:
[snip]
That is:
Probability( |"observed frequency" - 1/8| > epsilon ) < delta

Do you know how to proof it? I don't see any obvious one.

"the Law of Large Numbers" (or is it called something else, can't remember it) ensures that:
"The more you repeat the random process the more the empirically measured frequencies approach the values of the ''true'' underlying probabilities"
- repeatedly roll some eight-sided dies and your observed frequencies will get closer and closer to 1/8 as you go along.

Quote:
alexti said:
Quote:
Ivan Pedroso said:
And then adding up the three largest observed frequencies will then result in a value that is in the interval
[3/8 - 3*epsilon ; 3/8 + 3*epsilon]

That looks wrong. You could do this if your frequencies were independent random processes. However, in our case they are dependent from each other, because the total of all frequencies is always 1. And of course, sum of three largest frequencies is always >= 3/8, but that isn't a problem.

I'm still unsure if your theorem is right or not, but your proof needs fixing.
Sure... I should have used the interval: [3/8 ; 3/8+3*epsilon]
Adding up any three empirical frequencies will (very likely) result in a value that is included in the interval [3/8-3*e ; 3/8+3*e]. Adding the three largest will make the value end up in the smaller interval above.

(hehehe I could be a pedantic arse and state that the smaller interval is contained in the larger and still claim my statement to be true - but I simply just forgot about the obvious lower limit of 3/8 - made me look a bit foolish.)

I made a crude program to empirically calculate the Duck_Number: (I like MatLab )

Code:

clear %%% Clears stuff.
rand('state',sum(100*clock)); %%% Random seed gets mixed up a bit.
m=[0 0 0 0 0 0 0 0]; %%% A vektor is created:
%%% The first entry could be FIRE
%%% the second AIR, and so on.
N=100000 %%% Number of mages to be generated.
for I=1:N
roll=randint(1,1,8)+1; %%% Random integer between 1 and 8.
m(roll)=m(roll)+1; %%% The appropriate entry (FIRE, AIR...
end %%% gets bumped up by one.
f=m/N %%% The generated frequencies are computed.
sf=sort(f); %%% Frequencies are sorted (ascending order).
duck=sf(8)+sf(7)+sf(6) %%% The three highest values are added.



Doing a handfull of runs (N=100000) resulted in:
Duck_Number ~ 0.377
as a reference: 3/8 = 0.375
__________________
If I have seen further, it is by standing on the shoulders of Niefel Jarls
- Sir Ice-ac Newton
Reply With Quote
  #6  
Old February 7th, 2005, 02:55 AM

alexti alexti is offline
First Lieutenant
 
Join Date: Dec 2003
Location: Calgary, Canada
Posts: 762
Thanks: 0
Thanked 0 Times in 0 Posts
alexti is on a distinguished road
Default Re: Random Magic Paths - is it truly random?

Quote:
Ivan Pedroso said:
Quote:
alexti said:
Quote:
Ivan Pedroso said:
[snip]
That is:
Probability( |"observed frequency" - 1/8| > epsilon ) < delta

Do you know how to proof it? I don't see any obvious one.

"the Law of Large Numbers" (or is it called something else, can't remember it) ensures that:
"The more you repeat the random process the more the empirically measured frequencies approach the values of the
''true'' underlying probabilities"
- repeatedly roll some eight-sided dies and your observed frequencies will get closer and closer to 1/8 as you go along.

Ahh... I think your statement comes from Chebyshev's inequality. So it solves it. I guess to learn how to prove it I'll have to look up in the book

Quote:
Ivan Pedroso said:
Quote:
alexti said:
Quote:
Ivan Pedroso said:
And then adding up the three largest observed frequencies will then result in a value that is in the interval
[3/8 - 3*epsilon ; 3/8 + 3*epsilon]

That looks wrong. You could do this if your frequencies were independent random processes. However, in our case they are dependent from each other, because the total of all frequencies is always 1. And of course, sum of three largest frequencies is always >= 3/8, but that isn't a problem.

I'm still unsure if your theorem is right or not, but your proof needs fixing.
Sure... I should have used the interval: [3/8 ; 3/8+3*epsilon]
Adding up any three empirical frequencies will (very likely) result in a value that is included in the interval [3/8-3*e ; 3/8+3*e]. Adding the three largest will make the value end up in the smaller interval above.

(hehehe I could be a pedantic arse and state that the smaller interval is contained in the larger and still claim my statement to be true - but I simply just forgot about the obvious lower limit of 3/8 - made me look a bit foolish.)


What is wrong is that if you select N for epsilon, delta for the first path, using the same N for the second path is wrong, because after you've fixed one path, the distribution of the other remaining picks between paths is not the same as before. The interval didn't really matter, it was just a consequence of not considering that those variables became dependent.

However, you can prove by applying your reasoning to the random variables X1...Xm (m = C(3,8)) which represent rolling one of the 3 picks (for each combination of 3 paths), with mean = 3/8 for each variable. Than applying your original logic, selecting such N that
Probability( |"observed frequency of Xi" - mean| > epsilon ) < delta
Here, max ("observed frequency of Xi") is a "duck number", so it proves it.

So this case looks closed
Reply With Quote
  #7  
Old February 7th, 2005, 07:22 AM

Ivan Pedroso Ivan Pedroso is offline
Corporal
 
Join Date: Feb 2004
Location: Denmark
Posts: 67
Thanks: 0
Thanked 0 Times in 0 Posts
Ivan Pedroso is on a distinguished road
Default Re: Random Magic Paths - is it truly random?

(Sure - "choosing a large N" was always meant as: "as large as needed for the stuff to be correct".)

Back to the original question - has anyone found any significant deviations that suggest any hokey-pokey in the randomness ?!?
__________________
If I have seen further, it is by standing on the shoulders of Niefel Jarls
- Sir Ice-ac Newton
Reply With Quote
  #8  
Old February 7th, 2005, 11:47 AM

alexti alexti is offline
First Lieutenant
 
Join Date: Dec 2003
Location: Calgary, Canada
Posts: 762
Thanks: 0
Thanked 0 Times in 0 Posts
alexti is on a distinguished road
Default Re: Random Magic Paths - is it truly random?

It doesn't look likely to happen, the sample needed to find anything with a reasonable probability of correctness seems to be too big. My test with sample of 3000 wasn't even close to the point when the distribution significantly condenses, in your 100000 sample result is still 0.5% off.

What is the size of the sample required to show that there's a problem (using duck number indicator) with a 99.99% probability?

I think we'd need the code of RNG to test it on large samples...
Reply With Quote
  #9  
Old February 7th, 2005, 01:33 PM
Alneyan's Avatar

Alneyan Alneyan is offline
General
 
Join Date: Sep 2003
Location: United Kingdom
Posts: 3,603
Thanks: 0
Thanked 22 Times in 22 Posts
Alneyan is on a distinguished road
Default Re: Random Magic Paths - is it truly random?

I suppose there would be no way to create a program able to count the magic paths on Spectres? Getting high number of mages is not difficult, but counting them is (I currently have 4,000 spectres or so, with 128 spectres summoning a spectre every month). Of course, the game *will* crash sooner or later, but I think having as many mages as the game can handle should be good enough for this purpose. Or perhaps several such tests could be run?

Now, the question would be how to count all those magic paths without spending a lifetime on the matter. With further experimentation, I noticed the Nation Overview wouldn't work with that many commanders, and only one hundred commanders can be moved at once to another province. The game also hangs up sometimes when running a turn, but brute force seems to solve the problem, for now at least.
Reply With Quote
  #10  
Old February 7th, 2005, 02:22 PM
Arralen's Avatar

Arralen Arralen is offline
Major General
 
Join Date: Nov 2000
Location: 500km from Ulm
Posts: 2,279
Thanks: 9
Thanked 18 Times in 12 Posts
Arralen is on a distinguished road
Default Re: Random Magic Paths - is it truly random?

Err.. folks, I don't think, and the original claim wasn't about it either, that the RNG code is broken per se.

It's just that you e.g. get the "same" mage three times in a row in one game, say with earth/air as random pick, and in the next game, you only get nature and something, but never an air mage (while playing the same nation again).
And sometime the behaviour changes suddenly mid-game.

Would this be "singular" happenings, I woulnd't bother, but I have seen this way to often to write it off as Murphy's law or statistical effects or whatever.

But the error is not with the RNG, but with either the seed that is fed to it (and not re-set for some turns, essentially resulting in the same random number again) or with the code that turns that random num into the actual commander (maybe using old data from the previous turn, or copying the last build commander or something).

Wild guess: That bug about strangely ressurected commanders/heros, which turn up with other nations isn't fixed, too, as noone can figure out how and when it happens, right? Maybe there's some connection ???
__________________
As for AI the most effective work around to this problem so far is to simply use an American instead, they tend to put up a bit more of a fight than your average Artificial Idiot.
... James McGuigan on rec.games.computer.stars somewhen back in 1998 ...
Reply With Quote
Reply

Bookmarks


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is On

Forum Jump


All times are GMT -4. The time now is 02:06 PM.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Copyright ©1999 - 2025, Shrapnel Games, Inc. - All Rights Reserved.