Neural network based implementation of Conway's game of life

neural-life.coffee

brain = require('brain')
life = new brain.NeuralNetwork()
assert = require('assert')
_ = require('underscore')

THRESHOLD = 0.35
SIZE = 10

class Matrix
  state: []
  
  constructor: (arr, @size)->
    @size ?= SIZE
    @should_normalize = true
    @serialize(arr) if arr?
    @threshold = 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)

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

    @
  
  _flatten: (arrays) ->
    merged = []
    merged.concat.apply(merged, arrays)
  
  deserialize: ()->
    @_flatten(@state)

  translate: (x, y)->
    # create utility array function unless it exists
    unless Array::rotate?
      Array::rotate = (n) ->
        @unshift.apply(@, @splice(n, @length))
        @
  
    unless x is 0
      for row in @state
        row.rotate(-x)

    unless y is 0
      @state.rotate(-y)
  
    @   

  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)
    @
  
matrix = new Matrix()
patterns = []

#################### START


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

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

gl_3 = [
  0,0,0,0,0,0,0,0,0,0
  0,1,0,0,0,0,0,0,0,0
  0,0,1,1,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,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]

gl_4 = [
  0,0,0,0,0,0,0,0,0,0
  0,0,1,0,0,0,0,0,0,0
  0,0,0,1,0,0,0,0,0,0
  0,1,1,1,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,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);

layers = ([Math.max(3, Math.floor(initial_patterns[0].input.length / 2))])
console.log "nn options learningRate: #{life.learningRate}, momentum: #{life.momentum} hiddenLayers: #{life.hiddenSizes || layers}"

console.log 'testing that serialize works as expected'
#console.log 'gl_1', gl_1
deserialized_matrix = matrix.serialize(gl_1).deserialize()
#console.log '-->', deserialized_matrix, gl_1

assert(_.isEqual(deserialized_matrix, gl_1), 'test serialize')


# Ok so now we can serialize our 2x2 matrices into a form that our neural net will like

