PDA

View Full Version : Random Magic Paths - is it truly random?


Bummer_Duck
February 2nd, 2005, 04:07 PM
Hi!

So...I'm in my first real game. I have played a bunch of test beds, and sims to get familiar with the combat system, and what to research when. I have been concentrating on Vanheim for now, and I have noticed that the random magic picks don't seem to be that random. Each game is different, though. In one testbed/game, I may be flush with earth3, blood1 and earth3, Death1 Drawfs, and never get Fire or Astral. In the next game, I don't get any Blood or Death, but get earth3, air1 and earth4. I'm talking about a fairly good sample, of 14+ dwarf mages. While it isn't a huge sample, IMO it shows a pattern of non randomness.

Above and beyond this, the Sages that I recruit seem to follow the same sort of nonrandom distribution that the Dwarfs share per game. Is this a known bug? or is it just me. :-)

Chazar
February 2nd, 2005, 04:20 PM
There are three types of random picks: Elemental, Sorcery, and totally random. Otherwise chances should be equal.

Alneyan
February 2nd, 2005, 04:21 PM
Random paths are as random as they came, at least in the examples you give. Only the following characteristics can alter the distribution of random paths:

- Some units have Sorcery (Nature, Astral, Death, Blood) randoms, others have Elemental randoms, while most randoms are full randoms. A few units have both randoms (the Celestial Master among them, if memory serves).
- A few units do not have two randoms, but instead a random +2 level in the same path. This random could also be Sorcery, Elemental or a full random. Atlantis has a mage with this pattern: 3 water, and 2 randoms in the same path.
- Murphy's Law, obviously. If you need a fire random badly, you will never get that random. Ever. Your neighbours, of course, will have their hands full of Garnet Amazons, sages with a pick in fire, and things of the like. Should you attempt to "convert" their mages, you will end up taking their non-fire mages away.

The_Tauren13
February 2nd, 2005, 04:57 PM
Well, it is an obvious fact that over half of all PC games have poor random number generators. I'm sure this is just another example of that.

alexti
February 2nd, 2005, 09:14 PM
Bummer_Duck said:
I have been concentrating on Vanheim for now, and I have noticed that the random magic picks don't seem to be that random. Each game is different, though. In one testbed/game, I may be flush with earth3, blood1 and earth3, Death1 Drawfs, and never get Fire or Astral. In the next game, I don't get any Blood or Death, but get earth3, air1 and earth4. I'm talking about a fairly good sample, of 14+ dwarf mages. While it isn't a huge sample, IMO it shows a pattern of non randomness.



I don't see any pattern in your examples, it looks totally random (I assume that you know that earth3 is fixed and only one path is random). As you said in each game you've got different sequence of randoms which is the right behaviour for randoms. I would get concerned if you've observed something like Astral-Death-Blood-Earth-Air-... pick in every game.

alexti
February 2nd, 2005, 09:22 PM
The_Tauren13 said:
Well, it is an obvious fact that over half of all PC games have poor random number generators. I'm sure this is just another example of that.


I assume that you talk about pseudo-random number generators (because all software RNG are totally deterministic), But then that is some statement. Obvious why and to whom? Over half - where this number comes from? poor - how do you define "poor"?

To find a fault in most current pseudo-RNG (usually they have one fault or another) one needs to do quite a bit of research, which doesn't look possible by observing game's behaviour, because it would take too much time to collect meaningful statistics.

The_Tauren13
February 2nd, 2005, 10:59 PM
alexti said:
To find a fault in most current pseudo-RNG (usually they have one fault or another) one needs to do quite a bit of research, which doesn't look possible by observing game's behaviour, because it would take too much time to collect meaningful statistics.



Oh I quite disagree; it doesn't take long to realize. Examples of incredibly poor games: Disciples II: The hit percentages never worked well. Most notably paralyziation; you would frequently hit 10 in a row, and then miss 10 in a row. Warlords IV: A low combat creature is fighting a high combat creature and the weaker hits, nearly every time the high combat creature would then miss his next attack. Odd behavior like that is hard to miss.
The use of the term pseudo-random is pointless; there is no randomness in our universe. None. It is similar to when people argue that everything humans do is also natural because we are natural; the term becomes meaningless by its own definition.

By 'poor' I simply mean they simulate statistical results with less accuracy than one would expect. Perhaps I should say: 'less accuracy than I would expect', since you seem to be argumentative. Perhaps that was not meant as a flame against my intelligence, but it sure sounded like it.

quantum_mechani
February 2nd, 2005, 11:16 PM
The_Tauren13 said:


there is no randomness in our universe. None.



Er, so you are saying quantum mechanical probabilities are pre-determined?

Graeme Dice
February 3rd, 2005, 02:00 AM
The_Tauren13 said:
Well, it is an obvious fact that over half of all PC games have poor random number generators.



It's also an obvious fact that 76.45% of all statistics are made up on the spot.

Graeme Dice
February 3rd, 2005, 02:01 AM
The_Tauren13 said:
The use of the term pseudo-random is pointless; there is no randomness in our universe. None.



Here. Take this atom of U-238. Please tell me exactly when it will decay.

alexti
February 3rd, 2005, 02:08 AM
The_Tauren13 said:

alexti said:
To find a fault in most current pseudo-RNG (usually they have one fault or another) one needs to do quite a bit of research, which doesn't look possible by observing game's behaviour, because it would take too much time to collect meaningful statistics.



Oh I quite disagree; it doesn't take long to realize. Examples of incredibly poor games: Disciples II: The hit percentages never worked well. Most notably paralyziation; you would frequently hit 10 in a row, and then miss 10 in a row. Warlords IV: A low combat creature is fighting a high combat creature and the weaker hits, nearly every time the high combat creature would then miss his next attack. Odd behavior like that is hard to miss.


I'm not familiar with those games, but generall I doubt that you can distinguish RNG problem from the bug in the code. For example, Dom2 had a bug with mind duel, where it was OE D6 instead of simple D6. By monitoring statistics you could have thought that the problem is in RNG.


The_Tauren13 said:
The use of the term pseudo-random is pointless; there is no randomness in our universe. None. It is similar to when people argue that everything humans do is also natural because we are natural; the term becomes meaningless by its own definition.

By 'poor' I simply mean they simulate statistical results with less accuracy than one would expect. Perhaps I should say: 'less accuracy than I would expect', since you seem to be argumentative.


RNG are not designed to simulate statistical results. They're simulating stochastic processes. Statistics are result of observation of the stochastic process. Any statistics resulting from the observation of stochastic process is a stochastic process itself. That's what make it hard to make reliable conclusions about stochastic process from the statistics.

Consider the original post with those dwarven smiths. Assuming that randoms are uniformly distributed, probability that 2 particular paths won't appear in a sequence of 14 smiths is (6/8)^14 = 0.0178. There 7+6+...+1 = 28 different pairs of 2 paths. So probability of not getting some 2 paths in a sequence of 14 smiths is 0.0178*28=0.4989. Just about like flipping that famous two-sided coin. So the examples that the poster has shown falls well within expected results. So after doing these calculations, original example looks like: "I've flipped coin and got tails 4 times in a row. Is it a buggy coin or am I missing something?" Now consider that there're few hundreds people playing Dominions here (some of them are quite familiar with probability theory, so we exclude them from this consideration) who do our "flips". It is very probable that few of them will get quite a few tails in a row. So one of them has posted his question (remember that in the actual case it is not immediately obvious that the probability of that outcome is 50%)


The_Tauren13 said:
Perhaps that was not meant as a flame against my intelligence, but it sure sounded like it.


It was meant to question your knowledge of probability theory. You've jumped on Bummer_Duck hyphotesis/question claiming absolute knowledge (please reread your post) without any kind of backing. On top of that after closer examination Bummer_Duck's example is likely to be observed with ideal RNG. Of course, that doesn't prove that there's no problems with RNG, but this test, it passes very well.

Btw, I've noticed that you were not losing time meanwhile and have expanded your knowledge from over a half of PC games to the whole universe http://forum.shrapnelgames.com/images/smilies/wink.gif

Ygorl
February 3rd, 2005, 02:53 AM
Graeme, I read it was 95%.
Tauren, even just using rand() is pretty damn good. It's not perfect; if you look closely, you can tease out a little bit of structure from it... But it's nothing that you'd notice by playing a game.
What IS noteworthy is the human brain's ability to find structure and pattern... even when it's not there, or when it's there only by chance. Once we've convinced ourselves it's there, another one of our great skills is disregarding evidence to the contrary.
To make it concrete: there's an enormous amount of variability and complexity in Dominions (and, to some extent, most video games). Just by chance, sometimes things that look like patterns emerge (just like, if you flip a coin long enough, you'll see a run of ten heads; if you flip a thousand coins, you'll probably see such a run pretty frequently). Those tend to stand out, and we look for them. When we see them again, the tendency is to say "See? This isn't random!", while missing (because they're not salient) all the times we could have seen them but didn't.

FarAway Pretender
February 3rd, 2005, 03:01 AM
I once thought I had a random thought, but then it turned out to be improbable...


That aside, I have felt the same way as Bummer Duck. However, I suspect that's just a perception thing, rooted in my own desperation to get whatever I'm not getting. When I get what I'm looking for the first time, I spend a lot less time thinking about how unlikely that was--I just pack up my army and march out to whip whatever booty I can find nearby!

Bummer_Duck
February 3rd, 2005, 11:38 AM
Yes, I realize the earth3 is standard, and drawfs only get 1 random.

It could very well be a perception thing. It is true that I have probably gotten a complete random distribution, if I add all the test bed games together.

However, I find it strange that in each game I tested, the majority of the dwarves random picks are in 2 paths. I have testbeded at least 8 games, and have *never* gotten representation of all magic paths in 1 game. I find this, in and of itself, questionable. Perhaps I just don't understand RNG?

alexti
February 3rd, 2005, 12:00 PM
Bummer_Duck said:
However, I find it strange that in each game I tested, the majority of the dwarves random picks are in 2 paths. I have testbeded at least 8 games, and have *never* gotten representation of all magic paths in 1 game. I find this, in and of itself, questionable. Perhaps I just don't understand RNG?


How many smiths (or any mages with randoms you had)? For example, probability that you'll get every random path in a sequence of 8 smiths is 7/8*6/8*...*1/8 = 7!/8^7 = 5040/2097152=0.0024 - not that likely to happen, isn't it? With more smiths the chances obviously grow, so the question is how many of them you had.

Chazar
February 3rd, 2005, 12:03 PM
Bummer_Duck said:It could very well be a perception thing.


That's what I belive. I can recall quite a few games, where I deliberately waited for a fire random and only ended up with a lot of earth picks, and other games where I just needed a single earth pick and only got fire...

