Game of Life

In 1970, Martin Gardner published a Scientific American article describing a "zero-player game" devised by mathematician John Conway. Despite its name, the system was not intended to simulate any particular form of life. Its evocative metaphor and remarkably simple rules nevertheless helped make Conway's Game of Life one of the best-known and most extensively studied cellular automata.

A complete implementation of this algorithm in Utomata looks like this:

&V9 = #.SUM((-1, -1), (1, 1));
&V8 = sub(&V9, #);

#GOL {
   dim = (256, 256);
   set = sml(rand(), 0.1);
   run = max(eql(&V8, 3), eql(&V9, 3));
}

~vis {
  col = #GOL;
}

Run this example

In this guide, we will break the sketch down into its basic parts and use it to introduce how cellular automata can be expressed in Utomata. We will then move beyond Conway's original rule and explore how small changes to the same structure can produce different cellular dynamics.

What is a cellular automaton?

A cellular automaton (CA) consists of a regular grid of cells. Each cell stores a value and all cells are updated at regular intervals, while typically taking into account the states of their neighboring cells.

Many cellular automata algorithms, including Game of Life, use a two-dimensional grid where each cell only has two possible states: 0 and 1, referred to as a binary state CA.

At every step each cell in the grid:

reads its own current state value and its neighborhood
uses these values to calculate its new state according to the transition rule
commits its state to be made accessible on the next step

The transition rule is shared by all cells and applied uniformly so cells never read their neighbors mid-step. This synchronous update scheme is built directly into Utomata fields.

Setting up

We begin with a field to hold the grid and a formation to display it:

#GOL {
   dim = (256, 256);
}

~vis {
   col = #GOL;
}

#GOL contains a 256 × 256 grid of cells. We will use each cell to store a single binary state value.

The algorithm itself will exists entirely in #GOL. The formation does not participate in the simulation; it only projects the current field values as surface color for visualization.

Initial state

Every CA algorithm starts by assigning initial values to all cells in the grid. In Game of Life, we like to describe cells as dead or alive, but that simply means they can either bear a value of (0) or (1) respectively:

set = sml(rand(), 0.1);

rand() generates a random value between 0 and 1.

sml(a, b) compares its two inputs and returns 1 where a < b, and otherwise 0.

The expression therefore gives each cell a 10% chance of starting out alive.

Changing the threshold changes the initial population density:

set = sml(rand(), 0.5); // a 50-50 chance

CA algorithms are quite often deterministic, meaning that their evolution over time depends entirely on their transition rule and initial state. In Utomata, the pseudorandom values generated by rand() are seeded. This means that fields will generate the exact same outcome over any number of steps.

The neighborhood

Game of Life uses the Moore neighborhood, which includes the eight cells immediately surrounding the current cell.

■ ■ ■
■ X ■
■ ■ ■

Because Game of Life uses binary state, counting the number of living neighbors is equivalent to summing their values. The neighborhood count can therefore range from 0 to 8, ot 9 including the cell itself.

In Utomata, we can begin by summing the complete 3 × 3 region centered on the current cell using the SUM operator:

&V9 = #.SUM((-1, -1), (1, 1));

This looks at cells in relative units, extending from -1 to +1 on both x and y. The return value is then summed and returned. note that this includes the currently evaluating cell. For convenience, we store the result in a &macro.

To obtain only the eight surrounding cells we can subtract the current value:

&V8 = sub(&V9, #);

Here, # refers to the current value of the cell being evaluated.

We now have two useful quantities representing the Moore neighborhood for each cell in the field, representing the number of live neighbors, inclusive (&V9), and exclusive (&V8).

The transition rule

The algorithm for Game of Life is typically described as follows:

Survivals: Every cell with two or three living neighbors survives.
Deaths: Each cell with four or more neighbors dies from overpopulation; every cell with one neighbor or none dies from isolation.
Births: Each dead cell adjacent to exactly three neighbors becomes alive.

Utomata lets us articulate these rules numerically:

eql(&V8, 3) // part A

Part A is true (returns 1) whenever the cell has exactly three live neighbors (not including itself). This covers two situations from the algorithm above: a live cell with three live neighbors (survival), or a dead cell with three (rebirth).

eql(&V9, 3) // part B

Part B looks similar but note that the comparison uses &V9 this time. It is therefore true (returns 1) when a live cell has exactly two live neighbors, or when a dead cell has three. Note that the former case completes the survival rule (live cell has two or three live neighbors), while the latter case is shared by both A and B (dead cell has three).

Together, A and B fulfill the survivals and births requirement, leaving only deaths. But since deaths simply mean: "return 0 for all other cases", that rule can remain implicit because all remaining cases evaluate to zero anyway.

In other words - the transitioning cell should live IF either (part A) OR (part B) return 1, and otherwise dead. In Utomata, we can describe logical OR relationships with the max() operator, because it would be enough for either part to be 1 for max() to return a non-zero value:

max(0, 0) → 0 // neither a nor b
max(0, 1) → 1 // b but not a
max(1, 0) → 1 // a but not b
max(1, 1) → 1 // both a and b

The complete GOL rule is therefore:

max(
  eql(&V8, 3),
  eql(&V9, 3)
);

Variations

Conway's Game of Life is only one possible, albeit a very interesting, cellular automaton out of countless possible others.

Once a system has been created with neighborhood counters and numerical comparisons, other CA algorithms rules that bare familial resemblance to the Game of Life can be explored simply by mutating the transition rule.

first, let's add a few more common CA neighborhoods to play with:

// Von Neumann neighborhood
&V4 = #.SUM.RAD(1.25); // only 4 orthogonal neighbors

// Moore neighborhood
&V9 = #.SUM((-1, -1), (1, 1));   // inclusive
&V8 = sub(&V9, #);               // exclusive

// Extended Moore neighborhood
&V25 = #.SUM((-2, -2), (2, 2));  // inclusive
&V24 = sub(&V25, #);             // exclusive

Exploring new CA algorithms does not necessarily have to be an analytical endeavor. Once a neighborhood has been expressed numerically, the transition rule becomes a relatively small part of the system that can be changed independently.

This makes simple trial and error surprisingly productive. Changing a comparison, combining neighborhood counts differently, or substituting one neighborhood for another can produce entirely different dynamics. The examples below are a few such mutations of the same basic setup. Try running them and observing how each rule develops over time.

run = eql( sub(5, &V25), eql(0, #));

run = eql(mlt(3,&V9),add(3,&V24, #));

run = eql( eql(&V24, 4), sub( sub(4, &V9), &V24));

run = eql( eql(1,&V8), sub( sub(6,&V24), &V9));

run = eql( eql(&V24, 3), sub( sub(5, &V8), &V8));

These variations still operate within a fairly narrow family: binary states, regular neighborhoods, and a single transition rule. None of these constraints are fundamental to Utomata.

We can experiment with multi-channel or floating-point state values, asymmetric neighborhoods, and complex initial configurations. Several rules can be compounded within the same field, or multiple fields can evolve in parallel while reading state values from one another. From this point, the same basic CA structure can be extended in many different directions.