The game
cellular automata, before the board gets strange
A cellular automaton is a universe reduced to three decisions: a set of cells, each in one of a few states; a notion of neighbourhood, saying which cells each cell can see; and a rule, computing every cell's next state from what it sees. Time advances in lockstep — every cell updates at once, then the world repeats. Conway's Game of Life is the famous case: two states (alive, dead), the eight surrounding squares as neighbours, and one rule — a dead cell with exactly three live neighbours is born, a live cell with two or three survives, everything else dies.
Everything below runs in the same engine that produced this project's results, because to that engine a square grid is nothing special: it never sees squares, only a list of which cells neighbour which. Life is rule B3/S23 in its bookkeeping — born on 3 neighbours, surviving on 2 or 3 — and the grid is a graph it was handed.
Anatomy of one step
The neighbourhood is part of the game
"The eight surrounding squares" was a choice. Count only the four edge-sharing squares — the von Neumann neighbourhood — and B3/S23 names a different universe with different physics. On tilings, these two choices generalize exactly: neighbours that share an edge, or neighbours that share at least a corner. The paper calls them edge and vertex adjacency, and the distinction will turn out to matter.
Is the four-neighbour world simply barren, then? No — it just is not where B3/S23 lives. Each neighbourhood has its own physics, and rules must be found for the world they inhabit. Under the parity rule, the von Neumann neighbourhood does something Life never does:
More states: the Generations family
Life's cells die instantly. Give death a duration instead — states that count down before the cell can rest — and you get the Generations family with k states: state 1 fires, states 2 to k−1 are dying embers that no rule can see, and only firing neighbours are counted. The simplest member is also the liveliest:
Rules as tables
The descriptive power of the Generations rules can be limiting. The general form used in this project is a priority table: ordered rows, each demanding an own-state and up to two per-state neighbour counts (n₁ is the number of neighbours in state 1, and so on), first match wins, no match means ground. Brian's Brain, rewritten:
| own state | conditions | next state |
|---|---|---|
| 0 | n₁ ≥ 3 | 0 |
| 0 | n₁ ≥ 2 | 1 |
| 1 | — | 2 |
| * | — | 0 |
The first two rows encode "exactly two" by descending thresholds: three or more firing neighbours is caught first and does nothing, so the second row fires only on exactly two. That trick makes tables strictly more expressive than any B/S notation — and two of their extra powers, seeing non-firing states and demanding two counts jointly, are precisely what the hunt will eventually need.
Every rule above, from B3/S23 to the tables, shares one property: a cell's fate depends only on how many neighbours are in each state, never on which ones — the arrangement is invisible. Rules of this kind are called semi-totalistic, and the next section shows why, on the boards this essay is really about, there is no other kind.
That is the entire game. Nothing above cared that the cells were squares: the engine consumed a list of who neighbours whom and a rule for what each cell does with what it sees. Hand it a different list — one where the board is no longer the same everywhere — and the same game begins to ask harder questions.