The Game of Life with Non-Local Neighbors

Oguz Yetkin and Clint Sprott
Department of Physics, University of Wisconsin, Madison, WI 53706, USA
April 23, 1998

Introduction and Background

Since its invention by Conway in the 1970s, the Game of Life has fascinated most everyone who has come across it. The game is a very simple simulation of life. The "world" is a rectangular N x M grid of live and dead cells. The fate of each cell in the next generation is determined by its eight nearest neighbors by the following rules:

If a dead cell has exactly 3 neighbors, it is "born".
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 settles down into a stable pattern (or periodic behavior) after at most several thousand iterations, depending on the size of the grid. 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 remain the same with respect to the eight neighbors, which can now be anywhere in the grid. Such a model might mimic an organism that interacts mostly with other organisms not in its physical vicinity, such as an Internet community. You can download and examine the code for this new implementation:

C++ code Optimized for Windows NT and the executable (You will have to run this in a 100x80 console window with 8x8 fonts. The Microsoft compiler does not let you play with the VGA card.)
C++ code Optimized for UNIX (This 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

More cells are alive after a large number of generations in the non-local neighbor version than in the version where the neighbors are forced to be local (37% vs. 2.5 %).
Small arrays usually end up having no living cells after 100 or 200 generations with the new implementation.
Making it legal for cells to have themselves as neighbors does not appear to have an important effect.

Here's a sample of the output for a case with 3600 grid points after 5404 generations:

(More screen shots and code are available online.)

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:

D = number of dead cells

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

P_n = probability of a site having exactly n living neighbors

N_b = number born in each generation (= DP₃)

N_d = number dying in each generation (= A(P₀ + P₁ + P₄ + P₅ + P₆ + P₇ + P₈))

Since the probabilities P₀ through P₈ must sum to 1, the death rate can be simplified to

₂

₃

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

₀

⁸

₁

⁷

₂

⁶

₃

⁵

₄

⁴

₅

⁵

₆

⁶

₇

⁷

₈

⁸

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

In equilibrium, the birth rate N_b must equal the death rate N_d, so that

₃

₂

₃

We can now can solve for P

₂

₃

₂

Substituting the expressions for P₃ and P₂ leads to the following 8th order polynomial equation:

⁸

⁷

⁶

⁵

⁴

This equation can be easily solved by the Newton-Raphson method, which gives the following four real roots for P:

There are presumably also two pairs of complex conjugate roots which are unphysical. The first (negative) root above is unphysical as is the third root that gives a probability that exceeds 1. Of the remaining roots, the one at 0.1924... is unstable, and the one at 0.3701... is stable and is in excellent agreement with numerical results for the Game of Life with (random) non-local neighbors.

Suggestions for Further Study

This study could be extended in a number of ways. As with the regular Game of Life, you could alter the rules for the number of live sites required for birth and death. You could look at neighborhoods smaller or larger than 8. You could examine a hybrid scheme in which near neighbors are replaced by random far neighbors with a probability p. This modification would more realistically represent many real-world processes such as social interactions, the spread of diseases, the electrical power grid, and the operation of the brain.

Back to Sprott's Technical Notes