Page 1 of 1

Minecraft Shorelines are loops?

Posted: Fri Aug 12, 2011 7:30 pm UTC
by quadmaster
If, on a minecraft map, you pick a shoreline near your spawn point and start following it, what is the probability that you will end up back where you started? My intuition says it is 1, but I don't know how to prove it. (For this problem I think you can pretend a minecraft map is infinite, but I am not actually sure).

Re: Minecraft Shorelines are loops?

Posted: Fri Aug 12, 2011 8:02 pm UTC
by z4lis
quadmaster wrote:If, on a minecraft map, you pick a shoreline near your spawn point and start following it, what is the probability that you will end up back where you started? My intuition says it is 1, but I don't know how to prove it. (For this problem I think you can pretend a minecraft map is infinite, but I am not actually sure).


The question isn't really well-defined, since the method for generating the shoreline isn't really known. So the question is: Suppose I take the grid formed by the 2-d integer lattice and have some random way for defining certain blocks to be "land" and others to be "water". What is the probability that a given block belongs to an infinite land component? The question is very similar to those asked in percolation theory, and answering them is usually really, really difficult. Perhaps an easier question to answer is: what is the probability that an infinite land mass exists, at all? (Because if the answer to this is zero, then you know that the answer to your question is 1.)

Re: Minecraft Shorelines are loops?

Posted: Sat Aug 13, 2011 8:48 pm UTC
by mfb
You can consider every tile as an edge of a lattice which is rotated by 45° relative to the minecraft pattern. If every tile is land with a propability of p and there are no correlations*, a part of the solution is described on the wikipedia page: For p>1/2, there is one unique infinite landmass, for p<=1/2, there is not.

*this is not the case, otherwise minecraft maps would look very strange. But I think it is a good approximation for larger areas, so the same might be true for real minecraft maps. Maybe the specific generation algorithm shifts the critical p-value a bit by treating land and water different.

For p>1/2, it is still possible to land on a small island which is not connected to the infinite landmass.
It is interesting that it is possible to answer your question without calculating this:

>> you pick a shoreline near your spawn point and start following it, what is the probability that you will end up back where you started?
It is 1.
If you start at a finite lake or at a finite landmass, you will surround the lake/landmass and end up where you started. To walk for infinity time, both the landmass and the water would have to be infinite, which has a propability of 0 for random maps as long as the generation algorithm follows reasonable "random"s.

Re: Minecraft Shorelines are loops?

Posted: Sun Aug 14, 2011 1:42 am UTC
by Eastwinn
1.

Unless you include the possibility that some seed will generate intersecting lakes in a long chain and continues to do so indefinitely after each new chunk is generated. Does such a seed exist? Doubt it. So I'd go with 1.

Re: Minecraft Shorelines are loops?

Posted: Sun Aug 14, 2011 4:51 am UTC
by silverhammermba
mfb wrote:>> you pick a shoreline near your spawn point and start following it, what is the probability that you will end up back where you started?
It is 1.
If you start at a finite lake or at a finite landmass, you will surround the lake/landmass and end up where you started. To walk for infinity time, both the landmass and the water would have to be infinite, which has a propability of 0 for random maps as long as the generation algorithm follows reasonable "random"s.

I don't think I understand your reasoning. There are infinitely many ways to have an infinite landmass and infinitely many ways to have a finite landmass. I do not see any easy way to calculate this probability.

Re: Minecraft Shorelines are loops?

Posted: Sun Aug 14, 2011 12:17 pm UTC
by mfb
The problem is that an infinite landmass is not enough: You just walk around a finite lake and you are done.
Both the landmass and the sea have to be infinite to get an infinite shore line, and that is quite tricky. And it does not happen with random percolations, as described in the wikipedia article.

Re: Minecraft Shorelines are loops?

Posted: Sun Aug 14, 2011 2:01 pm UTC
by MartianInvader
Could someone link the wikipedia article? I'm having trouble understanding the p=1/2 case. Clearly land and water must follow the same probabilities here. Can all land and all lakes be finite on a single map? Actually, I guess that they can be (like some sort of infinite bulls-eye pattern), but it seems weird that such a pattern is guaranteed.

Re: Minecraft Shorelines are loops?

Posted: Sun Aug 14, 2011 7:15 pm UTC
by z4lis
MartianInvader wrote:Could someone link the wikipedia article? I'm having trouble understanding the p=1/2 case. Clearly land and water must follow the same probabilities here. Can all land and all lakes be finite on a single map? Actually, I guess that they can be (like some sort of infinite bulls-eye pattern), but it seems weird that such a pattern is guaranteed.


