So this is kind of funny. For years, I’ve heard references to an algorithm for the Game of Life, and I always pictured this:
I’ve never actually played this game, so I didn’t think about it too hard and figured it must be some weird case where an algorithm could solve the board game. Then I recently found out that it’s actually Conway’s Game of Life, an iterative mathematical algorithm devised in 1970.
Straight from Wikipedia, the rules are:
The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead (or populated and unpopulated, respectively). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:
- Any live cell with fewer than two live neighbours dies, as if by underpopulation.
- Any live cell with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies, as if by overpopulation.
- 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:
- Any live cell with two or three live neighbours survives.
- Any dead cell with three live neighbours becomes a live cell.
- All other live cells die in the next generation. Similarly, all other dead cells stay dead.
The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed, live or dead; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.
This sounded like a fun algorithm to write myself. First I decided to tackle a solution that uses pure Python with no third-party libraries.
Creating a Game Board
We’ll need a game board: a list of lists that represent a grid.
import random SIZE = 17 grid = [[random.choice([0, 1]) for _ in range(SIZE)] for _ in range(SIZE)]
This nested list comprehension gives us a random grid of 0s and 1s in the following structure:
[[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1], [0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0], [0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1], [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1], [1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0], [1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1], [1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1], [0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0], [1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0], [0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0], [0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1], [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1], [1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1], [0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1], [0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1]]
Checking Neighbor Values
Next we need to be able to check the alive status of each neighbor cell. We’ll write a function that will take the grid, plus row and col coordinates.
Complicating this is that we’re going to have the neighbors include cells that wrap around on the other side of the grid, creating an infinite game board. For example, if we take the item at coordinates (0, 0), what is its upper left neighbor? Since we need to wrap both the row and the column in this case, we are looking at coordinates (16, 16).
We can use Python ternary statements to easily roll around the grid in both directions:
# get upper right rown = row - 1 if row - 1 is not -1 else SIZE - 1 coln = col + 1 if col + 1 is not SIZE else 0
These statements check that we haven’t exceeded the boundaries by moving left to -1 or right to the SIZE of the grid, and if we have, we instead wrap to the other side of the grid.
The full function I’ve written here could probably be optimized into a loop, but I’m opting for “explicit is better than implicit” by taking each neighbor as a separate case.
Also note that once we have 4 or more live neighbor cells, the subsequent cells don’t matter under the rules (as the cell will die from overpopulation), so at the appropriate place in the function, we’re checking the count. There is also one check for 0 on the penultimate neighbor as 0 and 1 both result in the same death from underpopulation.
Here is the full function:
def get_neighbor_count(grid: List[List[int]], row: int, col: int) -> int:
"""For each of 8 neighbors for cell, check alive status."""
alive = 0
# get upper left
rown = row - 1 if row - 1 is not -1 else SIZE - 1
coln = col - 1 if col - 1 is not -1 else SIZE - 1
if grid[rown][coln]:
alive += 1
# get above
rown = row - 1 if row - 1 is not -1 else SIZE - 1
if grid[rown][col]:
alive += 1
# get upper right
rown = row - 1 if row - 1 is not -1 else SIZE - 1
coln = col + 1 if col + 1 is not SIZE else 0
if grid[rown][coln]:
alive += 1
# get left
coln = col - 1 if col - 1 is not -1 else SIZE - 1
if grid[row][coln]:
alive += 1
if alive > 3:
return alive
# get right
coln = col + 1 if col + 1 is not SIZE else 0
if grid[row][coln]:
alive += 1
if alive > 3:
return alive
# get lower left
rown = row + 1 if row + 1 is not SIZE else 0
coln = col - 1 if col - 1 is not -1 else SIZE - 1
if grid[rown][coln]:
alive += 1
if alive > 3:
return alive
# get below
rown = row + 1 if row + 1 is not SIZE else 0
if grid[rown][col]:
alive += 1
if alive > 3 or alive is 0:
return alive
# get bottom right
rown = row + 1 if row + 1 is not SIZE else 0
coln = col + 1 if col + 1 is not SIZE else 0
if grid[rown][coln]:
alive += 1
return alive
When we test our function with print(get_neighbor_count(grid, 0, 0)) we get 3, which is correct by my count: there are live neighbors to the bottom right, left (wrapped), and top left (wrapped).
Checking the Rules
Just getting the count of live neighbors isn’t enough. We need to apply the rules of the game to a given cell after getting its neighbor count. The function I’ve written to do so looks like this:
def check_rules(grid: List[List[int]], row: int, col: int) -> bool:
"""Checks rules and returns True if cell should be alive next gen"""
live_neighbors = get_neighbor_count(grid, row, col)
if live_neighbors is 3:
return True
elif grid[row][col] and live_neighbors is 2:
return True
else:
return False
After calling our previous function to get the cell’s neighbor count, we’re checking for three cases:
- If a cell has exactly
3living neighbors, the cell will be populated in the next generation regardless of its current status. - If a cell is alive (the truthy
cell_valueof1will be evaluated asTrue) and has2living neighbors, the cell will live on in the next generation. (Note that we are only checking for2neighbors since3neighbors was caught in the previous case. It’s a minor optimization to not check the same thing twice.) - In all other cases, the cell will die or remain dead in the next generation.
The function will return True if the cell will be alive in the next generation and False if not. We can again test against our test grid with print(check_rules(grid, 0, 0)) and get the expected value of True.
Two Other Helper Functions
We’re going to need two more functions to use in our game loop to be able to display this data in a readable way for the console.
First, we’ll have a function that will print the current grid with decent spacing:
def print_grid(grid):
"""Prints grid in a visually pleasing manner for the console"""
for row in grid:
for val in row:
print(val, end=" ")
print()
print()
This will print the grid looking like this:
0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 1 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 1 1 0 1
Second, rather than have the console print a continuous stream of grids, let’s give the appearance of updating the existing grid by clearing the console after each generation. We can do that on any platform with this function:
import os
def clear_screen():
"""Clear console so output is one continuous grid with changes"""
if os.name == 'nt':
os.system('cls') # for windows
else:
os.system('clear') # for mac and linux(here, os.name is 'posix')
Writing the Program Loop
This program will need to run in a continuous loop wherein the grid is evaluated and simultaneously updated with each subsequent generation. To simulate simultaneous updating, we’ll need to make a copy of the grid in each loop to make changes to while still looping through the original grid.
The main() function will look like this:
def main():
# Make a game grid
grid = [[random.choice([0, 1]) for _ in range(SIZE)] for _ in range(SIZE)]
# Start the game
gen_count = 1
while True:
clear_screen()
print(f"Generation {gen_count}:")
print_grid(grid)
sleep(.25)
# Working grid to track next generation for simultaneous changes
next_grid = grid.copy()
# Iterate over current grid, make changes to working grid
for row in range(SIZE):
for col in range(SIZE):
alive_next_time = check_rules(grid, row, col)
if alive_next_time:
next_grid[row][col] = 1
else:
next_grid[row][col] = 0
# Reset printed grid to working grid
grid = next_grid.copy()
gen_count += 1
The Full Code and Example Output
"""
Conway's Game of Life implemented with Python standard library
Author: Danny Brown
"""
import random
import os
from typing import List
from time import sleep
SIZE = 17
def clear_screen():
"""Clear console so output is one continuous grid with changes"""
if os.name == 'nt':
_ = os.system('cls') # for windows
else:
_ = os.system('clear') # for mac and linux(here, os.name is 'posix')
def print_grid(grid):
"""Prints grid in a visually pleasing manner for the console"""
for row in grid:
for val in row:
print(val, end=" ")
print()
print()
def get_neighbor_count(grid: List[List[int]], row: int, col: int) -> int:
"""For each of 8 neighbors for cell, check alive status."""
alive = 0
# get upper left
rown = row - 1 if row - 1 is not -1 else SIZE - 1
coln = col - 1 if col - 1 is not -1 else SIZE - 1
if grid[rown][coln]:
alive += 1
# get above
rown = row - 1 if row - 1 is not -1 else SIZE - 1
if grid[rown][col]:
alive += 1
# get upper right
rown = row - 1 if row - 1 is not -1 else SIZE - 1
coln = col + 1 if col + 1 is not SIZE else 0
if grid[rown][coln]:
alive += 1
# get left
coln = col - 1 if col - 1 is not -1 else SIZE - 1
if grid[row][coln]:
alive += 1
if alive > 3:
return alive
# get right
coln = col + 1 if col + 1 is not SIZE else 0
if grid[row][coln]:
alive += 1
if alive > 3:
return alive
# get lower left
rown = row + 1 if row + 1 is not SIZE else 0
coln = col - 1 if col - 1 is not -1 else SIZE - 1
if grid[rown][coln]:
alive += 1
if alive > 3:
return alive
# get below
rown = row + 1 if row + 1 is not SIZE else 0
if grid[rown][col]:
alive += 1
if alive > 3 or alive is 0:
return alive
# get bottom right
rown = row + 1 if row + 1 is not SIZE else 0
coln = col + 1 if col + 1 is not SIZE else 0
if grid[rown][coln]:
alive += 1
return alive
def check_rules(grid: List[List[int]], row: int, col: int) -> bool:
"""Checks rules and returns True if cell should be alive next gen"""
live_neighbors = get_neighbor_count(grid, row, col)
if live_neighbors is 3:
return True
elif grid[row][col] and live_neighbors is 2:
return True
else:
return False
def main():
# Make a game grid
grid = [[random.choice([0, 1]) for _ in range(SIZE)] for _ in range(SIZE)]
# Start the game
gen_count = 1
while True:
clear_screen()
print(f"Generation {gen_count}:")
print_grid(grid)
sleep(.25)
# Working grid to track next generation for simultaneous changes
next_grid = grid.copy()
# Iterate over current grid, make changes to working grid
for row in range(SIZE):
for col in range(SIZE):
alive_next_time = check_rules(grid, row, col)
if alive_next_time:
next_grid[row][col] = 1
else:
next_grid[row][col] = 0
# Reset printed grid to working grid
grid = next_grid.copy()
gen_count += 1
if __name__ == "__main__":
main()
The console output of running this application looks something like this:
Next Steps
This isn’t particularly fun to look at like the visualizations on Wikipedia. The next steps will be to create some sort of GUI to showcase the algorithm in a much more visually appealing, digestible way.
I’ve done this already using Pygame, but I’ll have to put off writing about that portion for now. Hopefully I’ll have time to write about my experience using Pygame for the first time soon!