Skip

Life begets life
June 3, 2010 1:04 PM   Subscribe

A functional self-replicator has been designed for Conway's game of life. The deceptively simple automata 'Conway's game of life' is a model system that illustrates how simple 'physics' can give rise to incredibly complex phenomena. Although a menagerie of existing patterns have been discovered/engineered that display a variety of interesting behavior (eg here), there are also many unanswered questions about what is possible within the simulation. Recently, life-enthusiast mscibing succeeded in designing a universal constructor pattern that is capable of building a functional copy of itself. Its execution can be viewed directly (though it takes a while!) using Golly, a sweet, open-source app for viewing life simulations, as well as other cellular automata.
posted by armheadarmlegleg (137 comments total) 108 users marked this as a favorite

 
This is... I'm... this is... this is AMAZING.
posted by Wolfdog at 1:17 PM on June 3, 2010 [1 favorite]


I am so excited.
posted by Wolfdog at 1:17 PM on June 3, 2010


Wow!
posted by BeerFilter at 1:22 PM on June 3, 2010


Is there somewhere we can see the winning pattern without downloading a Life application? This is pretty damn awesome!
posted by Xoder at 1:22 PM on June 3, 2010 [1 favorite]




Oh fuck yes. I am going to annoy the hell out of Matt and Jess about this come the next podcast.
posted by cortex at 1:24 PM on June 3, 2010 [18 favorites]


I love cellular automata.
posted by Blazecock Pileon at 1:24 PM on June 3, 2010 [1 favorite]


I can't watch the simulation right now, but this is an impressive feat.
posted by lekvar at 1:26 PM on June 3, 2010


Is there somewhere we can see the winning pattern without downloading a Life application?
It's a very long, thin, sparse construction. If you zoom out enough to see it in its entirety, it just looks like a diagonal line. If you zoom in close enough to see details, you just see some gliders with a lot of space between them, and not a lot of obvious pattern or structure in their placement.
posted by Wolfdog at 1:27 PM on June 3, 2010 [4 favorites]


Thanks for posting - it's a fascinating subject.
posted by Samuel Farrow at 1:28 PM on June 3, 2010


