* Map-related deja-vu
@ 2004-10-01 0:19 Lincoln Peters
2004-10-01 0:26 ` mskala
2004-10-01 18:47 ` Stan Shebs
0 siblings, 2 replies; 6+ messages in thread
From: Lincoln Peters @ 2004-10-01 0:19 UTC (permalink / raw)
To: Xconq list
I just had the weirdest thing happen when I was testing knightmare.g.
Although the module is set up to produce a new random map every time I
load it, the last time I ran it, it produced a map that, as far as I can
tell, is identical to a map it produced when I was testing a few days
ago, down to the layout of independent units!
Since the world-size is set to 240x120 (circumference 1440), I would
think that the chance of getting the exact same map twice would be
astronomically low. Has anyone else experienced this kind of behavior?
Could it be a bug in Xconq? Is it more likely a bug in my computer's
random-number generator? Or should I consider it to be a sign and buy a
pair of lottery tickets?
---
Lincoln Peters
<sampln@sbcglobal.net>
You have mail.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Map-related deja-vu
2004-10-01 0:19 Map-related deja-vu Lincoln Peters
@ 2004-10-01 0:26 ` mskala
2004-10-01 0:49 ` Eric McDonald
2004-10-01 18:47 ` Stan Shebs
1 sibling, 1 reply; 6+ messages in thread
From: mskala @ 2004-10-01 0:26 UTC (permalink / raw)
To: Lincoln Peters; +Cc: Xconq list
On Thu, 30 Sep 2004, Lincoln Peters wrote:
> Since the world-size is set to 240x120 (circumference 1440), I would
> think that the chance of getting the exact same map twice would be
> astronomically low. Has anyone else experienced this kind of behavior?
As far as I can tell, XConq's random number generator, if not seeded from
the command line with the -R option, automatically seeds itself with the
system time modulo 100000. By the Birthday Paradox, you should expect to
see a collision (i.e. two games starting with the same seed) if you play
316 games. (= sqrt(100000)) I think it's plausible that in heavy testing
you might start that many games. The world-size isn't relevant because
the generator only gets seeded once - so you aren't choosing maps from the
space of all possible maps (which space gets bigger with bigger
maps). There are 100000 maps that can ever be generated, and you get one
of those more or less at random.
Is this a problem? If so, we could easily put in a better seeding rule
and/or a better random number generator.
--
Matthew Skala
mskala@ansuz.sooke.bc.ca Embrace and defend.
http://ansuz.sooke.bc.ca/
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Map-related deja-vu
2004-10-01 0:26 ` mskala
@ 2004-10-01 0:49 ` Eric McDonald
2004-10-01 5:45 ` Lincoln Peters
0 siblings, 1 reply; 6+ messages in thread
From: Eric McDonald @ 2004-10-01 0:49 UTC (permalink / raw)
To: mskala; +Cc: Lincoln Peters, Xconq list
mskala@ansuz.sooke.bc.ca wrote:
> Is this a problem? If so, we could easily put in a better seeding rule
> and/or a better random number generator.
As I recall from looking at the 'util.c' code once upon a time, Xconq
uses a simple LCRNG. If we wanted something with a much longer cycle
length, we could go for a Mersenne Twister or some such. Of course, that
would not be suitable for cryptographic work, but neither is the current
one.
But, better seeding would probably be a good first step.
Eric
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Map-related deja-vu
2004-10-01 0:49 ` Eric McDonald
@ 2004-10-01 5:45 ` Lincoln Peters
2004-10-01 18:19 ` Eric McDonald
0 siblings, 1 reply; 6+ messages in thread
From: Lincoln Peters @ 2004-10-01 5:45 UTC (permalink / raw)
To: Eric McDonald; +Cc: Xconq list
On Thu, 2004-09-30 at 17:26, Eric McDonald wrote:
> mskala@ansuz.sooke.bc.ca wrote:
>
> > Is this a problem? If so, we could easily put in a better seeding rule
> > and/or a better random number generator.
>
> As I recall from looking at the 'util.c' code once upon a time, Xconq
> uses a simple LCRNG. If we wanted something with a much longer cycle
> length, we could go for a Mersenne Twister or some such. Of course, that
> would not be suitable for cryptographic work, but neither is the current
> one.
I don't know much about the logic (?) behind generating random numbers.
But I did find it rather surprising when the map looked exactly like the
map I had played on just a few days ago.
I doubt that an algorithm suitable to cryptographic work would be
necessary for any game, but if I ever find myself playing the exact same
"random" game more than once after the random-number generation code is
upgraded, we'll know that the it still needs work.
>
> But, better seeding would probably be a good first step.
Agreed.
I'm a bit surprised that nobody reported this before. Perhaps that is
because:
1. Anyone else who experienced this problem didn't realize that the maps
were actually identical.
2. Anyone else who experienced this problem neglected to report it (this
doesn't seem as uncommon as we would like).
3. I just got lucky.
---
Lincoln Peters
<sampln@sbcglobal.net>
Between grand theft and a legal fee, there only stands a law degree.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Map-related deja-vu
2004-10-01 5:45 ` Lincoln Peters
@ 2004-10-01 18:19 ` Eric McDonald
0 siblings, 0 replies; 6+ messages in thread
From: Eric McDonald @ 2004-10-01 18:19 UTC (permalink / raw)
To: Lincoln Peters; +Cc: Xconq list
On Thu, 30 Sep 2004, Lincoln Peters wrote:
> I don't know much about the logic (?) behind generating random numbers.
There is much logic (determinism) behind computer generation of
"random" numbers. Most generators should more properly be called
pseudorandom number gnerators (PRNG's).
To get some "true" randomness, you have to look for sources that
cannot be [easily] modelled. One example is backscatter of laser
light off of a swirling fluid; use the coordinates of the
backscattered rays and, voila, you have something that might pass
the definition of "random".
> But I did find it rather surprising when the map looked exactly like the
> map I had played on just a few days ago.
As Matthew was saying, the statistical probability of such an
occurance is higher than one might suspect, __at least with the
current seeding mechanism.
> I doubt that an algorithm suitable to cryptographic work would be
> necessary for any game,
Not in the game itself. I was thinking more towards if Xconq ever
went to a secure client-server model.
> 3. I just got lucky.
Yep. It must have been your "birthday."
Eric
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Map-related deja-vu
2004-10-01 0:19 Map-related deja-vu Lincoln Peters
2004-10-01 0:26 ` mskala
@ 2004-10-01 18:47 ` Stan Shebs
1 sibling, 0 replies; 6+ messages in thread
From: Stan Shebs @ 2004-10-01 18:47 UTC (permalink / raw)
To: Lincoln Peters; +Cc: Xconq list
Lincoln Peters wrote:
>I just had the weirdest thing happen when I was testing knightmare.g.
>Although the module is set up to produce a new random map every time I
>load it, the last time I ran it, it produced a map that, as far as I can
>tell, is identical to a map it produced when I was testing a few days
>ago, down to the layout of independent units!
>
>Since the world-size is set to 240x120 (circumference 1440), I would
>think that the chance of getting the exact same map twice would be
>astronomically low. Has anyone else experienced this kind of behavior?
>Could it be a bug in Xconq? Is it more likely a bug in my computer's
>random-number generator? Or should I consider it to be a sign and buy a
>pair of lottery tickets?
>
It certainly could be a duplicate. I thought about the possibility
when deciding how studly the randomization needed to be, but you
would likely only see the exact dup if you started up hundreds of
games with exactly the same size map, same number of players, same
options, etc., and if the world wasn't seen, you couldn't be sure it
was a dup until nearly the end of the game. If the world was seen and
you really didn't want the dup, you'd just kill it off and start
another game. Given the length of time a game takes, for a normal
player it would likely be years before a dup appeared, assuming
Xconq was not updated in the meantime.
On the flip side, one of my concerns back then was computational
efficiency, which seems rather quaint. One could seed from a bigger
number and do 64-bit arithmetic, will likely be unnoticeable to
performance.
Stan
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2004-10-01 18:37 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-10-01 0:19 Map-related deja-vu Lincoln Peters
2004-10-01 0:26 ` mskala
2004-10-01 0:49 ` Eric McDonald
2004-10-01 5:45 ` Lincoln Peters
2004-10-01 18:19 ` Eric McDonald
2004-10-01 18:47 ` Stan Shebs
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).