Artificial Life

Artificial life is the study of virtual worlds populated with organisms that interact with their environment and each other. The field is wide open -- it can be used to model existing life forms, or it can be used to create something completely new; it can be taken from a high-level standpoint with abstract virtual creatures, or from a low-level standpoint with a set of quantum physics.

Our research delved into the branch of artificial life called cellular automata, which deals with a type of virtual world comprised of a large number of cells, and executed over a certain number of discrete timesteps. A cellular Automata is defined by the following characteristics:

1 - Geometry. The world’s geometry defines the dimension of the world (one, two, or three-dimensional), the topography (flat, spherical, toroidal, etc.), how the cells are laid out (arranged in squares, hexagons, etc.), and the size of the world.

2 - Neighborhood. The neighborhood definition determines the area of effect that a cell has. A cell will react only to changes that occur within its neighborhood.

3 - Set of States. Each cell must have a finite number of states, describing the current condition of the cell. This may be as simple as "on or off," and can be as complex as an extensive set of genes.

Conway's Game of Life is a quite popular cellular automata. Cells live or die according to how many neighboring cells they have: if a living cell has less than two or more than three neighbors, it dies; if a dead cell has exactly three neighbor, it becomes alive. The simulation is given a starting point, and every state is calculated sequentially.

Cities can be viewed as another form of cellular automata, especially as depicted in this scene from Sim City 3000. Individual pieces of land can have many types of things built on top of them. Using a cellular automata always means breaking up a space into regions of identical properties, which lends easy to city building.

Cellular Automata is modeled quite like bacteria. Bacteria live in their own spaces and interact with their neighbors in ways such as movement, resources, and environment. Each bacterium is its own cell, and if it sexually reproduces with its neighbors, it hits at the core of what cellular automata is.

This model was based off of Conway’s Game of Life, but soon took on a life of its own. Instead of having one fixed rule of how cells interact with their neighbors, each cell carries a set of rules with them, in the form of genes, and passes them off to other cells they produce. In addition, instead of the simple on/off state found in Conway’s rules, each cell has a certain amount of life. The idea behind this was to allow a greater variety of patterns to come about, and to allow us to fine-tune rule sets.

Each of our cells now has a life value (from 0 to 7, 0 being "dead"), and a 9- part lookup table of values from -4 to +3, describing what changes the cell undergoes when it has no neighbors, one neighbor, two neighbors, etc.

Like the Game of Life, a live cell is created from a dead cell whenever it has exactly three neighbors. Each of the cell’s three parents contributes three genes to this new cell, and the life of the new cell is the average life of its surrounding cells.

This model allows us to do two main things. First, using a homogeneous gene pool, we have a great deal of freedom and room for experimentation on the rule set, allowing us to tweak the world and compare the effects of one gene pattern to another gene pattern. The bulk of the research of this model, including the "Frog World" example, was done with homogeneous gene pools.

Second, using a heterogeneous gene pool, we can watch individual genes spread and evolution run its course within our artificial worlds.

5		Gene Value 0 -1 1 -1 2 -3 3 +2 4 -1 5 -1 6 -1 7 -1 8 -1		7
This cell has 3 neighbors and a life of 5.		Its genes are consulted		The cell's new life is 7.

Example: The Frog World

The frog world (so named because of the frog- and tadpole-like patterns it creates) was one of our most successful experiments, happened onto almost completely by chance. It exhibits a form of self-replication -- the holy grail of artificial life -- and self-organization. When two "frogs" smash together, they make four frogs. In addition to the frogs, you can pick out tadpoles, jellyfish, blobs, and other interesting patterns, and if left alone, they will all swim together in perpendicular streams.

Gene Value 0 -1 1 -1 2 -2 3 -3 4 +1 5 -1 6 -1 7 0 8 +1

0 3 0 3 6 3 0 3 0 4 0 4 0 7 0 4 0 4 3 5 3 5 7 5 3 5 3 1 0 0 0 0 0 0 0 2 3 0 0 5 0 0 0 2 4 6 7 0 0 0 2 4 6 7 0 0 2 3 0 0 5 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 3 0 0 0 1 3 5 7 6 0 0 1 3 5 7 6 0 0 0 0 0 3 0 0 2 0 0 0 0 0

This model of cellular automata uses a 2-cycle approach.

Cycle 1: Birth and Death

• Each cell begins in the simulation with a given amount of life, assigned randomly.
• If at any time the cell's life falls at or below 0, it becomes dead.
• If a cell is surrounded by more than 3 cells, it becomes crowded and a set amount of life is deducted from its total.
• If a cell is surrounded by fewer than 2 cells, then it is lonely and a set amount of life is deducted from the total.
• If a blank space (dead cell) is surrounded by exactly 3 cells, then they "reproduce" by taking the median of their maximum life values, and each contributing 1/3 of its genetic code.

Cycle 2: Movement

• Each cell takes turn moving in priority given by a 2 input mathematical function, with the spatial coordinates yielding it's priority.
• In turn, each cell makes a move given by its next gene in repeating sequence, for example, the gene sequence may be left, stay put, up, up, right, and then repeat.
• If a cell moves to a location where another cell has already moved, then the moving cell "attacks" the stationary cell. If it has a higher life than the stationary cell, then it consumes the other cell (adds to its life), otherwise, it dies and deducts an amount from the cell it attacked.

Examples of Organizational Patterns

This shows many smaller organizational patterns, arising from a random initial state. The small organizing patterns are often related to each other and have similar genetics, so they generally each move in their own directions.

When the smaller patterns are left to themselves for longer periods of time in particular environments, they will continue to clump or grow into each other. This can make for some interesting organizational patterns.

When an individual colony is isolated and it has symmetric properties, more complex patterns can emerge.

Analysis Methods

After generating a world, they can be subject to further mathematical or visual analysis to help find patterns and determine what qualities "interesting" worlds share with each other.

Lookup Frequency Analysis

Lookup frequency analysis consists of counting up the number of times any specific neighborhood occurs over a certain span of time, and displaying the results as a histogram. Chaotic, static-like worlds will produce histograms with no distinct spikes. Orderly, dead worlds will produce histograms with many large spikes. Interesting worlds tend to produce histograms with a few medium-sized spikes.

Input-Entropy Analysis

Input-entropy is based on the results of the lookup frequency analysis. For each timestep, an entropy value is calculated based on Shannon’s input-entropy equation:

(S_t is the entropy at timestep t, k is the number of possible neighborhoods, n is the number of cells, and Q_t,i is the lookup frequency of neighborhood i at time t).

What is important is not the entropy value itself, but by how much the entropy changes with time. The entropy of a world that is too orderly or too chaotic will not change much over time, where the entropy of an interesting world will fluctuate greatly.

3D Analysis

Entropy: mean = 1.178; std. dev. = 1.613

Density: mean = 0.040; std. dev. = 0.681

Lookup Frequencies:

Entropy-Time Graph:

3-D Visual Analysis:

Analysis of Cells in Motion

Occurance of Sierpinski Gaskets

The Sierpinski Gasket is a mathematical entity that seems to pop up just about everywhere. It can be generated by taking 3 points in a triangle, and taking a pencil, putting a dot randomly, and randomly picking point of the triangle, move half way there, and placing another dot. Then repeat this thousands of times. Another way to generate it is to make Pascal's triangle and color in the odd numbers. There are other ways to make the Sierpinski gasket, such as using L-systems, and iterated function systems. It is quite interesting that we see the Sierpinski gasket when looking at the 3d views of certain rule sets in cellular automata. It shows the depth of math peering all the way to the heart of cellular automata.