I've always liked seeing these Game of Life things in action, although it's always too mind-boggling for me to wrap my mind around how to actually do any of it myself. The fact that this is done with only four rules (see Thing_Long's link) makes it all the more amazing; then grow those four rules into a functional Turing Machine, and self-replicating machines like the original link, and it begins to really, really, does look like Life itself. Anyone who wants proof that extraordinarily simple things can build into enormous complexity has proof right here.
posted by AzraelBrown at 1:31 PM on June 3, 2010 [1 favorite]


So... you're saying this was built by an intelligent creator and did not occur naturally over time?

I should probably go apologize to my mom.
posted by bondcliff at 1:31 PM on June 3, 2010


So... you're saying this was built by an intelligent creator and did not occur naturally over time?

No, but if the universe were an infinitely large grid that obeys Conway's Game of Life and then atomic decay randomly activated a random number of blocks in each cycle, eventually, over massive amounts of time, it would develop into one of these self-replicating machines. And, then, someday, they become trilobites, or something like that. Like I said upthread, I don't completely understand this crap.
posted by AzraelBrown at 1:41 PM on June 3, 2010 [15 favorites]


For those who find this sort of thing interesting, Conway's Life is a good example of what is generally termed "emergent behavior" in complex systems.

There has been a wealth of literature written on such systems; one very approachable introduction is hosted on ArXiv (Marsh, Gerald E., "THE DEMYSTIFICATION OF EMERGENT BEHAVIOR") and downloadable here (Word .doc) or Google's HTML cache. From the paper:
The emergent behavior of a system, while it is determined by the elements of thesystem and the rules of interaction between them and perhaps with the environment, isnot contained explicitly in any of the rules or elements themselves, nor is the behaviorexplained by a simple summation over the components making up the system. Emergentbehavior is characterized by being “greater than the sum of the parts.” [...]

In sum, one should view emergence and reductionism as opposite sides of thesame coin. Dissecting complex behavior from the top down eliminates internal degreesof freedom in the course of analysis, while emergent phenomena occur when internaldegrees of freedom appear when combining component elements into more complexsystems. If individual ants are studied to determine their rules of interaction, there isnothing mysterious about the process. But given those rules, one cannot predict thebehavior of the colony because the new degrees of freedom that appear in the collectivecolony cannot be deduced from the rules of interaction—these rules are necessary but notsufficient to predict the emergent behavior. It is the unexpected consequences of the additional degrees of freedom that appear mysterious.
The paper makes an analogy between emergent behavior as systems become complex and the classical idea of 'degrees of freedom'. I am not completely convinced about how far this analogy carries, but at least on the surface it seems like a useful one.
posted by Kadin2048 at 1:46 PM on June 3, 2010 [6 favorites]


No, but if the universe were an infinitely large grid that obeys Conway's Game of Life and then atomic decay randomly activated a random number of blocks in each cycle, eventually, over massive amounts of time, it would develop into one of these self-replicating machines.

Which is to say, such a thing has already been proven to exist in our own universe.
posted by JHarris at 1:50 PM on June 3, 2010 [3 favorites]


Is there somewhere we can see the winning pattern without downloading a Life application? This is pretty damn awesome!

There's nothing evil about Golly or anything. And if you download it and have it running for a few tens of millions of generations you can see it in action.
posted by JHarris at 1:54 PM on June 3, 2010


So... you're saying this was built by an intelligent creator and did not occur naturally over time?

Well that's one of the weird things about cellular automata. Is it really better to say that this thing was created or discovered? When you look at what happens when you start with a pi heptomino, that seems more like a discovery about the emergent properties of Conway's Life than a deliberate creation. This Universal Constructor seems definitely the creation of this guy. But I'd hate to have to precisely specify the difference.
posted by straight at 1:59 PM on June 3, 2010


Reading the posting in the FPP is like reading the EVE Online blogs. I understand the general idea and I want to enjoy it, but the specifics are effectively Greek.
posted by The Bellman at 2:08 PM on June 3, 2010 [8 favorites]


It just occurred to me that people who believe that the human mind is equivalent to a Turing machine must also (of necessity) believe that there's a Life pattern that's equivalent to a human intelligence. Which is neat because, like, all they have to do to prove their thesis is to demonstrate such a pattern. So, what are you waiting for? Get to work!

It would be so cool to have a little buddy that lives in a Life simulation....
posted by Crabby Appleton at 2:12 PM on June 3, 2010


Also, armheadarmlegleg, thanks so much for this post.
posted by Crabby Appleton at 2:13 PM on June 3, 2010


Tau-muon neutrino oscillations, and now this. This has been quite a wonderful week to be alive!
posted by atrazine at 2:16 PM on June 3, 2010 [1 favorite]


Golly is pretty fast, by the way. I got up to about generation 10 million in about 10 minutes. And this is a HUGE one. Last time I was playing with this and WireWorld I was toying around in 500x500 grids. Make sure you explicitly choose the hashlife algorithm and hit Faster until it's using 100% CPU.
posted by floam at 2:16 PM on June 3, 2010 [1 favorite]


Reading the posting in the FPP is like reading the EVE Online blogs.

I was thinking that, too; I basically just want to come into this thread and be like, "So... geeks. Uh. Say a lot more about this to me. Pretend, as you explain this stuff, that I'm incapable of doing much more than feeding myself pudding by grabbing fistfuls of it."
posted by Greg Nog at 2:16 PM on June 3, 2010 [10 favorites]


For those of us who were doing this manually, using Go stones, after reading Martin Gardner's column on Life...well, it has been a long journey. You could write a mini history of computing based on people doing Life simulations.
posted by vacapinta at 2:19 PM on June 3, 2010 [3 favorites]


Hmm, they should make make a version of this that can mutate. See what happens. Ultimately nothing too interesting is going to happen in a 2D space though. Not enough degrees of freedom. Someone should make a 3d version of life.
posted by delmoi at 2:26 PM on June 3, 2010


Someone should make a 3d version of life.

I had this same thought and found something. Doesn't seem like it has much of a community, but here is an implementation of 3d life.
posted by xorry at 2:33 PM on June 3, 2010 [3 favorites]


Someone should make a 3d version of life.

There are those who believe we're it. :-) Although my life seems one-dimensional these days. Work work work...
posted by Crabby Appleton at 2:35 PM on June 3, 2010


delmoi thanks for shitting in the thread, and talking about something you apparently don't know anything about. You may not have noticed, but the rest of us think plenty of interesting things happen in Conway's Life.
posted by garlic at 2:50 PM on June 3, 2010 [2 favorites]


delmoi, it's not the same, but you can start to run into approximations of that with artificial life, with apps such as Avida. It's more complex than Conway's Life, since you end up talking about programs written in simple computer languages, run in a simulator that adds in the occasional mutation, but you can watch evolution occur in such programs.

There's a simple one available on the web to play with here.
posted by evilangela at 2:51 PM on June 3, 2010 [2 favorites]


Thanks so much for this post. This is unmitigatedly awesome.

So... you're saying this was built by an intelligent creator and did not occur naturally over time?

Well that's one of the weird things about cellular automata. Is it really better to say that this thing was created or discovered? When you look at what happens when you start with a pi heptomino, that seems more like a discovery about the emergent properties of Conway's Life than a deliberate creation. This Universal Constructor seems definitely the creation of this guy. But I'd hate to have to precisely specify the difference.


Not to start a foolish and overdone derail, but this idea alone seems like an insanely badass argument against intelligent design. Even the things that humans create (or at least create the necessary substrates for) cannot necessarily said to have been created rather than discovered.
posted by solipsophistocracy at 3:04 PM on June 3, 2010 [1 favorite]


I'm curious, what are the similarities and differences with Langton's loops?
posted by redbeard at 3:06 PM on June 3, 2010


I played Life on my old Atari 800 when I was a kid. I didn't really understand it; I got as far as memorizing how to create a glider, then when I was bored I would turn it on and make gliders, trying to make the gliders' offspring collide. Looking back, I wish I'd really known what was going on.
posted by davejay at 3:08 PM on June 3, 2010


Yeah, davejay, same here, except with Lifegen on Windows 3.1 - I read it as Lie-Fee-Jen because I was six years old and felt like an idiot 5 years later when I got the old 386 out of the cupboard and played it again. I memorised the glider and another one that would pop out a couple of pseudo-gliders and then collapse on itself because I got something wrong, which I enjoyed.

No, but if the universe were an infinitely large grid that obeys Conway's Game of Life and then atomic decay randomly activated a random number of blocks in each cycle, eventually, over massive amounts of time, it would develop into one of these self-replicating machines.

How many generations? Because this seems like something we should be able to simulate in a pretty short amount of time these days.

--

Also, this is awesome.
posted by doublehappy at 3:38 PM on June 3, 2010 [1 favorite]


solipsophistocracy - that's sort of question that leads to bar fights where mathematicians drink. The Platonists would have it all pre-existing in an ideal state, so there are only discoveries, but never creation. Others differ. A lot.

I mean, really, 2 + 2 = 4 even before there was anybody around to count. Didn't it?

I'm so loving this. Since 1970 using poker chips on grids I drew on sheets of posterboard.
posted by warbaby at 3:46 PM on June 3, 2010


I'm intrigued but confused by this. The announcement on the ConwayLife.com forum calls it a "universal constructor based spaceship," rather than a "self-replicator." The folks on that forum seems excited that it's a "knight ship," which seems to mean that it moves along an L pattern rather than along the grid or the diagonal, and that since it's made from "universal constructors" it can be modified relatively easily to have other velocities and directions.

The Gemini page on LifeWiki shows the most interesting part of the pattern. As Wolfdog says upthread, if you zoom out to where you can see the entire pattern it looks like a very thin diagonal line, running from the northwest to the southeast. The middle of the lines are made of gliders spaced at irregular intervals traveling in both directions. This is the "instruction tape," in the Turing machine sense. The wiki page shows an image of the northwest end of the tape, where there are two identical groups of blotchy vertical constructions. As the program runs, the bottom group of vertical blotches disappears and a new group of vertical blotches appears above the original pair. Apparently after 34M generations the new group of vertical blotches is complete, and the cycle starts again with the second original vertical group beginning to disappear.

This isn't a pattern like Langton's loops that self-replicates until it fills space: it's a pattern that replicates but destroys the original. On the other hand, the discussion forum talks about a "destructor arm" that was explicitly included to remove one of the original patterns. It could be that a relatively minor change could turn this "spaceship" (thing that travels) into a "puffer" (thing that travels but leaves detritus behind).

A news post points out that there are several ways this pattern differs from the "Standard Architecture" for doing things, so it will probably new creativity in Life designs.

Neat post.
posted by fantabulous timewaster at 3:57 PM on June 3, 2010 [3 favorites]


Ultimately nothing too interesting is going to happen in a 2D space though.

A number of very interesting things have happened in 2D space. There's some fairly interesting stuff in 1D space, even; Wolfram's big book, for all its odd self-regarding weirdness, is chock full of examples of such.

Adding dimensions is a total valid idea, and it's not a new idea either, but there are two practical difficulties that arise when you do that:

1. Computation time explodes.

For small scopes that's not too much of a problem with modern equipment, but when you increase dimensionality you increase the rate of growth of complexity of calculations, which reduces practically the upper limits on the size of your simulations.

2. Search space for interesting behavior explodes.

Remember that Conway's configuration isn't some canonical intrinsic sort of behavior for 2D automata; it's just one possible set of rules for iteration. It happens to be an interesting ruleset in terms of the behavior it produces, but there's nothing obviously interesting about the rules themselves. There are a lot more rulesets for 2D automata space that produce very dull results. The problem is worse in 2D space than in 1D—there are a few truly interesting rulesets in 1D space, a number of superficially interesting rulesets, and a bunch of dull ones, but the proportion of interesting-to-dull in 1D is better than in 2D, and that is likely to prove just as true (and probably has in fact been looked at already in at least some detail by mathematicians and enthusiasts) moving from 2D to 3D.

Which isn't to say that there isn't potentially very interesting behavior in 3D space to be found. I imagine there is. It's just non-trivial to find it and explore it, for computational reasons, search-space reasons, and to a degree display reasons as moving to 3D means sacrificing some erstwhile simplicity and universality in the rendering of output.
posted by cortex at 4:05 PM on June 3, 2010 [6 favorites]


Um, excuse me, only God can create something like that, you clearly have your facts wrong.
posted by Pope Guilty at 4:19 PM on June 3, 2010 [1 favorite]


Plato says that it was there before God was.
posted by warbaby at 4:20 PM on June 3, 2010 [1 favorite]


It would be so very fucking awesome if a thread about cellular automata could not turn into an argument about religion.
posted by cortex at 4:31 PM on June 3, 2010 [14 favorites]


It just occurred to me that people who believe that the human mind is equivalent to a Turing machine must also (of necessity) believe that there's a Life pattern that's equivalent to a human intelligence. Which is neat because, like, all they have to do to prove their thesis is to demonstrate such a pattern. So, what are you waiting for? Get to work!

(Maybe this is a joke and I'm missing the tone but) there's no reason to believe this would be easier to do with cellular automata than with any other model of computation that has equivalent power to a Turing machine.
posted by advil at 4:34 PM on June 3, 2010


Next step: Lego.
posted by Smedleyman at 4:35 PM on June 3, 2010 [1 favorite]


It would be so very fucking awesome if a thread about cellular automata could not turn into an argument about religion.

I'm really sorry my stupid little joke caused a derail in a thread about such an awesome thing. Please delete it if necessary.
posted by bondcliff at 4:50 PM on June 3, 2010


advil, it was a facetious remark. (I thought for sure the superfluous "like" would give it away.)
posted by Crabby Appleton at 4:58 PM on June 3, 2010


No, but if the universe were an infinitely large grid that obeys Conway's Game of Life and then atomic decay randomly activated a random number of blocks in each cycle, eventually, over massive amounts of time, it would develop into one of these self-replicating machines.

Well... maybe. If you have an infinite, randomly-populated starting grid, then the grid already contains an infinite number of copies of every possible self-replicating Life machine, in every possible state. And at each turn, when you throw your atomic-decay dice, you'll be regenerating an infinite number of copies of every possible self-replicating Life machine, in every possible state.

Given that every state you can possibly reach by running the simulation is already on the board somewhere at time 0, there doesn't seem much point hitting "run" at all.

Infinity is weird.
posted by Leon at 5:15 PM on June 3, 2010 [3 favorites]


Okay, now can someone design a space drive that injects particles into the cosmic background of virtual particles -- but results in some real particles all going off in one direction? Kind of a combination of LIFE and a Bussard ramjet, with benefits?
posted by hank at 5:21 PM on June 3, 2010


There used to be an ass-kicking Mac "screensaver" Life that was perfect for those long boring phone calls. I wonder why they took it out of rotation and where I could get another one that looked so good. Golly boot-crashes on my fairly new Mac.
posted by Camofrog at 6:29 PM on June 3, 2010


Holy Grail! shot in arm! 40 years of Conway (very simple rules) exploration has finally discovered (?) replication. Now (other varieties are sure to follow), it'll be interesting to learn -what conditions- are necessary for replication.

A clue that life (slowly) could arise spontaneously -simply out of the universal ruleset-. (viz. Schrodinger, 1940s What is Life?)

On the emergence thing: Ted Talk. (Steven Strogatz) "A deep tendency toward spontaneous order in the universe."
posted by Twang at 6:36 PM on June 3, 2010 [2 favorites]


This sounds really awesome. I clicked on the link and the first sentence is:
I've created a universal constructor based spaceship. The speed is (5120,1024)c/33699586, and it runs well in Golly's hashlife. It is larger in extent, but smaller in population than the caterpillar, and the bulk of the pattern is taken up by the instruction tape
so I think I'm just going to assume this is awesome and go eat some pie.
posted by Justinian at 6:37 PM on June 3, 2010 [4 favorites]


There have been multiple calls for explanations in this thread. I've known about Life for going on twenty years now, have played around with Golly in other contexts and have it installed on two computers, have written Life simulators before, and even once long ago created a computer game that utilized Life rules, so I guess I'm as qualified as anyone.

"Life," invented by famed mathematician John Horton Conway, does not require a computer to explore, although it greatly speeds up the process. The original experiments were carried out with grids hosted by tabletops with checkers for counters. In fact, there is something to be said with starting out your explorations in cellular automata in such a way, because Life's foundations are dead simple to understand. A child could run it; I can vouch personally that at least one child did.

Basically, you start with a theoretically infinite grid. Of course in real life no grid can practically be infinite, but the idea is still there. You start this grid out with a given pattern of counters, the initial generation. All Life patterns begin with such a pattern. The self-replicating pattern in the post is such a pattern, although ginormous beyond belief. Instead of an infinite grid, a checkerboard will suffice for most simple patterns.

You run your little grid universe through a series of turns. On each turn, you do the following in order:
1. Find every empty square on the grid that has a total of exactly three adjacent neighbors, horizontally, vertically or diagonally. Put a counter of a different color than the ones forming your pattern in all of those places. These are births. You use a different color because the births don't become "official" until step 3.
2. Find every non-birth counter on the grid that has less than two or more than three non-birth neighbors. These are deaths. Remove them now.
3. Replace all the birth counters with normal counters.

You have now completed one turn, or move, or generation, of your pattern's life. Simply, you just do this over and over again. This is important, so I will add emphasis: Conway's Game of Life is no more complicated than this. Anything you hear about the game that you don't understand is simply a logical implication of these basic rules. Really!

One thing about Life is that it's difficult, if not impossible, to "predict" what a given pattern will do without running it through its generations. Although there are computing tricks you can use to greatly speed up the simulation (Hashlife, included with Golly, probably works partly by ignoring all spaces that aren't adjacent to live counters, which for gigantic patterns consisting mostly of empty space can speed things up tens of thousands fold), ultimately you still have to work through each generation, or perform operations that end up equivalent to that. There are no shortcuts other than those of software optimization. This is partly because a single extra counter placed can turn a long-lived pattern into one that dies in short order.

Most Life patterns fall into one of three types:
1. Many patterns eventually die out, that is, eventually produce an empty grid. An empty grid is static; you need counters to birth more counters, so if you don't have any the world is basically over. The world doesn't really end until you end it however, by ceasing to calculate new generations.
2. Many patterns eventually find a stable configuration. A 2x2 square of counters is the simplest example of this; since each cell has three neighbors none of them die, but none of the spaces around it have exactly three neighbors so none are born. Unless a cell from another part of the pattern grows close enough to the square to upset it, it will remain like that until the end of time. It is also, thus, static.
3. Some patterns oscillate, cycle endlessly between a number of steps, the last one leading to the first. The simplest such pattern is a line of three counters; the ones on the ends die every generation, but the empty spaces beside the center counter give birth each turn, causing the line to effectively turn 90 degrees. This happens endlessly, again, until another counter strays close enough to upset it.

There are some patterns that appear to grow explosively. Most of these, after a long time, appear to turn into one of the types above. But there are some exceptions. Most of the time when you see a web page talk excitedly about Life, it's because experimenters have discovered one of the exceptions.

One of the earliest exceptions found was the glider, a pattern of five counters that, four generations after it starts, has recreated itself, flipped diagonally, one space diagonally away from its start. The new pattern likewise recreates itself one more space away, flipped back to normal, another space away diagonally. This continues endlessly; it's not static and it doesn't oscillate in place. It glides.

A glider is the simplest type of spaceship, that being Life lingo for a pattern that reproduces itself some distance away from its origins. Some spaceships leave "exhaust," a trail of stable or oscillating patterns behind them as they go. Some even produce gliders or other spaceships as exhaust! Those patterns prove that there exist Life patterns that are not doomed to become static, to oscillate endlessly, or to simply move; they may grow without limit.

Until now, however, in the roughly 30 years Life patterns have been explored, no pattern has ever been found that reproduced itself and could continue doing so indefinitely.

One term that comes up when talking about Life patterns, and spaceships in particular, is the "speed of light," also called "c" in reference to Real Life Physics. No matter how complex a pattern gets, it's still generated using the three steps stated above, and those steps don't look any farther away from a square than its nearest neighbors. Thus, if you add a single extra counter to a carefully balanced stable pattern or oscillator, the havoc it wreaks can never travel further than one space in all directions per turn. This is the fastest rate at which changes in the universe can propagate, one space per generation. If a part of the pattern is different 100 away, the soonest it can affect the part of the pattern here is 100 turns from now. This is similar to how the speed of light works in our universe, hence the name. Gliders and spaceships work by reproducing themselves a number of spaces away; hence, they have a speed that can never be faster than the speed of light. In practice, they can't even get that fast. Gliders reproduce themselves one space away every four turns, so their speed is said to be 1/4 of c. When the linked article says this replicator's speed is (5120,1024)c/33699586, if you figured that out you'd end up with the speed of each of the two copies of the base pattern.

Life is important to mathematics for several important reasons. First, it introduced many people (including myself!) to the idea of mathematics for fun, and there may be no better way to ensure the prosperity of the field. Second, it is one of the earliest discovered types of cellular automata, which Stephen Wolfram was so enamored with that he wrote a book claiming it was the secret of the universe. Third, and maybe most importantly, it demonstrates conclusively in a way anyone can understand the principle of emergent behavior, that simple rules can give rise to incredibly complex phenomena. That makes Conway's Game of Life an important intuitive tool towards showing people how evolution can be real. The existence of a self-replicator makes it more useful still; now that we know one of these exists, we might be able to build it into a self mutator like delmoi suggests.

In a way it's kind of fitting that the pattern was discovered so close to the death of Martin Gardner, for it was his Mathematical Recreations column for Scientific American that did more than anything else for making Conway's Game of Life known to the masses. If it weren't for it, many wouldn't have known about Life until at least the dawn of the Internet. Gardner's rate of influence may have traveled outward from his body at our own universe's c, but it was nowhere as destructive as one of those single random counters can be in Life. Truly, he was a spaceship of profound elegance.
posted by JHarris at 7:16 PM on June 3, 2010 [208 favorites]


Justinian:
so I think I'm just going to assume this is awesome and go eat some pie.


Yeah. That's what I shoulda done- what? about an hour'n'a half ago.

Golly is fun, though- and yes, I did my share of flipping go-stones around years ago. Now I can sit back and just push a mouse around.

And speaking of pie, there's a fresh cherry pie in the kitchen. 'Bye.
posted by drhydro at 7:40 PM on June 3, 2010


> Hmm, they should make make a version of this that can mutate. See what happens. Ultimately nothing too interesting is going to happen in a 2D space though. Not enough degrees of freedom. Someone should make a 3d version of life.

delmoi, the thing is a universal constructor using a series of gliders to store information in Turing-tape-like fashion. It is a Turing complete system, which means, given enough extent and time, any computation that can be conceived of in 3-d, 1-d, or n-dimensional space (where n can be an arbitrarily large number) can be encoded into those gliders, not just (as is the case here) instructions on how to create the same pattern a certain distance away from the original and destroy the current pattern.

To create your mutable engine, one could conceivably encode a genetic programming system in the gliders. It won't operate in a very interesting, fashion, I admit; just gliders flying back and forth until the computation completes.

I would totally re-write the Metafilter engine in this, given enough space, time, money, and interest. (current interest = zero)

On preview: JHarris, yes, the hashlife algorithm only computes on non-empty cells; all the cells are stored as nodes in a tree; and multiple instances of the same pattern only get stored once, so everything on the huge tape is probably stored as pointers to eight patterns representing a glider in flight along the axis of the tape, with pointers to the location. Compact and elegant algorithm. Dr Dobbs had a comprehensible write-up on this several years ago.
posted by gentilknight at 7:42 PM on June 3, 2010 [1 favorite]


Delmoi wrote: Ultimately nothing too interesting is going to happen in a 2D space though.

Heh. I don't think you realise that a 2-d or even a 1-d space can represent a 3-d space. It wouldn't look the same (i.e., you wouldn't say oh, that's a 2-d picture of a 3-d world) but it would be functionally equivalent. In fact, it's recently been theorised that we all actually exist as holographic ripples on the 2-d surface of a singularity! Here's a recent FPP that touches on it.

So if you can simulate our 3-d world at all, you can simulate it in 2-d or even 1-d. And the fact that what we perceive to be 3-d events are actually taking place on a 2-d surface surely counts as something interesting!
posted by Joe in Australia at 7:53 PM on June 3, 2010


To make Joe in Australia's point a bit clearer: computers have a 1-dimensional memory. If you write any simulation of an iterated 3D system, you're doing it using a 1D system and some slightly fancy iteration rules.
posted by polyglot at 9:40 PM on June 3, 2010 [2 favorites]


And some more information on what was really done.

Coincidence: this is the second form of artifical life this month.
posted by polyglot at 9:50 PM on June 3, 2010


Thanks for the great explanation, JHarris. Much easier to understand than the wikipedia article, even.
posted by Solon and Thanks at 10:01 PM on June 3, 2010


To make Joe in Australia's point a bit clearer: computers have a 1-dimensional memory. If you write any simulation of an iterated 3D system, you're doing it using a 1D system and some slightly fancy iteration rules.

To further clarify:

I could build a 2x3 grid that contains letters, in - obviously - two dimensions:

abc
def

But I can also represent that as follows, in one dimension:
2x3abcdef

ie, a notation about the dimensions of the grid, followed by its contents, all laid out in one dimension. It works just as well for three dimensions, or more.

This is, in fact, how every computer's memory works, though it's a bit more complicated than that, doesn't necessarily store the grid size right next to the grid contents, etc. But the point is, one dimension, with appropriate notation, is perfectly sufficient to store data representing n dimensions.
posted by Tomorrowful at 10:23 PM on June 3, 2010


I remember 8th grade and seeing Conway's Game of Life for the first time, in the form of a DOS program a friend downloaded from a BBS. I remember the shock of seeing such a simple set of rules and such simple starting conditions give rise to such startling complexity. I remember thinking I was in the presence of a transcendental truth, but being unable to actually grasp it.

This post roused those old feelings of being awestruck by the incomprehensible comprehensibility of the universe. I can't really articulate this feeling, so I'll have to rely on someone who said it much better than I could aspire to:

The Child is father of the Man;
And I could wish my day to be
Bound each to each by natural piety.


Thank you armheadarmlegleg. Thanks to everyone who contributed to this incredible thread. This is sidebar material and I flagged it as such, but I'm unable to move on. I can't favorite this enough.
posted by [expletive deleted] at 12:29 AM on June 4, 2010 [1 favorite]


Dejavu...
I read a sci-fi book once, about 15 years ago, in which the main character noodles around with a cellular automata system in his(her?) spare time. There is a small community of enthusiasts, but not many and mostly just hobbiests because the system is pretty simple and pretty old and most people figure that the interesting stuff has been done, so it's cute but largely stagnant.
Then he/she stumbles upon something new, and... I can't remember the rest of the book, except that I think the new thing maybe paved the way for simulating our brains if enough processing could be obtained... and some guy had a crackpot idea how to obtain this processing through some trick of physics that also unfortunately meant that there was effectively no way to prove from the outside whether it worked (maybe a Heisenberg issue?)

Um, does anyone know what the hell I'm yammering about? I wouldn't mind remembering the book :)
posted by -harlequin- at 12:45 AM on June 4, 2010