It's buried in the percolation article. The result is this: Take a graph G. For each edge, with probability p we will keep it, otherwise delete it. Each edge is removed independently of the others. We want the probability q that the resulting graph has an infinite connected component. Intuitively, this probability increases with p (and does) and by Kolmogorov's 0-1 law we must have q either 0 or 1. So, we have a critical probability [imath]p_c(G)[/imath] at which we go from having 0 probability for an infinite component to 1. For [imath]Z[/imath], this critical value is 1. For [imath]Z^2[/imath], it's been shown to be [imath]\frac{1}{2}[/imath] with lots of work. There aren't even conjectures for the number for [imath]Z^d; d \geq 3[/imath].

So our minecraft question can be modeled by this if the choice between land and water is made independently for each block and has probability p of being land. For [imath]p < \frac{1}{2}[/imath], there will be no infinite components of land almost surely, and so you will start out on a finite-sized island (and so have a finite coastline to walk) almost surely. For [imath]p > \frac{1}{2}[/imath], we instead consider the problem of looking at how large the water components are. For the same reason, there will be no infinite water body almost surely (since a block was chosen to be water with probability [imath]1- p < \frac{1}{2}[/imath]), and so we will walk around the one we started at in finite time almost surely. This is mfb's argument.

Re: Minecraft Shorelines are loops?

Posted: Mon Aug 15, 2011 12:35 am UTC
by gmalivuk
MartianInvader wrote:Can all land and all lakes be finite on a single map?
Why would they need to be? The point is that they're not both going to be infinite, but that doesn't imply that both of them are finite, only that at least one of them is.

Re: Minecraft Shorelines are loops?

Posted: Mon Aug 15, 2011 3:19 pm UTC
by Yakk
But, what happens at exactly p=1/2? I get that above p=1/2 one component is almost certainly infinite and the others are finite, and at less than p=1/2 the other component is almost certainly infinite while the other is finite.

At p=1/2, do we get "50% chance one is infinite, 50% chance the other is infinite, 0% chance that both are infinite"?

That violates the 0-1 law. Which indicates that at p=1/2, either there is a 0% chance of infinite seas and continents, or there is a 100% chance of both infinite seas and continents.

I missed where someone pointed out which is the case in this thread.

Re: Minecraft Shorelines are loops?

Posted: Mon Aug 15, 2011 5:33 pm UTC
by z4lis
Yakk wrote:But, what happens at exactly p=1/2? I get that above p=1/2 one component is almost certainly infinite and the others are finite, and at less than p=1/2 the other component is almost certainly infinite while the other is finite.

At p=1/2, do we get "50% chance one is infinite, 50% chance the other is infinite, 0% chance that both are infinite"?

That violates the 0-1 law. Which indicates that at p=1/2, either there is a 0% chance of infinite seas and continents, or there is a 100% chance of both infinite seas and continents.

I missed where someone pointed out which is the case in this thread.


I'm not sure what happens at 1/2. But it still has to be either 0 chance of having an infinite land component, or 100% chance of having an infinite land component. I'm just not sure exactly which it is at the critical value. Also, keep in mind that when p > 1/2, then we almost surely have an infinite land mass, while almost surely do not have an infinite water mass, since the water was chosen with probability 1 - p < 1/2. In either case, one of water or land almost surely has an infinite component, while the other almost surely has no infinite components. And so we will return to where we started with probability 1, assuming blocks were chosen as above.

