Articles‎ > ‎

Conway's Game Of Life

posted 2 Jul 2010, 11:01 by Nilangshu Bidyanta   [ updated 22 Feb 2011, 05:28 ]


In this article I'll show you how to get started with the "Game Of Life" and guide you through the construction of the "Golly Ticker" and how to modify it to display custom text.

The Game Of Life (not the board game by Hasbro / Funskool!) is a mathematical 'zero-player game' - the player can't intervene after the game has started. Technically, it's a type of cellular automaton, the brainchild of British mathematician John Conway, which became very popular in the 1970s after an article about this game was published by Martin Gardner in the Scientific American. The game originated as a solution of a problem presented by John von Neumann. The task was to create a hypothetical machine that could replicate itself. The Game Of Life or simply, Life, is a mathematical model of such a machine. It was named "Game Of Life" since the rules of the game are similar to life of an organism albeit over-simplified.

The game is also interesting from a theoretical point of view because it can be used to simulate a Universal Turing Machine. What is a Turing Machine? The Turing Machine is an abstract computational device which was first described by Alan Turing to investigate the limitations of what can be computed. Such a machine can compute anything that can be put in the form of an algorithm, with two assumptions - the amount of memory available is infinite and time taken for completion of the task is unimportant. A Universal Turing Machine is one which can simulate an arbitrary Turing Machine with an arbitrary input. Because of the above assumptions, the machine has no practical use.

OK. Getting into the nitty-gritty of Life, it is played on a theoretically infinite, 2 dimensional square grid where each cell of the grid can take one of two states: 'Alive' or 'Dead'. The game requires the player to put in an initial pattern of living and dead cells and a program, following some rule, computes the next generation of the pattern. The standard 'rule' of Life is:

  • Any live cell with less than two live cells in the surrounding eight cells will die (analogous to dying out of loneliness)
  • Any live cell with more than three live cells in the surrounding eight cells will also die (analogous to dying due to overcrowding)
  • Any live cell with two or three live cells in the surrounding eight cells will continue to live to the next generation (sustained existence)
  • Any dead cell with exactly three live cells in the surrounding eight cells will come alive (analogous to reproduction)

A shorthand notation of the above is B3/S23 - 'B' for "born" and 3 for the number of alive cells needed in the eight surrounding cells to trigger a reproduction. 'S' stands for "stay alive" and the digits after it are for the number of living cells which can sustain the existence of the cell under consideration. The B3/S23 rule was proposed by John Conway himself keeping certain criteria in mind. There are many variants to the above rule, each producing a unique outcome for the same input patterns.

A very good program for exploring cellular automata including Life is Golly. Operating it is as simple as using a program like MS Paint. The default pen tool is used to mark dead cells alive and vice-versa. You can also change the speed at which each generation is computed. The accompanying "Help" is extensive and Golly also includes the Hashlife algorithm which can compute many generations of a given pattern in a small amount of time. But we won't be needing that for this article.

Screenshot of the Golly interface. Click to enlarge.

After you've gone ahead and tried Golly with random patterns or the ones found in the left panel, you would have noticed that some of the patterns occur frequently. The patterns which remain still for all subsequent generations are called 'Still Lives'. Examples include the Block and the Beehive. Some patterns move across the field at different speeds and directions and are called spaceships. The spaceships change form while moving wherein each form can be described as a 'phase' of the spaceship. The smallest spaceship known is the Glider. Other patterns repeat after certain generations while maintaining their positions. These are called oscillators. The Blinker shown below is a simple oscillator. Try out these pattern in Golly to get a feel of what they exactly do!


Blinker Block Beehive Glider Light Weight Space Ship
Blinker                      Block                       Beehive                      Glider                      LWSS


The more complex patterns must be constructed from a basic set of patterns - like the Gosper Glider Gun which is made up of two 'Queen Bee shuttles' between two stabilizing ends, realized here by two 'blocks'. Of course I'll be describing the function of each pattern used in the "Golly Ticker" but for other patterns and Life terminology, a good place to start  would be the Life Lexicon compiled by Stephen A. Silver. It's also included in the Golly Help file. A modified version with images in place of ASCII Art can be found here. More info about Life and newly discovered objects can be found at the Life Wiki page.

Gosper Glider Gun - The first infinitely growing Life object


Gosper Glider gun in action

Gosper Glider Gun in action

Let's begin with reviewing what the 'Golly Ticker' does. Load it from under 'Guns' in the left panel and play it. You should see the word "Golly" (with a stylized 'o') move across the screen and then disappear at the left. This continues indefinitely.

Golly Ticker in action. Click to enlarge.

