Time is Neutral

Notes and thoughts on computing, mathematics, and anything else I can write about.

About

Paul English is a student and software developer in Salt Lake City.

Email · Resume

14 February 2013

Game of Life Simulation

Conway's Game of Life is a simulation, specifically a cellular automata that contains four primary rules for calculating each step of the simulation. You create a grid of variable size, and use each cell to represent a life. These cells live or die based on the four rules setup for this game. They are as follows,

  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  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 overcrowding.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Using these rules and an animation loop, you can create perplexing, ever evolving, animations that may include repetitive sequences, moving sequences, and can even be turing machines. Most of the time you end up with a bunch of dots that have characteristic grouping patterns, and they usually eventual cycle into a stale board with little movement.

Implementing this simulation is usually trivial, here's an example in the Processing language that's under 67 lines, and with a bit of code golf you could get that down to 2 lines, readability be damned.

We're going to see what happens if we train a neural network to emulate the game of life. Neural networks are mathematical implementations of biological neural networks, or more commonly known as brains. Will we see familiar patterns? Will we be able to accurately re-implement the four key rules necessary for the game? How much work will it take? What kind of process do we need to go through to accomplish something of use? Why would we want to use a neural network, or when would we best apply it to a problem? Is it efficient?

Implementation Plan

Implementing a neural network is a bit more non-trivial than the scope of this article, maybe we'll save that for a future time, though you can readily find many resources to help you, if you're interested in how to do that. We'll be using a library called brain to perform our training and output. We'll use coffee-script for implementation.

A neural network uses layers of emulated neurons to observe inputs and related outputs, and estimate the patterns required to repeat the output calculations. It's functionality is open ended until you train it on data, at which point it will attempt to replicate the output data you've provided given an input. Brain.js provides us with this example, implementing an XOR function.

net = new brain.NeuralNetwork()

net.train([{input: [0, 0], output: [0]},
           {input: [0, 1], output: [1]},
           {input: [1, 0], output: [1]},
           {input: [1, 1], output: [0]}])

output = net.run([1, 0])  # [0.987]

Though these examples that we're reviewing contain simple and understandable functions, in most cases where you'd use a neural network your problem is more complex than you can easily guess at or know about. An XOR table is easy to recognize and digest, so it makes a good initial example.

In looking at the example provided how will we create the Game of Life? What we'll need is a set of input parameters, and corresponding output parameters. Since you would traditionally use a loop to implement the simulation of the game, we'll take an initial state and use that as an input, then calculate what the next step of the cycle would be for an output. If we then loop our output back around into the net's input, we'll have a similar loop that we can animate through.

State Representation

Each board will be represented as a matrix filled with binary variables. A matrix can be represented by using a 2-dimensional array in Javascript, or in our case Coffeescript.

lifeState_Matrix = [
    [0,1,0,0,0]
    [0,0,1,0,0]
    [1,1,1,0,0]
    [0,0,0,0,0]
    [0,0,0,0,0]
]

However to make our interactions with the neural net simpler we're going to flatten the 2-dimensional matrix into a 1-dimensional array of values. We will be able to serialize & deserialize our array by providing a size parameter, optionally if you were to always assume square matrices, you could infer the matrix size using the square root of your array length. Here's what our arrays will look like, formatted to look nice, notice that it's just an array which happens to have line breaks. Also we'll build a class which we'll be using to convert our data quickly back & forth.

# It's just an array
lifeState = [
    0,1,0,0,0,
    0,0,1,0,0,
    1,1,1,0,0,
    0,0,0,0,0,
    0,0,0,0,0
]

# A default constant which we can use four our matrix size
MATRIX_SIZE = 5

class Matrix
    state: []

    constructor: (arr, @size)->
        @size ?= MATRIX_SIZE
        @serialize(arr) if arr?

    # This will set our internal state to a 2x2 dimensional array
    serialize: (arr, size = @size)->
        # Note that we're using a utility function from the
        # underscore.js library for convenience.
        arr = _.clone(arr)

        # Clear any previous state
        @state = []

        # loop and push a new array (row) into our state
        for i in [0..size-1]
            @state.push(arr.splice(0,size))

        # Return this, allowing us to chain functions
        @

    # A utility function that will flatten an array of arrays into
    # one array
    _flatten: (arrays) ->
        merged = []
        merged.concat.appply(merged, arrays)

    deserialize: ()->
        @_flatten(@state)

Training

In order to train our network, we'll need to create several known inputs and outputs. We can then feed these into our network, run the network with a new input and then see what kind of output we get, and if it seems to match up. Let's try training our network on the glider pattern, a well known sequence that translates itself across the grid over the course of 4 steps.

gl_1 = [
  0,1,0,0,0
  0,0,1,0,0
  1,1,1,0,0
  0,0,0,0,0
  0,0,0,0,0
]

