Lab Report: The Game of Life

Introduction:

The rule of “The Game of Life” in two dimension is defined on an infinite plane divided into a number of adjacent square, with each one surrounded by eight. Each square is considered as a “cell” with two attributes: Alive & dead, with the rules of altering between the to attributes shown below:

       If cell == alive {cell = dead if surrounded by n < 2 or n > 3 cells}; (living condition)

       If cell == dead {cell = alive if surrounded by n == 3 cells}; (reviving condition)

One “Generation” is defined as applying the two rules above simultaneously once. 

This report studies different algorithms which implement it, and how the rules behave on different two dimensional spaces through the algorithm.

Algorithm Analyzation:

1.  In two dimensional flat plane, the algorithm realizations is coded in  C#, which core part includes defining a three dimensional array to express a 100 x 100 2D plane and the correspondent cell value: 

private int[][] cellValues = new int[100][];

for (int r = 0; r < 99; r ++) {cellValue[r] = new int[100];}

using the “surrounding function” to tell how many other cells surround one, for example:

private int surrounding(int c, int v)
{if cellValue[r][c - 1] > 0 {count ++};}

Then it pass the count ‘g’ as the cell value to the correspondent cell value:

cellValue[r][c] = g;

To make one generation, the algorithm firstly calculate the cell value of every cell on the plane, then if a cell’s value is above 0, it will be activated, else it will be deactivated in the GUI codes.  

2. Another algorithm realized it in two dimensional toroidal surface via Python.

 The algorithm uses similar idea to tell whether a cell is alive or dead after one generation, that is, first calculate the cell value of every cell, then update the attribute of each. However, to express a toroidal surface in a regular two dimensional list: 

total = int((grid[i, (j - 1) % N] + grid[i, (j + 1) % N]
+ grid[( i - 1 ) % N,  j]+ grid[(i + 1) % N,  j]
 + grid[(i - 1) % N, (j - 1) % N] + grid[(i - 1) % N, (j + 1) % N]
+ grid[(i + 1) % N, (j - 1 ) % N] + grid[(i + 1) % N, (j + 1) % N])/255)

What’s special here is the mod operator (%), when a counting index goes out of the plain, it “drags” the index back. For example, in a 10 x 10 plane, the point (9, 9) connects to: (8, 9), (9, 8), (8, 8), (8, 0), (9, 0), (0, 0), (0, 9), (0, 8). Thus, if being observed on a 2D flat plane, a pattern will appear from another side of the plane if it reaches one boundary.

Rule Analyzation:

The report specially studies the reviving condition: why the conditional number is n = 3 but not others, using the Python code on toroidal surface.

The Python code provides several stable pattern on n = 3. Among them, A Glider is a small pattern moves diagonally, and a Gosper is a larger pattern that keeps firing Gilders. As they can represent the behavior of motion and reproduction, the report uses them as two study objects.

By experiment it shows when n = 4 or above the glider stays put without any motion and the Gosper ceased to a pairs of a-group-of-four blocks, which is a classic static pattern in Game of life. When n = 2, both patterns quickly expand and fill the whole surface with random moving patterns. Other experiments reveal similar results.

The experiment shows that it is reasonable to set the reviving condition to n = 3, as when n < 3 it is too easy for a cell to revive and the surface will be filled with chaotic moving patterns. and when n > 4 it is relatively difficult for cells to revive, thus the active patterns in n = 3 condition will be likely to stay stationary. n = 3 may be the rule for existing the most number of stable patterns.

However, further experiment find in n = 2, a flat plane is slower than a toroidal surface to become chaotic. Thus, it is likely that the reviving condition n is connected to the type of the space in order to create a rule with most stable patterns. For example, in 3D，4D Euclid space, or Rehman space the best reviving condition may not be 3. A correspondent function: best reviving condition = f(space type) may exist.

A study on 3D Euclid situation done by Carter Bays shows there are more cases in Game of Life on different spaces for further exploration.

Sources: 

MATHEMATICAL GAMES The fantastic combinations of John Conway’s new solitaire game “life”, by Martin Gardner, Scientific American 223 (October 1970): 120-123. https://web.stanford.edu/class/sts145/Library/life.pdf

Candidates for the Game of Life in Three Dimensions’, Complex Systems 1 (1987) 373-400, Carter Bays, Department of Computer Science, University of South Carolina, Columbia, SC 29208, USA, https://pdfs.semanticscholar.org/c865/e0d19f53ba646e076d6e542e1002c92fd3ad.pdf

C# code.
https://code.msdn.microsoft.com/windowsdesktop/Conways-Game-of-Life-75508f8f

Python code.  https://github.com/electronut/pp/blob/master/conway/conway.py