Introduction and Background

Ever since its invention by Conway in the 1970s, the Game of Life has fascinated pretty much anyone who has come across it. The game is a very simple simulation of life. The "world" is a rectangular N x M grid, and the fate of each cell in the grid is determined by the following rules:

if a dead cell has exactly 3 neighbors, and is it is "born" (and is now alive).

if a living cell has < 3 neighbors, it dies of loneliness.

if a living cell has 3 or 4 neighbors, it stays alive

if a living cell has > 4 neighbors, it dies of overcrowding

As the generations are advanced, these simple rules lead to relatively complex behavior. The world typically settle down into a stable pattern (or periodic behavior) after at most several thousand iterations. Here's the code for a straightforward implementation in C++. If you'd like to play the game, here's a much better windows implementation by someone else...

The Experiment

The game of life was modified so that neighbors of a cell could be assigned randomly. The rules governing birth and death remained the same with respect to neighbors. You can download & look at the code of the new implementation:

C++ code Optimized for Windows NT ...the executable (you will have to run this in a 100x80 console window with 8x8 fonts. Sorry, the microsoft compiler does not let you play with the VGA card...)

C++ code Optimized for UNIX (will compile under anything--but graphics output is just ASCII characters)

In order to verify that the new implementation was correct, a test-case was run forcing the neighbors to be local. This implementation does indeed behave like the game of life.

C++ code with forced local neighbors for UNIX (and other character based displays)

The NT executable (with forced local neighbors)

Observations

1) More cells are alive after a large number of iterations in the non-local neighbor version than the version in which neighbors were forced to be local (35% vs. 2.5 %).

2) Small array sizes end up having no living cells after 100 or 200 iterations with the new implementation

3) Making it legal for cells to have themselves as neighbors does not appear to have an important effect.

(more screen shots and code are online for the self-destructively curious)

Discussion

The game of life with non-local neighbors eventually settles down to a probability density of around 37% (i.e., 37% of the cells are alive after a large number of iterations). This figure can be statistically justified as follows:

Let

A= number of Living Cells

D= number of Dead Cells

P=probability that a site is alive (A/(A+D))

P=2/8=25% is a solution, but this is unstable.

Let Pn = probability of having n living neighbors

Nb=number born = D*P3

Nd=number dying=A(P0+P1+P4+P5+P6+P7+P8)

The probabilities of having n living neighbors can be calculated as follows:

(coefficients are 8 "choose" n, or "8 nCr n" for avid scientific calculator users)

P0=(1-P)^8

P1=8(1-P)^7 * P

P2=28(1-P)^5 * P^2

P3=56(1-P)^5 * P^3

P4=70(1-P)^4 * P^4

P5=56(1-P)^3 * P^5

P6=28(1-P)^2 * P^6

P7=8(1-P)^1 * P^7

P8=P^8

We know that

n=0 [SIGMA] 8 Pn=1 (will fix notation)

therefore

Nd-A(1-P2-P3)

In equilibrium Nb=Nd

so

DP3=A(1-P2-P3)

so now we can solve for P

P=A((A+D))=A/(A+A(1-P2-P3)/P3)) = 1/ (( 1 + (1 - P2 - P3) /P3) = P3/ (P3 + 1 - P2 - P3)

= P3 / (1 -P2) =0.3702

37% agrees with the value that is obtained when the simulation is run for a long time.