test_1 = [
  0,0,0,0,0,0,0,0,0,0
  0,0,1,0,0,0,0,0,0,0
  0,0,1,0,0,0,0,0,0,0
  0,0,1,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
expected_1 = [
  0,0,0,0,0,0,0,0,0,0
  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,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
out = life.run(test_1)
console.log 'test 1: blinker'
matrix.serialize(out).print()
# since the neural net is predicting a probability of each
# value of our array, we want to normalize that prediction to either
# an alive state, or a dead state.
  
# implement normalize
  
test_2 = [
  0,0,0,0,0,0,0,0,0,0
  0,0,0,1,0,0,0,0,0,0
  0,0,0,1,0,0,0,0,0,0
  0,0,0,1,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
expected_2 = [
  0,0,0,0,0,0,0,0,0,0
  0,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,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
out = life.run(test_2)
console.log 'test 2: translated blinker'
matrix.serialize(out).print()

# These results look like a valid life state, but they aren't what we expect
# We haven't trained enough, our neural net is still absurdly simple under
# the scenes


# what are some tricks we can do to make sure our game understands all the rules?
# 1. we can calculate all useful translations of our training data, and retrain our net
#
# this will help because our neural net doesn't know that it's not
# important what position a living cell is at to make it turn on
# or off, it's the neighbors.
#
# by calculating all translations of the board with our first examples,
# we'll reduce the rigidity of the net, and it will more likely predict
# the next state for us.
trans_1 = [
  0,0,0,0,0,0,0,0,0,0
  0,0,0,1,0,0,0,0,0,0
  0,0,0,1,0,0,0,0,0,0
  0,0,0,1,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
trans_expect_1 = [
  0,0,0,0,0,0,0,0,0,0
  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,1,0,0,0,0,0
  0,0,0,0,1,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]

# implement translate
#console.log 'testing a translation'
assert(_.isEqual(matrix.serialize(trans_1).translate(1, 2).deserialize(), trans_expect_1), 'translate works')
  
# ok, so how do we retrain with all possible translations?
#
# loop & train, loop & train
# We'll be looping both the input & the output value
glider_sequence = [gl_1, gl_2, gl_3, gl_4]

translateAndPush = (input, output)->
  for x in [0..(SIZE-1)]
    for y in [0..(SIZE-1)]
      #console.log 'translating', x, y
      #console.log matrix.serialize(gl_1).translate(x, y).state
      patterns.push {
        input: matrix.serialize(gl_1).translate(x, y).deserialize()
        output: matrix.serialize(gl_2).translate(x, y).deserialize()
      }

console.log "creating glider patterns - #{patterns.length}"
# Loop through each glider step
generateSequencePatterns = (sequence)->
  # translate each matrix 2 times, so that we don't get literal "edge" cases
  rotations = (sequence.length-2) * 2
  for i in [0..rotations]
    input = sequence[0]
    output = sequence[1]
    translateAndPush(input, output)
    sequence.rotate(1)
  sequence.rotate(1)

generateSequencePatterns(glider_sequence)

console.log "---- training on #{patterns.length} patterns"
#console.log patterns[0]
console.log life.train(patterns)

# Ok let's try running it again

test_2 = [
  0,0,0,0,0,0,0,0,0,0
  0,0,0,1,0,0,0,0,0,0
  0,0,0,1,0,0,0,0,0,0
  0,0,0,1,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
expected_2 = [
  0,0,0,0,0,0,0,0,0,0
  0,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,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
out = life.run(test_2)
console.log 'life run test 3'
matrix.serialize(out).print()


# That still didn't really work out well
# It's got translation down, but not the rules of the game.
# It still thinks it can only outcome things it's seen before
#
# What more can we do?
# - We can train it on more steps
console.log "creating more patterns - #{patterns.length}"

# empty sets
empty = [
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
patterns.push({input: empty, output: empty})

# full set
full = [
  1,1,1,1,1,1,1,1,1,1
  1,1,1,1,1,1,1,1,1,1
  1,1,1,1,1,1,1,1,1,1
  1,1,1,1,1,1,1,1,1,1
  1,1,1,1,1,1,1,1,1,1
  1,1,1,1,1,1,1,1,1,1
  1,1,1,1,1,1,1,1,1,1
  1,1,1,1,1,1,1,1,1,1
  1,1,1,1,1,1,1,1,1,1
  1,1,1,1,1,1,1,1,1,1
]
# everything will die, overcrowding
patterns.push({input: full, output: empty})

# what steps can we train on?
# still life sets
# - block
# - behive
# - loaf
# - boat
block = [
  1,1,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,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
translateAndPush(block, block)
behive = [
  0,1,1,0,0,0,0,0,0,0
  1,0,0,1,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,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
translateAndPush(behive, behive)
loaf = [
  0,1,1,0,0,0,0,0,0,0
  1,0,0,1,0,0,0,0,0,0
  0,1,0,1,0,0,0,0,0,0
  0,0,1,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
translateAndPush(loaf, loaf)
boat = [
  1,1,0,0,0,0,0,0,0,0
  1,0,1,0,0,0,0,0,0,0
  0,1,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
translateAndPush(boat, boat)


# oscillators
# - blinker
blinker_step_1 = [
  0,1,0,0,0,0,0,0,0,0
  0,1,0,0,0,0,0,0,0,0
  0,1,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
blinker_step_2 = [
  0,0,0,0,0,0,0,0,0,0
  1,1,1,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
translateAndPush(blinker_step_1, blinker_step_2)
# - toad
toad_step_1 = [
  0,0,0,0,0,0,0,0,0,0
  0,1,1,1,0,0,0,0,0,0
  1,1,1,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
toad_step_2 = [
  0,0,1,0,0,0,0,0,0,0
  1,0,0,1,0,0,0,0,0,0
  1,0,0,1,0,0,0,0,0,0
  0,1,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
translateAndPush(toad_step_1, toad_step_2)
# - beacon
beacon_step_1 = [
  1,1,0,0,0,0,0,0,0,0
  1,1,0,0,0,0,0,0,0,0
  0,0,1,1,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,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
beacon_step_2 = [
  1,1,0,0,0,0,0,0,0,0
  1,0,0,0,0,0,0,0,0,0
  0,0,0,1,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,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
translateAndPush(beacon_step_1, beacon_step_2)

console.log "---- training on #{patterns.length} patterns"
#console.log patterns[0]
console.log life.train(patterns)

out = life.run(test_2)
console.log 'life run test 4, with glider, still lifes, oscilators'
console.log '--- in'
matrix.serialize(test_2).print()
console.log '--- out'
matrix.serialize(out).print()
console.log '--- expected'
matrix.serialize(expected_2).print()
if (true)
  console.log 'raw results'
  matrix.normalize(false)
    .serialize(out)
    .print()
    .normalize(true)

# so now that we increase the size of our arrays, we improve our results
# well sort of.



# additional spaceship
# - lightweight spaceship, maybe..
#
lwss_1 = [
  0,0,0,0,0,0,0,0,0,0
  0,1,0,0,1,0,0,0,0,0
  0,0,0,0,0,1,0,0,0,0
  0,1,0,0,0,1,0,0,0,0
  0,0,1,1,1,1,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
lwss_2 = [
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,1,1,0,0,0,0
  0,0,1,1,0,1,1,0,0,0
  0,0,1,1,1,1,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,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
lwss_3 = [
  0,0,0,0,0,0,0,0,0,0
  0,0,0,1,1,1,1,0,0,0
  0,0,1,0,0,0,1,0,0,0
  0,0,0,0,0,0,1,0,0,0
  0,0,1,0,0,1,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
lwss_4 = [
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,1,1,0,0,0,0
  0,0,0,1,1,1,1,0,0,0
  0,0,0,1,1,0,1,1,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,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
lwss_5 = [
  0,0,0,0,0,0,0,0,0,0
  0,0,0,1,0,0,1,0,0,0
  0,0,0,0,0,0,0,1,0,0
  0,0,0,1,0,0,0,1,0,0
  0,0,0,0,1,1,1,1,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
  0,0,0,0,0,0,0,0,0,0
]
lwss_sequence = [lwss_1, lwss_2, lwss_3, lwss_4, lwss_5]

generateSequencePatterns(lwss_sequence)

console.log "---- training on #{patterns.length} patterns"
console.log life.train(patterns)

out = life.run(test_2)
console.log '--- in'
matrix.serialize(test_2).print()
console.log '--- out'
matrix.serialize(out).print()

options = 
  errorThresh: 0.005,  # error threshold to reach
  iterations: 20000,   # maximum training iterations
  log: true,           # console.log() progress periodically
  logPeriod: 10       # number of iterations between logging

life2 = new brain.NeuralNetwork()
console.log "---- training life2 on #{patterns.length} patterns"
console.log life2.train(patterns, options)

out = life2.run(test_2)
console.log '--- in'
matrix.serialize(test_2).print()
console.log '--- out'
matrix.serialize(out).print()

options = 
  errorThresh: 0.9,  # error threshold to reach
  iterations: 20000,   # maximum training iterations
  log: true,           # console.log() progress periodically
  logPeriod: 10       # number of iterations between logging

life3 = new brain.NeuralNetwork()
console.log "---- training life3 on #{patterns.length} patterns"
console.log life3.train(patterns, options)

out = life3.run(test_2)
console.log '--- in'
matrix.serialize(test_2).print()
console.log '--- out'
matrix.serialize(out).print()

options = 
  errorThresh: 0.001,  # error threshold to reach
  iterations: 20000,   # maximum training iterations
  log: true,           # console.log() progress periodically
  logPeriod: 10       # number of iterations between logging

life4 = new brain.NeuralNetwork()
console.log "---- training life4 on #{patterns.length} patterns"
console.log life4.train(patterns, options)

out = life4.run(test_2)
console.log '--- in'
matrix.serialize(test_2).print()
console.log '--- out'
matrix.serialize(out).print()

options = 
  errorThresh: 0.0001,  # error threshold to reach
  iterations: 20000,   # maximum training iterations
  log: true,           # console.log() progress periodically
  logPeriod: 10       # number of iterations between logging

life5 = new brain.NeuralNetwork()
console.log "---- training life5 on #{patterns.length} patterns"
console.log life5.train(patterns, options)

out = life5.run(test_2)
console.log '--- in'
matrix.serialize(test_2).print()
console.log '--- out'
matrix.serialize(out).print()

options = 
  hiddenLayers: [25, 25]
  learningRate: 0.2 # lowering this will prevent overfitting

train_options = 
  errorThresh: 0.001,  # error threshold to reach
  iterations: 20000,   # maximum training iterations
  log: true,           # console.log() progress periodically
  logPeriod: 10       # number of iterations between logging

life6 = new brain.NeuralNetwork(options)
console.log "---- training life6 on #{patterns.length} patterns"
console.log life6.train(patterns, train_options)

out = life6.run(test_2)
console.log '--- in'
matrix.serialize(test_2).print()
console.log '--- out'
matrix.serialize(out).print()
console.log '--- raw'
matrix.normalize(false).serialize(out).print().normalize(true)

if (process.argv[2] == 'run')
  setInterval ()->
    out = life6.run(out)
    console.log '---'
    matrix.serialize(out).print()
  , 1000 / 5