Conway's Game of Life - Introduction | ||||||||||||||||||||||||||||||||||||||||||||||||||

The "Game of Life" is a game with no player created by John Conway in 1970. | ||||||||||||||||||||||||||||||||||||||||||||||||||

The game is essentially a set of rules that applies to certain number of "cells" in a grid. | ||||||||||||||||||||||||||||||||||||||||||||||||||

In a grid of any dimension, each square is called a "cell" | ||||||||||||||||||||||||||||||||||||||||||||||||||

The 8 squares surrounding it are called "neighbors" | ||||||||||||||||||||||||||||||||||||||||||||||||||

Each cell can have one state: dead or live | ||||||||||||||||||||||||||||||||||||||||||||||||||

a cell | Usually when a cell is live, it's also | |||||||||||||||||||||||||||||||||||||||||||||||||

its neighbors | said to be "populated" i.e inhabited. | |||||||||||||||||||||||||||||||||||||||||||||||||

a live cell | The total number of live cells is also | |||||||||||||||||||||||||||||||||||||||||||||||||

a dead cell | called population. | |||||||||||||||||||||||||||||||||||||||||||||||||

population = 8 | ||||||||||||||||||||||||||||||||||||||||||||||||||

Rules | ||||||||||||||||||||||||||||||||||||||||||||||||||

Death | A live cell with less than 2 live neighbors dies of loneliness | |||||||||||||||||||||||||||||||||||||||||||||||||

A live cell with more than 3 live neighbors dies of overpopulation | ||||||||||||||||||||||||||||||||||||||||||||||||||

Birth | A dead cell with exactly 3 live neighbors comes alive | |||||||||||||||||||||||||||||||||||||||||||||||||

None | A cell with 2 neighbors remains in the same state | |||||||||||||||||||||||||||||||||||||||||||||||||

Compute | I rendered this in MS Excel using a matrix for each grid, 0 representing a dead cell | |||||||||||||||||||||||||||||||||||||||||||||||||

and 1 representing a live cell. They were colored using conditional formatting. | ||||||||||||||||||||||||||||||||||||||||||||||||||

(every cell with value "1" is colored black) | ||||||||||||||||||||||||||||||||||||||||||||||||||

Steps | State of the cells is updated after each step. I call the initial grid step 1, so that | |||||||||||||||||||||||||||||||||||||||||||||||||

the final number of steps can't be smaller than 2, since 0 and 1 will be colored by | ||||||||||||||||||||||||||||||||||||||||||||||||||

the formatting rule. | ||||||||||||||||||||||||||||||||||||||||||||||||||

End | The game "ends" when the popularity of cells equal zero (death), or reaches a | |||||||||||||||||||||||||||||||||||||||||||||||||

configuration that stays the same every step (stable config), or reaches multiple | ||||||||||||||||||||||||||||||||||||||||||||||||||

configurations that cycle after every number of steps (oscillation). Oscillations that | ||||||||||||||||||||||||||||||||||||||||||||||||||

can "move" accross the plane are called spaceships. | ||||||||||||||||||||||||||||||||||||||||||||||||||

Apparently this definition only works with smaller grid (< 6x6) because with | ||||||||||||||||||||||||||||||||||||||||||||||||||

larger grids the "ending" could be a combination of deaths, stable configs, | ||||||||||||||||||||||||||||||||||||||||||||||||||

oscillations and spaceships. That is, if the game ever end at all. | ||||||||||||||||||||||||||||||||||||||||||||||||||

Example | Example of a game. Each game is displayed in a row like this. | |||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||||||||||||||||||||||||||

0 | 0 | 1 | 0 | ---> | 0 | 1 | 1 | 1 | ---> | 0 | 1 | 0 | 1 | ---> | 1 | 1 | 0 | 0 | ---> | 0 | 1 | 0 | 0 | ---> | 0 | 0 | 0 | 0 | number of steps: 5 | |||||||||||||||||||||

0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | end: death | ||||||||||||||||||||||||||

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||||||||||||||||||||||||||

step 1 | step 2 | step 3 | step 4 | step 5 (end) | one extra step | |||||||||||||||||||||||||||||||||||||||||||||

to classify the end | ||||||||||||||||||||||||||||||||||||||||||||||||||