First, let's start with the Life objects that make up the text "Golly". The text is made up of what is known as the 'Light Weight Space Ship' or LWSS for short. These Life objects continuously move in one of the four directions - up, down, left or right but never diagonally. Their speed is often expressed as a fraction of 'c' or the speed of light. The speed of light taken in the context of Life refers to advancement of one cell per generation and this is the fastest a Life object can move.

The Glider (shown above) can move only diagonally at c/4 whereas the LWSS can move orthogonally at c/2. You can easily verify this using Golly, running slow enough to clearly see each generation.


A close up of "G" made up of LWSS


Each letter is 9 LWSSs in height except for the "O" which is 11 LWSSs in height. If you take a close look at the characters, not all LWSSs are in the same phase. Some seem to "point" downwards and the rest upwards. Take note of their orientation, we'll need it for our next discussion.

At the left end, there are structures called "Eaters" or "Fishhook" initially flanked one either side by structures known as "Kok's Galaxy".

    
Eater in two configurations

Eaters are 'Still Lives' which can eat away many objects without sustaining permanent damage. The job of the eater here is to assimilate the LWSSs coming in from the right. Since we have two distinct phases of LWSSs, the eater must be oriented properly to perform its job, otherwise the LWSSs permanently destroy the eater. The same eater can also be used to absorb gliders, Medium Weight Space Ships (MWSS), Heavy Weight Space Ships (HWSS) and some 'Still Lives' as well.

Some other still lives can also act as eaters, although they are not called so in the strict sense. For example, a single 'Loaf' or a single 'Ship' eat away two gliders and then disappear completely.

    
Loaf                           Ship

Temporary Glider eater using 'Loaves'




Temporary Glider eater using 'Ships'



Kok's Galaxy belongs to a class of Life objects known as oscillators. These are patterns which repeat after a certain number of generations while retaining their position and orientation and having a finite number of cells. That's why spaceships don't qualify as oscillators in the Game Of Life although they are defined to have periods. The minimum number of generations after which an oscillator repeats is known as its period. If you've taken a closer look, you'd see that the "o" in "Golly" is actually one of the generations of Kok's Galaxy. Same goes for the two 'L's which are from another generation. Functionally, the generations of Kok's Galaxy flanking the eaters don't serve any purpose since deleting them doesn't affect the ticker at all.

The text is generated by the technique used in Alan Hensel's Decimal Counter. It starts by first creating the rows in the middle - the sixth and seventh rows. Rows 1 to 6 are created by the six structures at the right-top which are called "memory loops". The other five are created by the five memory loops at the right bottom. The memory loops hold a specific pattern made of gliders that keep looping in the structure. At one end, they are duplicated where one glider is fed to the "Converter" and the other back into the memory loop.


Close-up of the memory loop technology used in the Golly Ticker
Click to enlarge.

The structure inside the red dotted border is the memory loop. The gliders follow the yellow arrows with the help of 'Reflectors' placed at either ends. Additionally at the bottom end there is a glider duplicator and a 'Converter' which converts the glider to a LWSS. The glider duplicator produces a glider that moves parallel to the original. While the duplicated glider is sent back into the loop, the original glider is sent to the converter (moves along the first green arrow). Following conversion, the LWSS takes the path of the second green arrow. All of the memory loops (numbered 1 to 11) work in the same way and are slightly displaced in height to produce LWSS in separate rows. Furthermore, temporary glider eaters made using loaves are used at the bottom of some memory loops (like loop #2) to time the rows correctly, otherwise the rows of LWSSs produced will be out of alignment. Zoom in on the lower end of the memory loop and run the ticker at a slower speed to see exactly how the gliders move.

To place the gliders inside the memory loops, start from the desired output character and row-by-row replace the LWSSs with gliders. Next, place the gliders into separate memory loops - one row per loop taking care of appropriate spacing between gliders. As you might have realized by now, the length of the text to be displayed (memory capacity of the loops) depends on "height" of the memory loop (i.e. length along the longest yellow arrow in the figure above), whereas the number of memory loops used, controls the number of LWSSs needed to cover the height of the text.

Click to enlarge

Of course placing the gliders in the appropriate positions and phases in the memory loop involves a lot of trial and error especially if you are new to the 'Game of Life'. Life objects need to be placed at exactly the right position -- the distance between an incoming glider in a particular phase and a reflector needs to be just right so that the reflector is not destroyed -- proper timing is very important. To help get you started, I'm providing a "Ticker Template" with extended memory. You simply need to delete the appropriate gliders (and temporary eaters) to get the desired text. Of course you could experiment and make your own version of the ticker without using the template! And don't forget about the temporary glider eaters when you can't seem to get your text aligned!!

The green band the in two images above shows the correspondence between
glider positions and LWSS positions in memory loop 2 and row 2 respectively.


Here's my name being displayed on the ticker, based on the ticker template I made:

Custom Ticker


Click here to download the customized ticker in the video.
Click here to download the ticker template.




Comments