Thursday, July 23, 2020

A Minimal Python Implementation of Conway's Game of Life

I was incredulous that the simple rules of John Conway's Game of Life could result in such complex behavior, providing many analogies to Biology, Physics and Economics. So, I wanted to check it for myself. Unfortunately, most code available online has a lot of bells and whistles that obscure the simplicity of Conway's rules. So, here is a minimal implementation in Python. Being small, it is easy to verify that the program does implement Conway's rules faithfully, and introduces nothing else.

Download link: game-of-life-minimal.py
import numpy as np
from scipy import ndimage
import matplotlib.pyplot as plt

n  = 100   # grid size
t  = 1/24. # simulation update interval in seconds
pT = 0.1   # percentage of cells initialized to True/on

# randomly initialize a boolean grid, with more off cells than on
G = np.random.choice([True, False],n*n,p=[pT, 1-pT]).reshape(n, n)

# neighbor weights for convolution
W = np.array([[1,1,1],
              [1,0,1],
              [1,1,1]], dtype=np.uint8)

fig = plt.figure()

while(True):
    plt.matshow(G, fig.number)
    
    # find the Live Neighbors around each cell using convolution
    LN = ndimage.convolve(G.view(np.uint8), W, mode='wrap')
    
    # update grid based on Conway's rules using boolean operations
    # G = G*((LN==2)+(LN==3)) + np.invert(G)*(LN==3)
    G = G*(LN==2) + (LN==3)
    
    plt.pause(t)
    plt.cla()

A simple experiment that can immediately be carried out, is to see what happens when Conway's rules are ever so slightly tweaked. Say what happens if the 'overpopulation limit', 3 is changed to 4, or the 'reproduction number' is adjusted. Depending on your worldview/weltbild, the results will remind you either of 'Intelligent design' or the 'Anthropic principle'.

Verifying Correctness

As per Wikipedia, the rules of Conway's Game of Life are:

At each step in time, the following transitions occur:

  1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overpopulation.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

These rules, which compare the behavior of the automaton to real life, can be condensed into the following:

  1. Any live cell with two or three live neighbours survives.
  2. Any dead cell with three live neighbours becomes a live cell.
  3. All other live cells die in the next generation. Similarly, all other dead cells stay dead.

The above rules translated into pseudocode:

if C==1 AND ((LN==2) OR (LN==3)):
    C' := 1
else if C==0 AND (LN==3):
    C' := 1
else:
    C' := 0

are equivalent to the Boolean expression:

C' := C AND ((LN==2) OR (LN==3)) OR (NOT(C) AND (LN==3))

or equivalently (using * for AND and + for OR)

C' := C * ((LN==2) + (LN==3)) + (NOT(C) * (LN==3))

simplifying:

C' := C*(LN==2) + C*(LN==3) + NOT(C)*(LN==3) 
   := C*(LN==2) + (LN==3)*(C + NOT(C))
   := C*(LN==2) + (LN==3) ∵ (C OR NOT(C)) is always True.

The Yin-Yang (Tai Chi) Symbol is Inspired by the Full Moon

While looking at a reflection of the full moon today on a slightly distorted glass window, I suddenly realized that the Yin-Yang symbol is ...