I do believe that pseudo-random number generation is generally good enough for games like Dom2. I also believe that "Murphys Law" is mostly due to the fact that oddities and failures are far easilier remembered than average things. I also recall a newspaper report about traffic-jams on multi-lane motorways and lane-hopping: People will always believe that they are in the one wrong lane which is progressing slowest. The report said that this is due to the fact that people who are waiting will notice each car that overtakes them, whereas overtaking others is far less memorizable. Generally, each car that you overtake gives much less satisfaction than the annoyance pereceived by each other car that overtakes oneself...

The_Tauren13
February 3rd, 2005, 01:47 PM
alexti said:
I'm not familiar with those games, but generall I doubt that you can distinguish RNG problem from the bug in the code. For example, Dom2 had a bug with mind duel, where it was OE D6 instead of simple D6. By monitoring statistics you could have thought that the problem is in RNG.


Whether or not the bug is in the code of the implementation of the random number algorithm used or that algorithm itself, it still comes to the same effect: the randomess for that game is bugged.


alexti said:
RNG are not designed to simulate statistical results. They're simulating stochastic processes. Statistics are result of observation of the stochastic process. Any statistics resulting from the observation of stochastic process is a stochastic process itself. That's what make it hard to make reliable conclusions about stochastic process from the statistics.


You are determined to think me the fool, simply by my choice of wording, when your English is not so perfect either. Lets just say, for it to not be 'poor', in my eyes, I should be able to observe the results of the RNG and accumilate reasonable statistical results.


alexti said:
It is very probable that few of them will get quite a few tails in a row. So one of them has posted his question


Perhaps your Dom II experience differs greatly from mine, but I have noticed many examples of random magic paths following odd distributions. Allow me to look at my current games: King of the Hill: 32 sages, no astral. So... (5/6)^32 ≈ .00293, .00293 * 6 magic paths ≈ .0176 = 1.76%... quite a low probablitity. Now we are looking at nearly 6 tails in a row, which is of course still believable... Unfortunately I am now forced to finish this message on another computer, so when I get home I can look at Borrowed Time as well and see the distribution of my Sauromancers' paths. If that isn't enough data for you, I could run a test game and recruit a hundred random mages... Hell, you could run a test game if youre not too busy. If I come up with more reasonable results, I may concede the point that Dominions II is not another example of a poor RNG. But it would take much more for me to concede my other examples... but those games aren't half as good as Dom II, so who cares http://forum.shrapnelgames.com/images/smilies/happy.gif. If you give me your email I could send you my turn files and you can check my mage counting...


alexti said:
Of course, that doesn't prove that there's no problems with RNG, but this test, it passes very well.


Perhaps, which is why I am attempting to further testing. But I dont have Dominions II installed here so you will have to wait.


alexti said:
Btw, I've noticed that you were not losing time meanwhile and have expanded your knowledge from over a half of PC games to the whole universe http://forum.shrapnelgames.com/images/smilies/wink.gif


Indeed. If you dispute my deterministic view of the universe and my claim that everything in the universe comes down to gravitational, nuclear, electromagnetic, etc. (which are not random) forces acting on atomic particles, go ahead, and we can argue that as well http://forum.shrapnelgames.com/images/smilies/happy.gif. And while the subject may be considered philosophical, please don't bring religion into it... I'm a hardcore atheist. And thanks for adding the smiley this time so I know you're not just trying to be insulting.

Bummer_Duck
February 3rd, 2005, 02:15 PM
I totally agree that 8 smiths is too small of sample. I believe I stated 14+ earlier, but perhaps not. In my current game, I will be recruiting my 15th drawf this year, and I am still missing representation of 2 magic paths. 3 paths represent 71.4% of the mages, with 3, 3, and 4 mages per magic path, respectively (3 magic paths have 1 representative each). This is the widest distribution of paths I can remember in all my tests. So...turn those equations around for me. How likely is it that in each game or test, that ~3 paths would represent +71% of the mages? shouldn't it approach 3/8? or 37.5% the larger the sample is? What am I missing here?

Graeme Dice
February 3rd, 2005, 02:43 PM
The_Tauren13 said:
Perhaps your Dom II experience differs greatly from mine, but I have noticed many examples of random magic paths following odd distributions. Allow me to look at my current games: King of the Hill: 32 sages, no astral. So... (5/6)^32 ≈ .00293, .00293 * 6 magic paths ≈ .0176 = 1.76%... quite a low probablitity.



And hardly outside of the realm of possibility either.



Indeed. If you dispute my deterministic view of the universe and my claim that everything in the universe comes down to gravitational, nuclear, electromagnetic, etc. (which are not random) forces acting on atomic particles, go ahead, and we can argue that as well http://forum.shrapnelgames.com/images/smilies/happy.gif.



So you are telling me that the moment when a particular atom of a radioactive element will decay can be determined before it decays? Because that's what you're claiming when you claim a deterministic universe. Of course people dispute your claim, because it's known to be false.

Yvelina
February 3rd, 2005, 04:21 PM
Here is some data for you number crunchers:

First game (three types of mages with randoms)

A: 0,3,0 - 3
E: 2,6,2 - 10
W: 2,8,0 - 10
F: 2,6,0 - 8
D: 1,1,0 - 2
S: 0,3,0 - 3
N: 1,4,0 - 5
B: 2,3,2 - 7

Looks pretty random to me.

Second game: (three types of mages with randoms)
A: 0,0,1 - 1
E: 2,3,8 - 13
W: 1,6,2 - 9
F: 2,3,2 - 7
D: 2,2,2 - 6
S: 4,4,2 - 10
N: 4,0,1 - 5
B: 2,3,2 - 7

A bit light on air... and frankly, I had not noticed, because I am Vanheim in both games (the mage types are smith, vanadrott and sage, of course)

Speaking of things I just realized, I guess I am hurting for cash in the first game http://forum.shrapnelgames.com/images/smilies/frown.gif

PvK
February 3rd, 2005, 05:13 PM
Alneyan said:
...
- Murphy's Law, obviously. If you need a fire random badly, you will never get that random. Ever. Your neighbours, of course, will have their hands full of Garnet Amazons, sages with a pick in fire, and things of the like. Should you attempt to "convert" their mages, you will end up taking their non-fire mages away.



I just really desperately needed a one-in-eight random magic path pick on a new mage... and I got it.

So, obviously the real explanation is ... I stole your luck! http://forum.shrapnelgames.com/images/smilies/tongue.gif

PvK

alexti
February 3rd, 2005, 10:19 PM
The_Tauren13 said:
You are determined to think me the fool, simply by my choice of wording, when your English is not so perfect either. Lets just say, for it to not be 'poor', in my eyes, I should be able to observe the results of the RNG and accumilate reasonable statistical results.



I don't claim the perfect knowledge of English, it's not even my native language, but I don't see any other possible meaning of your over half of all PC games have poor random number generators, but to think that you have either found somewhere a research that studied in details RNG in more than a half of PC games or you've conducted such a study yourself. Considering amount of time and effort required to perform such a task I find it hard to believe that your statement was based on facts and not on a wrong expectations from RNG. Another doubt comes, because RNG for uniformly distributed numbers is included in CRT and most games are likely to use it. Those RNG are not perfect, but you won't find their faults without collecting massive amounts of data.


The_Tauren13 said:

alexti said:
It is very probable that few of them will get quite a few tails in a row. So one of them has posted his question


Perhaps your Dom II experience differs greatly from mine, but I have noticed many examples of random magic paths following odd distributions. Allow me to look at my current games: King of the Hill: 32 sages, no astral. So... (5/6)^32 ≈ .00293, .00293 * 6 magic paths ≈ .0176 = 1.76%... quite a low probablitity. Now we are looking at nearly 6 tails in a row, which is of course still believable...