harlequin, there's quite a bit about the game of life in Brin's Glory Season but I'm not sure that's what you're remembering.
posted by Justinian at 1:17 AM on June 4, 2010


Sounds vaguely like Greg Egan's Permutation City.
posted by hattifattener at 1:52 AM on June 4, 2010 [3 favorites]


First, I hadn't realized when I wrote the spiel above that the pattern is not, itself, a full replicator. (Although maybe it can be used to construct one?) I'm not sure how the FPP got to calling it one. Am I missing something? Anyway, I might also have the significance of the tuple in the speed wrong, which would be a regrettable error.

I've created a universal constructor based spaceship. The speed is (5120,1024)c/33699586, and it runs well in Golly's hashlife. It is larger in extent, but smaller in population than the caterpillar, and the bulk of the pattern is taken up by the instruction tape

To explain:
constructor: A pattern used to create other patterns. A universal constructor would be able to create arbitrary other patterns if a part of the pattern devoted to holding data is used. This does not necessarily imply a full replicator is possible using it: to create a pattern, it might be possible that a far larger pattern is required, and to create that one a far larger pattern still might be needed.
spaceship: See my longpost above.
hashlife: A special Life generation algorithm that uses optimization tricks to make figuring of huge patterns more feasible.
population: Raw number of counters.
caterpillar: A name for a specific Life pattern, one I'm unfamiliar with but from context seems to be another constructor.
instruction tape: A linear portion of a pattern used for data storage. Apparently, the constructor presented here works by means of a spaceship that moves along the tape. The passing of the 'ship affects the specially-constructed tape in certain defined ways, which is how it constructs.

I'm not sure if Life is Turing-complete, but I think I remembered reading somewhere that it is.
posted by JHarris at 2:41 AM on June 4, 2010


Yep, harlequin, it's most likely "Permutation City" by Greg Egan that you're thinking of. And anybody interested in this story, or cellular automata in general, would probably enjoy Egan's stuff. He's easily the most science-fictiony of all the science fiction authors I've read.
posted by Ipsifendus at 5:18 AM on June 4, 2010 [2 favorites]


I don't understand. If it's replicating itself at a slow speed a little ways away, how is it not just a very complex glider? If it replicated itself exactly where it is, why is it not considered a oscillator? What makes it special from those types?
posted by yeti at 5:23 AM on June 4, 2010 [1 favorite]


