Posted by: sloanjh
« on: December 21, 2011, 12:04:17 AM »Until recently, odds were quite important in my day job.
Which I was thinking while I was typing
It was more exposition for the OP....Merry Christmas!
John
Which I was thinking while I was typing
It was more exposition for the OP....Merry Christmas!
John
Posted by: Steve Walmsley
« on: December 20, 2011, 11:46:12 AM »But the chance of a loop existing somewhere in that 100 systems is O(1). Intuitively, this can be understood by thinking about the next 100 systems. You'll be rolling against odds of at least 100-1 100 times, so the odds are that at least one of those rolls will come up a winner. For the first 100 systems, the odds will be lower than 100-1, but the same general principle applies - systems 51-100 will give you at least roughly 1-in-4. This is very similar to the "compare birthdays" cocktail game http://en.wikipedia.org/wiki/Birthday_problem - the odds of two people in a room having the same birthday approaches unity for a surprisingly small number of people, because it doesn't matter which birthday gets a match. The reason that this maps to the birthday problem is that the "new" end of a link can be thought of as that link's "birthday".
As discussed in the article, the true probability of no matches occurring in m links with N systems is roughly m!*(N choose m)/N^m (up to shifts by 1 or two in the value of m). Also as discussed in the article, the easy way to see when the probability of a match approaches unity is to compare N to (m choose 2) = m*(m-1)/2. When m ~ sqrt(2N), these will be roughly equal and the odds are high of a match somewhere.
So if you want to be able to generate roughly M systems before the odds are good of getting a match, you need roughly M^2 total systems. I would choose N at either 1,000,000 or even 1,000,000,000 (assuming Steve didn't use 16-bit ints for system index). I wouldn't go much above 1,000,000,000, since that would overflow a 32-bit integer.
John
Yes, I was aware of that. Until recently, odds were quite important in my day job
. I was just pointing out that after 100 systems have been discovered, the next jump point you go through has a 100-1 chance of connecting to one of those systems. I didn't really express that as clearly as I could have done Steve
Posted by: sloanjh
« on: December 19, 2011, 08:23:25 AM »Thanks for that John, it allowed me to solve a minor (but very irritating) problem at work.
Who says gaming is not good for productivity!
You're welcome. And here I was, thinking people would say "ho hum"
John
Posted by: ZimRathbone
« on: December 18, 2011, 11:32:07 PM »Thanks for that John, it allowed me to solve a minor (but very irritating) problem at work.
Who says gaming is not good for productivity!
Who says gaming is not good for productivity!
Posted by: sloanjh
« on: December 18, 2011, 07:53:55 PM »When 100 systems have been discovered the chance of connecting to an existing system is still 100-1
But the chance of a loop existing somewhere in that 100 systems is O(1). Intuitively, this can be understood by thinking about the next 100 systems. You'll be rolling against odds of at least 100-1 100 times, so the odds are that at least one of those rolls will come up a winner. For the first 100 systems, the odds will be lower than 100-1, but the same general principle applies - systems 51-100 will give you at least roughly 1-in-4. This is very similar to the "compare birthdays" cocktail game http://en.wikipedia.org/wiki/Birthday_problem - the odds of two people in a room having the same birthday approaches unity for a surprisingly small number of people, because it doesn't matter which birthday gets a match. The reason that this maps to the birthday problem is that the "new" end of a link can be thought of as that link's "birthday".
As discussed in the article, the true probability of no matches occurring in m links with N systems is roughly m!*(N choose m)/N^m (up to shifts by 1 or two in the value of m). Also as discussed in the article, the easy way to see when the probability of a match approaches unity is to compare N to (m choose 2) = m*(m-1)/2. When m ~ sqrt(2N), these will be roughly equal and the odds are high of a match somewhere.
So if you want to be able to generate roughly M systems before the odds are good of getting a match, you need roughly M^2 total systems. I would choose N at either 1,000,000 or even 1,000,000,000 (assuming Steve didn't use 16-bit ints for system index). I wouldn't go much above 1,000,000,000, since that would overflow a 32-bit integer.
John
Posted by: Mysterius
« on: December 18, 2011, 05:08:01 PM »Thank you all
Posted by: Steve Walmsley
« on: December 18, 2011, 05:01:37 PM »Yes, increasing the max number of systems is clearly a good option. I was only asking if it was possible to limit hidden JP while also having a limited number of systems.
I understand that systems are only generated when they are explored. Still, since I like to play with NPRs, they will tend to generate new NPRs as they explore (and increase lag). Or is the "NPR generation chance" enabled only when the player race explores?
Thanks for the answers anyway people, i'll live with what I have
Unfortunately they are mutually exclusive requirements. If you generate 100 systems with a max system number of 10,000 then they will tend not to be interconnected. If you generate 100 systems with a max system number of 100 then they have connect to each other because there is nowhere else to go. This is regardless of whether you or NPRs are doing the exploring.
Steve
Posted by: Vynadan
« on: December 18, 2011, 04:49:32 PM »NPRs can 'awaken' other NPRs.
Actually, you could manually set the NPR generation chance to 0% at the game info screen whenever you're not transiting a jump point for the first time yourself. This way you'd stop NPRs from creating new ones, but keep the chance for yourself. That'd require minimal increment adjustments / attention for your survey fleets.
Actually, you could manually set the NPR generation chance to 0% at the game info screen whenever you're not transiting a jump point for the first time yourself. This way you'd stop NPRs from creating new ones, but keep the chance for yourself. That'd require minimal increment adjustments / attention for your survey fleets.
Posted by: Mysterius
« on: December 18, 2011, 04:45:12 PM »Systems are not generated until they are explored so having 10,000 max or 100 max makes no difference to performance. That is only affected by systems that have been generated.
Yes, increasing the max number of systems is clearly a good option. I was only asking if it was possible to limit hidden JP while also having a limited number of systems.
I understand that systems are only generated when they are explored. Still, since I like to play with NPRs, they will tend to generate new NPRs as they explore (and increase lag). Or is the "NPR generation chance" enabled only when the player race explores?
Thanks for the answers anyway people, i'll live with what I have
Posted by: ZimRathbone
« on: December 18, 2011, 04:41:04 PM »That's what i said. Okay... I wasn't very clear
What i was saying is that setting 90% in Gen. Chance and 2 in Gen. Spread. (for example) is, in fact, ineffective. With these settings, a system should only have 4 possible jump points, sometimes more if they fall into the "10%" that does not link to a local system.
Not quite. It is possible to have multiple JP in a system that go to the same destination system (although different JPs obviously) - the most I have seen is three JP pairs linking the same two systems. I believe that its even possible for a system to link to itself, but I'm not sure if the time I saw this was in Aurora or Starfire Assistant. I certainly remember it being quite useful as the physical locations of the two ends were quite far apart, and allowed a short cut from the outer edges of the system to the inner planets (a bit like Lagrange points can be now)
Posted by: Steve Walmsley
« on: December 18, 2011, 04:34:49 PM »A random one. I couldn't even play with the System Gen. Chance and System Gen. Spread options in a real star game ^^.
Yes, I know but not everyone realises that
I would just set local system generation chance to zero and have a large number of systems. If you pick say 10,000 systems, then there is only a 1 in 10,000 chance that a jump point will connect to any particular system number. Once ten systems have been discovered, the chance of connecting to an existing system is 1000-1. When 100 systems have been discovered the chance of connecting to an existing system is still 100-1
Systems are not generated until they are explored so having 10,000 max or 100 max makes no difference to performance. That is only affected by systems that have been generated.
Steve
Posted by: Vynadan
« on: December 18, 2011, 04:16:46 PM »I could swear that I read something along that G-star line someplace here ... but I couldn't find it again, nor do I recall it precise enough to be 100% secure ... But then again, the aurora board already showed up in a dream I had once, so I should better shut up at this point 
... But then again, the aurora board already showed up in a dream I had once, so I should better shut up at this point Posted by: Mysterius
« on: December 18, 2011, 03:52:10 PM »A random one. I couldn't even play with the System Gen. Chance and System Gen. Spread options in a real star game ^^.
Posted by: Steve Walmsley
« on: December 18, 2011, 03:48:59 PM »Steve, what do you think about my initial "problem"? Is what I try to achieve impossible at the moment? (limiting dormant JP with a low number of systems)
Is this a real stars or random game?
Steve
Posted by: Mysterius
« on: December 18, 2011, 03:21:27 PM »Steve, what do you think about my initial "problem"? Is what I try to achieve impossible at the moment? (limiting dormant JP with a low number of systems)
