{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Conway's Game Of Life" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*This notebook originally appeared as a post on*\n", "[*Pythonic Perambulations*](http://jakevdp.github.io/blog/2013/08/07/conways-game-of-life/)\n", "*by Jake Vanderplas. The code and content is BSD-licensed.*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "In 1970 the British Mathematician John Conway created his \"Game of Life\" -- \n", "a set of rules that mimics the chaotic yet\n", "patterned growth of a colony of biological organisms. The \"game\" takes place on\n", "a two-dimensional grid consisting of \"living\" and \"dead\" cells, and\n", "the rules to step from generation to generation are simple:\n", "\n", "- **Overpopulation:** if a living cell is surrounded by more than three living cells, it dies.\n", "- **Stasis:** if a living cell is surrounded by two or three living cells, it survives.\n", "- **Underpopulation:** if a living cell is surrounded by fewer than two living cells, it dies.\n", "- **Reproduction:** if a dead cell is surrounded by exactly three cells, it becomes a live cell.\n", "\n", "By enforcing these rules in sequential steps, beautiful and unexpected patterns can appear." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "I was thinking about classic problems that could be used to demonstrate the effectiveness\n", "of Python for computing and visualizing dynamic phenomena, and thought back to a high school\n", "course I took where we had an assignment to implement a Game Of Life computation in C++.\n", "If only I'd had access to IPython and associated tools back then, my homework assignment\n", "would have been a whole lot easier!\n", "\n", "Here I'll use Python and NumPy to compute generational steps for the game of life, and use\n", "my [JSAnimation](http://github.com/jakevdp/JSAnimation) package to animate the results.\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Because the Game of Life is so simple, the time step can be computed rather\n", "tersely in Python. Here I implement two possibilities: one using generator expressions,\n", "and one using the ``convolve2d`` function from ``scipy``. Note that neither of\n", "these are extremely performant: they involve creating several temporary arrays,\n", "and will not work well for large problems with many time steps. Nevertheless,\n", "the simplicity makes these functions very attractive, and they are absolutely sufficient\n", "for the small examples we'll consider here:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import numpy as np\n", "\n", "def life_step_1(X):\n", " \"\"\"Game of life step using generator expressions\"\"\"\n", " nbrs_count = sum(np.roll(np.roll(X, i, 0), j, 1)\n", " for i in (-1, 0, 1) for j in (-1, 0, 1)\n", " if (i != 0 or j != 0))\n", " return (nbrs_count == 3) | (X & (nbrs_count == 2))\n", "\n", "def life_step_2(X):\n", " \"\"\"Game of life step using scipy tools\"\"\"\n", " from scipy.signal import convolve2d\n", " nbrs_count = convolve2d(X, np.ones((3, 3)), mode='same', boundary='wrap') - X\n", " return (nbrs_count == 3) | (X & (nbrs_count == 2))\n", " \n", "life_step = life_step_1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that we've made a choice here about the game boundary. Classically, the\n", "game takes place on an infinite, flat plane. Here, for simplicity, we've used\n", "a torroidal geometry (likely familiar to players of 1980s computer games like\n", "Asteroids), where the grid wraps from top to bottom and left to right." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we'll use the matplotlib animation submodule to visualize the results\n", "(for a tutorial on matplotlib animations, see my [previous post](http://jakevdp.github.io/)\n", "on the subject). We'll make use of my ``JSAnimation`` package, which you\n", "can read about [here](http://jakevdp.github.io)." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Populating the interactive namespace from numpy and matplotlib\n" ] } ], "source": [ "%pylab inline" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# JSAnimation import available at https://github.com/jakevdp/JSAnimation\n", "from JSAnimation.IPython_display import display_animation, anim_to_html\n", "from matplotlib import animation\n", "\n", "def life_animation(X, dpi=10, frames=10, interval=300, mode='loop'):\n", " \"\"\"Produce a Game of Life Animation\n", " \n", " Parameters\n", " ----------\n", " X : array_like\n", " a two-dimensional numpy array showing the game board\n", " dpi : integer\n", " the number of dots per inch in the resulting animation.\n", " This controls the size of the game board on the screen\n", " frames : integer\n", " The number of frames to compute for the animation\n", " interval : float\n", " The time interval (in milliseconds) between frames\n", " mode : string\n", " The default mode of the animation. Options are ['loop'|'once'|'reflect']\n", " \"\"\"\n", " X = np.asarray(X)\n", " assert X.ndim == 2\n", " X = X.astype(bool)\n", " \n", " X_blank = np.zeros_like(X)\n", " figsize = (X.shape[1] * 1. / dpi, X.shape[0] * 1. / dpi)\n", "\n", " fig = plt.figure(figsize=figsize, dpi=dpi)\n", " ax = fig.add_axes([0, 0, 1, 1], xticks=[], yticks=[], frameon=False)\n", " im = ax.imshow(X, cmap=plt.cm.binary, interpolation='nearest')\n", " im.set_clim(-0.05, 1) # Make background gray\n", "\n", " # initialization function: plot the background of each frame\n", " def init():\n", " im.set_data(X_blank)\n", " return (im,)\n", "\n", " # animation function. This is called sequentially\n", " def animate(i):\n", " im.set_data(animate.X)\n", " animate.X = life_step(animate.X)\n", " return (im,)\n", " animate.X = X\n", "\n", " anim = animation.FuncAnimation(fig, animate, init_func=init,\n", " frames=frames, interval=interval)\n", " \n", " #print anim_to_html(anim)\n", " return display_animation(anim, default_mode=mode)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's give this a try with a random starting field:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", " Once \n", " Loop \n", " Reflect \n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.random.seed(0)\n", "X = np.zeros((30, 40), dtype=bool)\n", "r = np.random.random((10, 20))\n", "X[10:20, 10:30] = (r > 0.75)\n", "life_animation(X, dpi=10, frames=40, mode='once')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "With the above random seed, the cells die off after about 40 generations.\n", "In the process, some very interesting patterns show up: there are static\n", "patterns, oscillating patterns, and a lot of spontaneous symmetry. Let's\n", "explore a few of the well-known patterns here:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Static Configurations" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Several static configurations are known: some of the smallest static units\n", "are shown here. We'll generate a few frames just to show that they are\n", "in fact static." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", " Once \n", " Loop \n", " Reflect \n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "X = np.zeros((6, 21))\n", "X[2:4, 1:3] = 1\n", "X[1:4, 5:9] = [[0, 1, 1, 0],\n", " [1, 0, 0, 1],\n", " [0, 1, 1, 0]]\n", "X[1:5, 11:15] = [[0, 1, 1, 0],\n", " [1, 0, 0, 1],\n", " [0, 1, 0, 1],\n", " [0, 0, 1, 0]]\n", "X[1:4, 17:20] = [[1, 1, 0],\n", " [1, 0, 1],\n", " [0, 1, 0]]\n", "\n", "life_animation(X, dpi=5, frames=3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Some simple oscillators (The \"Blinker\" and the \"Toad\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "An oscillator is a pattern that returns to its initial configuration after some number\n", "of steps. The static patterns shown above could be thought of as oscillators with a\n", "period of one. Here are two commonly-seen period-two oscillators:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", " Once \n", " Loop \n", " Reflect \n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "blinker = [1, 1, 1]\n", "toad = [[1, 1, 1, 0],\n", " [0, 1, 1, 1]]\n", "\n", "X = np.zeros((6, 11))\n", "X[2, 1:4] = blinker\n", "X[2:4, 6:10] = toad\n", "life_animation(X, dpi=5, frames=4)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Another Oscillator: The \"Pulsar\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "More complicated oscillators exist. Here's a period-three oscillator known as\n", "\"The Pulsar\", which displays some appealing symmetry." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", " Once \n", " Loop \n", " Reflect \n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "X = np.zeros((17, 17))\n", "X[2, 4:7] = 1\n", "X[4:7, 7] = 1\n", "X += X.T\n", "X += X[:, ::-1]\n", "X += X[::-1, :]\n", "life_animation(X, frames=6)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The \"Glider\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There are other classes of object which oscillate, but also move while oscillating.\n", "One of the earliest seen is the \"Glider\", which after 4 steps returns to its\n", "initial configuration, but shifted by one cell in both the x and y direction.\n", "This is a configuration that often emerges from random starting points." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", " Once \n", " Loop \n", " Reflect \n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "glider = [[1, 0, 0],\n", " [0, 1, 1],\n", " [1, 1, 0]]\n", "X = np.zeros((8, 8))\n", "X[:3, :3] = glider\n", "life_animation(X, dpi=5, frames=32, interval=100)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Unbounded Growth" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "An early question posed about the Game of Life was whether any configurations exist which\n", "result in asymptotically unbounded growth. It was quickly found that the answer was yes. Though\n", "it wasn't the first discovered, the following is one of the most compact configurations which\n", "display unbounded growth. Note that this claim is precisely true only on an infinite game\n", "board: using a torroidal (i.e. wrapping) geometry like we do here will lead to different\n", "results, but the first several hundred generations are unaffected:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", " Once \n", " Loop \n", " Reflect \n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "unbounded = [[1, 1, 1, 0, 1],\n", " [1, 0, 0, 0, 0],\n", " [0, 0, 0, 1, 1],\n", " [0, 1, 1, 0, 1],\n", " [1, 0, 1, 0, 1]]\n", "X = np.zeros((30, 40))\n", "X[15:20, 18:23] = unbounded\n", "life_animation(X, dpi=10, frames=100, interval=200, mode='once')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The \"Gosper Glider Gun\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The earliest known instance of unbounded growth is one of my favorite configurations:\n", "the \"Glider Gun\" discovered by Bill Gosper. It is an oscillating pattern that creates\n", "an infinite series of gliders. It still amazes me that something like this can even\n", "emerge from Conway's simple rules, but here it is. We'll stop after a couple hundred\n", "frames, but given an infinite game board this action would go on forever:" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", " Once \n", " Loop \n", " Reflect \n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "glider_gun =\\\n", "[[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0],\n", " [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0],\n", " [0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1],\n", " [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1],\n", " [1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0],\n", " [1,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0],\n", " [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0],\n", " [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],\n", " [0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]\n", "\n", "X = np.zeros((50, 70))\n", "X[1:10,1:37] = glider_gun\n", "\n", "life_animation(X, dpi=15, frames=180, interval=50, mode='once')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Going Further" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that while the code above is well-suited for small explorations,\n", "it is probably not sufficient to do very large and long game of life\n", "computations. For that, I'd recommend [Golly](http://golly.sourceforge.net/), an\n", "open-source cross-platform package for computing and visualizing the Game of Life.\n", "It has some nice optimizations, including a blazing fast hash-based computation of\n", "generational steps for long-lived problems." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Diving further in, you might come across other very cool patterns. One pattern, known as a \"Breeder\",\n", "moves through space creating glider guns, which in turn create an endless series of\n", "gliders. Wikipedia has a [great animation](http://en.wikipedia.org/wiki/File:Conways_game_of_life_breeder_animation.gif)\n", "of this in action:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notice the series of glider guns, similar to the one we built above.\n", "While this animation could certainly be created using the above Python code,\n", "I'm just not sure I'd have the patience!\n", "\n", "\n", "Despite (or perhaps because of) its simplicity, the Game of Life\n", "has inspired an entire community of people who study its properties. It has influenced fields\n", "as diverse as mathematics, computer science, biology, epidemiology, and sociology.\n", "This interest has led to the discovery of configurations with some very surprising properties.\n", "Incredibly, it has even been shown that a Universal Turing Machine can be created within\n", "the rules of the game of life. That is, a computer which can compute game of life steps\n", "could, in theory, use this process to compute just about anything!\n", "\n", "Here are another few patterns you might try embedding in a game board, to see what will happen." ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [], "source": [ "diehard = [[0, 0, 0, 0, 0, 0, 1, 0],\n", " [1, 1, 0, 0, 0, 0, 0, 0],\n", " [0, 1, 0, 0, 0, 1, 1, 1]]\n", "\n", "boat = [[1, 1, 0],\n", " [1, 0, 1],\n", " [0, 1, 0]]\n", "\n", "r_pentomino = [[0, 1, 1],\n", " [1, 1, 0],\n", " [0, 1, 0]]\n", "\n", "beacon = [[0, 0, 1, 1],\n", " [0, 0, 1, 1],\n", " [1, 1, 0, 0],\n", " [1, 1, 0, 0]]\n", "\n", "acorn = [[0, 1, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 1, 0, 0, 0],\n", " [1, 1, 0, 0, 1, 1, 1]]\n", "\n", "spaceship = [[0, 0, 1, 1, 0],\n", " [1, 1, 0, 1, 1],\n", " [1, 1, 1, 1, 0],\n", " [0, 1, 1, 0, 0]]\n", "\n", "block_switch_engine = [[0, 0, 0, 0, 0, 0, 1, 0],\n", " [0, 0, 0, 0, 1, 0, 1, 1],\n", " [0, 0, 0, 0, 1, 0, 1, 0],\n", " [0, 0, 0, 0, 1, 0, 0, 0],\n", " [0, 0, 1, 0, 0, 0, 0, 0],\n", " [1, 0, 1, 0, 0, 0, 0, 0]]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "I hope you enjoyed this quick exploration! \n", "For more information on the wealth of information about this\n", "game, you can browse the discussions and forums at\n", "[Conway's Game of Life](http://conwaylife.com/)\n", "\n", "*This post was written in an IPython notebook, which can be downloaded*\n", "[*here*](http://jakevdp.github.io/downloads/notebooks/GameOfLife.ipynb),\n", "*or viewed statically*\n", "[*here*](http://nbviewer.ipython.org/url/jakevdp.github.io/downloads/notebooks/GameOfLife.ipynb)." ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python [default]", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.1" } }, "nbformat": 4, "nbformat_minor": 0 }