However, I doubt this is how Notch figures out where to put land and water (and having played the game and seen the terrain, I can safely say that it isn't) but the duality idea above might suggest that you would still have finite shorelines even if some other random method of generating the terrain is chosen.

Re: Minecraft Shorelines are loops?

Posted: Mon Aug 15, 2011 6:39 pm UTC
by Yakk
z4lis wrote:
Yakk wrote:But, what happens at exactly p=1/2? I get that above p=1/2 one component is almost certainly infinite and the others are finite, and at less than p=1/2 the other component is almost certainly infinite while the other is finite.

At p=1/2, do we get "50% chance one is infinite, 50% chance the other is infinite, 0% chance that both are infinite"?

That violates the 0-1 law. Which indicates that at p=1/2, either there is a 0% chance of infinite seas and continents, or there is a 100% chance of both infinite seas and continents.

I missed where someone pointed out which is the case in this thread.
I'm not sure what happens at 1/2. But it still has to be either 0 chance of having an infinite land component, or 100% chance of having an infinite land component. I'm just not sure exactly which it is at the critical value.

In the symmetrical case (which may not apply to minesweeper!), where land and water are opposites of each other, and the p=1/2 treats water symmetrically, if at p=1/2 there is a 0% chance of an infinite land mass then there is also a 0% chance of an infinite water mass. Similarly, at p=1/2 if there is a 100% chance of an infinite land mass there is also a 100% chance of an infinite water mass.
Also, keep in mind that when p > 1/2, then we almost surely have an infinite land mass, while almost surely do not have an infinite water mass, since the water was chosen with probability 1 - p < 1/2. In either case, one of water or land almost surely has an infinite component, while the other almost surely has no infinite components. And so we will return to where we started with probability 1, assuming blocks were chosen as above.

The above is irrelevant to the p=1/2 case, no? Ie, at the critical threshold, all bets are off.
However, I doubt this is how Notch figures out where to put land and water (and having played the game and seen the terrain, I can safely say that it isn't) but the duality idea above might suggest that you would still have finite shorelines even if some other random method of generating the terrain is chosen.

Yes, it appears that the game of minesweeper matches the 0-1 rule's hypothesis (where subsets of the game don't correlate to any significant degree with the existence of an infinite water/land mass), so there is going to be some critical threshold, above which you get an infinite land with lakes, below which you get an infinite ocean with islands (almost certainly, that is), and at the threshold ... you will either almost certainly get (infinite continent in an infinite ocean) or (both islands and seas are always finite).

Is it possible for every island to be finite, and every sea to be finite, at the same time? ... I do not think so. If that is the case, then at some critical value (if attainable! It might not be attainable in minesweeper) there must be an infinite continent and an infinite ocean (or more than one).

Re: Minecraft Shorelines are loops?

Posted: Mon Aug 15, 2011 6:44 pm UTC
by gmalivuk
Yeah, I wasn't specifically describing the p=1/2 case, but just the distinction between not both infinite and both not infinite.

But I don't think a 50% chance of either being infinite violates the 0-1 law, because there is still a 100% chance that one is infinite with a 0% chance that the other is.

Yakk wrote:Is it possible for every island to be finite, and every sea to be finite, at the same time?
Yes, though I imagine it's with probability 0.

Re: Minecraft Shorelines are loops?

Posted: Mon Aug 15, 2011 6:50 pm UTC
by Yakk
gmalivuk wrote:Yeah, I wasn't specifically describing the p=1/2 case, but just the distinction between not both infinite and both not infinite.

But I don't think a 50% chance of either being infinite violates the 0-1 law, because there is still a 100% chance that one is infinite with a 0% chance that the other is.
I think it does. Ignore the other (the land case).

What is the probability that there is an infinite sea? Well, I believe that this question satisfies the 0-1 theorem's requirements, so by the 0-1 law, the chance must be 0 or 1, right?
Yakk wrote:Is it possible for every island to be finite, and every sea to be finite, at the same time?
Yes, though I imagine it's with probability 0.

How is it structured? I'm having problems visualizing any such pattern.

Hmm. I guess an infinite nested bulls-eye structure would do it. Ie, every sea is a lake, and every continent is an island in a larger sea.

(I wouldn't expect that to be characteristic of an actually randomly generated case -- I was just not seeing the possibility before, so a made-up example is good enough information ... for now!)

Re: Minecraft Shorelines are loops?

Posted: Mon Aug 15, 2011 7:10 pm UTC
by mfb
From the wikipedia article:
"There are no infinite clusters (open or closed)"

So yes, you get some infinite bulls-eye structure (with p=1). The scaling factor of these clusters may be very large, I don't know.

The rotation I mentioned before is not unique, you can get two different shapes for the two choices of how to deal the individual tiles - and the shoreline may look a bit strange. But as long as we don't have a better definition of that, I think it is good to use that transformation. And in that case, we are done.

Re: Minecraft Shorelines are loops?

Posted: Mon Aug 15, 2011 11:31 pm UTC
by skeptical scientist
Yakk wrote:What is the probability that there is an infinite sea? Well, I believe that this question satisfies the 0-1 theorem's requirements, so by the 0-1 law, the chance must be 0 or 1, right?

Yes it does. The property of having an infinite sea is closed under finite changes, so by the 0-1 law, it has probability 0 or 1.

Re: Minecraft Shorelines are loops?

Posted: Tue Aug 16, 2011 5:20 pm UTC
by MartianInvader
So when p=1/2, the probability is either 100% that there is both an infinite island and an infinite sea, or it's 100% that all islands and seas are finite. The finite case would have to be some kind of infinite bulls-eye pattern, which seems unlikely, but having infinite of both would require some sort of "infinitely long stripes" pattern, which seems even less likely.

I guess I can intuitively buy that the infinite bulls-eye pattern has to happen. If you're not in an infinite component, any region you choose is either enclosed by water or by land, with even probability. As you zoom out, you're always guaranteed that you'll be enclosed by water at some point, then by land at some later point, etc. It's reminiscent of the fact that a random 1-d walk always hits every number. This obviously isn't rigorous, but it kind of makes some intuitive sense to me.

Re: Minecraft Shorelines are loops?

Posted: Tue Aug 16, 2011 6:02 pm UTC
by gmalivuk
Yeah, it will actually look like a bullseye (i.e. concentric rings, each with only one island/lake of the next smaller size) with probability zero. But I guess there will be islands and lakes that, in relation to each other, are topologically equivalent to a bullseye with probability 1.

Re: Minecraft Shorelines are loops?

Posted: Fri Aug 19, 2011 11:27 am UTC
by skeptical scientist
Another possibility (other than bullseye) for a minecraft map with no infinite region of either kind would be a checkerboard.