First, I hadn't realized when I wrote the spiel above that the pattern is not, itself, a full replicator.

I installed golly just now and tried the pattern out. I was just coming in here to wonder aloud why this was being called a replicator, since it doesn't appear to build a copy of itself. Or anything else.

Oh wait, reading farther in the linked thread, I think I misunderstood something. I thought he said something somewhere about replicating in ~580 generations. But this other quote brings the real claim into better focus:
Ran it for 33,699,586 generations. Population census (846278) matched the initial count.
It takes 34 million generations to complete. And I guess it "replicates" itself in that the final state is the same as the starting one? Isn't that just a really, really, really slow oscillator?
posted by DU at 5:31 AM on June 4, 2010


I can't help but wonder if the Life geeks will eventually come up with some form of quantum communication that transcends c.
posted by kalessin at 5:43 AM on June 4, 2010 [2 favorites]


It is a spaceship. The numbers (5120,1024) indicate the displacement of the new copy from the original. In other words, it moves along a line of slope 1/5. It has been long known that spaceships moving with all different slopes are possible, but until Gemini, all known spaceships have moved either horizontally, vertically, or along a diagonal of slope 1. That is why this is notable.
posted by Wolfdog at 5:55 AM on June 4, 2010 [2 favorites]


It replicates itself but murders its parent in the process. I think that's where the confusion arises, as its fairly easy to see that when you do that (making exact copies) it's not terribly different in the end result. Much like a teleporter that copies you and destroys you in the process is replicating you, but has the end result that is the same as simply moving you somewhere else.
posted by edd at 5:58 AM on June 4, 2010


Much like a teleporter

Teleportation technology, eh? Well, it's about damn time.
posted by yeti at 6:42 AM on June 4, 2010 [1 favorite]


Here's the 1970 Martin Gardner article that started it all.
posted by Twang at 7:28 AM on June 4, 2010 [5 favorites]


Dumb question: is the significance of each of these Life iterations discovered visually? Or do you people have some sort of program that alerts you when something is happening? It seems like a challenge to sit and watch something cycle through 34 million generations without getting distracted and missing a crucial moment.
posted by Think_Long at 9:07 AM on June 4, 2010


It takes 34 million generations to complete. And I guess it "replicates" itself in that the final state is the same as the starting one? Isn't that just a really, really, really slow oscillator?

It is displaced in the process, which makes it a spaceship, not an oscillator—oscillators are fixed in place. And as Wolfdog said, the fact that it moves along a non-cardinal, non-diagonal slope is significant in practice. Really impressively so.

I'm still trying to get my head around the replication process; I love Life to death but have never truly wonked out on it and so am having to book up on the non-rudiementary stuff here. But this appears to be very exciting work even if the lay-level descriptions of what's significant here are a little muddled. In any case, JHarris's intro above is superlative and I'd sidebar it right now if someone else hadn't already beat me to it.

I got the idea last night to look at 3D extrusions of 2D automata, something that I can't recall if Wolfram messed with at all in his book but which I figure some folks must have played with previously. Basically, take each generation of a life grid and represent it as e.g. cubes for live cells on an XY grid, giving each generation an incrementing position along the Z axis.

So generate a board as a thin slice of cubes. The next generation is another thin slice of cubes sitting right on top of the last one. Keep stacking those up to create essentially a 3D model of the history of the 2D grid over time.

Googling, I was only able to find a couple examples of this, but I may have just not been using the right terms. This closeup (with a few more to click to) on Flicker looks neat but doesn't a great overview of the emergent structures; this writeup and renders give a more intriguing picture even if the renders themselves are less pretty, and it includes the code used to generate so someone else could try and run with that.

I find those latter renders really kind of exciting to look at. The middle, grey one in particular is kind of wonderful; it takes a fairly typical random board's first many dozen iterations and makes it look like a burning cityscape. The bushy ground is the bulk of the pattern dying out in the first few generations; the skyscrapers are common static and oscillating objects like blinkers, blocks, beehives and loafs; and the rising smoke clouds are more complicated, unstable configurations growing and moving over time.

Which is a very blatantly anthrocentic analysis of an image that in fact has nothing to do with civic infrastructure, but that's part of what's exciting about this kind of emergent behavior: the odd ways in which it speaks to the pattern-recognition bits of our neural hardware. A comparison to the formation of crystals might be more meaningful, if just as much a projection.
posted by cortex at 10:14 AM on June 4, 2010 [5 favorites]


Tau-muon neutrino oscillations, and now this. This has been quite a wonderful week to be alive geek!

FTFY.

Yeah, this is awesome.
posted by nickmark at 10:30 AM on June 4, 2010


Any sort of "Conway's game of life" reference makes me feel all nostalgic. The algorithm and its implementation are so simple that they were well within the programming abilities of my 11 year old self to code on my first computer. It was one of the first programs I wrote that had truly cool results.

And of course, once you've written the code yourself, you can mess around with different starting configurations to see what happens, and you can alter the algorithm to see how that affects things.

I do recall running a 3D version that someone had written. It was most likely on an Amiga. It wasn't all that interesting because the cube-shaped cells were opaque, so you couldn't really see the internal structure. Now if they were semi-transparent... come to think of it, I have been messing around with code that generates raytracer input files recently. Maybe now I have something to try this weekend.
posted by FishBike at 10:33 AM on June 4, 2010


A Turing-complete tea cosy.
posted by Quietgal at 10:33 AM on June 4, 2010


On the 2-d/3-d point: has any work been done on doing a Life simulation in a 2-d representation of a closed 3-d surface?

What I think would be cool about that, but maybe it has already been explored and found to be dull, is that rather than things evolving on an infinite plane, the little gliders you send off one direction will come back around the map and into the action from the other way.

I suppose a trivial way of implementing that would be to just wrap the edges of the simulation over to the opposing edge.

Also: have people explored Life rule sets that include polygons with number of sides n>4?

Also: this is puregeekjoy!
posted by slickvaguely at 11:00 AM on June 4, 2010


Life on a torus has been done a LOT, if only because it makes an "infinite" grid easy. I don't know about other topologies.

Also: The number 3 called in tears. It wants to know why you hate it so much.
posted by DU at 11:06 AM on June 4, 2010


The original article says it's a universal constructor, which I take to mean that, if you manipulate the "tape," can be used to make arbitrary things. The thing it makes here just happens to be itself, which does make it a spaceship, just one with both an unusual form of exhaust and an unusual direction.

There are some YouTube demonstrations of interesting patterns:
"Metacells," basically a way to (you dawg) play a game of life in your game of life:
(Three pre-made arrangements of metacells are included in Golly in the Hashlife folder, so you can have these up and running immediately.)

A banner printer, that can be used to create arbitrary trails of gliders.
posted by JHarris at 11:25 AM on June 4, 2010 [6 favorites]


Also: have people explored Life rule sets that include polygons with number of sides n>4?

There are not actually that many kinds of regular single-polygon-type tiled grids. Hexagons are the most-sided kind of regular polygon that can be tiled indefinitely and seamlessly. Since Life uses diagonal connections on a square grid as another kind of connection, effectively its grid squares work like octagons anyway. A analogous diagonal connection on a hexagonal grid, to produce 12 connections for each hex, would actually be non-adjacent. Even allowing for that, hexagonal life is not trivial to just up-port, since it's not just the proportions of the values in Life's rules that lend it its elegance.

Probably a more rewarding field for experimentation lies in the direction of other Life-like automata. There are many rules included with Golly that are loads of fun to play with, all well-documented, and it's not hard to create your own. My favorite is Day & Night, which is a symmetric rule; "off" cells work exactly like "on" cells. If you take a field of a given size, fill it with 50% random counters, then start up Day & Night, it will self-organize into increasingly large contiguous regions, like the continents and seas of an alien world. (It's not even the fastest pattern that will do this, although I forgot the other one I found, a few years ago, that did it more efficiently.)

A good page to refer to while finding rules to explore is: http://psoup.math.wisc.edu/mcell/rullex_life.html

Another interesting cellular automata to look into is the Margolus universe, which isn't as complex as Life generally but produces some interesting physical simulations, including one that naturally produces a "world of sand" type of simulation. These are harder to explore with Golly than with Mirek's Cellebration, an older cellular automata program.
posted by JHarris at 12:12 PM on June 4, 2010 [1 favorite]


I graphed Conway's Life patterns on paper in the '70s for fun. I seriously considered getting an R-pentomino tattoo at one point.
posted by Aquaman at 12:12 PM on June 4, 2010


Cortex:

I can't remember if Wolfram's book features many 2D cellular automata extruded into 3 dimensions (in fact, I can't remember whether I ever even managed to finish it... :\ Quite large!). But a TON of the material and illustrations are devoted to 1 dimensional CA extruded into 2D, with results quite fascinating and, especially when he goes on to show what appear to be some of the exact same patterns naturally occurring in real organisms (in the shells of certain mollusks, for example), quite provocative. Game of Life indeed!
posted by theDTs at 12:26 PM on June 4, 2010


More for slickvaguely:

Found at the Mirek Cellebration page, an essay on hexagonal Life: http://www.mirekw.com/ca/files/hexrule.txt
posted by JHarris at 4:55 PM on June 4, 2010


But a TON of the material and illustrations are devoted to 1 dimensional CA extruded into 2D

Yeah, the illustrations of 1D progressions in the book are great. It's been long enough since I read through the book that I can't remember the details of what I liked and disliked about it anymore, but I do recall that all else aside it's a pretty fantastic picture book.
posted by cortex at 5:02 PM on June 4, 2010


When I was a kid, I read about Life someplace and tried it out. I think I bugged my parents about it endlessly, so much so that one day my Dad presented me with a present which he was shocked I was less than enthusiastic about: The Game of Life. I don't think I ever played it. One of the first programs I wrote when I got my old Atari was a screen grid with joystick rollover to place Life elements. I think I spent the next few months coding (badly) ways to animate the patterns. I never did get that finished (but I did learn enough to write a nice little drawing app, along with a connect-4 clone), so I am tremendously glad that such as Golly exist. This replicator is brilliant and I am off to reread Permutation City as soon as possible.
posted by meehawl at 9:35 PM on June 4, 2010 [1 favorite]


polyglot: "And some more information on what was really done.

Coincidence: this is the second form of artifical life this month.
"

*Gasp* The Singularity!!!

ohmagicgeniecomputerpleasebringmehealthyicecream

posted by Bonzai at 9:44 PM on June 4, 2010


I think I bugged my parents about it endlessly, so much so that one day my Dad presented me with a present which he was shocked I was less than enthusiastic about: The Game of Life. I don't think I ever played it.

Poor guy! Your father was only trying to make his son happy, heh. I hope you explained it all to him eventually.

When I first found out about Life I was amused by the similarity of name to the Milton-Bradley game. I don't think it's possible for it to be more wildly different from Conway's invention.
posted by JHarris at 12:30 AM on June 5, 2010


Great thread, forwarding to my cylon overlords now for determination of God's next move.
posted by Potomac Avenue at 12:03 PM on June 5, 2010


Heh, so, now I know what you get if you run Conway's Game of Life in a 3D universe, using the 2D rules and a random starting configuration. You get this weird Borg cube-looking thing [warning: self-link1]. I tried making the cubes semi-transparent, but at this density it's still impossible to see the inside of the cube clearly.

1: I hope this is OK to self-link to, because the picture is just meant to be an attachment to my comment here.
posted by FishBike at 1:26 PM on June 5, 2010 [1 favorite]


Non-spammy self-links in comments are pretty much always fine.
posted by cortex at 2:36 PM on June 5, 2010


Ultimately nothing too interesting is going to happen in a 2D space though. Not enough degrees of freedom. Someone should make a 3d version of life.

After messing around with this for most of the day, albeit in a decidedly amateurish fashion, I'm leaning towards the opposite conclusion: a 3D version has too many degrees of freedom. My attempts to tweak the rules and use various starting configurations have so far lead to only three different results in 3D:
  • All cells die off within a few generations
  • A few widely-separated clusters remain unchanged after a couple of generations
  • A sufficiently dense collection of cells grows explosively until most of the universe has been filled with something resembling foam
I'm starting to wonder if working in two dimensions is a necessary constraint to get oscillating and traveling configurations of cells? When I was searching the web for ideas, there was one page that suggested rules that should work. But so far, any time I've got something that oscillates or travels, it grows explosively as well. Do any clever-er people have any suggestions?
posted by FishBike at 7:34 PM on June 5, 2010


Heh. I don't think you realise that a 2-d or even a 1-d space can represent a 3-d space.

Of course I 'realize' that. But who cares? Who wants to watch an (exponentially slowed down) 2d Turing machine grind away on a 3d simulation?
To make Joe in Australia's point a bit clearer: computers have a 1-dimensional memory.
Computer memory has as many dimensions as you want, you can even think of each bit as dimension in a Z2 vector space if you want. In actuality they are embedded on real world 3d structures (with one very thin dimension).
I can't help but wonder if the Life geeks will eventually come up with some form of quantum communication that transcends c.
Not possible.

Also, Stephan Wolfram is a huge tool
The easiest way to show that something is a universal computer is to show that it can emulate something you already know is a universal computer, like a Turing machine. Now, it's been known since the work of Emil Post in the 1930s that something called a Post tag system (see here or here for more or less mathematical explanations) is Turing-equivalent. A New Kind of Science describes a new formal system, called a cyclic tag system (Wolfram drops "Post"), which is equivalent to a Post tag system, and so to a universal Turing machine. Finally, there is a sketch of how propagating structures ("gliders") in Rule 110 can be used to implement a cyclic tag system, assuming you had an infinite lattice to play with.

This is a genuinely new result. Rule 110 is the simplest CA (in terms of the number of states and the rule radius) which is known to support universal computation. (Indeed, in his 1985 book on cellular automata, Wolfram declared that universal computation in an elementary CA was obviously impossible.) However, lots of things are capable of universal computation — there's less interest in this kind of result than there was in, say, 1970. In 1990, for instance, Cristopher Moore devised a kind of idealized pin-ball machine which is capable of universal computation. This result, like the one about rule 110, is neat for people who care about dynamical models of universal computation — on the order of a thousand scientists and mathematicians world wide. What Wolfram wants to claim is that, since one universal computer is equivalent to another, by studying the behavior of one we learn things which are true of all others (true), therefore Rule 110 is as complex as anything in the universe, and all intelligent life, including, perhaps, the gods must have much in common. This, to put it mildly, does not follow. Wolfram even goes on to refute post-modernism on this basis; I won't touch that except to say that I'd have paid a lot to see Wolfram and Jacques Derrida go one-on-one.

The real problem with this result, however, is that it is not Wolfram's. He didn't invent cyclic tag systems, and he didn't come up with the incredibly intricate construction needed to implement them in Rule 110. This was done rather by one Matthew Cook, while working in Wolfram's employ under a contract with some truly remarkable provisions about intellectual property. In short, Wolfram got to control not only when and how the result was made public, but to claim it for himself. In fact, his position was that the existence of the result was a trade secret. Cook, after a messy falling-out with Wolfram, made the result, and the proof, public at a 1998 conference on CAs. (I attended, and was lucky enough to read the paper where Cook goes through the construction, supplying the details missing from A New Kind of Science.) Wolfram, for his part, responded by suing or threatening to sue Cook (now a penniless graduate student in neuroscience), the conference organizers, the publishers of the proceedings, etc. (The threat of legal action from Wolfram that I mentioned at the beginning of this review arose because we cited Cook as the person responsible for this result.)
posted by delmoi at 12:03 AM on June 6, 2010 [1 favorite]


Of course I 'realize' that. But who cares?

People who find that kind of thing interesting. I'm not sure what's confusing there. It is, to a lot of folks, fascinating and exciting stuff. You seem to be walking this weird line of saying it might, in theory, be fascinating stuff if it was just a little more fascinating in the way you prefer, while defending that criticism on the basis of a glib dismissal of the proven depth and complexity of the emergent system. Which, okay, who cares that you don't care? Why are you making a point of not-caring, and somehow failing to notice that other people in this very discussion do in fact care?

Who wants to watch an (exponentially slowed down) 2d Turing machine grind away on a 3d simulation?

Probably not a whole lot of people for any great stretch of time at a go. But the ideas behind it and the process of building the substructures and structures involved in making it possible are very neat if you're into that sort of thing. If your impression is that to be actively interesting something has to make good television viewing, you might just be coming at this from a different angle than most CA enthusiasts.

Stephan Wolfram is a huge tool

Of this there is no doubt. I'm pretty sure he's the biggest fan of his book. Distractable and overblown and conclusory though much of the text may be, however, it's still an interesting book, and Wolfram is still a brilliant guy even in his self-regarding forest-for-trees monomania.
posted by cortex at 7:07 AM on June 6, 2010 [1 favorite]


A sufficiently dense collection of cells grows explosively until most of the universe has been filled with something resembling foam

So you created the universe, then?
posted by empath at 11:28 AM on June 6, 2010


People who find that kind of thing interesting. I'm not sure what's confusing there. It is, to a lot of folks, fascinating and exciting stuff. You seem to be walking this weird line of saying it might, in theory, be fascinating stuff if it was just a little more fascinating in the way you prefer
Well, I do think Turing machines and whatnot can be interesting in and of themselves. But what I meant when I said "nothing interesting is going to happen in a 2D space" I was talking interesting in the context of creating actual self-duplicating life with evolution, competition, all that stuff. Maybe I could have explained that more but I didn't think the comment was that big of a deal.

And while it's true that you can create a (super-slow) Turing machine in a 2d CA, which can then simulate a 3+ dimension -- but in that case there is nothing 'special' about running your simulation on a 2d CA computer instead of running running it on a normal computer directly. And all you would "see" would be data changing on the tape.

Of course there are probably more efficient ways to 'compress' more degrees of freedom into a 2d space then running a 3d simulation on a 2d computer. But they are still going to be pretty slow as cells that are 'next' to eachother in 3d are going to be 'far' from eachother in 2d.
posted by delmoi at 11:44 AM on June 6, 2010


So you created the universe, then?

Nope, a giant brain. [animated PNG if you click the static picture]

At least I presume this would continue to grow without limit to any arbitrary size, given enough time and memory. The thing that's neat about this one is the 1 cell-width gap between the two starting objects seems to be preserved forever, thus the somewhat brain-like appearance.
posted by FishBike at 4:29 PM on June 6, 2010


What kind of rule tweaks have you been doing, Fishbike?

It seems obvious to me that the rules need to be changed make the system less POPULATION EXPLODE!-y, as a 2D cell has only 8 possible neighbors, when there are 26 in the 3D world. Have you tried limiting who counts as a neighbor or upping the required number of on neighbors?

Perhaps you have tried all manner of things and all of them fail, but I'm curious to hear what you have tried.
posted by that girl at 12:21 AM on June 7, 2010


What kind of rule tweaks have you been doing, Fishbike?

Like all of these game of life type algorithms, I've got four neighbor count parameters to adjust: lower and upper limit for existing cell survival, and lower and upper limit for a new cell to be created.

It is possible to come up with settings for these parameters where specific configurations of cells are stable. But so far, all of those that I've tried result in explosive growth for any collection of cells above a certain size. Ones that don't do that seem to lead to rapid death of all existing cells within 1-4 generations. The adjustment between these two results is just adjusting one parameter by a single count, so there's no splitting the difference.

But there are a lot of possible values for these four parameters. I'm thinking I might have better luck by trying to work out the best values in some analytical way rather than just using trial and error. I have so far lacked sufficient cleverness to actually do that, however, and I've been quite surprised by how little I've found when searching the web for prior art.

Have you tried limiting who counts as a neighbor [...]

Yeah, and this did lead to at least one visually interesting result. If you look at the 6 neighbors that are attached to the faces of a cell, separately from all the non-face neighbors, then you can get some more ordered structures to grow out of randomness.

I'm away from my regular computer at the moment, but I had a set of rules along the lines of:
  • 1 to 3 face neighbors and 0 or 1 non-face neighbors causes a new cell to grow
  • 0 or 4-6 face neighbors, OR 2+ non-face neighbors causes a cell to die
This is then evaluated not in the "entire universe at once" method that the normal game of life uses, but a "one cell at a time, with results immediately visible when evaluating the next cell" method, which results in a more stable configuration. I was expecting this to grow a bunch of rectangular pipes connected together in a sort of labyrinthine configuration, and that's exactly what I got!

I was only looking at the final result then, but now that I've figured out how to get animated PNGs out of my collection of wrong tools for the job, I'm going to go back and re-run this one to see how the final result comes about. I'll post the pictures if anybody's interested. It's pretty far removed from "game of life" type stuff, and more along the lines of locally applied rules creating large structures, kind of like bees building a beehive.
posted by FishBike at 7:55 AM on June 7, 2010


Like all of these game of life type algorithms, I've got four neighbor count parameters to adjust: lower and upper limit for existing cell survival, and lower and upper limit for a new cell to be created.

With respect, this is a little reductionist. 2D Life rules are expressed in the format xyz/xyz, where the first numbers are what produce survivals, and the second are what produce births. Your system only produces rules in which each set of values are continuous. Frequently 2D CA rules will have gaps in one or the other sets.

What might be interesting is a 3D version of the Day & Night algorithm I mentioned above, which would cause random counter snow to resolve into solid blobs. It shouldn't be difficult to get working either.

Come to think of it fishbike, what program are you using in your explorations? Something widely available, or something you cooked up yourself? It might be fun to play with if you don't mind making it available.
posted by JHarris at 5:31 PM on June 7, 2010


Thanks for the explanations FishBike--it's interesting how sometimes these things that work so well in one medium don't translate to another (or in this case, 2D to 3D).

I'd also be interested in playing around with it if the program is something that is available or you can make available.
posted by that girl at 5:58 PM on June 7, 2010


With respect, this is a little reductionist. 2D Life rules are expressed in the format xyz/xyz, where the first numbers are what produce survivals, and the second are what produce births. Your system only produces rules in which each set of values are continuous. Frequently 2D CA rules will have gaps in one or the other sets.

Interesting! For the 3D version, it would not be at all difficult to represent the rules as an array of 27 elements, one for each possible neighbor count including 0, and for each of those set the result to be birth, death, or no change. If I'm doing the math right, this leads to 327 different possible rulesets, so exploring those by trial and error might take a little while.

What might be interesting is a 3D version of the Day & Night algorithm I mentioned above, which would cause random counter snow to resolve into solid blobs. It shouldn't be difficult to get working either.

This does sound interesting and I'll see if I can give it a go once the current thing I'm running is finished.

Come to think of it fishbike, what program are you using in your explorations? Something widely available, or something you cooked up yourself? It might be fun to play with if you don't mind making it available.

Something I cooked up myself: a sort of scene template for the Povray raytracer, combined with a C++ program that runs the simulation and spits out Povray macro function calls to create the individual cells. Then I just run Povray to create the images. The C++ program is a console application that doesn't even take any command line arguments. Everything is hard-coded so it's a matter of commenting out or modifying stuff, recompiling it, and running it.

If you're still interested in it after this description, I'd be happy to send you the code and/or refer you to a therapist, whenever I can find one who understands why the way I'm doing this is sign of some kind of mental illness.
posted by FishBike at 6:07 PM on June 7, 2010


An animation of the system I mentioned in this earlier comment turned out not to be any more interesting than just a static image of the final configuration. But I think that image itself is kind of neat, so here's the resulting maze-like cube.
posted by FishBike at 7:34 PM on June 7, 2010


So is each face of that maze cube identical, or is it mostly an ordered chaos?
posted by Think_Long at 8:06 AM on June 8, 2010


As far as I can tell, each face is different, and the interior of the cube is also filled with a similarly semi-random, semi-structured network of cells. I suspect it would be much more ordered if it grew from a single starting cell instead of a massive blob of random cells.
posted by FishBike at 8:57 AM on June 8, 2010


Ah, I see. I missed that bit about the random starting configuration.
posted by Think_Long at 9:03 AM on June 8, 2010


Thanks, but unfortunately I don't have time to play with such code right now Fishbike. Maybe later?
posted by JHarris at 1:43 AM on June 9, 2010


What might be interesting is a 3D version of the Day & Night algorithm I mentioned above, which would cause random counter snow to resolve into solid blobs. It shouldn't be difficult to get working either.

I made an initial attempt at this last night, taking into account your note that defining ranges of neighbor counts is overly simplified and going with a 27-element array to configure a separate effect (birth, death, no change) for each possible count. It works well, but I didn't get the result I was hoping for, in that I got configurations of cells that very rapidly stabilized, or died off completely, depending on the rules I selected.

I suspect, though, that having a "universe" with a boundary of permanently dead cells is the problem. It occurred to me this morning that I should try a universe where each axis wraps around to the other side so that there is no real boundary at all. I've seen this referred to as a toroidal space when done in 2D, and I'm not sure what it's called in 3D (hypertoroidal, maybe?) but it's easy to implement.

I'll give that a try when I get a chance and then play with different configurations of the rules again. I'm hoping to come up with another neat animation to look at.
posted by FishBike at 6:48 AM on June 9, 2010


The permanently dead boundary might indeed be a problem. In something like Day & Night it'd act like a kind of black hole, a sink that forever generates dark, dark void, killing whatever living cells get near it.

In Day & Night-style rulesets the living counters and the empty spaces are basically the same thing under different names. Imagine if the borders of your world were constantly "on" counters, what that would do to the world?

It'd be like INFINITE CAKE. I seem to be insane right now, be right back.
posted by JHarris at 7:06 AM on June 9, 2010


In Day & Night-style rulesets the living counters and the empty spaces are basically the same thing under different names.

Visualizing this based on what appears to be the traditional notation for the rulesets is a little tricky. For the 2D version of Day & Night, it's described as B3678/S34678. The alive/dead symmetry of that wasn't immediately apparent to me, though of course it is there if you think it through. However if you write it out in the form of what happens with each possible neighbor count, with complementary counts beside each other, the symmetry of the ruleset is more obvious:
0:d 8:b
1:d 7:b
2:d 6:b
3:b 5:d
4:s 4:s
The currently non-obvious thing is how to re-write these rules for the 3D case with 0-26 neighbors instead of 0-8. Fixing the boundary issue will hopefully make it work the way I think it should.

Imagine if the borders of your world were constantly "on" counters, what that would do to the world?

Exactly! So I think some of the rulesets I tried that resulted in an entirely dead universe might be the right ones when the ever-present boundary of death is removed.

It'd be like INFINITE CAKE.

I'm trying to lose weight, so I'll limit myself to finite-but-unbounded cake instead.
posted by FishBike at 7:51 AM on June 9, 2010


I'll give a shot at composing a ruleset.

In a 0-8 neighbor domain, 4 is the midpoint. In a 0-26 neighbor domain, 13 would be, so that one at least should be either "stable" or "flip" each turn; for it to result in a stable birth or death would mean an asymmetry in the pattern. The high-end neighbor counts should all be birth + survive, and the low-end neighbor counts thus should be death + empty.

To start with, maybe try: B10 12 15 17 18 19 20 21 22 23 24 25 26/S10 12 13 15 17 18 19 20 21 22 23 24 25 26

Day & Night is one of the rules that I think is more intuitive in its operation, if the two states are direct analogues with each other then generally most populations should remain constant. I'm sure there are exceptions to this, but in the general case.
posted by JHarris at 4:30 PM on June 10, 2010


Success! Somewhat, anyway. The wrap-around universe, plus some additional thought about how to scale up the traditional 2D Game of Life ruleset, has resulted in this animation of a random starting configuration gradually changing into a fairly sparse, but not completely empty, arrangement. And it takes about 150 generations to do it, too. No oscillators or spaceships yet, that I can see, but overall it looks a lot more like I've come to expect from the 2D version than anything else I've tried.

I saw your comment, JHarris, after I'd already started rendering this one. I'll give your ruleset a try when I have a chance. I've played around with the Day and Night-style symmetrical rulesets at bit and not come up with anything that seems to do quite the right thing, yet. But I haven't tried the one you're suggesting, so that'll be a good experiment.
posted by FishBike at 7:29 PM on June 10, 2010


just reminded me of xkcd 505 :P that is all!
posted by kliuless at 8:11 AM on June 11, 2010


Here's what the first 100 generations look like using the ruleset suggested by JHarris. It's pretty good! I think it behaves about like the 2D version does, visually.

The first time I ran it, I noticed by about generation 400 or so, the universe was entirely filled with live cells, which is a stable configuration. To check if this was because of some mistake in my entry of the ruleset (which should be symmetrical) or just as result of that particular random starting configuration, I tried running it again with the starting configuration inverted.

This resulted in death of all cells within about 400 generations, so the rules appear to be symmetrical, as expected. It's just a matter of whether the live or the dead cells start with a slight advantage, and eventually they "win". Since the latter version is easier to watch (dead cells being transparent), that's the one I went with to run the animation of the first 100 generations.
posted by FishBike at 7:09 PM on June 11, 2010


Ah, cool!

You know FishBike, I have thought for some time that cellular automata have many computer game applications that are not being adequately researched. Day & Night is particularly interesting to me as a tool for random terrain generation. 3D D&N may have similar applications, although they aren't as obvious.
posted by JHarris at 4:47 PM on June 12, 2010


I took another shot at a more Game of Life-like ruleset for 3D. This one allows cells to survive with between 7 and 17 neighbors, and new cells are born where they have exactly 8 neighbors. This is the result. It's again a random starting configuration, and it quickly settles down to just a few clusters of stable cells... almost!

One cluster in the corner is just right to trigger unceasing growth. This kind of demonstrates the problem. Only one neighbor count produces new cells at all, so that can't be reduced. Reducing the range of neighbors that allows cells to survive doesn't prevent explosive growth, it just changes the resulting density. Until you reduce it a little more, then all the cells die.

I ran the animation for about 120 generations anyway, just because it's sort of cool-looking. I was working on the visuals a little bit, too, so this looks nicer than previous ones. It also doesn't compress nearly as well. I may have to actually encode these as videos rather than animated PNGs if it gets any worse. A 16 MB image file is pretty heavy... Google Sites doesn't allow anything over 20.

I keep Googling for prior art here, but all I find is comments from other people who've tried this an encountered similar problems. It's really interesting how different this is working in 3D compared to 2D. It makes me wonder if there is something fundamental about having that extra axis that prevents this from working nicely, like that any ruleset that allows cells to grow at all allows too many to grow, because there's a whole extra direction for them to grow in? So you either get explosive growth or instant death in the following generation from over-crowding.
posted by FishBike at 6:09 PM on June 12, 2010


Man, I really want to start fiddling with this but am otherwise distracted, but: it occurs to me that one of the things that seems to keep growth checked in traditional Life is the fact that it's easy for new growth to overstep its bounds a bit and create overcrowding that immediately leads to die-off. Which makes me wonder if you'd have luck specifically trying to push the birth condition toward the high end of the survival range—make it so that birth is more likely in a situation where there's already a high-ish density in survivability terms, so that explosions are harder to produce.

But that might just lead to quick death and sparseness.

I wonder if there would be something to trying to treat the three axes as isolated planes, and use some sort of summing function to across three different 2D calculations to determine birth and death of the whole? Of course, that's moving a bit away from a straightforward interpretation of 3D life as an analogue to 2D life, but I do wonder.

I was reading something via a link via a link via...discussing a couple week's exploration of a hex arrangement. I turned up some interesting Life-like phenomenon but the guy playing with it didn't get as much satisfaction out of it as out of real Life; whether that's a reflection of a subpar substrate or just not enough exploring is hard to say, but it did get me thinking about the difference in a hex vs. traditional grid lattice—hex has six equidistant neighbors and is built out of congruent local connections between cells, whereas the 2D grid we're accustomed to has connection of two different "lengths", if you will, at the cardinal and at the diagonal directions. It's eight neighbors, yes, but four of one type and four of another. Which is an assertion I haven't totally satisfied myself of the implications or value of, but, yeah, there.

So I wonder from there if there might be something to what makes the system work, if there is some power embedded in that not-quite-simple lattice that we take for granted.
posted by cortex at 6:49 PM on June 12, 2010


Man, I really want to start fiddling with this but am otherwise distracted, but: it occurs to me that one of the things that seems to keep growth checked in traditional Life is the fact that it's easy for new growth to overstep its bounds a bit and create overcrowding that immediately leads to die-off. Which makes me wonder if you'd have luck specifically trying to push the birth condition toward the high end of the survival range—make it so that birth is more likely in a situation where there's already a high-ish density in survivability terms, so that explosions are harder to produce.

I've tried a little bit of this, without a lot of success. But there are a lot of possible rulesets to try, so maybe there is one that'll work. The trick is finding one that allows a reasonable amount of death from overcrowding, yet doesn't cause clusters of cells to grow for 1 generation and then instantly die off from overcrowding themselves. I think this is where working in 3D makes it difficult to do this, since the number of new cells that grow is so much larger.

I may also be running into trouble from the random starting configuration. Going through every space in the universe and putting a live cell in it with some probability 1/N may be either way too dense (for small values of N) or way too sparse (for large values of N). What I might do is the same random start, but limited to a handful of 3x3x3 cubes, or maybe a little larger. Trying to find the tradeoff between configurations I'd never have come up with myself, and still having lots of empty space around to watch what happens.

The 2D version is kind of like that. Just a few starting cells in a few clusters can produce a lot of action that eventually settles down to some static clusters and some oscillators. That's what I would really like to see in 3D as well.

I wonder if there would be something to trying to treat the three axes as isolated planes, and use some sort of summing function to across three different 2D calculations to determine birth and death of the whole? Of course, that's moving a bit away from a straightforward interpretation of 3D life as an analogue to 2D life, but I do wonder.

I've been thinking about this possibility too. Maybe some sort of stratified 3D version where each 2D plane is treated independently according to the usual 2D rules, but with specific conditions where the pattern may leak in the vertical direction.

Something like:
Pass 1: count neighbours from the 8 adjacent cells in the same plane. Apply the usual B 3/S 2 3 ruleset.

Pass 2: count neighbors from the 8 adjacent cells in the same plane plus the current cell itself. Only if this count is 0, count neighbors from the 18 cells in the 3x3 squares on the planes above and below the current plane. Apply the usual B 3/S 2 3 ruleset.

Pass 1 is run for the whole universe before pass 2, and results from pass 1 would be visible to pass 2.
I think this should allow live cells to leak out of the existing pattern up and down into empty portions of the adjacent planes, but then run like the regular 2D rules once there is something there.
posted by FishBike at 7:35 PM on June 12, 2010


What I might do is the same random start, but limited to a handful of 3x3x3 cubes, or maybe a little larger. Trying to find the tradeoff between configurations I'd never have come up with myself, and still having lots of empty space around to watch what happens.

Yeah, it seems like you could maybe do some more organized hunting by fudging your start condition toward the usefully implausible. Create a well-organized starting state that's basically a collection of unique specimens, each a different small object within a 3x3x3 bounding box surrounded by another generous bit of dead space (an extra 3 or so blocks on each side, maybe, so each 3x3x3 bounded specimen starts in a 9x9x9 "lot").

Then use that as the seed for a bunch of trials using various rulesets, and look for interesting behavior from any given specimen under any given ruleset. Mark down the more interesting ones and go back and explore those specifically with other starting conditions.

That may be pretty much what you were talking about, I'm not sure.
posted by cortex at 7:56 PM on June 12, 2010


That's the basic idea, yes, though it might be a day or two before I get to it. On the plus side, the animations render much faster when there are a small number of living cells and a small number of cell transitions, so rulesets that don't cause population explosions can be turned into graphical representations pretty quickly.
posted by FishBike at 8:13 PM on June 12, 2010


Further to some of my mumbling last night about hexes and grids, I wasn't immediately able to track down the article about hex experimentation that I was reading last week but did find in some googling just now a number of other folks talking about experiments with hex-based Life. And they noted across the board that the six-neighbor version of hex rules (taking into account only the six cells immediately bordering a cell in a hexagon-shaped boundary) was not sufficiently interesting: using a 12-neighbor "star of David" configuration with connection to both the six bounding cells and the six cells on the far side of each pair of adjacent boundary cells, was required for the good stuff to show up.

Which is a nod in the direction I was thinking: the standard grid analog to a six-neighbor hex layout would be not the eight-neighbor version we're accustomed to but a four-neighbor cardinal-only setup, where diagonals would in fact be two cells away from one another.

With the 8-neighbor grid (or the 12-neighbor hex star), there's a crossover situation going on, where e.g. two cells adjacent horizontally can each immediately "touch" cells located vertically above one another—the scope of each of their momentary effects on the universe is allowed to criss-cross. The speed of light "c" in Life is as I understand it discussed as a distance of one cell per iteration, but there's a question there of whether c-along-the-diagonal and c-along-the-cardinal are really the same thing. (Which is an old discussion in tile-based turn-based games like roguelikes, of course.)

Anyway, I need to go looking for what's been said about this in enthusiast circle. It's an angle I hadn't really thought much about before, though the basic idea had tickled me a bit. I'm curious to what degree that two-speed property is likely to for whatever odd emergent-behavior part of what makes the interesting Life stuff work; would it be possible to generate equally interesting behavior from a system that used some other sort of ruleset to deal with non-equidistant cells but at a similar minimal degree of basic complexity? Etc.
posted by cortex at 9:03 AM on June 13, 2010


Ah, and some quick looking tells me these 4-neighbor and 8-neighbor conceptions are Von Neumann and Moore neighborhoods, respectively. I knew vaguely of Von Neumann's early experiments with CA but didn't realize his conception was so starkly different from Conway's in terms of complexity. I think I might need to do some more bookreading about the early history of this stuff.

Anyway, extending from that a little bit re: FishBike's 3D experiments, it seems like there's a middle ground between a Von Neumann 3D neighborhood (which would just be six cells adjacent to the six faces of the root cell) and a Moore 3D neighborhood (which is the 27-cube 3x3x3 FishBike is using): a 15-cube neighborhood that includes only those cells that can be reached by planar moves of one diagonal or two cardinal moves from the root cell. No "superdiagonals", if you will. So the eight corners of the 3x3x3 cube are omitted from the scope of cell's influence.

(I guess this would essentially be a size-2 Von Neumann 3D neighborhood with the six pointy cardinal bits cut off. Hmm.)

Not sure what if anything that would accomplish, or whether the results would be anything interesting, but it'd be a way of sort of containing the scope of the rulesets to play with and might have some interesting effects on growth and such.
posted by cortex at 9:37 AM on June 13, 2010


Starting out with a few random little cubes instead of an entire random universe seems to be a good thing to do. I wrote a few lines of code to initialize the universe with a 3x3x3 matrix of 3x3x3 cubes, and each cell in those cubes has a 50% chance of being live at the start.

I then started with the traditional B 3/S 2 3 ruleset from 2D life again. This gave explosive growth, as before. I then tried incrementing the numbers by 1 (B 4/S 3 4) until explosive growth no longer occurred. That resulted in universe-wide death instead. So I added more survival neighbor counts back in at the low end. Explosive growth again. I increased the number of neighbors required for a new cell to be born by 1 more. I kept adjusting in that fashion until I got something where the live cell count stabilized instead of heading for 0 or 5,000.

And that's when this happened.

This is the ruleset B 6/S 3 4 5 6. It doesn't grow explosively with this starting configuration, nor does it die out or just sit there doing nothing. In fact one of the clusters (bottom center) fizzes away for quite a few generations before settling down. And, we have 3D oscillators!

This makes me far happier than it really ought to.

It's possible explosive growth will still occur with other starting configurations. I do wonder though if the existence of oscillators means that spaceships can now be built in 3D with this ruleset, or maybe with a similar one?
posted by FishBike at 5:25 PM on June 13, 2010 [1 favorite]


This makes me far happier than it really ought to.

I didn't even do any work and I'm excited!

It's possible explosive growth will still occur with other starting configurations.

True, but I wonder if that's a real worry or not? I know that Life as we know it tends toward death and stability with random noise, but it might be a red herring to analogize that to 3D starting points—perhaps by focusing on sparse initial states you'll be able to find some interesting rulesets that otherwise would seem uncompelling with a semi-dense random start.

Apropos of nothing, I found cell-auto.com today and thought it was an interesting (if kind of dense and partitioning-centric) collection of thoughts on Life variations. Doesn't really address the 3D stuff you're fiddling with, but it was an interesting peek into Margolus-inspired varying-partition approaches I was previously unfamiliar with.
posted by cortex at 6:55 PM on June 13, 2010


Along the lines of different neighborhoods and different geometries, I've been sketching out ideas this morning for a 3D version where every cell has 8 neighbors, just like the 2D version. I think I can even draw it as ASCII art at this point.

Let's say we look at one plane of cells, which instead of being a regular square lattice, are a diamond-shaped lattice, where X's represent possible cell locations.
  X   X

X   X  

  X   X

X   X
Now let's say the plane immediately above this one has an identical but offset lattice (show with O's for possible cell locations):
O   O  

  O   O

O   O

  O   O
Superimposing these in one diagram, where the X's are cells in one plane and the O's are cells in the plane above it, we get this:
O X O X

X O X O

O X O X

X O X O
If you then have the neighborhood consist of no cells on the same plane, but the 4 nearest cells on the planes above and below, you get this (with lines showing which cells are each others neighbors):
O-X-O-X
| | | |
X-O-X-O
| | | |
O-X-O-X
| | | |
X-O-X-O
This shows each cell having 4 neighbors (even the edges if the co-ordinate system wraps around). Obviously the same thing is going on with the plane represented by X's and the plane underneath it, too, so that gives 8 neighbors.

And I think this is actually not too hard to code using normal array structures and just evaluating it in a sort of checkerboard pattern that inverts on alternate planes. I'm not sure what shape to use in the actual 3D rendering of a cell, maybe octahedrons, but that's a secondary issue. I'm more curious to see how the 2D life ruleset works in a 3D structure that has the same neighbor count as the 2D version.
posted by FishBike at 8:24 AM on June 14, 2010


Interesting. If you look at that lattice as being constructed essentially of square-based pyramids, it analogizes really directly to a 3D Von Neumann neighborhood, the difference being that the Von Neumann version is composed of triangle-based pyramids instead. In either case the local neighborhood can be imagined as a regular polyhedron with the root cell suspended at the midpoint and the neighbor cells defining the vertices of the polyhedron.

With a Von Neumann, that's regular octohedra—six neighbors makes six vertices forming eight triangular faces. With your idea, it's cubes instead, with eight neighbors defining six square faces. Your lattice could be imagined as a vast stack of cubes with edges all horizontal and perpendicular, whereas the Von Neumann version would be octohedra standing on points, with edges all at 45 degree angles.

Maybe I'll go looking, see if I can find any good documentation of experiments in 3D Von Neumann neighborhoods. My first blush impression is that getting complicated behavior out of that (and out of your not-much-more-connected alternative) may be hard, but that's just speculation.
posted by cortex at 8:55 AM on June 14, 2010


With a Von Neumann, that's regular octohedra—six neighbors makes six vertices forming eight triangular faces. With your idea, it's cubes instead, with eight neighbors defining six square faces. Your lattice could be imagined as a vast stack of cubes with edges all horizontal and perpendicular, whereas the Von Neumann version would be octohedra standing on points, with edges all at 45 degree angles.

Yeah, it occurred to me over lunch that what I had in mind is basically just the equivalent of the simple cubic arrangement, considering only neighbors on the 8 corners (the double diagonals, I think you called them), and only looking at the 50% of cells that are all connected via corners. A 3D checkerboard pattern.

A possible interesting side property of that arrangement is that there's physically space for a 2nd such structure made up of the other half of the cells. Two universes, physically intertwined and yet they don't interact at all. Funky.

