Hunting the Snark

Katie Steckles

A while ago I wrote about zero-player games, including the famous Game of Life created by mathematician John Conway. If you are confused because you thought the Game of Life was a board game where you put a tiny peg character in a car and drive it around a board, here is a quick reminder of how the mathematical Game of Life works.

Imagine an infinite grid of squares – initially all empty (white). Some of these squares could be coloured in black, which we would call ‘alive’ cells, and the white cells can be thought of as ‘dead’. The way the game works is that at each step in time, we consider all the cells in their current state, and based on some rules we decide whether that cell will be alive, or dead, in the next time step.

The cells in the Game of Life have preferences fairly similar to real living organisms – they do not like to be lonely, so any cell which is only next to one other living cell, or no living cells, will die of loneliness. (‘Next to’ in this case includes horizontally, vertically or diagonally adjacent). They also prefer not to be overcrowded, so any cell which has four or more living neighbours will die out in the next iteration. And anything with exactly two or three neighbours stays alive to fight another day, or comes alive if it was not already.

Why two and three?

Obviously, we could have picked any set of rules here – a slightly different definition of ‘neighbour’, or different thresholds for loneliness and overcrowding – but if your settings are not right, you might find it is very difficult to keep anything alive and that things all die out quickly, or that your board gets infested with a growing mass of black cells you cannot stop.

But with these particular rules, there is just enough balance for it to be interesting – some configurations die out, others stay alive forever (some examples above), and some behave in fun ways. For example, it is possible to make a glider, which iterates through a series of steps to create a version of itself one cell across from where it was before. Watching this loop repeat, the shape ‘glides’ across the grid and will keep going forever unless it is interrupted.

Mathematicians seek out interesting structures that you can build in this universe of rules. One configuration of interest is the idea of an oscillator – something which loops through a set of states and returns to its exact original configuration. A simple example might be a ‘blinker’ – something which flips between two possible states, the simplest of which is a straight line of three cells. This will oscillate between a vertical line and horizontal line, unless disturbed by any other living cells nearby.

It is also possible to construct oscillators of other periods – ones which take three, four and five steps to return to their original state are seen below.

Left-right:Caterer, Mazing and the Pseudo-Barberpole

Zooologists of Life

This obviously leads to a further question: Which periods of oscillator can be created in this game? The people who study this question are probably aware that such discoveries are not going to shatter the foundations of mathematics, or necessarily lead to much else beyond the satisfaction of finding the answer – but whole websites exist of enthusiasts seeking out and excitedly studying and cataloguing examples of life they have found, like Charles Darwin on a voyage of discovery.

The story of periodic oscillators has an interesting history: Oscillators of small periods (up to about 15) were found within a few years of the invention of the game in 1970, as well as some interesting examples of higher periods – the twin bees shuttle, a period 46 oscillator, was found by Life expert Bill Gosper in 1971.

But the rest of the list took a bit longer to fill in. People continued to discover new oscillators over the years, but ticking off the list one at a time was unsatisfying. Surely we can find something that knocks out a bunch of cases in one go, like mathematical induction? Well, yes, we can. The existence of gliders in the game (structures which move in a straight line) means we can build more complex structures using a glider, and tweak them to get different periods.

A reflector is a structure in Life which is stable, but when a glider approaches it from the right direction, it will absorb it and create a new glider going off in a different direction. The first such structure was discovered by Paul Callahan in 1996, and over the next couple of decades many people discovered others, including ones which took fewer and fewer steps to complete the reflection, and using fewer initial live cells. The smallest known reflector is called the Snark, and was discovered in 2013 by Mike Playle – it reflects a glider through 90 degrees, and uses 52 cells (in a box of 23×17 cells).

This kind of structure can be used to build oscillators: Imagine pointing four of these at each other, so they pass a glider around between them. By tweaking the distance between the reflectors, and the types of reflectors used, we can build oscillators of any large period – and in fact this discovery meant that it is possible to construct an oscillator of any period greater than 59. The discovery of the Snark made this even smaller, showing that a non-trivial oscillator of any period 43 or above can be constructed.

Filling in the Gaps

This means, excitingly (for people who find this kind of thing sufficiently exciting), that we might be close to solving the problem in general, and finding an oscillator of every possible period. All we would need is to find oscillators of every period up to 43, and then we are covered. In July this year, one of the missing cases was fixed – a period 19 oscillator named Cribbage was found by Mitchell Riley.

This really put the pressure on Life-ologists to fill the one missing hole: The only period for which we did not know of a non-trivial oscillator was 41. But luckily, mathematicians do some of their best work under pressure and it took less than a week for Nico Brown to find one (casually posting it on the ConwayLife forums with the understated caption “Interesting loop”!) Consisting of 204 cells, the so-far-boringly named 204P41 oscillator (below – click for animation) completes a search which started over 50 years ago when this game was first invented.

This confirms that the Game of Life cellular automaton is omniperiodic – it has oscillators of every possible period. And yes, this research is not going to win any Nobel Prizes or spin off into whole new fields of research – but it has closed a gap in human knowledge and given us a new fun thing to play with – and is that not what maths is all about, really?

The post Hunting the Snark originally appeared on the HLFF SciLogs blog.