Breeding Gliders in Cellular Automata

Background
This is partially based on the work of Chris Langton (Artificial Life II proceedings, 1992). Kirk Isreal inspired the idea in a conversation. Another reference is Karl Sims' Interactive Evolution of Dynamical Systems. Examples of many classic CA's are found in John Walker/Rudy Rucker's CA's. Also, a site with info on CA's, edited by Howard Gutowitz, from Artificial Life Online, has a lot of info as well. A good book to get is "Cellular Automata Machines", by Toffoli and Margolus, 1987, MIT Press). Also look at Jean-Claude Heudin's overview of CA's in Virtual Worlds . Also, Poundstone's "The Recursive Universe" is a good book, for a nice intro on Conway's Life. These are of course just a few examples of references.

How Does the CA Actually Work?
The implementation I have made works as follows: CA's are finite-state automata occuring at the sites of a triangular 2D lattice. The lattice wraps around to avoid boundary issues. Each cell can be in one of 7 states, whose colors are black, red, orange, yellow, green, blue, and violet. As the clock ticks, each cell can change its state, depending on its current state and the various states of its six neighbors. This CA uses the counting scheme: each cell counts the number of neighbors of each of the states. Based on these numbers, it uses a transition rule to change to its new state. Similar to Conway's Game of Life, this CA considers it's own state in addition to the counts of neighbor states.

Memory
An important addition to this scheme is the use of "memory". Each cell will keep its state for up to 4 time steps, unless a transition rule dictates that it must change. By the default, the cell will change to the 0 state (black, or 'quiescence') by default. The addition of memory adds more complexity and the potential for more life-like behaviors to emerge.

Fitness
At the start, each CA is given a random fitness value ranging from 0.0 to 1.0. When you judge a CA as bad, the fitness value becomes 0.0. When you judge it as ok, its fitness becomes 0.5. When you judge it as good, the fitness becomes 1.0. Whenever you judge a CA as good, all the fitness values decay by a tiny amount (fitness * 0.99). In doing so, the fitnesses of older CA's are able to slowly fade into the past as new CA's are introduced into the population. After a while, the fitness profile will vary quite a bit with values ranging from 0.0 to 1.0. The purpose of this is psychological: you, the breeder, are likely to favor your more recent CA's than the ones of the remote past, and so you would rather not have some old CA that was once the best (but is now not the best) to stay as a strong influence. read on for more info on mating, and this should become more clear.

Genes
CA's can mate with each other to make offspring CA's which inherit the genes of the parent CA's. A CA's genes are what determine the transition rules for each of its cells. For a given CA, the exact same rule is used on each cell, thus, genetic variety does not occur among cells of one CA, but rather among different CA's. The genes determine things like which states a cell will be in when it checks its neighbor count, which states it counts, and how many neigbors of a specific state it takes for the cell to change its own state. Other genes determine the new state the cell takes on. As you can imagine, there are many possible permutations of transition rules possible with only a handful of genes. I have merely scratched the surface. Other folks have devised much larger genetic search spaces than this one. This is something I will be exploring, so as to make many more CA's possible. I am, however, just as interested in making this a real-time appplication, which is fun and educational, so I am considering ways to keep the CA running fast on average computers, and on having relatively fast evolutionary convergence.

What You Do
Simply watch the CA as it animates and judge it as either bad, ok, or good. After you judge it, another CA will animate. Judge that one. Repeat this process many times. You may eventualy hit upon a CA with gliders you really like. Many of the CA's you see will die off quickly, and some will be very chaotic. These should be judged as "bad" because their dynamics are too far off on either side of the edge of chaos - that lovely fractal boundary where life-like behavior emerges. At the beginning, most of them will be bad. If you see "objects", give it a good or ok judgement. It will take several minutes, but gradually, more interesting dynamics will appear, as the population genetics converges to the edge. Make sure you judge some of them as good. Remember: your judgements provide the Darwinian fitness values that help guide the direction of evolution.

Stir it Up
Click and drag in the CA window to stir the soup.

BE PATIENT! ...... Evolution takes time
The number of possible CA's is simply astronomical. But artifical evolution is a tool to help you weed out the vast majority of useless CA's. Even so, you may find this to be a boring task (unless you are like me and are completely obsessed with CA's). There will be times when it seems like all you are doing is hitting the "bad" button. Roll with it. But make sure to sometimes reward CA's that are vaguely promising, if you feel like you are in a dead-end. Eventually, the fruits of your labor will start to show though.

How Do The CA's Mate?
While you are judging CA's, some of them are having sex in the background, behind the scenes. (no need for you to see this - it is not interesting or arousing at all). Two CA's mate per breeding cycle. Every time you make a judgement, two random CA's mate and have one offspring. In fact each CA you judge is the offspring of two parent CA's who have just mated. The CA's that mate are statistically more fit than the rest, meaning, they have been given (relatively) good fitness values by you, at some point. Also, for every breeding cycle, one CA is killed off to make room for the new offspring. The one that is killed off is the one with the lowest fitness value. Since the more fit CA's are doing the mating, their offspring have a better chance of looking interesting to you.

What's So Important About Gliders?
Gliders are chunks of non-quiescent cells that move around, sometimes in dizzying circles, and sometimes along straight paths. Glider interactions can be seen as simulating the primitive elements of computation, and so they are explored by researchers interested in the origins of information, and the dawn of life. For some of us, gliders are just plain aweseome. It's great when aesthetics and scientific research come together.

Related Work by Jeffrey Ventrella