> > So I think what happened, if I remember what Sam said, is that the random seed which generated the map just happened to coincide with the one which had been used earlier in the day. I have no idea how unlikely this is, but it's maybe not too far out there.
>
> The random number seed is time(0) + getpid(), which is the number of seconds since January 1, 1970, added to the internal process ID of CGI hit in which a new board is generated. I *think* UNIX process IDs fall in the range of 1-32768. They are allocated sequentially, wrapping around and skipping process IDs still in use. So five processes fired off in a row will probably have consecutive process IDs. There are usually a few hundred processes running on the system at any given time: some of these are fly-by-night processes that disappear as quickly as they appear, while others are daemons -- things like the web server and telnet sessions and so forth -- that stick around for long periods of time, some even from the moment the machine is booted until it is shut down.
>
> At any rate, if you fire up a game of EF exactly 30000 seconds after your previous one, and the process ID you get is exactly 30000 less than the previous one, then you'll get the same game layout. Everything that's randomized *during* the game will be different, but everything generated initially will be the same.
>
> Obviously this is a pretty highly unlikely occurrence. I'll leave it to you to calculate some estimates on its probability.
>
> In any event, the window of opportunity for firing up a repeat game ends after 32768 seconds.

Hmm, so what'd you need is for exactly 32768-x processes to start up within the x seconds after starting a particular game, for you to get the same layout on the second game (assuming x is less than 32768).

This is probably never going to happen for small values of x (for example, if you don't get more than 30 processes started per second, you're *guaranteed* not to get a repeat random seed within the first 1057 seconds.) Now the faster the average rate of process creation, the sooner you'd be able to get a repeat.

The difference (random seed at time x - random seed at time 0) would not necessarily be even approximately random for a fixed value of x, but as the average rate of process creation increases, the difference would look more and more uniformly random.

There are other sources of randomness, too, of course. The average rate of process creation would vary a lot depending on the time of day and day of the week, I'd guess, and there's also randomness in the value of x chosen.

So I guess all this leads up to is that if you randomly pick 2 games that are within 9.1 hours or so, out of all the games I've played, then there's *approximately* a 1/32768 chance they had the same random seed. So let's say that I played 1000 games, and I did this by playing 4 games in fairly close succession (each within an hour of the next) for 250 days. How many chances of a repeat game does this give me?

On any given day, following the simplifying assumptions above, there's about a 1/10922.66671 chance of a repeat. So after 250 days, the chance of a repeat would be 1 - (1 - 1/10923)^250 which is about 1/44.2. Hmm, still a fairly unlikely occurrence that it ever happened to me. Would I necessarily even notice if a repeat layout occurred? I suppose not. That makes *noticing* a repeat seed a bit less likely than just having one.

But what if I played 8 games a day (all within 9.1 hours of each other, and none withing 9.1 hours of an adjacent day's game) for 125 days? Same total number of games, but you increase the number of possible pairings in each day. In this case, the odds work out to about 1/37.9. Not dramatically different, so this shows that the number of games I play on each day isn't too important, as long as it averages out to about 4, which it had for the longest time until I stopped playing regularly.

Okay, so it looks like I was still fairly lucky that it ever happened, if in fact it did. But it might also have been a different random seed which happened to duplicate the positions of two level boosters and the whitestone. I'd estimate about a 1/80 (about an average of 80 trees?) chance of having the whitestone under the same tree, for all layouts with equal tree distributions. The chance of a particular non-midline square having a level booster is about 1/71, I guess, so if you look at all those put together it's about a 1/400000 chance of correctly guessing the positions of two level boosters and the whitestone. Over 10 times less likely than the approximated 1/32768 chance of having them all the same because of having the same random seed.

Could I have imagined the similarities? I'd say I could, if *after the fact* I told myself, "Hey, that's where that level booster was before." But the way it happened was that I looked at the map and said, "Well, if indeed it's the same map, I recall that level booster #1 was on this square, level booster #2 was on this square, and the whitestone was exactly on this square," before even checking.

That, of course, followed my initial observation that the layout of trees looked *very* familiar in a couple of places, which is an unlikely occurrence to start from. So, even though a repeat seed was unlikely, the fact that the only other good explanation is over 10 times less likely leads me to suspect that I did in fact get a repeat game layout that day.