gl_2 = [
  0,0,0,0,0
  1,0,1,0,0
  0,1,1,0,0
  0,1,0,0,0
  0,0,0,0,0
]

gl_3 = [
  0,0,0,0,0
  0,1,0,0,0
  0,0,1,1,0
  0,1,1,0,0
  0,0,0,0,0
]

gl_4 = [
  0,0,0,0,0
  0,0,1,0,0
  0,0,0,1,0
  0,1,1,1,0
  0,0,0,0,0
]


console.log "---- training on 3 patterns"
initial_patterns = [
  {input:gl_1, output:gl_2}
  {input:gl_2, output:gl_3}
  {input:gl_3, output:gl_4}
]
console.log life.train(initial_patterns);
# { error: 0.004746702439165265, iterations: 57 }

Since the glider is a sequence of 4, we have 3 initial patterns we can train on. From step 1 to 2, step 2 to 3, and step 3 to 4. The sequence can continue indefinitely, but we'd need to create additional arrays to represent each step in the process.

Training is going to be the most computationally intense process, you won't notice it with three patterns, but as your patterns grow it will start to become noticeable.

First lets add a utility method to our matrix class to cleanly print a matrix to the screen.

class Matrix
  ...
  
  print: (val = " ")->
    for row in @state
      out_row = row.map (item)->
        return if item is 1 or item is 0 then item else item.toFixed(2)
      console.log "   " + out_row.join(val)
    @

We should now be able to run some new patterns through our life network and see what the results are. Let's try it on another familiar pattern, the blinker. This pattern simply oscillates back and forth, between two states.

test_1 = [
  0,0,0,0,0
  0,0,1,0,0
  0,0,1,0,0
  0,0,1,0,0
  0,0,0,0,0
]
expected_1 = [
  0,0,0,0,0
  0,0,0,0,0
  0,1,1,1,0
  0,0,0,0,0
  0,0,0,0,0
]
console.log 'test 1: blinker'
out = life.run(test_1)
matrix = new Matrix()
matrix.serialize(out).print()
# test 1: blinker
#    0.02 0.02 0.03 0.03 0.02
#    0.27 0.31 0.69 0.02 0.02
#    0.02 0.28 0.63 0.73 0.02
#    0.03 0.98 0.72 0.39 0.03
#    0.03 0.03 0.02 0.02 0.02

Well that's definitely a unique output, but it's not really clear. What we're looking at is the probability that each value is a 1 as opposed to a 0. Some neural networks are better built to work with categorical data like we're dealing with, but we can still use this. What we can do is set a threshold in our Matrix class for all arrays that we serialize. This threshold will round each of these array values into a 1, or 0 helping us to see what our network is predicting.

BINARY_THRESHOLD = 0.35

class Matrix
  constructor: (arr, @size)->
    @size ?= MATRIX_SIZE
    @should_normalize = true
    @serialize(arr) if arr?
    @threshold = BINARY_THRESHOLD
  
  ...
  
  _normalize: (arr)->
    #console.log 'normalize arr in', arr
    arr = arr.map (item)=>
      return if item >= @threshold then 1 else 0
    #console.log 'normalize arr out', arr
    arr
    
  # getter/setter for normalize
  normalize: (normalize)->
    if normalize?
      @should_normalize = normalize
      return @
    else
      @should_normalize

  serialize: (arr, size = @size)->
    arr = _.clone(arr)

    @state = []

    if @should_normalize
      arr = @_normalize(arr)

    for i in [0..size-1]
      #console.log 'arr', clone_arr
      @state.push(arr.splice(0,size))

    @

We've added 2 new methods, and augmented our constructor & serialize method to accomodate a BINARY_THRESHOLD constant which we've set at the top. I didn't battle test this too much, 0.35 seems to work well enough for our purposes now.

Let's try our test again & see what the output is.

console.log 'test 2: blinker'
out = life.run(test_1)
matrix = new Matrix()
matrix.serialize(out).print()
# test 2: blinker
#    0 0 0 0 0
#    0 0 1 0 0
#    0 0 1 1 0
#    0 1 1 1 0
#    0 0 0 0 0

So that certainly looks like a life state, binary variables in a 5x5 grid, but the actual output isn't really at all what we're expecting.

This is mostly because we've trained on just a few examples, 3 to be precise. Our network is actually generating a pattern that more closely resembles a glider, mixed with a little bit of randomness.

When it comes to using a neural network, or any machine learning algorithm for that matter, your results will only ever be as good as the data you train with. In this case our training is about as simple as it can get.

I'll spend some time this next week on follow-up posts that continue this project, and enhance open this work with further training and modeling. Stay tuned, let me know if you find this interesting or useful.