Now, am I missing something? Sages have complete random, right? So the probability of never getting one particular path in sequence of 32 sages is (7/8)^32=0.014 and the probability of never getting unspecified path in sequence of 32 sages is 0.11 - 11%. (That is 10.8% rounded to 11, not 0.014*8, because possibility of 2 missing paths needs to be taken into account). I assume that you would have made a similar observation if your 32 sages were missing some other path. So the probability of making your observation is any particular game is 11% (it's close to the probability of getting 3 tails in a row).


The_Tauren13 said:
Unfortunately I am now forced to finish this message on another computer, so when I get home I can look at Borrowed Time as well and see the distribution of my Sauromancers' paths. If that isn't enough data for you, I could run a test game and recruit a hundred random mages... Hell, you could run a test game if youre not too busy. If I come up with more reasonable results,



That again goes back to my question of your usage of "poor". What do you expect as "reasonable results"? Any particular result that you'll get has quite low probability of happening. However, when you play the game, some result *has* to happened. There isn't any "highly probable" result. RNG would start looking suspicious if you were repeatedly getting the same lowly probable results. (For example, missing astral in 32 sages in every game you've played).


The_Tauren13 said:
I may concede the point that Dominions II is not another example of a poor RNG. But it would take much more for me to concede my other examples... but those games aren't half as good as Dom II, so who cares http://forum.shrapnelgames.com/images/smilies/happy.gif. If you give me your email I could send you my turn files and you can check my mage counting...



I don't doubt your counting and I don't suspect your data, I just questioning the conclusion you make from those observations...


The_Tauren13 said:

alexti said:
Of course, that doesn't prove that there's no problems with RNG, but this test, it passes very well.


Perhaps, which is why I am attempting to further testing. But I dont have Dominions II installed here so you will have to wait.



This is well intended effort, but you need to understand what you're looking for. Let's say you look into some saved game and do the count. You can find some "unique feature" there (like 32 sages without astral). By itself, that doesn't indicate anything (because some result had to happen). However, if you can find the same "unique feature" in many other games, that will start to look suspicious. So I suggest you to list "unique features" you want to consider, then I will look for the same features in my games (I have few dozen of saved games I can check).



The_Tauren13 said:

alexti said:
Btw, I've noticed that you were not losing time meanwhile and have expanded your knowledge from over a half of PC games to the whole universe http://forum.shrapnelgames.com/images/smilies/wink.gif


Indeed. If you dispute my deterministic view of the universe and my claim that everything in the universe comes down to gravitational, nuclear, electromagnetic, etc. (which are not random) forces acting on atomic particles, go ahead, and we can argue that as well http://forum.shrapnelgames.com/images/smilies/happy.gif.



No... I'm disputing your ability to know every aspect of the universe http://forum.shrapnelgames.com/images/smilies/wink.gif To my knowledge deterministic/stochastic nature [of nearly anything] have not been established by the science and I haven't heard about anybody getting anywhere closer to understanding of those things. It is not even clear what kind of methods one can use to reliable establish deterministic/stochastic nature of something.

alexti
February 4th, 2005, 12:23 AM
Bummer_Duck said:
I totally agree that 8 smiths is too small of sample. I believe I stated 14+ earlier, but perhaps not.



Here calculations are getting more complicated.
Probability of 14 smiths missing one of the paths is 80.8%.


Bummer_Duck said:
In my current game, I will be recruiting my 15th drawf this year, and I am still missing representation of 2 magic paths. 3 paths represent 71.4% of the mages, with 3, 3, and 4 mages per magic path, respectively (3 magic paths have 1 representative each). This is the widest distribution of paths I can remember in all my tests. So...turn those equations around for me. How likely is it that in each game or test, that ~3 paths would represent +71% of the mages?



It seems to be even more complicated to calculate (Probability that 10 or more smiths out of 14 will be concentrated in 3 paths). It seems to be around 40-45%, but I had to drop the tail of the sequence, so I'm not sure about accuracy. I will try to calculate it precisely later.


Bummer_Duck said:
shouldn't it approach 3/8? or 37.5% the larger the sample is? What am I missing here?


You mean number of mages concentrated in 3 paths should approach 37.5% of total number of mages? - No it should not, what are you saying would effectively mean that the equal number of mages in each path, which is very unlikely event. On the large samples peak of probability will probably be somewhere in 45-60% range (that's very rough estimate, I will try to calculate it precisely some time later)

The_Tauren13
February 4th, 2005, 12:40 AM
alexti said:
Now, am I missing something? Sages have complete random, right?


Indeed. I must have been smoking something, for I was basing my probabilities off of there being only 6 magic paths http://forum.shrapnelgames.com/images/smilies/shock.gif


alexti said:
However, when you play the game, some result *has* to happened. There isn't any "highly probable" result.


Yes, I have not been too terribly clear. What I am specifically looking for is: large numbers of random mages of the same type being recruited, and a particular path having been unrepresented. So to refute my hypthesis, simply find several games in which all paths of magic are represented. The reason I was thinking a test game, though, is that in normal games (or at least my games) don't tend to have enough mages of one particular type to really formulate any conclusion. What I was thinking is just playing several games and recruiting 100+ mages, perhaps Vanheim dwarves as in the origional situation, and observing if frequently only 7 paths will be represented in the set.


alexti said:
I don't doubt your counting and I don't suspect your data, I just questioning the conclusion you make from those observations...


Which I do not deny are questionable, which is why I am making the attempt to gather somewhat more concrete data.


alexti said:
To my knowledge deterministic/stochastic nature [of nearly anything] have not been established by the science and I haven't heard about anybody getting anywhere closer to understanding of those things.


There is no reliable evidence, either way. In quantum machanics, effective observation is impossible. You cannot observe particle behavior without interfering with it. Also, simply because we do not have the means of predicting the exact behavior of such particles does not mean it is not possible to do so.

Yes, the general trend these days is to believe in Quantum Indeterminacy. This may have much to do with why I don't. I prefer to follow the less beaten paths. For example, I am currently working on an astrophysical project with the purpose of providing evidence to support Modified Newtonian Dynamics, an alternative theory to the widely supported Dark Matter Theory. Science requires disbelievers in order to continue its advancement. Where would we be if nobody ever questioned that the world was flat? http://forum.shrapnelgames.com/images/smilies/smirk.gif

Graeme Dice
February 4th, 2005, 12:58 AM
The_Tauren13 said:
Where would we be if nobody ever questioned that the world was flat?



About the same place we are now, since very few people ever believed that the world was flat.

alexti
February 4th, 2005, 12:59 AM
The_Tauren13 said:
The reason I was thinking a test game, though, is that in normal games (or at least my games) don't tend to have enough mages of one particular type to really formulate any conclusion. What I was thinking is just playing several games and recruiting 100+ mages, perhaps Vanheim dwarves as in the origional situation, and observing if frequently only 7 paths will be represented in the set.



You're right about the need to do it in testing game. I've started counting randoms in some finished game and noticed how few spectres have water. Then I've realized that I was using spectres with water as mini-SC for raiding, and obviously I've lost quite a few of them.

alexti
February 4th, 2005, 01:53 AM
About the tests. I suggest to take Jotuns or C'tis or Ermor with death mage pretender, research to Well of Misery and then set couple of mages on summon spectres monthly. After 24 hosting 24 turns you'll get 96 random picks (I was choosing multiplication of 8, so that Bummer_Duck's number (may I call it duck number?), which is max percentage of picks concentrated in 3 paths, can reach its ideal value.
Move all non-spectres out and count results in F1 screen. It seems to be doable under 10 minutes (unlike buying mages which can not be queued). I've just run 2 test games:

Game 1.
F-13,A-12,W-13,E-13,S-11,D-11,N-11,B-12. Duck number is 41%.

Game 2.
F-12,A-12,W-9,E-15,S-9,D-14,N-14,B-11. Duck number is 45%.

Ivan Pedroso
February 4th, 2005, 06:50 AM
alexti said:

Bummer_Duck said:
shouldn't it approach 3/8? or 37.5% the larger the sample is? What am I missing here?


You mean number of mages concentrated in 3 paths should approach 37.5% of total number of mages? - No it should not, what are you saying would effectively mean that the equal number of mages in each path, which is very unlikely event. On the large samples peak of probability will probably be somewhere in 45-60% range (that's very rough estimate, I will try to calculate it precisely some time later)



Hmmmmmm, why shouldn't it approach 3/8 ?!?

Let us assume that the distribution behind the scenes is uniform. Then the observed frequencies will approach 1/8. Of cause getting a sequence that actually results in an observed frequency of exactly 1/8 for every path will be highly unlikely, but they WILL approach 1/8 as the sample grows. I mean: if you use a uniform distribution to generate some values, then the distributed values will look more and more uniform. And therefor adding the frequencies of the three highest represented paths will tend towards 3/8 (from above obviously). I concede that getting the result 3/8 in a test sample will "never" happen.

atul
February 4th, 2005, 11:02 AM
Ivan Pedroso said:
Hmmmmmm, why shouldn't it approach 3/8 ?!?

Let us assume that the distribution behind the scenes is uniform. Then the observed frequencies will approach 1/8.


What you're missing here, assuming I've managed to follow the debate, is that they're talking about 3 most common random result. As there's selection based on how the randoms have turned out, the distribution is altered.

Gah, talking hard, let me give an example.

Two random numbers, x1 and x2, both with uniform distribution from zero to one. Each have an expected value of 0.5. But if you're asking what's the expected value of the _greater_ of two, that's 2/3!

Same thing told in the universal language of love (mathematics):
x1,x2 ~ U(0,1)
E(x1)=E(x2)=1/2
E(max(x1,x2))=2/3

My language or notation may be a bit off, but I hope the general idea is clear.

Of course, same applies to discrete case with magic randoms and so on, but is a bit harder to calculate.

alexti
February 4th, 2005, 11:39 AM
Ivan Pedroso said:

alexti said:

Bummer_Duck said:
shouldn't it approach 3/8? or 37.5% the larger the sample is? What am I missing here?


You mean number of mages concentrated in 3 paths should approach 37.5% of total number of mages? - No it should not, what are you saying would effectively mean that the equal number of mages in each path, which is very unlikely event. On the large samples peak of probability will probably be somewhere in 45-60% range (that's very rough estimate, I will try to calculate it precisely some time later)



Hmmmmmm, why shouldn't it approach 3/8 ?!?



Do you talk about convergence? Like lim(percentage, N->inf)= 3/8?


Ivan Pedroso said:
Let us assume that the distribution behind the scenes is uniform. Then the observed frequencies will approach 1/8. Of cause getting a sequence that actually results in an observed frequency of exactly 1/8 for every path will be highly unlikely, but they WILL approach 1/8 as the sample grows.



not WILL, only likely. For example, for any sample size, you have positive probability of getting all picks in one path. For samples of large size the distribution function will be getting more or more condensed, which you may call "approach". But you can't provide N for some small value x such that percentage of picks concentrated in 3 paths will deviate from 3/8 by no more than x.


Ivan Pedroso said:
I mean: if you use a uniform distribution to generate some values, then the distributed values will look more and more uniform. And therefor adding the frequencies of the three highest represented paths will tend towards 3/8 (from above obviously). I concede that getting the result 3/8 in a test sample will "never" happen.


The resulting process (the percentage of picks concentrated in 3 paths) is also a random process. That means that for different samples of the same size will produce different results.

The chances of getting 3/8 are getting smaller as you increase the sample size. The root of the issue is that the more your sample size is, the more possible outcomes can happen. That makes every particular outcome less and less likely to happen.

This random process also has a certain distribution. Which will roughly look like:
<font class="small">Code:</font><hr /><pre>
xxx
xxxxxxx
xxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxx
3/8 1
</pre><hr />

If we pick the range [x1,x2] that covers 99% of possible outcomes, then we could show that lim (x1, N-&gt; inf) = lim (x2, N-&gt; inf) = 3/8 (well, I think we can show), which intuitively seems as "approach", but unlike convergence, this "approach" has a stochastic character, like the difference between *will* and *most probably will*

Bummer_Duck
February 4th, 2005, 12:40 PM
Ok, the math you guys are throwing out is just beyond me. I would, however, dispute lumping all mages into the same catagory for a test, though. There could be a problem with 1 particular unit type. If I have some time this weekend, I'll try a few Drawf recruiting tests too.

Thanks for the responses!

The Panther
February 4th, 2005, 12:54 PM
Graeme Dice said:
So you are telling me that the moment when a particular atom of a radioactive element will decay can be determined before it decays? Because that's what you're claiming when you claim a deterministic universe. Of course people dispute your claim, because it's known to be false.



You should at least be accurate here. The correct wording of your last sentence ought to be "Of course some people dispute your claim, because many believe it to be false."

Just because some scientists believe that radioactive decay is totally random does not make it so. I work at a nuclear weapons research facility in the field of radiation detection, and I can assure you that this question is far from settled.

In fact, I personally believe that if the means to observe a single nucleus WITHOUT interference were to ever be developed, one would likely be able to predict when a particular radioactive atom is about to decay. But Heisenberg has a theorum which makes this a very difficult thing to achieve, even in a Gedanken experiment. http://forum.shrapnelgames.com/images/smilies/confused.gif

Be very careful with making sweeping judgements about the universe. It will likely bite you in the end.



On the subject of random paths for your mages, I used to think it seemed biased towards elemental over sorcery. I still do, but less severe than I used to think.

I also think that my opinion of seeing bias in my mages can perhaps be traced to such things as in my current Atlantis game, where I was REALLY wanting an earth King of the Deep, and had none after about 30 mages had been recruited. I then used my first earth mage to chain summon troll kings and now I have all the earth commanders I need.

Of course, I have since bought several Kings of the Deep with earth skill at a significantly higher rate now that it is less important to me. This may just be yet another emample of Murphy's Law! http://forum.shrapnelgames.com/images/smilies/biggrin.gif

The Panther
February 4th, 2005, 01:13 PM
All right, I just went back in this thread and added up the four cases where people posted details with a decently high total to give us some meaningful statistics. On the conjecture of a bias of elemental over sorcery, here are the totals of elemental vs. sorcery picks.

Yvelina Game 1 : 31-17
Yvelina Game 2 : 30-28
Alexti Trial 1 : 51-45
Alexti Trial 2 : 48-48
Elemental seems favored in this to the first level.

This matches many of my own earlier trials on this subject. In fact, I can't seem to rcall of a decent-sized trial where the total sorcery randoms exceeded the total elemental randoms. The Alexti Trial 2 above is the first one I have seen where they were even equal.

Random or bias? I have no idea at this point, for one can argue either way based on the sparse data.

Later today, I will add up my Atlantis King totals and post that. I know I have not lost one as yet, so it will be a fair total. However, the game is early enough that I do not have as many Kings as any of the above four cases.

Alneyan
February 4th, 2005, 01:17 PM
Another sample if you want, rather small, but I should be able to increase the number of these mages if my neighbours leave me in peace (those are my sages in the Yarnspinners game):

Air and Blood: 4
Astral and Fire: 5
Death and Nature: 7
Water: 9
Earth: 10
Total: 51 sages, 28 in Elemancy and 23 in Sorcery.

The_Tauren13
February 4th, 2005, 01:23 PM
Well, I must say your test game results show none of the odd distributions mentioned in this thread; they don't appear to be more concentrated into 3 paths, and certainly aren't lacking any one path. If Im less busy today I might actually run some tests myself, and we could even look at the elemental/sorcery ratio for hundreds of mages.

For your test games, let me combine the two:
F-25,A-24,W-22,E-28,S-20,D-25,N-25,B-23
the 'duck number' is 41%
the elemental/sorcery ratio is 1.0645

Looks good to me. Hopefully I can make some more tests today.

johan osterman
February 4th, 2005, 01:29 PM
Duck: The random generated paths use the same function for all units with randoms odf the same kind. So if a unit has any random paths it will not have more or less of a problem than any other unit using the same allocation of randoms.

Panther: All randomly generated numbers in the game are derived from a large set of pregenerated numbers. These numbers are cycled through. While it is possible that there might be a very slight weight in the numbers towards the lower or higher range of a die, it is not a weight that should be readily perceptible.

Edit: I reread my post and realised it wasn't very clear what the point of my response to panther was, so here comes the explanation. A weight of the numbers to the lower or higher half of the distribution would be by far the likeliest cause for a predomince of either elemental or sorcery. If this was the case it would also mean that all other 'random die rolls' in the game would show similar tendencies, ie the bottom half of the distribution would show up more htan the tophalf, obviously most of those 'rolls' are not quite as readily accessible to the player though.

Alneyan
February 4th, 2005, 02:11 PM
Another test, with Spectres this time (there are 97 of them). Here are the results:
Fire:22
Air:22
Water:25
Earth:28
Astral:22
Death:31
Nature:17
Blood:27

It gives 97 elemental picks against 97 sorcery picks. Hmm, I guess I will run another time to try to get more Sorcery than elemancy.

*Grumbles* 110 for elemental picks, 86 for sorcery. The elements win once more.

Agrajag
February 4th, 2005, 05:37 PM
I took the sceptre test as well, 99 spectres.
Air 22 (3)
Fire 24 (0)
Earth 28 (3)
Water 26 (2)
Death 19 (2)
Nature 29 (2)
Astral 26 (1)
Blood 24 (2)
The first number is the total of results, the second is how many times that path appeared twice on the same spectre.
I find it interesting that no double fires came along, but with a chance of around 4% (Im not sure I did the math right) that's quite acceptable.
Total Sorcery: 98
Total Elemental: 100
Elemental wins, but by a very small margin.
I'd say there's no bias towards Elemental, atleast according to my tests, but with all the other tests...

Ivan Pedroso
February 4th, 2005, 08:38 PM
atul said:

Ivan Pedroso said:
Hmmmmmm, why shouldn't it approach 3/8 ?!?

Let us assume that the distribution behind the scenes is uniform. Then the observed frequencies will approach 1/8.


Two random numbers, x1 and x2, both with uniform distribution from zero to one. Each have an expected value of 0.5. But if you're asking what's the expected value of the _greater_ of two, that's 2/3!




You a right that if I roll a number of dies (in this case eight-sided) and then only write down the largest value every time, then the average of this "highest-value-thrown" will indeed be higher than the usual 4.5 that is the average value of a standard eight-sided die. But that is (if understand it correctly) not the situation at hand.

As I see it, we are dealing with:
Some dude rolls a bunch of eight-sided dies, and then write down how many ones he got, how many twos he got and so on. He then adds the numbers of the three most common results, and divides this number with the total number of dies rolled.

An example:
100 eight-sided dies are rolled, and the following is written down:
#1 : 15
#2 : 12
#3 : 19
#4 : 10
#5 : 9
#6 : 12
#7 : 10
#8 : 13
The three highest are added (i.e. #3,#1, and #8) and we get:
19+15+13 = 47
And get (the Duck_Number): 47/100 = 0.47

The observed frequencies of the different values of the above example are:
P(x=1) : 15/100 = 0.15
P(x=2) : 12/100 = 0.12
P(x=3) : 19/100 = 0.19
P(x=4) : 10/100 = 0.10
P(x=5) : 9/100 = 0.09
P(x=6) : 12/100 = 0.12
P(x=7) : 10/100 = 0.10
P(x=8) : 13/100 = 0.13
Which are not all that close to the 1/8 = 0.125 value that where used to generate this sample.

If you increase the number of rolled dies to a much larger number than 100, then these frequencies will be closer to 1/8. (Well the probability of getting a sample using say 1.000.000.000.000.000 dies that results in frequencies that deviate greatly from 1/8 will be extremely unlikely - that is why I say that they "will approach" 1/8)

In fact you could choose any two small positive numbers, epsilon &gt;0 and delta &gt;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| &gt; epsilon ) &lt; delta

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]
with as close to one hundred percent certainty as you want (just choose epsilon and delta to be very small)

So yes - I do in fact claim that given N = some extremely large number, then the Duck_Number will (most most most likely) be (ever ever ever so close to) 3/8.

Sorry for all this dry boring stuff http://forum.shrapnelgames.com/images/smilies/wink.gif

alexti
February 4th, 2005, 08:55 PM
alexti said:
If we pick the range [x1,x2] that covers 99% of possible outcomes, then we could show that lim (x1, N-&gt; inf) = lim (x2, N-&gt; inf) = 3/8 (well, I think we can show)


Or maybe we can not... I feel really rusty. Does anybody know how to prove (or disprove) that lim (x2, N-&gt; inf) = 3/8? I did few attempts, and didn't manage it http://forum.shrapnelgames.com/images/smilies/frown.gif

Taqwus
February 4th, 2005, 08:56 PM
No.

Think about it: it's actually impossible for the total allocation of the three most-picked paths to be anything less than 3/8. If it were, at least one of those three paths would necessarily be underrepresented (below 1/8) and at least one of the five "rarer" paths must be overrepresented (above 1/8), which is a contradiction because then they wouldn't be the three most-picked paths.

The_Tauren13
February 4th, 2005, 09:37 PM
F-46;A-36;W-35;E-37;S-30;D-32;N-34;B-42
292 total...

Elemental: 154
Sorcery: 138

Duck number: 43%

Well, from our accumulated statistics, I would say Panther's Elemental/Sorcery ratio hypothesis may be fairly accurate.
No other conjectures show any consitancy. So much for my origional hypothesis http://forum.shrapnelgames.com/images/smilies/redface.gif

RonD
February 4th, 2005, 10:21 PM
This is elementary probability.

With p=.5 and 292 trials, there is about a 16% probability that you would get 154 (or more) of one outcome. You cannot reject the null hypothesis that Pr(elemental) = Pr(sorcery).

[I used the BINOMDIST function in Excel to calculate that]

atul
February 4th, 2005, 10:26 PM
Ivan Pedroso said:
So yes - I do in fact claim that given N = some extremely large number, then the Duck_Number will (most most most likely) be (ever ever ever so close to) 3/8.


Okay, you are the undisputed king of the hill when it comes to these things, I grant you that. Unless someone like Alexti wishes to disagree, I'll leave that dispute to you. ;p

Anyway, I was mostly worried by the way some people seemed to think that 20 or so instances would be a amount enough for representative statistics. With 100 or so randoms the distribution is hardly yet uniform, I'd call a test for a lot larger sample before anyone makes any hasty decisions...

...although that disrepancy between elemental and sorcery picks seems interesting, not all of the results are statistically significant but there's a trend forming.

The_Tauren13
February 4th, 2005, 10:36 PM
31-17
30-28
51-45
48-48
28-23
99-93
97-97
110-86
98-100
154-138

Total of all statistics posted on this thread:
Elemental: 746
Sorcery: 675

The_Tauren13
February 4th, 2005, 11:10 PM
Using the BINOMDIST function that is only a 3% chance... make of that what you will.

alexti
February 5th, 2005, 12:55 AM
Ivan Pedroso said:
In fact you could choose any two small positive numbers, epsilon &gt;0 and delta &gt;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| &gt; epsilon ) &lt; delta



Do you know how to proof it? I don't see any obvious one. Let us consider frequency of death picks.
<font class="small">Code:</font><hr /><pre>
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 &gt; 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?
</pre><hr />

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


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 &gt;= 3/8, but that isn't a problem.

I'm still unsure if your theorem is right or not, but your proof needs fixing.

alexti
February 5th, 2005, 12:58 AM
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)

Kristoffer O
February 5th, 2005, 07:12 AM
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 http://forum.shrapnelgames.com/images/smilies/happy.gif

bone_daddy
February 5th, 2005, 09:29 AM
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.

Ivan Pedroso
February 6th, 2005, 11:58 PM
alexti said:

Ivan Pedroso said:
[snip]
That is:
Probability( |"observed frequency" - 1/8| &gt; epsilon ) &lt; 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.


alexti said:

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 &gt;= 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 http://forum.shrapnelgames.com/images/smilies/biggrin.gif - made me look a bit foolish.)

I made a crude program to empirically calculate the Duck_Number: (I like MatLab http://forum.shrapnelgames.com/images/smilies/cool.gif )

<font class="small">Code:</font><hr /><pre>
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.
</pre><hr />

Doing a handfull of runs (N=100000) resulted in:
Duck_Number ~ 0.377
as a reference: 3/8 = 0.375

alexti
February 7th, 2005, 02:55 AM
Ivan Pedroso said:

alexti said:

Ivan Pedroso said:
[snip]
That is:
Probability( |"observed frequency" - 1/8| &gt; epsilon ) &lt; 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 http://forum.shrapnelgames.com/images/smilies/wink.gif


Ivan Pedroso said:

alexti said:

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 &gt;= 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 http://forum.shrapnelgames.com/images/smilies/biggrin.gif - made me look a bit foolish.)



http://forum.shrapnelgames.com/images/smilies/happy.gif
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| &gt; epsilon ) &lt; delta
Here, max ("observed frequency of Xi") is a "duck number", so it proves it.

So this case looks closed http://forum.shrapnelgames.com/images/smilies/happy.gif

Ivan Pedroso
February 7th, 2005, 07:22 AM
(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 ?!?

alexti
February 7th, 2005, 11:47 AM
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...

Alneyan
February 7th, 2005, 01:33 PM
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.

Arralen
February 7th, 2005, 02:22 PM
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 ???

Ivan Pedroso
February 7th, 2005, 03:09 PM
@Arralen

(As started by others)
Just because something looks a bit funny doesn't mean that it isn't random.

Ivan Pedroso
February 7th, 2005, 03:15 PM
The Duck_Number is not an easy tool to utilize in order to check if the distribution of random picks is in fact uniform. It is much easier to just count the different number of FIRE, AIR, WATER,… picks and then do a reduced_Chi^2 test to see if we can uphold the notion, that the random picks are uniformly distributed.
(Chi^2 is the square of the Greek letter Chi – looks like an X and is pronounced: “Kai”)

How to do it:
(1) Take your data-sample and group the measurements in some “bins” (intervals).
(2) Decide on a distribution (or model) that you would like to check your measurements against.
(3) Use your distribution to calculate the expected number of “hits” in each of the bins.
(4) Calculated the reduced_chi^2 value.

Formula:
Reduced_chi^2 = (1/d) * SUM[ (O(i) – E(i))^2 / E(i) ]
d = the number of degrees of freedom
O(i) = observed number of hits in the i’th bin.
E(i) = expected number of hits in the i’th bin.

Depending on the reduced_chi^2 you can now determine the following:
“How likely is it that my chosen distribution could be responsible for the observed data-sample.”
If the reduced_chi^2 is close to one, then agreement is satisfactory. If it is larger, then the observed results do not fit the assumed distribution. “Larger” depends on the value of d, but it usually means larger than 2 or 3.

I’ll do an example to illustrate the method:
I use the sample that Alneyan showed some posts above.

Fire:22, Air:22, Water:25, Earth:28, Astral:22, Death:31, Nture:17, Blood:27

Going through the steps above:
(1) well… an obvious choice of bins would be bin1=FIRE, bin2=AIR bin3=WATER and so on. (You could test the ratio of elemental vs. sorcery by choosing just two bins. There could be other interesting bin’ings.)
(2) I choose a model with equal probability (1/8) of getting the different paths.
(3) The total number of mages generated were 194. So the expected value in each bin is 194/8 = 24.25
(4) We first need to explain the “d” in the formula. Here d = 7. That is because of the following constraint: O(1)+O(2)+…+O(8) = 194. There are eight different bins. If you fill up the first 7, then the rest will just go into the last one.

Reduced_Chi^2 = (1/7)*[ (22 - 24.25)^2 / 24.25 + (22 – 24.25)^2 / 24.25 + (25 – 24.25)^2 / 24.25 + … + (27 – 24.25)^2 / 24.25 ] = 0.798

Apparently there is a nice level of agreement between Alneyan’s data and the hypothesis (probability of 1/8 of getting any of the paths).

But beware of jumping to conclusions!!! This result just mean that we can’t reject the hypothesis. We can’t claim that the probabilities are in fact (1/8) for the different paths, just that the data-sample doesn’t give us any reasons to discard it.

An example of a distribution that would be rejected by this data-sample is this:

FIRE = AIR = WATER= EARTH = 0.25 * 60/100 = 0.1625
ATRAL = DEATH = NATURE = BLOOD = 0.25 * 40/100 = 0.0875
(Corresponding to a 65%-35% distribution between elementals an sorcery)

O( i = 1,2,3,4 ) = 194*0.1625 = 31.525
O( i = 5,6,7,8 ) = 194*0.0875 = 16.975

Reduced_Chi^2 = (1/7)*[ (22 – 31.525)^2 / 31.525 + (22 – 31.525)^2 / 31.525 + (25 – 31.525)^2 / 31.525 + … + (27 – 16.975)^2 / 16.975 ] = 3.7852

With d=7 a result of 3.7852 indicates that it is highly unlikely that this new distribution is responsible for Alneyan’s data.

alexti
February 7th, 2005, 09:12 PM
Ivan Pedroso said:
The Duck_Number is not an easy tool to utilize in order to check if the distribution of random picks is in fact uniform. It is much easier to just count the different number of FIRE, AIR, WATER,&amp;#8230; picks and then do a reduced_Chi^2 test to see if we can uphold the notion, that the random picks are uniformly distributed.



It is not as difficult to test for distribution as to test for independence. Consider pseudo-RNG that produces uniformly distributed numbers from 1 to 8. If we implement it as x(i) = 1+(i%8), it will generate very well distributed samples, however, those x(i) are not independent at all. In fact every x(i+1) is completely determined by x(i).

This lack of independence is a typical problem in pseudo-RNG. They often tend to repeat certain sequences more often that others. So if we're looking for a problem in RNG, I'd expect to find something like if you've sequentially rolled 1,2 and 8, there's about 50% probability that the next number will be 3 or 5.

Bummer_Duck
February 15th, 2005, 11:25 PM
Ok I'm done being sick...

I finished my test to 100, the totals were:

F 13
A 7
W 10
E 16
A 11
D 14
N 17
B 12

It took a little while, cause I wrote them down in the order I recruited them.

The only thing that bothers me, is the streakyness of some picks. For example, I got my first air random on dwarf 17, then no more till #57. Or, I get 7 Earth randoms from Dwarf #8 to #21, and another grouping of 5 between #64 and #75. Astral and Water distribution look a little fishy to me also...

Fire, Nature, Death and Blood *look* random, I guess. So maybe it has just been my perception. Plus everyone else seems to think everything is OK, for the most part.

Thanks for the responses!

Oversway
February 16th, 2005, 10:11 AM
The only thing that bothers me, is the streakyness of some picks



But if you had a higher chance to pick a certain path because you hadn't gotten one in awhile, that wouldn't be random.

BigDaddy
February 16th, 2005, 02:46 PM
I'm inclined to believe the system IS random. I think anyone who doesn't think so, should just start a game and run a test with King of the deep or other applicable units. Hire like 200 of them and count them up. You may need 300 for checking all 8 paths. Don't play the game, just give yourself like 9 starting provinces and go to work. My results of 168 sea kings yielded 83 elemental picks and 85 sorcery picks. This yield no significant statistical difference from the null hypothesis.

Restrain yourself from trusting the tests of others if your test comes out more even. I apoligize in advance to anyone who feels insulted, but the probability of getting the 746 elemental paths to 675 sorcery paths is significantly &lt;1%, so I had to either accept that the system wasn't random, or do a controlled test myself (whick i did, and drew my own conclusions). For instance, non controlled in game test may be skewed by using some random paths for blood hunting or less desireable one as troop ferries.

Bummer_Duck
February 16th, 2005, 03:42 PM
Don't play the game, just give yourself like 9 starting provinces and go to work. My results of 168 sea kings yielded 83 elemental picks and 85 sorcery picks.



All this tells us is the overall randomness. However, if the picks follow some sort of pattern, your conclusion will be wrong, even if it looks distributed. This is why I recorded each mage, in the order I recruited them.

I guess what I am saying is if you get 50 death mages in a row, then 50 blood mages in a row, etc, totalling them all up at the end will look like it is a random distribution, even though it was not. That was the main reason for my first post. I felt, and still do, that it is not completely random. I always seem to get "gaps" and 2-4 paths that have the majority of the random picks, at any given point. Testing on a large scale is somewhat irelevent, as you don't recruit 1000 mages (or I don't)

Again, this seems to be my perception...

BigDaddy
February 16th, 2005, 03:53 PM
Perception is difficult with the study of randomness. You have to repeatedly see the same pattern before you can assume the either random number generator or pregenerated random number table is flawed. I'm not sure which this game uses. Anyway, strings of mages are entirely likely. . . Kind of like a couple having 4 girls and no boys. The likelyhood of that is .5^4 or (6.25%).

If you want to test your hypothesis you need to document patterns. . .BBF ... BBF...

I don't think 1000 mages will produce much more significance than say 400, or even 300. Thats just the way significance works. I've misplace my statistics book, or I'd tell you exactly how to find significance, but trust me, you don't need 1000 mage, 300 will do.

BigDaddy
February 16th, 2005, 04:14 PM
Well, Bummer_Duck, you have to do larger scale tests to get any significance out of your test, like I said earlier about the likelyhood of a couple getting 4 girls and no boys, the likelyhood of getting a couple blood mages in a row is not that remote. The likely hood of getting 6 blood mages in a row is, however, quite remote .125^6=.00038%. Significance increase markedly for the first several units sampled, so you need a significant number of mages to make any judgement. If that doesn't suit your fancy, try hiring 20 mages after starting 10 new games and draw your results from there.

Even after 200 units 4 paths are very likely to have a "majority" of the picks, 2-3, however, are not.

BigDaddy
February 16th, 2005, 04:46 PM
I apologize for posting 3 time in a row, but I think I may need to expound on statistics and randomness, since it seems the topic may be misunderstood. Indeed parts of statistics are still theoretical, and it took until the middle ages before statistics was really a science.

First, remember that BEFORE you run a test you can estimate the probabilities of something happening, like 2 blood paths in a row (.125^2=1.54% chance), BUT in a random system the previous result does not effect the next result. So, after you recruit and get a blood path, the probability of the next recruit being a blood path is still 1/8. This is what makes next round projections impossible in a random system, and is why you need patterns to prove your hypothesis.

Also, it appears that significance is misunderstood. So:

Statistical Significance-the probability (P) that a sample (s) is representative of the population (S).

More simply the probability that the mages you hired are representative of all the mages that have been and ever will be recruited.

While demonstrating why large numbers of samples (recruits) are necessary is more difficult, a simple example can show why just a few recruits is not enough is quite simple.

So, if you hire just 1 mage, and assume it is representative of the population you'll get a result of 100% of mages belong to 1 path. Similarly if you hire just 8, and don't get mages of 2 paths, you could conclude that some paths recieve 0% of random picks. In a random system the likelyhood of these results declines with sample size (the number of mages recruited). In conclusion, simply take our word for it that you NEED to recruit many mages to draw any conclusions. Significance (alpha) can be found given population constraints (even for infinite populations), however, I've misplaced my book. I am quite experienced (and educated) in statistics and trust me that you do not need 10000 or even 1000 recruits to test a sytem with 7 degrees of freedom, 300-400 will be just fine.

I sincerely hope this helps.

Arralen
February 16th, 2005, 08:57 PM
You may be right, daddy, but you just quite don't hit the mark.

I'm 100% with Bummer here:
There are odd patterns in the randomly generated commanders skills.

But those patterns are so short, that they will not influence the overall result if you do several hundreds of test, e.g. 500 sages.
I estimate the sample size, where those patterns could be observed, is about 20.. 30. After that, the alghorithm produced the next pattern.

And the significance is not in the number of samples you get by buying sages in a test, but in how often this behaviour is observed in ongoing games. And I must state -again- that I have seen it way to often as to dismiss it as statistical oddities.

Hey, I have even got commanders which had the very same randomly drawn name, additionally to having the same magic skills.

And this behaviour is quite understandable, as we are not talking about a bunch of thown dice, but about complex programm code, whose behaviour isn't really suited to be discribed by statistical analysis but maybe by chaos theory http://forum.shrapnelgames.com/images/smilies/wink.gif

What if the RNG works great, but is -because of some flaw somewhere else- fed with exactly the same seeding value turn after turn, unless the numbers of orders in a turn is odd, in which case it uses the cross summ of all player 1 commmander names as seed for it's next sequence of random numbers?
You could buy sages for ages, and in the end you'll find perfect random skill distributions. But for 20 or 50 turns you may not get a single "blood" one, but alternating air and earth ones.

BigDaddy
February 16th, 2005, 11:08 PM
You have a 6.9% chance in any game to draw 20 random path mages in a row without getting a blood mage. An actual example of the strange behavior might be more helpful.

I must admit I'm skeptical about the odd behavior not being random. Random systems often spit out nearly patternlike garbage all the time, especially short patterns when the system has a low number of degrees of freedom. But then you never see that pattern again. If you just use a coin for instance you'll get lots of HHHT's, but that doesn't make the toss not random. A large number of degrees of freedom cut down significantly on the number of false patterns, but such a test is for the programmers not for us. Repeatedly getting commander with the same skills and names MIGHT be worrisome, but we were never told the name where random, plus I doubt much double checking was done on the naming system.

On the technical side, it is possible that your computer or operating system is limiting the randomness of the RNG (which would explain why some people are certain of the problem and others aren't so sure). Has anyone using a non-windows OS witnessed this problem?

Also, if the program uses a pregenerated random number list or table, you may very well find yourself in the midst of a pattern, but this type of problem is easily patched with a larger table and more complex seed starting position. This is an entirely plausible problem, but not one I have personally witnessed.

People are not able to generate random numbers themselves, its been shown. They have tendency to just pick a number they haven't picked for a while. It is far more likely for a computer or die to pick 1,2,3 but it is highly unlikely a human would ever do that (unless they knew that was a problem of course). All I'm saying is that human preception of random and actual randomness are quite different. It is also quite unlikely that computers are entirely random, but they are a lot better than people.

Saber Cherry
February 17th, 2005, 07:49 AM
Furthermore, unless I'm just up too late and should really go to bed now (probably true), it seems that the chances of 20 random picks missing a least one path (in other words, getting 20 consecutive sages and still not having 8 paths between them) is 43.6%, which is relatively high. Math:

1-((1-.0692)^8), where the .0692 is derived from the same calculation as above.

As far as RNGs go, I found a really nice one, called the Mersenne Twister. It is a software RNG, but the software actually finds stray radioactive particles in the dust on your CPU and monitors them for randomness. If you clean your case a lot the randomness goes down, which may explain some of the problems in this thread.

On the other hand... I just disassembled dom2.exe and got this little code fragment... maybe this is the problem?

<font class="small">Code:</font><hr /><pre>
public int rand(){
for(int i=0; i&lt;100; i++){
if(seemsRandom(i)){return i;}
}
return secret_very_random_number;
}

public boolean seemsRandom(int x){
// note: add some stuff here before Dominions 3 is released
return true;
}

private int secret_very_random_number=42;
</pre><hr />

The_Tauren13
February 17th, 2005, 02:06 PM
roflmfao

BigDaddy
February 17th, 2005, 02:28 PM
Arallen and Bummer_Duck, if you are actually seeing long strings of alternating air and earth mages, I would suggest that it is a bug, but with the sophistication of random number tables and RNG these days, I believe the flaw would be in the windows OS. If you're using a different OS, I almost can't comprehend the problem. Depending on the actual coding of course, it could be caused by an artifact in the memory of the computer, caused by windows clunky and inefficient memory management.

Reboot, and try again! But be warned random systems do do unexpected things, and thats the beauty of them.

BigDaddy
February 17th, 2005, 03:54 PM
Restarting the computer incessently is a dogmatic method of course, if you're not seeing a real pattern.

If the system wasn't random you could use and expert system (thats the engineers term for artificial intelligence) to predict the outcome. Of course with the turing machine's (a computer is a turing machine)inability to actually produce random numbers, with enough samples the expert system may eventually learn how predict the supposed randomness, but it would take quite a few samples and a very sophisticated expert system.

Has anyone learned anything from reading these posts?

(Corrected spelling)

Kristoffer O
February 17th, 2005, 04:38 PM
I learned that Bone Daddy is a nerd http://forum.shrapnelgames.com/images/smilies/happy.gif

BigDaddy
February 17th, 2005, 04:39 PM
Thats funny because i'm not bone daddy and Ivan's posts where nerdier. No offense intended Ivan.

Turms
February 17th, 2005, 04:46 PM
You reasoning is invalid BigDaddy. Johan Osterman already posted that Dominions II uses a pregenerated random number table. That means it's random number generator works exactly the same in any computer with any OS. If it didn't the battle replays wouldn't work.

I have still a question though:
How is the seed for a new turn generation chosen?
The normal way is to take it from the clock or something. That is the only place I could think that could somehow affect the randomness of picks (very unlikely).

Turms

BigDaddy
February 17th, 2005, 04:53 PM
OK, I didn't notice Johan's post (I was wondering what method was used). Pre-generated number tables are very common (they are more efficient), but I think an artifact could still cause problems.

I don't think the seeding technique is likely to be the problem. I believe the seeds are used to select a starting point on the table and a "movement" pattern around the table, and it can be made even more comples. Repeats are highly unlikely in any case.

Kristoffer O
February 17th, 2005, 07:04 PM
BigDaddy: But it was Bone Daddy that claimed that we and he and his whole family were nerds http://forum.shrapnelgames.com/images/smilies/happy.gif

Turms: Clock I believe.

Chazar
February 18th, 2005, 06:08 AM
(Removed joke) http://forum.shrapnelgames.com/images/smilies/redface.gif

Turms
February 18th, 2005, 06:39 AM
Chazar:
I would prefer to be quoted me, you would do it in such a way that it does not distort my words.
It is no big deal, but if someone just checks your post one could draw the conclusion that I am whining because I believe that the random picks are not really random. Which is not what I was doing.

Thank you,
Turms

Chazar
February 18th, 2005, 12:11 PM
Umh, sorry, I did not see that: I did not distort anything in my quote and I left the quoted sentence intact and in full. Furthermore all I quoted from you looked to me like a mere, valid and purely technical question, which received an honest and purely technical answer from Illwinter in reply. So I didnt see any possible harm in my joking. Sorry!

Turms
February 18th, 2005, 06:07 PM
Sorry, It was me who overreacted.

Turms

alexti
February 19th, 2005, 01:30 PM
Saber Cherry said:
Furthermore, unless I'm just up too late and should really go to bed now (probably true), it seems that the chances of 20 random picks missing a least one path (in other words, getting 20 consecutive sages and still not having 8 paths between them) is 43.6%, which is relatively high. Math:

1-((1-.0692)^8), where the .0692 is derived from the same calculation as above.



0.0692 is probability of not getting particular path. Then 1-0.0692 is probability of getting that particular path. Then you consider that events of getting/not getting some path are independent from each other. But those events are not independent. Consider, that your first event (getting blood path has happened on your serie, but that serie happened to have astral too). This makes the probability of your second event (getting astral) = 1, not 1-0.0692.

<font class="small">Code:</font><hr /><pre>
p(missing at least one of the paths) =
= p(missing path A) + p(missing path B) - p(missing path A and path B) + p (missing path C)+ ... =
= sum[i=1..8]((-1)^(i+1)*C(i,8)*p(i)), where p(i)= ((8-i)/8)^20.
</pre><hr />
This comes to around 46.94%, which is even "relatively higher" http://forum.shrapnelgames.com/images/smilies/happy.gif

bone_daddy
February 19th, 2005, 03:36 PM
So has anybody here managed to create an infinite improbability drive yet? http://forum.shrapnelgames.com/images/smilies/smirk.gif

Ivan Pedroso
February 19th, 2005, 04:11 PM
BigDaddy said:
Thats funny because i'm not bone daddy and Ivan's posts where nerdier. No offense intended Ivan.



Hehehe none taken http://forum.shrapnelgames.com/images/smilies/biggrin.gif

"20 sages in a row with exactly 1 path missing":
(7/8)^20 *8 = 0.554

Explanation:
the (7/8) is the chance of getting one of the 7 "good" paths when you hire a sage.
^20 is just 20 such sages in a row.
*8 stems from the fact that you can choose your pool of 7 "good" paths from the 8 possible paths in 8 different ways.

General formula:
(chance of one good)^(number in a row) * (ways to make a good pool)

Getting 20 in a row with exactly 2 paths missing:
(6/8)^20 * 28 = 0.0888
(28=(8!)/(6!2!) is the number of ways of taking 6 from a sample of 8)

Getting 20 in a row with 1 or more paths missing:
~65%

Surprisingly high ? or ?

alexti
February 19th, 2005, 04:56 PM
Ivan Pedroso said:
"20 sages in a row - exactly 1 path missing":
(7/8)^20 *8 = 0.554

Explanation:
the (7/8) is the chance of getting one of the 7 "good" paths when you hire a sage.
^20 is just 20 such sages in a row.
*8 stems from the fact that you can choose your pool of 7 "good" paths from the 8 possible paths in 8 different ways.



7/8 probability means that you will get one of a "good" paths, but repeating the roll 20 times does not guarantee that you'll get each of "good" paths at least once. Thus 7/8 ^ 20 is probability of missing "bad" path (and maybe some of the "good" paths), not one path exactly. If you write your 20 random picks, using digits from 0 to 7 to indicate different paths, 8^20 is a total number of possible numbers (outcomes). Not getting one particular path means getting number without particular digits. There's total of 7^20 such digits. However, there're numbers like 111...1, 222...2 etc amongst them. Those numbers indicate outcomes where 7 paths are missing. Other numbers will represent outcomes with various number of paths missing.


Ivan Pedroso said:
General formula:
(chance of one good)^(number in a row) * (ways to make a good pool)

Getting 20 in a row without exactly 2 paths:
(6/8)^20 * 28 = 0.0888
(28=(8!)/(6!2!) is the number of ways of taking 6 from a sample of 8)



Same problem as above, it's probability of missing 2 paths or more.


Ivan Pedroso said:
Getting 20 in a row with 1 or more paths missing:
~65%

Surprisingly high ? or ?

BigDaddy
February 19th, 2005, 06:11 PM
Based on his knowledge of statistics he made an estimate, thats what the ~ is for.

The exact value is given by
((7/8)^20 * 8c7) + ((6/8)^20 * 8c6) + ((5/8^20 * 8c5) + . . . + ((1/8^20 * 8c1) = .647163

If he didn't figure it out exactly he's a pretty good guesser.

And he did say it properly:

Probability of not getting 1 or more paths after recruiting 20 random paths.

*8c5 = 8 combinataion 5 (ways to get 5 out of 8 with replacement) = 8!/5!3!

Ivan Pedroso
February 19th, 2005, 06:28 PM
@Alexti

Ahhhh yeah - that was sloppy.

(7/8)^20*8 is NOT the probality of getting exactly one path missing. You are absolutely right about it not garanteeing that the other 7 paths are present.

Back when I have had time for a better look (sorry 'bout posting too hastilly http://forum.shrapnelgames.com/images/smilies/biggrin.gif )

alexti
February 19th, 2005, 07:54 PM
BigDaddy said:
Based on his knowledge of statistics he made an estimate, thats what the ~ is for.

The exact value is given by
((7/8)^20 * 8c7) + ((6/8)^20 * 8c6) + ((5/8^20 * 8c5) + . . . + ((1/8^20 * 8c1) = .647163



What I said is that the formula is wrong and so the result was off by about 18%.


BigDaddy said:
If he didn't figure it out exactly he's a pretty good guesser.

And he did say it properly:

Probability of not getting 1 or more paths after recruiting 20 random paths.



That was said right, only the result was wrong it's approximately 47%, not 65%.

If you've missed my point, consider the case of getting random out of 3 magic paths and doing just 3 rolls. Ivan's formula gives (2/3)^3*3c2 + (1/3)^3*3c1 = 3*8/27 + 3/27 = 27/27 = 1 - probability of missing 1 or more paths, which is clearly wrong because you have positive probability of getting 3 different paths in 3 rolls.

Note. Number of combinations of N out of M is notorious for having many different notations (like McN, C(N,M) (M,N) etc). So we're all talking about the same coefficients

alexti
February 19th, 2005, 08:00 PM
Ivan Pedroso said:
@Alexti

Ahhhh yeah - that was sloppy.

(7/8)^20*8 is NOT the probality of getting exactly one path missing. You are absolutely right about it not garanteeing that the other 7 paths are present.

Back when I have had time for a better look (sorry 'bout posting too hastilly http://forum.shrapnelgames.com/images/smilies/biggrin.gif )


Curiously enough, the correct formula (I'm 99% sure http://forum.shrapnelgames.com/images/smilies/wink.gif) looks very much like yours, only the sign alternates (see my earlier post, coefficients are the same, only the sign is different).

Ivan Pedroso
February 19th, 2005, 09:25 PM
alexti said:

Ivan Pedroso said:
Back when I have had time for a better look (sorry 'bout posting too hastilly http://forum.shrapnelgames.com/images/smilies/biggrin.gif )


Curiously enough, the correct formula (I'm 99% sure http://forum.shrapnelgames.com/images/smilies/wink.gif) looks very much like yours, only the sign alternates (see my earlier post, coefficients are the same, only the sign is different).



Yeah - your initial formula is correct. But I must admit that it could do with some explanations. I looked at it (briefly, I'll admit) and could not see what it all meant, or what the idea behind the factors and numbers were. And when I saw that p(i)=0 for i=8 I just disregarded the whole thing and wrote up my (wrong) ideas. (now I get it, and that p(8)=0 is perfectly fine. It's the probability of getting 20 sages in a row with eight(!) paths missing - zero of cause.)

The alternating signs are introduced when probabilities of non-independent events are added.

Same as when non-disjoint sets are unified:

U(A,B) = A + B - I(A,B)
U: unified
I: intersection (written as an upside-down "U")

With 3 sets A,B, and C you get:
U(A,B,C) = A + B + C - I(A,B) - I(A,C) - I(B,C) + I(A,B,C)

With 8:
U(all eight) = A + B + ... + H - I(all with two) + I(all with three) - I(all with four) and so on with plus and minus alternating between the groups of intersections.

One of the ones in the group called I(all with four) could be: I(A,B,C,D) or I(A,B,D,F) or ... well anyone with four letters http://forum.shrapnelgames.com/images/smilies/happy.gif

- - - - we'll use the above stuff now - - - -

"A" above could mean no FIRE pick in 20 sages in a row. "B" no AIR and so on.

Then U(A,B,C,D,E,F,G,H) is all the sets that can be constructed with 20 sages where any one path is missing.

P(getting one of the sets in U(A,B,C,D,E,F,G,H)) is then the probability of getting a row of 20 sages with any one path missing. But as Alexti said, if you add together P(A)+P(B)+ ...+P(H) you will NOT get P(getting one of the sets in U(A,B,C,D,E,F,G,H)).
Because P(A) is the the probability of getting 20 sages without seeing any FIRE paths. But a series of 20 with all sorcery paths will then be a part of A, B, C, and D and would thus get counted 4 times instead of only once. The alternating signs ensures that these "extra countings" gets added and deducted correctly, in order to only count the relevant contributions once. The above describes how P(getting one of the sets in U(A,B,C,D,E,F,G,H)) should be calculated.

P(A) = (7/8)^20 (so are P(B) and P(C) and so forth)
so the first part (the one with A + B + C...) is thus:
8*(7/8)^20

P( I(A,B) ) = (6/8)^20 (and so are P( I(A,C) ) and bla bla)
the re are 28 ways to make these parings, so the second part is:
- 28*(6/8)^20

The third part is ( 8!/(5!3!)=8*7*6/(3*2)=56 ways to combine three letters from the eight available):
+ 56*(5/8)^20

And so on and so on... resulting in:
((7/8)^20 * 8c7) - ((6/8)^20 * 8c6) + ((5/8^20 * 8c5) - . . . + ((1/8^20 * 8c1) = 0.4694

As stated by Alexti and misunderstood by me, but now hopefully clear to all http://forum.shrapnelgames.com/images/smilies/biggrin.gif

BigDaddy
February 19th, 2005, 11:40 PM
That equation looks very familiar, but I've misplace my book... http://forum.shrapnelgames.com/images/smilies/fear.gif (not my advance statistics books with all their distributions and tests, just the basic one).

Anyway, for anyone who stumble across this with some arcane pattern and thinks it might not be random, remember that radomness is elusive even to statisticians. Understanding randomness could be likened to understanding the actual magnitude of infinite. We can use it and test it, just like infinite, but our perception of it will never be quite accurate. So, consider a random number off of an infinitely long number line. . .

alexti
February 20th, 2005, 12:38 AM
Ivan Pedroso said:
Yeah - your initial formula is correct. But I must admit that it could do with some explanations.



Thanks for the explanation why my formula is obvious http://forum.shrapnelgames.com/images/smilies/wink.gif Indeed, that's where it comes from. It reminds me of my teacher in the university who was used to say "and obviously *something* follows". After it would take me couple of hours to figure out why it was obvious http://forum.shrapnelgames.com/images/smilies/happy.gif


Ivan Pedroso said:
I looked at it (briefly, I'll admit) and could not see what it all meant, or what the idea behind the factors and numbers were. And when I saw that p(i)=0 for i=8 I just disregarded the whole thing and wrote up my (wrong) ideas. (now I get it, and that p(8)=0 is perfectly fine. It's the probability of getting 20 sages in a row with eight(!) paths missing - zero of cause.)



In general case, formula is
<font class="small">Code:</font><hr /><pre>
p=sum[i=1..m]((-1)^(i+1)*C(i,m)*p(i)), where p(i)= ((M-i)/M)^N
</pre><hr />
where M is a number of picks and m &lt;= M is number of picks in a subset, so the formula gives the probability of missing one (or more) of the paths out of subset of m paths.
I've just substitued 8 for m and M for our case, which produced curious p(8)=0 http://forum.shrapnelgames.com/images/smilies/happy.gif

bone_daddy
February 20th, 2005, 12:52 AM
So, does this have to do with true randomness not being possible within a system containing a limited number of variables?

BigDaddy
February 20th, 2005, 02:57 AM
A computer can never make really random numbers, a computer scientist has ensured me that that is the case as I believed it was. Instead it uses the clock to produce seemingly random numbers. The numbers themselve seem very much random, in fact, you could call them "virtually random".

True randomness is a rather complicated term, but according to my text randomness is part of anything who's probability of occurence or omission is &lt;100%. So, I'd say that the probability of failure of a device, or the probability of throwing heads on a coin are still random, regardless of their distribution. Distributions just describe some specific random systems. So, I'd have to say no. It's just easier to feel you've grasped random with a coin flip.

Considering a random point on an infinitely long numberline is just a good way to illustrate a humans inability to truly understand certain concepts. Cosider a point on a numberline, if you take an infinitely small movement from that number to any other position on that numberline, there are an infinite number of uniques points between the first and the second, until the movement = 0.

Similarly, we make do with random models and distribution that resemble the things we can test. So, consider this, the probability of flipping heads or tails on a coin 1000 times is 9.3326E-302. IF the coin is flipped an infinite number of times, the probability of this occuring is 1.

In this example we have a demonstration of true randomness, with only two choices (heads or tails).

Saber Cherry
February 20th, 2005, 03:48 AM
Via's CPU's produce random numbers, using special hardware. A Turing Machine cannot make random numbers, but modern computers don't have all the limitations of Turing machines (as shown by Via).

Ivan Pedroso
February 20th, 2005, 09:41 AM
alexti said:
It reminds me of my teacher in the university who was used to say "and obviously *something* follows". After it would take me couple of hours to figure out why it was obvious http://forum.shrapnelgames.com/images/smilies/happy.gif




Hehehe. I can relate to that http://forum.shrapnelgames.com/images/smilies/biggrin.gif, I've heard and read it many times too. What about: "The proof of [bla bla] is left to the reader as an exercise" - that occured alot in my text books.

(It's a typical situation in math, until you get the point you are more or less in the dark, but when you get it, it really feels obvious afterwards. All teachers really could do with remembering their fumblings in the dark in their early days.)

bone_daddy
February 20th, 2005, 10:03 AM
Ok, so although the occurence of any given number within the set of variables will be random, there will be an emergent pattern (the distribution) which is not. Is my comprehension of what you are saying correct?

Please forgive my ignorance concerning stats and probs, but I've never taken any math courses beyond basic algebra and trig. Never really needed them. I have a tendency to only learn things as I need them, unless it's something I find interesting. :-/

BigDaddy
February 20th, 2005, 02:56 PM
It is true that a computer can give numbers that have a nearly random distribution, BUT because they use a distribution (my brother called it an MT, for I think Marsenne Twist) and a seed (from the clock) there is an element of forecasting available that is completely impossible with true random systems. I think ANSI, which regulate random numbers I guess, has determined the the MT is the new method of choice! Still sophisticated software CAN match/nearly match random distributions, but it can't come up with random numbers. Nearly matching distributions is all you have to prove, and I don't believe that it was ever speculated that computers couldn't come close to random. In a logical system such as the computer, its impossible for the PC to pull a number out of it's B***, it's programmed how to follow a distribution.

Bone_daddy, yes, random systems have their own "patterns". Such as the normal distribution, where outliers of very high numbers are explained, but most number fall close to the average.

Verjigorm
February 21st, 2005, 03:18 PM
Interesting... is this device a miniature Geiger-Muller tube with some sort of radioactive isotope in a sealed chamber (similar to the technology used to make smoke detectors)? Is there a website where I can see a press release for it--I couldn't seem to find one in my own search (although I didn't look very long).

BigDaddy
February 21st, 2005, 03:26 PM
That IS interesting. Basically, its like programming a robot to roll a die and then read the number, but it doesn't remove the theoretical limitation (that being that a computer is unable to come up with its own random numbers, in any case because you can forecast them knowing the time/function).

A very good use of it would be to make a pregenerated table or random numbers to seed your RNG.

PvK
February 21st, 2005, 06:12 PM
On the other hand, if you _don't_ know the formula a pseudo-random number genrator is using, and it has the desired distribution, and there is no easy way to deduce the formula, then the result may be indistinguishable from a true random number.

Arguing that a distribution isn't predictable by any practical means is sufficient and entirely different from philisophical or even mathematically provable arguments that it's hypothetically possible to predict a distribution.

Certainly it is quite possible to make a pseudo-random number genrator that is impossible to predict or be considered broken from a game-player's perspective. If the distribution is right, the sequence of play itself adds a shuffling that is too complex to predict.

Which is not to say that some games don't have random number problems, or more often, algorithm bugs, which are capable of detection during play.

PvK

Saber Cherry
February 21st, 2005, 06:38 PM
Verjigorm said:
Interesting... is this device a miniature Geiger-Muller tube with some sort of radioactive isotope in a sealed chamber (similar to the technology used to make smoke detectors)?



Hehe... no=) It's pretty simple - it uses some sort of temperature-monitoring circuitry, with random thermal fluctuations accumulating in a large buffer to be stored until a random number is needed. The chip also has a built-in hardware cryptography engine (using AES) and I think the random numbers are utilized by that, though they are also availible to software running on the computer.

Obviously, on the macro scale, temperature is not a purely random thing, or else chemistry would be a lost cause. However, if you measure temperature precisely enough, you start getting true randomness from microscopic sources, just like if you track a dust particle closely enough, you see random Brownian motion. Is Brownian motion random? Yes, because air molecules are small enough that the Heisenburg Uncertainty Principle and momentum changes from randomly emitted photons start to play a significant role.

If you want to learn more about it, try doing a search for Via's hardware encryption engine. Also, either Ace's Hardware or ViaArena did a big feature on it a year or so back.

BigDaddy
February 21st, 2005, 08:34 PM
PvK said:
On the other hand, if you _don't_ know the formula a pseudo-random number genrator is using, and it has the desired distribution, and there is no easy way to deduce the formula, then the result may be indistinguishable from a true random number.

Arguing that a distribution isn't predictable by any practical means is sufficient and entirely different from philisophical or even mathematically provable arguments that it's hypothetically possible to predict a distribution.

Certainly it is quite possible to make a pseudo-random number genrator that is impossible to predict or be considered broken from a game-player's perspective. If the distribution is right, the sequence of play itself adds a shuffling that is too complex to predict.

PvK



Yes, for all practical purposes, the system likely works as ordered. I have long sustained my opinion that it is random enough to be indistinguishable from the real thing. That's also why ANSI regulated it http://forum.shrapnelgames.com/images/smilies/smirk.gif.

VIA's method seems good enough to be considered theoretically random. Sensor's generally perform randomly (anything P&lt;100% is random by definition).

Arralen
March 1st, 2005, 02:31 PM
So, folks, lets stir up the discussion again:

Ongoing game, Jotunheim, 3 turns.

1st turn - building a Vaetti Hag: Blood-1
2nd turn - doing the same ..... result the same ..
3rd turn - same again .. and the same again...

Likelyhood for this happening: 1,56%

As far as my experience goes, if I keep on building Vaetti Hags, I'll get 1 more Blood-1, then it will switch to some other path. If I build commanders in newly conquered provinces, I'll get some other path this turn. If someone else does I-don't-know-what, I'll get another path.

But after some time, the effect will reoccur. But it will get less likely, as more and more things are happening each turn, what seemingly influences the random number generation.

And it's eactly this effect that I have seen way to often to dismiss it as "statistical". If you do big test buying some hundred units, things will equal out o.c. . Obviously, short term randomization is bugged. But the error occures randomly http://forum.shrapnelgames.com/images/smilies/wink.gif

bone_daddy
March 1st, 2005, 02:42 PM
Agitator http://forum.shrapnelgames.com/images/smilies/biggrin.gif

alexti
March 1st, 2005, 09:36 PM
Arralen said:
1st turn - building a Vaetti Hag: Blood-1
2nd turn - doing the same ..... result the same ..
3rd turn - same again .. and the same again...

Likelyhood for this happening: 1,56%



Yeah, but for each other possibility of 3 hags, the probability is approx. 0.2%. That's just people don't usually notice when they get nature hag, then blood hag and then death hag.

FrankTrollman
March 1st, 2005, 11:18 PM
Indeed, since you only start counting the strangeness when the second one comes up the same as the first one, your chances of seeing the totally perplexing 3 in a row would be 1 in 4 for a character with a random sorcery pick. Really, 25%

Here's how it works: you build a bunch of leaders with random Sorcery picks, and they give you various stuff. Blood, Astral, whatever. Sooner or later, two in a row are going to give the same thing. When that happens, you say "that's odd". Here's where The Gambler's Fallacy. (http://skepdic.com/gamblers.html) kicks in: You've already noticed that things are weird, because you got two bloods in a row. Or two Deaths, or whatever. At this point, you are looking at the next character, who is an independent event. So when she comes up, she has a brand new chance of having the same type of magic that the other two got - and if she does you'll flip out.

So as soon as you start counting, you have a 25% chance of getting a "strange coincidence". Now, if you go back in time to the beginning, your chances are .25^3 - 1.6%. But you didn't, you started counting after the second hag had already come up a double.

-Frank

alexti
March 2nd, 2005, 01:09 AM
Very good explanation. And interestingly enough, a lot of people will not notice anything suspicious if blood-astral pair is *always* followed by nature http://forum.shrapnelgames.com/images/smilies/happy.gif

BigDaddy
March 2nd, 2005, 01:39 AM
If I hired 10,000 mages and 25 in a row were blood mages is that rigged? What if I hire 100,000 mages and 32 in a row were blood mages is that rigged?

If you play this game long enough you may even get 4 or FIVE of the same mage in a row, or even more.

Remeber the ANY particular set of 3 in a row, say Death, Nature, Blood has the same likelyhood as Blood, Blood, Blood. AGAIN, Each new mage's path is independent of the one before it.

FrankTrollman
March 2nd, 2005, 03:22 AM
Interesting note, I did some experiments with purchasing 9 of our scampy little hags in a row.

Here's the first five runs, played on Aran with only one opponent and random events low. The number after the trial run is the number of repeats there are. The expected value is 2:

BBBNANBBD - 3*
NAANANNAD - 2
ABNAAABNA - 2
BDAAADBDD - 3
DDDDAAABB - 6*

That's a little high. Not astoundingly high, but a little high. I thought I noticed something about the non-repeats and the correlation with things happening. Also, both of the starred ones were way in the low numbers with their starting province. So I tried a couple runs with 17 players, common events, and a big map (cradle). Here are the first couple of test runs:

BNNBDBDBN - 1
ANDNAADAA - 2

OK, that's average. Actually, it's below average, but within statistically expected norms for that sort of thing.

I suspect that if the game state doesn't change enough, that you might get recursion of random paths - but in a multiplayer game or a game with many players in it, you won't notice. I also have a little bit of evidence that maybe being in the provinces that the game checks early end up with the same random generator several times in a row - but there isn't enough statistical evidence to say that with any certainty at all.

I will go out on a limb and say that the 7 test runs I've done so far don't lead me to believe that the generation is particularly unfair. If it's true about the simple game/complex game difference, it may explain why some people are so convinced that the fix is in - different play styles would make that happen either always or never in the early game.

-Frank

Arralen
March 4th, 2005, 08:37 AM
Ongoing game, Jotunheim, 6 turns.

1st turn - building a Vaetti Hag: Blood-1
2nd turn - doing the same ..... Blood-1
3rd turn - same again .. Blood-1
4th turn - Gyjgya : Blood-1, Nature-1
5th turn - Vaetti : Nature-1
6th turn - Skratti Blood-1

So with 7 random sorcery pics, I got 5x Blood and 2x Nature...

Bummer_Duck
March 4th, 2005, 08:21 PM
Arralen said:
So with 7 random sorcery pics, I got 5x Blood and 2x Nature...



I'm sure you will get the same sort of answer I recieved... I have to say that back in the board game days, these sorts of results would end in the offending dice getting banned. Apparently, though, once games moved to the computer, results are no longer questioned as closely. :-)

FrankTrollman
March 6th, 2005, 05:38 AM
That's completely statistically meaningless. And I mean completely meaningless. Not "vaguely meaningful", but total devoid of information of any worth whatsoever.

You built three Vaetti Hags in a row that had 2 repeats, and the chances of that happening are only 1 in 16. But honestly, that means that if everyone on the thread performed this test, several of us would expect to get a similar result.

But then you went on and built other stuff and didn't get the same stuff, but different stuff instead. Woot. What does that mean? Nothing.

You got no Astral or Death in 7 picks. That's a 1 in 128 chance. But the thing is, it would be just as "notable" if you got no Blood or Nature in 7 picks. And it would likewise be just as notable if you missed out on Blood and Death, or Blood and Astral, or Astral and Nature, or Nature and Death. From the standpoint of you coming to us and pointing out how weird it was, it would in fact be the same exact event.

So really, that's a simple 3/64 chance to get some 6 turn run that is functionally like that in terms of you pointing out how non-random it looks. In fact, in any particular 7 pick block, the chances of it not producing any discernable pattern are very low - it's only 13% just to not have any consecutive repeats. The chances of actually having at least one of each magic type in 4 picks is only 9%.

By showing us a block of seven consecutive picks (not even really in order, because one of the sets is "choose two", so you can't tell which order it came in) with a discernable pattern, you haven't showed us a damned thing.

When I posted up 63 picks under controlled circumstances, that was small time. 7 picks is a joke.

-Frank

-Frank

Saber Cherry
March 6th, 2005, 07:22 AM
Bummer_Duck said: I'm sure you will get the same sort of answer I recieved... I have to say that back in the board game days, these sorts of results would end in the offending dice getting banned. Apparently, though, once games moved to the computer, results are no longer questioned as closely. :-)



Too soft! In my day, the offending hand of the offending dice-roller would be cut off. Sometimes, to add to the randomness, we would make a pact to only perform crucial rolls during earthquakes or after the injection of adrenaline directly into the heart muscle. A simple replacement of the die giving bad rolls... SOLVES NOTHING!

Bummer_Duck
March 6th, 2005, 02:25 PM
Saber Cherry said:Sometimes, to add to the randomness, we would make a pact to only perform crucial rolls during earthquakes



We thought about that one, but don't live in an earthquake zone. Our solution was to attach a bunch of orbital sanders under the gaming table... Worked great! http://forum.shrapnelgames.com/images/smilies/wink.gif