Assignment 2

872a Model Based Design

Assignment 2, due 9/26:
Cellular Automata: Complexity from Simplicity

Submissions are to be posted to the web before class so that we can do an online "pinup" in the second half of class.

Introduction

In 1970 British mathematician John Conway started placing checkers in a grid on his office floor. His game soon spread out into the hallway, and eventually, he found it impossible to get into or out of his office without disturbing the structures that were emerging from his simple rules. He called it "The Game of Life." If he weren't already a mathematician, people would have thought he was crazy.

In fact what he was doing was discovering a particularly fruitful variety of cellular automata, a field originated in the 1940s by John von Neumann, the principal founder of modern computer science.

Cellular automata live on a gridded plane, one to a grid cell. (There are also linear, triangular, hexagonal and 3D cellular automata, but for now, we'll consider a grid of squares.) The automata cannot move--they are confined to their individual cells (hence cellular). Each automaton carries with it information called its state. State can be any data, simple or complicated, but in many cases, including the Game of Life, state only consists of a single boolean value, alive or dead.

To begin with cells are assigned state at random. Then an update cycle begins in which each cell in turn is asked to update its state based on a set of internal rules. All automata obey the same set of rules. These rules dictate how the internal state should change based on the environment around the cell, which consists of the states of its neighbors. (Note that the state does not actually change immediately. The next state is stored, and later, after all the cells have applied their rules, they all change to their new states at once. That way each cell is responding to the same existing set of states, not a continuously changing set.)

The rules are usually quite simple. In the case of the "Game of Life," they are remarkably simple:

1) If you are alive, stay alive if two or three neighbors are alive. Otherwise die.
2) If you are dead, come to life if exactly three neighbors are alive.

And from that comes this, a bubbling pot of odd creatures. It is the simplicity of the rules, and the amazing complexity of the resulting forms that have inspired people over the last thirty years to spend an inordinate amount of time and energy studying the properties of this particular system. People acting as digital naturalists have cataloged thousands of different forms that can emerge and the properties they exhibit. (See Eric Weisstein's Treasure Trove and the Life Lexicon, for instance.)

Life is by no means the only cellular automata system of interest to research, however. Stephen Wolfram, the brilliant, reclusive, megalomaniac, millionaire mathematician has devoted the majority of his research to cellular automata, most recently suggesting that they can be used to model all physical laws. (He did some early work with one-dimensional CAs that produce patterns that are easy to find in nature on seashells, for instance.) You might find his new book A New Kind of Science useful as inspiration. It's beautifully illustrated.

The template

As you may have guessed or seen linked above, this week's template is a cellular automata template that implements the Game of Life. But you are invited to go well beyond that into other explorations. Here it is.


1. New rules		One of the easiest ways to modify a cellular automata system is to change the rules the cells use to update their states. In a simple life-or death system based on 2D neighbors in a grid, there is a shorthand for describiing these rules in which Conway's Life would be called "23/3". The numbers before the slash indicate the number of living neighbors that are acceptable to maintain a living cell (in this case two or three). The numbers after the slash indicate the numbers of living neighbors that will resurrect a dead cell (in this case only three). For example, there is a variant called "HighLife" in which a dead cell with six living neighbors will also come to life. This is written "23/36". Try out HighLife, and see the difference. You may want to slow down the frame-rate and make the cells bigger to really see the differences more clearly. Most rule combinations do not yield much of interest. They either die or explode immediately. Such is the delicate balance of life, which points out the radical dependence in complex interacting systems on tiny variations in initial conditions. Wikipedia lists a bunch of interesting variants on life rules. Try some of them out. Make up new ones of your own. Also remember that your rules are not bound to look only at immediate neighbors or even at all the neighbors. You can, for instance, look only at neighbors to the left or something. Play at length with the rules. Find two or three new rule sets that do interesting things. Describe what they do and why. What kinds of structures emerge from these rules?

2. More substantial changes		Changing rules is just the beginning. Now it's time to make some more substantial changes. Produce at least two good ones. You're on your own here, but here are some ideas for inspiration: Mike Davis has done a couple of beautiful CAs, some of which use multiple automata types on the same grid. It's not hard to modify our template to support that. Look here and here. Rules do not have to be deterministic. They may have probabilistic components. Maybe with a certain number of neighbors there is a specific chance of survival. Experiment with this. Wolfram is a good source. Maybe try some 1D automata. These tend to be viewed in 2D (you just keep the active line moving down the screen). For more examples see here. This one is a little harder, but can be pretty rewarding. I'll help if you want. Cellular automata don't have to be done on a rectangular grid. In fact, they can be run on any tesselation of the plane at all. Try doing CAs on a triangular or hexagonal grid. Look here, for a good reference. (Be sure to scroll down.) Along the same lines, CAs can be done in 3D. Here is a template I did in Processing. It is tough in 3D to come up with good rules that don't lead quickly to extinction or explosion. I haven't really found them yet. This example uses some Java/Processing language features that we haven't discussed yet. If you're feeling adventurous, go for it.

3. Developing your own model, part 1		Pick one of the two systems you started looking at last week. (Or a new one if you can't stand either one.) See if it makes sense to break it down into a set of interacting agents or particles. Note that not all systems do break down easily this way, and some that do require a little imagination. What are those agents? What kind of interactions do they have with each other? What kind of state would they need to carry to describe themselves? Make some diagrams to describe the agents and their interactions. Do not fear that you will have to model your system as a CA. As interesting as CAs are, it is often hard to apply them to the modeling of real-world systems. I think that's because in real systems, most agents are at least somewhat mobile. (We'll look at mobile agents next week.) Therefore do not think that CAs are necessarily the tool you'll end up using to describe your system.