Minecraft Shorelines are loops?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
quadmaster
Posts: 192
Joined: Mon Apr 27, 2009 12:39 am UTC

Minecraft Shorelines are loops?

Postby quadmaster » Fri Aug 12, 2011 7:30 pm UTC

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).
I... I didn't do it.
<- he did it, I swear

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: Minecraft Shorelines are loops?

Postby z4lis » Fri Aug 12, 2011 8:02 pm UTC

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.)
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Minecraft Shorelines are loops?

Postby mfb » Sat Aug 13, 2011 8:48 pm UTC

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.

User avatar
Eastwinn
Posts: 303
Joined: Thu Jun 19, 2008 12:36 am UTC
Location: Maryland

Re: Minecraft Shorelines are loops?

Postby Eastwinn » Sun Aug 14, 2011 1:42 am UTC

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.
http://aselliedraws.tumblr.com/ - surreal sketches and characters.

User avatar
silverhammermba
Posts: 178
Joined: Fri Oct 13, 2006 1:16 am UTC

Re: Minecraft Shorelines are loops?

Postby silverhammermba » Sun Aug 14, 2011 4:51 am UTC

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.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Minecraft Shorelines are loops?

Postby mfb » Sun Aug 14, 2011 12:17 pm UTC

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.

User avatar
MartianInvader
Posts: 809
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Minecraft Shorelines are loops?

Postby MartianInvader » Sun Aug 14, 2011 2:01 pm UTC

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.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: Minecraft Shorelines are loops?

Postby z4lis » Sun Aug 14, 2011 7:15 pm UTC

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.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26823
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Minecraft Shorelines are loops?

Postby gmalivuk » Mon Aug 15, 2011 12:35 am UTC

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Minecraft Shorelines are loops?

Postby Yakk » Mon Aug 15, 2011 3:19 pm UTC

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.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: Minecraft Shorelines are loops?

Postby z4lis » Mon Aug 15, 2011 5:33 pm UTC

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.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Minecraft Shorelines are loops?

Postby Yakk » Mon Aug 15, 2011 6:39 pm UTC

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).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26823
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Minecraft Shorelines are loops?

Postby gmalivuk » Mon Aug 15, 2011 6:44 pm UTC

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Minecraft Shorelines are loops?

Postby Yakk » Mon Aug 15, 2011 6:50 pm UTC

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!)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Minecraft Shorelines are loops?

Postby mfb » Mon Aug 15, 2011 7:10 pm UTC

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Minecraft Shorelines are loops?

Postby skeptical scientist » Mon Aug 15, 2011 11:31 pm UTC

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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
MartianInvader
Posts: 809
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Minecraft Shorelines are loops?

Postby MartianInvader » Tue Aug 16, 2011 5:20 pm UTC

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.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26823
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Minecraft Shorelines are loops?

Postby gmalivuk » Tue Aug 16, 2011 6:02 pm UTC

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Minecraft Shorelines are loops?

Postby skeptical scientist » Fri Aug 19, 2011 11:27 am UTC

Another possibility (other than bullseye) for a minecraft map with no infinite region of either kind would be a checkerboard.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests