Good Math/Bad Math

Wednesday, April 05, 2006

Fun with cellular automata: Conway's Game of Life

A cellular automaton (CA) is an incredibly simple thing. But when you put a bunch of them together, you can produce incredibly fascinating results. The individual machines are trivial, but when you put them together in large numbers, you can do just about anything. To me, this is an amazing thing: incredibly complexity and even beauty can emerge from the simplest of mathematical systems.

Basically, CAs are grids of lots and lots of trivial machines called cells. Each cell can be in one of a small number of colors (sometimes also called states). The CA runs in steps, where every cell runs its program once each step; and in each step, it can look at what the colors of its neighbors were in the previous step, and use that to decide what color it should turn. In fact, that's really the only computation it can do: choose a new color, based on what color it was last step, and what colors its neighbors were in the previous step.

The most famous CA is called Conway's Game of Life; we'll take a look at that first. In the Game of Life, the cells are arranged in a rectangular grid. Each cell has 8 neighbors: north, northeast, east, southeast, south, southwest, west, and northwest. At any given time, each cell is either black (alive) or white (dead). For example, here's a single cell with its neighbors; the cell is black, but all of its neighbors are white:



In Life, the rules for how a cell picks its color are:

  1. Statis rule: If a cell is white, and it has less than three black neighbors, it stays white.
  2. Birth rule: If a cell is white, and it has three black neighbors, it turns black.
  3. Survival rule:If a cell is black, and it has either two or three black neighbors, it stays black.
  4. Overcrowding rule: If a cell is black, and it has more than three black neighbors, it turns white (dies)
  5. Loneliness rule: If a cell is black, and it has either zero or one black neighbors, it turns white (dies).


So what can you do with this? Life is a very neat playground for figuring out how to construct interesting patterns. The simplest stable pattern is a black square:



In the square, each cell in the square has three live neighbors, and so they stay alive; the cells outside of the square never have more than two live neighbors, and so they never become alive.

A more interesting stable pattern is a flicker-cross - it's a pattern which alternates between two states. The flicker cross is a row of three black cells. When the cells are a vertical row, the center cell has two live neighbors, and so it stays alive; the top and bottom cells each have only one neighbor, and so they die. But the cells horizontally next to the center cell have three neighbors, and so they're born; so it switches to a horizontal row of three. Here's an image of the two states of a flicker cross, with the number of live neighbors marked in each square.



One last pattern for today, my favorite of the simple ones. This is called a glider. The glider is a semi-stable pattern. It doesn't create a stable pattern in one place, but it creates a pattern that moves accross the grid. It goes through four states, and winds up one cell north and one cell west of where it started:




How much can you do with something as simple as the game of life? You can draw a pattern which is a universal turing machine - so this seemingly trivial little thing is capable of doing any task which can be done by any computing device.

There's a nifty applet online to let you watch the Life CA in action, and play with lots of different patterns.

5 Comments:

  • If you're interested in Conway's Life and blogging, you should definitely check out Game of Life News. Lots of fascinating and complex patterns, and a sidebar of links to many good GoL resources.

    By Anonymous D. Eppstein, at 9:22 PM  

  • Nice post, Mark. (I like the graphics, too.) A long, long time ago, I was privileged to meet John Horton Conway in England and spend a couple of hours interviewing him for a book project that ended up going nowhere. It was from him that I learned an earlier version of Life included sex in the generation rules. Conway said the two sexes were labeled A and B, which he and his students began referring to as Actresses and Bishops. As they tinkered with the rules to make the game as interesting as possible, the distinction between A's and B's eventually went away.

    Now that you've piqued my interest again, I've got to look around and see if anyone else has this story. I don't think Poundstone included it in his Recursive Universe book. I need to find my copy.

    By Blogger Zeno, at 10:06 PM  

  • Would this be considered a genetic algorithm or is that something different?

    By Anonymous steve, at 12:42 AM  

  • steve:

    No, this is not a genetic algorithm. Genetic algorithms are very different from this. In genetic algorithms, you actually have complex programs; in each generation, you make a large number of copies of the best program(s) you've found so far, and make random modifications to them, and then again evaluate to see which of the programs is the best. The competing programs do not generally interact directly.

    In the CA, there's no competition between the cells, the program never changes, every cell runs the same program,and the cells are interacting.

    By Blogger MarkCC, at 8:05 AM  

  • Speaking of genetic algorithms, I recently came across a neat evolutionary life simulator called Nanopond. Perhaps this is old news to people here, but it was the first time I'd seen anything like it-- self-replicating genomes evolve fairly quickly (on the order of minutes).

    By Anonymous ivan m., at 1:44 AM  

Post a Comment

Links to this post:

Create a Link

<< Home