The last extra step is not counted into number of steps, but it's to tell the computer each | ||||||||||||||||||||||||||||||||||||||||||||||||||

ending this game should be classified in. | ||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | |||||||||||||||||||||||||||||||||||

0 | 1 | 1 | 0 | ---> | 0 | 1 | 1 | 0 | ---> | 1 | 0 | 0 | 1 | ---> | 1 | 0 | 0 | 1 | number of steps: 3 | |||||||||||||||||||||||||||||||

0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | end: stable config | ||||||||||||||||||||||||||||||||||

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | |||||||||||||||||||||||||||||||||||

step 1 | step 2 | step 3 (end) | final extra step | |||||||||||||||||||||||||||||||||||||||||||||||

In this example, the final step tells that the game ended in a stable configuration. | ||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | |||||||||||||||||||||||||||||||

0 | 0 | 1 | 0 | ---> | 0 | 0 | 1 | 1 | ---> | 0 | 0 | 0 | 1 | ---> | 0 | 0 | 1 | 1 | ---> | 0 | 0 | 0 | 1 | number of steps: 4 | ||||||||||||||||||||||||||

1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | end: oscillation | ||||||||||||||||||||||||||||||

1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |||||||||||||||||||||||||||||||

step 1 | step 2 | step 3 | step 4 (end) | final extra step | ||||||||||||||||||||||||||||||||||||||||||||||

In this example, the final step tells that the game ended in an oscillation. | ||||||||||||||||||||||||||||||||||||||||||||||||||

Like meta stuff? Check
this out. |
||||||||||||||||||||||||||||||||||||||||||||||||||

Formula | Probably not the best ones, but this is how I do it. | |||||||||||||||||||||||||||||||||||||||||||||||||

Update cell state: | example cell B8, cell + neighbors = (A7:C9) | |||||||||||||||||||||||||||||||||||||||||||||||||

A7 | A8 | A9 | =IF(B8=0,IF(SUM(A7:C9)=3,1,0),IF(SUM(A7:C9)<5,IF(SUM(A7:C9)>2,1,0),0)) | |||||||||||||||||||||||||||||||||||||||||||||||

B7 | B8 | B9 | if cell is dead --> if there's 3 cells around --> live, otherwise dead. | |||||||||||||||||||||||||||||||||||||||||||||||

C7 | C8 | C9 | if cell is live --> if there's less than 4 cells around --> if there's more than 2 | |||||||||||||||||||||||||||||||||||||||||||||||

cells around --> live, otherwise dead. | ||||||||||||||||||||||||||||||||||||||||||||||||||

/ | A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | A9 | A10 | A11 | A12 | A13 | A14 | A15 | Calculate steps: | ||||||||||||||||||||||||||||||||||

A1 | 1 | 2 | 3 | =A$6 | ||||||||||||||||||||||||||||||||||||||||||||||

B1 | ||||||||||||||||||||||||||||||||||||||||||||||||||

C1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | Calculate end: | |||||||||||||||||||||||||||||||||||||

D1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | =IF(SUM(A11:F14)=0,"death",IF(AND(EXACT(A11:F14,A6:F9)),"stable config","oscillation")) | |||||||||||||||||||||||||||||||||||||

E1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | if final population = 0 ---> death, if not: | |||||||||||||||||||||||||||||||||||||

F1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | if the two last matrices equals each other exactly ---> stable config, otherwise oscillation. | |||||||||||||||||||||||||||||||||||||

Calculate stats: | (provided that the games starts at line 8) | |||||||||||||||||||||||||||||||||||||||||||||||||

deaths | =COUNTIF(8:1048576,"death") | |||||||||||||||||||||||||||||||||||||||||||||||||

oscillations | =COUNTIF(8:1048576,"oscillation") | |||||||||||||||||||||||||||||||||||||||||||||||||

stable configs | =COUNTIF(8:1048576,"stable config") | |||||||||||||||||||||||||||||||||||||||||||||||||

total number of steps | =SUMIF(8:1048576,">1") | |||||||||||||||||||||||||||||||||||||||||||||||||

total number of games | =COUNTIF(8:1048576,"steps:") | |||||||||||||||||||||||||||||||||||||||||||||||||

average number of steps | = total steps / total games | |||||||||||||||||||||||||||||||||||||||||||||||||

END. |