Graph of Game of Life States

Conway's Game of Life is a mathematical toy which describes a transition of a grid-world over time. As one can read on the Wikipedia article, there are certain structures which are either stable or form short cycles. I wanted to see whether these structures could be found in a systematic way.

So I have just tried a brute-force way to generate states, and see how they evolve. This builds a graph, and that graph can be decomposed into subgraphs. The subgraph that is connected to the empty world is the not very interesting. So I show some of the ones which are not connected to the empty world.

The simplest subgraph is one with only a single node, which is stable:

The next one is the blinker:

The glider forms a cycle of four steps, and looks pretty neat in this graph way:

The loaf can be reached through various states, they all end up in a 1-cycle, a stable state:

Another stable one can be reached via four branches:

A really interesting graph is this one, it ends in a state with four blinkers:

Another stable state:

Some states have really long periods. I only computed 20 steps for each, but some of them don't terminate within that. These are potentially endless chains of nodes that never terminate.

Another stable state:

This symmetric state can be reached through multiple seeds that I have tried:

The solid block seems to be another interesting fix point where a lot of states converges.

And then there is another interesting stable state, which can be reached from different seeds in different time:

Scaling up

I have only tried seeds with 3×3 elements. These are 9 elements, such that in total I have to try 2⁹ = 512 seed states. Each of them is potentially evolved for 20 steps, so the whole graph might contain 10,240 nodes. That works pretty well.

I have tried to do all 4×4 seeds, those are 65,536 seeds. Computing these is fine, but then decomposing the graph seems to take quite some time. I haven't let the laptop finish that computation.

There may be ways to do this in a more intelligent fashion, I might persue that at some point.