Maybe I'll go looking, see if I can find any good documentation of experiments in 3D Von Neumann neighborhoods. My first blush impression is that getting complicated behavior out of that (and out of your not-much-more-connected alternative) may be hard, but that's just speculation.

If you or anyone else still reading this finds anything, I'd love to hear about it. I'm convinced other people must have tried all of these same ideas many times, but I'm just not finding a whole lot about it. I'm also not looking all that hard, because it's more fun to just play with the toys and see what I can make. It doesn't reduce the fun if someone else already made the same thing with their Lego blocks, so to speak.

My guess is also that this won't do anything interesting. 8 neighbors allows the 2D rules to be applied as-is, but the relationships between those neighbors, and their neighbors, etc., are quite different. I mean, they have to be, because if they were the same it would all just be a flat plane again.

That said, I find it hard enough just to visualize the arrangements of cells when they get more complicated than a cubic lattice. Trying to visualize what a given ruleset will do with a given configuration of live cells seems to be pretty well in the "brain cannot do this" category for me right now. I'll just have to try it.
posted by FishBike at 10:55 AM on June 14, 2010


(the double diagonals, I think you called them)

Superdiagonals!

A possible interesting side property of that arrangement is that there's physically space for a 2nd such structure made up of the other half of the cells. Two universes, physically intertwined and yet they don't interact at all. Funky.

Yeah, I almost posted a "OH BUT WAIT HALF YOUR CELLS NEVER TOUCH" objection until I stopped and worked out the visualization more carefully and realized I was inventing that second structure out of thin air.

Trying to visualize what a given ruleset will do with a given configuration of live cells seems to be pretty well in the "brain cannot do this" category for me right now.

Yeah, that's I think part of what makes 1D and 2D rulesets so appealing—complexity questions aside, it's nice to be able to just look at something and see what's up (to some extent) at a glance.
posted by cortex at 11:09 AM on June 14, 2010


Also it appears if I want to make this 3D 8-neighbor thing without having any gaps around the cells, a truncated octahedron is the shape I want for the cells. I found a helpful diagram of this in a Google Books link to a 1976 textbook about polyhedra. "Close-packing polyhedra" seems to be the search term for stuff about this. I'll wait to see if the concept works at all before trying to figure out how to make that shape and orient it correctly, though.
posted by FishBike at 11:47 AM on June 14, 2010


Fishbike,

I did a quick Google and I did find some stuff on 3D life.

It's not a lot, but looks slightly interesting:

http://www.ibiblio.org/e-notes/Life/Game.htm
http://www.ibiblio.org/e-notes/Life/Gliders.htm

They've got some additional links that might also be helpful.

Fishbike, I love what you've done here; it's quite cool to see.
posted by caphector at 12:28 PM on June 14, 2010


(Heh, I had seen those pages before, but... well, let me just say they are a whole lot more useful now that I'm looking at them on a machine with a working Java Runtime Environment on it. So the link to them here was indeed helpful.)
posted by FishBike at 12:43 PM on June 14, 2010


I think I wandered here from one of caphector's links, but this collection of gliders in various 2D rulesets is pretty neat (and pretty big!).

After becoming familiar over the years with the meat-and-potato substructures of Conway's ruleset, it's interesting to look at stuff in other rulesets. Like discovering a whole new ecology; the forms aren't wholly alien but they're also not what I'm used to seeing.

And it gives me a silly idea for a kind of mixed-ruleset thing where you start a board with multiple populated zones each beholden to a given ruleset, and those rulesets move with their life forms as a kind of substrate.

So you could assign to every cell on the grid a "ruleset" value along with the standard live/dead value for the state of the cell. Each cell would be evaluated according to its underlying ruleset. When a new cell is born its tile's ruleset changes to the ruleset best represented by the tiles responsible for the birth. Simple majority, ties broken with fair random chance. Make a sort of competitive evolution game out of it.
posted by cortex at 2:46 PM on June 14, 2010


Wow, I step away from the thread for just a couple of days and it springs to life again. Hmm, familiar behavior....

a 15-cube neighborhood that includes only those cells that can be reached by planar moves of one diagonal or two cardinal moves from the root cell. No "superdiagonals", if you will. So the eight corners of the 3x3x3 cube are omitted from the scope of cell's influence.

Isn't that actually 19 cubes?
posted by JHarris at 5:08 PM on June 14, 2010


So you could assign to every cell on the grid a "ruleset" value along with the standard live/dead value for the state of the cell. Each cell would be evaluated according to its underlying ruleset. When a new cell is born its tile's ruleset changes to the ruleset best represented by the tiles responsible for the birth. Simple majority, ties broken with fair random chance. Make a sort of competitive evolution game out of it.

I've had an idea for a computer game for quite a long time something like this. It's one of the two-dozen or so game ideas I've got laid away for when if I ever get the chance to work on them. At this rate it's not looking good, and that makes me incredibly depressed....
posted by JHarris at 5:10 PM on June 14, 2010


Isn't that actually 19 cubes?

Look, I have a computer science degree and took AP Calc in high school so I'm pretty fucking sure that 27 - 8 = 15.

Kill me now.
posted by cortex at 5:12 PM on June 14, 2010 [1 favorite]


So many ideas! So little time!

I took a stab at the 8-neighbor geometry from this comment, complete with truncated octahedral cells so there aren't gaps between adjacent cells. Intuition was correct this time, it wasn't interesting, though it didn't experience a population explosion or a complete die-off, so I guess that's kind of neat.

Anyway, I spent so long trying to get the truncated octahedra right, and oriented and spaced correctly, that I put a little 10-frame animation up. It doesn't look as nice as the cubes because rounding off the corners and sharp edges is even more difficult. The rounded cubes are just superquadratic ellipsoids, which POV-Ray does natively. I had to make the truncated octahedra myself from the intersection of an octahedron and a cube, though there's probably a way to sand them down by using an isosurface instead. The math for that is currently beyond me, though.

Look, I have a computer science degree and took AP Calc in high school so I'm pretty fucking sure that 27 - 8 = 15.

Well, I'm a high school dropout, so that's my excuse.
posted by FishBike at 6:45 PM on June 14, 2010


I was trying out some odd ways of looking at the cell neighborhoods in a sort of hybrid of 2D and 3D, a bit like I mentioned in this comment. What I did here was count the 8 neighboring cells in the X-Z plane. Only if that was 0, then I counted the neighbors in the Y-Z plane. And only if *that* was zero, I finally counted the neighbors in the X-Y plane.

The result is a count of neighboring cells in the first of those three planes that had a non-zero count. From there I just applied the traditional 2D life rules to the resulting count. I think the outcome was pretty neat.

For one thing, there's an actual 3D glider buzzing around at the top! Most of the starting clusters (27 flat 3x3 random tilings) seem to stabilize, but one sort of takes off and seems to be getting bigger and bigger, but slowly. And it sort of has the 2D life style about it, somehow.
posted by FishBike at 6:07 PM on June 17, 2010


Cool, cool. Although I have to say that dividing up the neighborhood situationally like that somehow doesn't feel as "pure" as original Life.
posted by JHarris at 2:00 PM on June 20, 2010


Although I have to say that dividing up the neighborhood situationally like that somehow doesn't feel as "pure" as original Life.

Yeah, I agree, it does feel sort of contrived to engineer a specific type of result. I looked at that other page with some 3D gliders on it, and while those do work with the rulesets given, those rulesets don't really work in the general case of random clusters of starting cells. They seem to fall into the 'everything dies' or 'everything grows indefinitely' categories unless the starting configuration is very carefully designed.

One thing I still haven't tried, and plan to, is to use those truncated octahedron shapes again, and make the neighborhood the 14 cells attached to the 14 faces of the shape. I think this can still be done on a cubic framework, and the 6 cells attached to the square faces of the truncated octahedron are in the same direction as the 6 neighbors on the faces of a cube, but 2 cubes away instead of directly adjacent.

It's still interesting to me that the 3D case is so much more challenging than the 2D one, and I still suspect, but have no idea how to prove, that there's something very basically mathematical that explains why.
posted by FishBike at 5:42 PM on June 20, 2010


They seem to fall into the 'everything dies' or 'everything grows indefinitely' categories unless the starting configuration is very carefully designed.

Well to be fair it took Life enthusiasts quite some time to discover higher-order Life forms like glider guns and large spaceships. I don't know how much experimenting Conway did before he discovered the B3/S23 rule, but it must have been a lot. (I have this vision of the guy sitting at his table with a huge array of mathematical toys, checkerboards, counters, calculators, and all matter of other things, doing random things all day long. As part of his job. Why can't I find jobs like that?)
posted by JHarris at 7:38 PM on June 20, 2010


« Older Tripmaster Monkey   |   On the Fly Newer »


This thread has been archived and is closed to new comments



Post