Vey.ie

Eoin Davey. Problem solver/creator. CS/Maths/Philosophy Undergrad student @ NUIM, Ireland

Graphs, Topology and the Game of Life

Game of Life

Conway’s Game of Life is the most famous example of a “Cellular Automaton”.

We consider a whole infinite 2d grid of cells, each cell is either dead or alive, and we allow the cells to evolve over time. The rules by which cells evolve are decided by their neighbours.

  1. Any live cell with 2 or 3 neighbours survives.
  2. Any dead cell with 3 live neighbours becomes alive (is born).
  3. All other live cells die, and all other dead cells stay dead.

These simple rules give rise to very complex behaviour, such as this repeating pattern known as “Gosper’s Glider gun”:

Gosper's Glider Gun

Cellular automata take this idea and generalise it, adding more states than just “dead” and “alive”, and looking at neighbours in 1 dimension or 3 dimensions instead of just 2. Cellular automata are not just visually pretty, they’re also powerful, they can compute any programs that any computer can, you can even simulate Conway’s game of life in Conway’s game of life. They don’t even need to be 2 dimensional, shockingly there exists simple 1 dimensional cellular automata are theoretically able to compute anything that any supercomputer could.

But what if we’re sick of just 2 dimensions, 3 dimensions or even 4 dimensions? What if we want to compute in arbitrary dimensions, or compute in pacman’s wrap-around world? We need to think about what we mean when we say “neighbours”.

Graphs

Graph theory is the first tool that jumps to mind when I think about neighbours. Graphs are defined as a set of nodes, and a set of relationships, the relationships tell you what nodes are neighbours of what other nodes. We usually visualise graphs as circles and lines, the circles are the nodes, and the lines connect the neighbours.

Example graph

In Conway’s game of life, neighbours of a cell are all the 8 surrounding cells, we can draw this as a graph like this:

2D lattice graph

Each cell has 8 lines coming from it, connecting to its 8 surrounding neighbours.

Now that we’ve take away the grid, we can start changing things up, we can start adding lines and removing lines all we want. We could use this to represent any simple structure we could think of, for example, we could consider a 2D grid, but only connect cells that a chess knight can jump between; We get this much more complex looking graph:

Knight graph

Every cell still has eight neighbours, so lets run a simulation with the same rules as the game of life:

Knights Game of Life

(You can play with this simulation in Setanta here)

You could imagine how this idea could be used to consider cellular automata in all sorts of wile and wonderful situations. You could have a cellular automata with the structure of the road network of your respective country, or construct a graph of a population, with edges for people who regularly come into contact, and use it to do simple disease modelling, the list goes on.

There is another area of mathematics that’s all about neighbourhoods, and in fact is closely related to graph theory.

Topology

Topology is often called rubber sheet geometry, most people understand it as the doughnuts = coffee cup kinda maths, the study of what shapes are functionally equivalent if you’re allowed to stretch’em and squish’em.

At it’s core though, topology is all about neighbourhoods. It’s all about what points are in some way adjacent to other points. When you think about your neighbourhood, you might think of your immediate adjacent neighbours, or maybe your whole street or estate. All of these would be considered neighborhoods from topology’s perspective. When we say neighborhood we effectively mean a set of points that are in some way related to each other, our topology defines exactly what way they’re related.

Formally speaking a topology \(T\) on some set \(X\) is a collection of subsets of \(X\) satisfying some simple conditions. The elements of \(T\) are our neighbourhoods. These conditions guarantee that elements of \(T\) behave like neighbourhoods around points.

  1. \(X\) and the empty set are both neighbourhoods.
  2. A union of any amount of neighbourhoods is still a neighbourhood.
  3. Any intersection of some finite amount of neighbourhoods is still a neighbourhood.

For example, on the 2d-plane, we could call any circle around a point a neighbourhood of that point.

The way we describe the neighbourhoods tells us then how we can stretch and squish our shapes, we can do whatever we want without ripping or tearing up our neighbourhoods (roughly).

So what can topology tell us about cellular automata? One of the first thing that we can look at is what structures can we represent with real objects? Which cellular automata can be physically put into 2D space, or 3D space?

Pacman’s game

The world of pacman is a world where going out the left side brings us back to the right side, and going out on the top brings us back at the bottom. We could represent this with a graph by connecting the top and bottom vertices, and the left and right vertices, then connect the others in the usual fashion.

Using the game of life glider we can watch this wrap around behaviour:

Torus Glider

Can we represent this in a real physical space? This is a well explored topic in topology, and the answer is yes. Imagine taking a piece of paper, we want to join the left and right sides, and the top and bottom. First we wrap the piece of paper into a cylinder to join the left and right sides, then we can twist the piece of paper around to join the top and the bottom; What we’re left with is a doughnut (a torus).

Torus

This means we can embed our pacman world game of life simulation into the real world. You can see this in action here or here.