Sunday, 26 May 2019

NeuroEvolution using TensorFlow JS - Part 2

Introduction


This tutorial is part 2, if you have not completed NeuroEvolution using TensorFlowJS - Part 1, I highly recommend you do that first. As it will:
  • Explain how to setup the codebase
  • How to run the local dev environment
  • How to setup the basic NeruoEvolution implementation

In this tutorial we will be:
  • Adding visual debugging information
  • Adding more inputs for TensorFlow to use to predict jumping
  • Implement crossover within TensorFlowJS
  • Use the best progressing NeuralNetwork to ensure faster NeuroEvolution
  • Add saving and loading of NeuralNetwork models

This tutorial is also based on the source code found on my GitHub account here https://github.com/dionbeetson/neuroevolution-experiment.

Let's get started!

Add in visual/debugging

We will be adding in useful debugging information to the right hand column and to the game itself.

Chart the progress of each evolution

We are going to use ChartJS to track the progress (as a percentage) and the score for the best game of each evolution. Create a file called js/ai/NeuroEvolutionChart.js and copy the below logic into it. It is a basic ChartJS implementation that I won't go into detail in this tutorial.

js/ai/NeuroEvolutionChart.js

class NeuroEvolutionChart {
  constructor() {
    this.chart = null;
    this.config = {
    type: 'line',
    data: {
     labels: [],
     datasets: [{
      label: '',
      backgroundColor: '#999999',
      borderColor: '#EEEEEE',
          borderWidth: 3,
      data: [],
      fill: false,
     },{
      label: '',
      backgroundColor: '#91C7B1',
      borderColor: '#A1CFBC',
          borderWidth: 2,
      data: [],
      fill: false,
     }]
    },
    options: {
     responsive: true,
     title: {
      display: false
     },
     tooltips: {
      mode: 'index',
      intersect: false,
     },
        legend: {
          display: false
        },
     hover: {
      mode: 'nearest',
      intersect: true
     },
     scales: {
      xAxes: [{
       display: false,
       scaleLabel: {
        display: true,
        labelString: 'Round'
       }
      }],
      yAxes: [{
       display: true,
            ticks: {
              beginAtZero: true,
              min: 0,
              max: 100
            },
       scaleLabel: {
        display: false,
        labelString: 'Progress'
       }
      },{
       display: true,
            position: 'right',
            ticks: {
              beginAtZero: true,
              min: 0,
              max: 200
            },
       scaleLabel: {
        display: false,
        labelString: 'Score'
       }
      }]
     }
    }
   };

    this.setup();
  }

  setup(){
    var ctx = document.getElementById('trend').getContext('2d');
    this.chart = new Chart(ctx, this.config);
  }
}
Now, add an update() method that will be responsible for pushing the data points onto the chart. It will also only keep 12 data points (the very first evolution, and the latest 11 evolutions). This is to avoid clutter on the page.

js/ai/NeuroEvolutionChart.js

update(progress, score) {
  // Purge middle data (to avoid clutter)
  if( this.config.data.labels.length > 12 ) {
    this.config.data.labels.splice(1, 1);
    this.config.data.datasets[0].data.splice(1, 1);
    this.config.data.datasets[1].data.splice(1, 1);
  }

  this.config.data.labels.push((this.config.data.labels.length+1))
  this.config.data.datasets[0].data.push(progress);
  this.config.data.datasets[1].data.push(score);

  this.chart.update();
}
Back in the NeuroEvolution class add the following variable declaration to the top

js/ai/NeuroEvolution.js

#neuroEvolutionChart = new NeuroEvolutionChart();
Then in the same file in the finishGeneration(games, timeTaken) method, right after the line this.#bestGames.sort(this.sortByFitness); add in.

js/ai/NeuroEvolution.js

// Update UI - Chart
this.#neuroEvolutionChart.update(bestPlayerByFitness.progress, bestPlayerByFitness.score);
Reload your browser, and click the 'start evolution' button. After each evolution you will start to see the chart in the top right update.

Additional debugging visuals

Let's quickly add in some more useful debug information which includes:
  • The best game progress to date
  • Track the best score from each evolution
  • A progress bar in the header to track round and generation progress

In the NeuroEvolution class add the below methods

js/ai/NeuroEvolution.js

updateUIaddBestGenerationToBestScore( pickBestPlayerByFitness, timeTaken ) {
  let bestScore = document.createElement("li");
  bestScore.innerHTML = pickBestPlayerByFitness.score + ' (' + pickBestPlayerByFitness.progress.toFixed(1) + '%) (' + pickBestPlayerByFitness.fitness.toFixed(3) + ') (' + timeTaken + 's)';
  this.#bestScores.insertBefore(bestScore, document.querySelector("li:first-child"));
}

updateUIRoundInformation() {
  document.querySelector("#round-current").innerHTML = this.#generation;
  document.querySelector("#round-total").innerHTML = this.#maxGenerations;
  document.querySelector("#round-progress").style.width = '0%';
  document.querySelector("#generation-progress").style.width = (this.#generation/this.#maxGenerations)*100 + '%';
}

updateUIBestPlayerScore( bestGame ) {
  document.querySelector("#best-player-score").innerHTML = bestGame.score + " points (" + bestGame.progress.toFixed(1) + "%)";
}
In the first line of the start() method add:

js/ai/NeuroEvolution.js

processGeneration(games, bestPlayerBrainsByFitness) {
  this.updateUIRoundInformation();
  ...
Then right after where you added in this.#neuroEvolutionChart.update... add in:

js/ai/NeuroEvolution.js

// Update UI
this.updateUIaddBestGenerationToBestScore(bestPlayerByFitness, timeTaken);
this.updateUIBestPlayerScore(this.#bestGames[0]);
this.updateUIRoundInformation();
Lastly, add the following variable declaration to the top

js/ai/NeuroEvolution.js

#bestScores = null;
and the following constructor

js/ai/NeuroEvolution.js

constructor() {
  this.#bestScores = document.querySelector("#best-scores");
}
Reload your browser, and click the 'start evolution' button. You should start seeing debug information in your right hand column.

Another useful debug is to visualise the inputs that are being used to predict the jump() action.

Back in the Ai class within the think() method, just before the game.brain.predict() line, add in this code block to push debug points into the game canvas.

js/ai/Ai.js

game.gameApi.setDebugPoints([
  {
    x: 0,
    y: inputs[0]
  },
  {
    x: inputs[2],
    y: 0
  },
  {
    x: 0,
    y: inputs[3]
  },
  {
   x: 0,
   y: inputs[4]
  }
]);
Reload your browser, and click the 'start evolution' button. You should start seeing crosshairs for the inputs being used by TensorFlow JS on every prediction call.

Sometimes it is useful to be able to 'pause the game before the next evolution begins. You will see a checkbox in the left column labelled 'Pause after generation'. Let's wire it up, as it currently is not.

In ui.js add in the below change handler to capture user interaction.

js/ai/ui.js

document.querySelector("#ml-pause-before-next-generation").addEventListener("change", function() {
  neuroEvolution.pauseBeforeNextGeneration = this.checked;

  if( false == neuroEvolution.pauseBeforeNextGeneration && neuroEvolution.pausedGames.length > 0 && neuroEvolution.pausedBestNeuralNetworksByFitness.length > 0 ) {
    neuroEvolution.start(neuroEvolution.pausedGames, neuroEvolution.pausedBestNeuralNetworksByFitness);
  }
});

neuroEvolution.pauseBeforeNextGeneration = document.querySelector("#ml-pause-before-next-generation").checked;
This isn't enough though, we need to build in the logic to actually pause the game. We are basically going to wrap the ai.start(bestPlayerBrainsByFitness); call within the start() method in NeuroEvolution.js in an IF statement based on if the pause checkbox is checked. If it is checked, we will then store the current games within a local class variable so we can retrieve it once the checkbox is unchecked.

The completed method looks like this now.

js/ai/NeuroEvolution.js

start(games, bestPlayerBrainsByFitness) {
  this.updateUIRoundInformation();

  if ( this.#generation < this.#maxGenerations ) {

    if( false == this.#pauseBeforeNextGeneration ){
      for ( let i = 0; i < games.length; i++ ) {
        games[i].gameApi.remove();
      }

      games = undefined;

      this.#pausedGames = [];
      this.#pausedBestNeuralNetworksByFitness = [];

      this.#generation++;

      const ai = new Ai(this.finishGeneration.bind(this));
      ai.start(this.#useImageRecognition, bestPlayerBrainsByFitness);

    } else {
      this.#pausedGames = games;
      this.#pausedBestNeuralNetworksByFitness = bestPlayerBrainsByFitness;

      for ( let i = 0; i < games.length; i++ ) {
        games[i].gameApi.show();
      }
    }
  } else {
    this.enableSpeedInput();
  }
}
Then add in the following variable declarations in the NeuroEvolution class.

js/ai/NeuroEvolution.js

#pausedGames = [];
#pausedBestNeuralNetworksByFitness = [];
#pauseBeforeNextGeneration = false;
And then add in the required getters/setters in the NeuroEvolution class.

js/ai/NeuroEvolution.js

get pauseBeforeNextGeneration() {
  return this.#pauseBeforeNextGeneration;
}

set pauseBeforeNextGeneration( pauseBeforeNextGeneration ) {
  this.#pauseBeforeNextGeneration = pauseBeforeNextGeneration;
}

get pausedGames() {
  return this.#pausedGames;
}

get pausedBestNeuralNetworksByFitness() {
  return this.#pausedBestNeuralNetworksByFitness;
}

get bestGames() {
  return this.#bestGames;
}

set pauseBeforeNextGeneration( pauseBeforeNextGeneration ) {
  this.#pauseBeforeNextGeneration = pauseBeforeNextGeneration;
}

Speeding up NeuroEvolution

Ok that is debugging done for now. Let's move onto improving our NeuroEvolution to solve this game a little faster. This involves 3 things:
  1. Adding more inputs for TensorFlow to use to predict jumping
  2. After each evolution randomly choosing to use the 'best game to date', as this can keep things on track if we have a single bad evolution randomly (trust me it happens)
  3. Implementing a crossover method so instead of mutating only 1 of the best games, we take 2 of the best games and breed a child NeuralNetwork from their 2 results (which is called a crossover)
  4. If a game passes the level, don't mutate or crossover, as we already have a successful NeuralNetwork

Adding more inputs for TensorFlow JS

In the Ai class we are going to add in 3 more inputs for (isPlayerJumping, playerVelocity & canPlayerJump). Within the think() method after the existing 5 inputs, add in these additional inputs.

js/ai/Ai.js

// Is player jumping
inputs[5] = (game.gameApi.isPlayerJumping() ? 1 : 0);
inputsNormalised[5] = map(inputs[5], 0, 1, 0, 1);

// Player velocity
inputs[6] = (game.gameApi.getPlayerVelocity() ? 1 : 0);
inputsNormalised[6] = map(inputs[6], -1.1, 1.1, 0, 1);

// Can play jump?
inputs[7] = (game.gameApi.canPlayerJump() ? 1 : 0);
inputsNormalised[7] = map(inputs[7], 0, 1, 0, 1);
Then change the variable declaration for inputs in Ai class to 8

js/ai/Ai.js

#inputs = 8; 

Implement crossover within TensorFlowJS

In the NeuroEvolution class within the completeGeneration() method, we are going to modify the breeding section to make it a little smarter. Make the for loop look like this.

js/ai/NeuroEvolution.js

// Breeding
for (let i = 0; i < games.length; i++) {
  let bestPlayerA = this.pickBestGameFromFitnessPool(games);
  let bestPlayerB = this.pickBestGameFromFitnessPool(games);
  let child;

  child = this.mutateNeuralNetwork(this.crossoverNeuralNetwork(bestPlayerA.neuralNetwork.clone(), bestPlayerB.neuralNetwork.clone()));
 
  bestPlayerBrainsByFitness.push(child);
}
Now we need to add in the crossover method to the same file.

js/ai/NeuroEvolution.js

crossoverNeuralNetwork(neuralNetworkOne, neuralNetworkTwo) {
  let parentA_in_dna = neuralNetworkOne.input_weights.dataSync();
  let parentA_out_dna = neuralNetworkOne.output_weights.dataSync();
  let parentB_in_dna = neuralNetworkTwo.input_weights.dataSync();
  let parentB_out_dna = neuralNetworkTwo.output_weights.dataSync();

  let mid = Math.floor(Math.random() * parentA_in_dna.length);
  let child_in_dna = [...parentA_in_dna.slice(0, mid), ...parentB_in_dna.slice(mid, parentB_in_dna.length)];
  let child_out_dna = [...parentA_out_dna.slice(0, mid), ...parentB_out_dna.slice(mid, parentB_out_dna.length)];

  let child = neuralNetworkOne.clone();
  let input_shape = neuralNetworkOne.input_weights.shape;
  let output_shape = neuralNetworkOne.output_weights.shape;

  child.dispose();

  child.input_weights = tf.tensor(child_in_dna, input_shape);
  child.output_weights = tf.tensor(child_out_dna, output_shape);

  return child;
}
Reload your browser, and click the 'start evolution' button. You should start seeing games solve themselves a bit faster in fewer generations (normally around 20).

10% chance to crossover best game

Back in the NeuroEvolution class, within breeding section, let's add one final update so that on random occasions (10% chance), we do a crossover with the best game to date. Make the breeding section look like this

js/ai/NeuroEvolution.js

// Breeding
for (let i = 0; i < games.length; i++) {
  let bestPlayerA = this.pickBestGameFromFitnessPool(games);
  let bestPlayerB = this.pickBestGameFromFitnessPool(games);
  let bestPlayerC = this.#bestGames[0];
  let child;

  if ( random(1) < 0.1) {
    const ai = new Ai();
    let bestPlayerD = new NeuralNetwork(ai.inputs, ai.neurons, ai.outputs);
    child = this.mutateNeuralNetwork(this.crossoverNeuralNetwork(bestPlayerC.neuralNetwork.clone(), bestPlayerD));
  } else {
    child = this.mutateNeuralNetwork(this.crossoverNeuralNetwork(bestPlayerA.neuralNetwork.clone(), bestPlayerB.neuralNetwork.clone()));
  }

  bestPlayerBrainsByFitness.push(child);
}
We also need to expose getters in the Ai class for the input, neuron & output variables. Add the following methods:

js/ai/Ai.js

get inputs(){
  return this.#inputs;
}

get neurons(){
  return this.#neurons;
}

get outputs(){
  return this.#outputs;
}
Reload your browser, and click the 'start evolution' button. You should start seeing games solve themselves a bit faster in fewer generations (normally around 10-15).

Don't mutate on success

Now wrap the Breed functionality in an IF statement to ensure that if a game passes the level, we don't mutate or crossover, we just continue using the successful NeuralNetwork.

js/ai/NeuroEvolution.js

if ( false != gamePassedLevel ) {
  for ( let i = 0; i < games.length; i++ ) {
    if (games[i].gameApi.isLevelPassed() ) {
      games[i].neuralNetwork.save('neuralNetwork');
      for (let ii = 0; ii < games.length; ii++) {
          bestPlayerBrainsByFitness.push(games[i].neuralNetwork.clone());
        }
      }
    }

    console.log('Level Passed:', this.#bestGames[0], this.#bestGames.length, this.#bestGames);
    this.start(games, bestPlayerBrainsByFitness);
  } else {
    // Breeding
    for (let i = 0; i < games.length; i++) {
      let bestPlayerA = this.pickBestGameFromFitnessPool(games);
      let bestPlayerB = this.pickBestGameFromFitnessPool(games);
      let bestPlayerC = this.#bestGames[0];
      let child;

      if ( random(1) < 0.1) {
        const ai = new Ai();
        let bestPlayerD = new NeuralNetwork(ai.inputs, ai.neurons, ai.outputs);
        child = this.mutateNeuralNetwork(this.crossoverNeuralNetwork(bestPlayerC.neuralNetwork.clone(), bestPlayerD));
      } else {
        child = this.mutateNeuralNetwork(this.crossoverNeuralNetwork(bestPlayerA.neuralNetwork.clone(), bestPlayerB.neuralNetwork.clone()));
      }

      bestPlayerBrainsByFitness.push(child);
    }
 
   this.start(games, bestPlayerBrainsByFitness);
}
Reload your browser, and click the 'start evolution' button. Once enough evolutions process to pass the level, you will notice that all future games in evolutions will start passing consistently.

This is a far as we will take this tutorial in regards to evolving and speeding up our NeuroEvolution logic. Next we will move onto saving/loading our NeuralNetwork models.

Saving & Loading our NeuralNetwork models

The last piece to implement is the saving and loading functionality of our NeuralNetwork. This is so once you have a NeuralNetwork that works you can save it and load it back when needed. We will be implementing the:
  1. Ability to automatically save a NeuralNetwork that passes to localStorage
  2. Ability to manually save best NeuralNetwork to localStorage
  3. Ability to manually save best NeuralNetwork to disk
  4. Ability to load from local storage
  5. Ability to load from disk

First we need to add the ability to save within the NeuralNetwork.js file. Add these 2 methods

js/ai/NeuralNetwork.js

stringify() {
  let neuralNetworkToSave = {
    input_weights: this.input_weights.arraySync(),
    output_weights: this.output_weights.arraySync()
  };

  return JSON.stringify(neuralNetworkToSave);
}

save( key ) {
  localStorage.setItem(key, this.stringify());
}

Automatically save a NeuralNetwork that passes to localStorage

In the NeuroEvolution. class within the method finishGeneration(). Add in the below to the IF statement when a game level is passed.

js/ai/NeuroEvolution.js

games[i].neuralNetwork.save('neuralNetwork');
So it should look like this:

js/ai/NeuroEvolution.js

for ( let i = 0; i < games.length; i++ ) {
  if (games[i].gameApi.isLevelPassed() ) {
    games[i].neuralNetwork.save('neuralNetwork');
    for (let ii = 0; ii < games.length; ii++) {
      bestPlayerBrainsByFitness.push(games[i].neuralNetwork.clone());
    }
  }
}

console.log('Level Passed:', this.#bestGames[0], this.#bestGames.length, this.#bestGames);
this.start(games, bestPlayerBrainsByFitness);
Your game will now automatically save the NeuralNetwork model to localStorage key neuralNetwork if it passes the level.

Manually save best NeuralNetwork to localStorage

To manually save to local storage add the below code to ui.js

js/ai/ui.js

document.querySelector("#btn-ml-save-neuralnetwork-localstorage").addEventListener('click', function (event) {
  if( neuroEvolution.bestGames.length > 0 ) {
    neuroEvolution.bestGames[0].neuralNetwork.save('neuralNetwork')
  }
});

Manually save best NeuralNetwork to disk

To manually save to disk you can add the below code to ui.js

js/ai/ui.js

document.querySelector("#btn-ml-save-neuralnetwork-disk").addEventListener('click', function (event) {
  if( neuroEvolution.bestGames.length > 0 ) {
    let neuralNetworkJSON = neuroEvolution.bestGames[0].neuralNetwork.stringify();
    let a = document.createElement("a");
    let file = new Blob([neuralNetworkJSON], {type: 'application/json'});
    a.href = URL.createObjectURL(file);
    a.download = 'neuralNetwork.json';
    a.click();
  }
});

Loading NeuralNetwork Models

To load from local storage or disk we need to create a method to handle loading a NeuralNetwork into memory. Create the below method in ui.js (there is probably a better file location for this method now that I think about it).

js/ai/ui.js

const loadNeuralNetwork = (neuralNetworkData) => {
  const ai = new Ai();
  let neuralNetwork = new NeuralNetwork(ai.inputs, ai.neurons, ai.outputs);
  neuralNetwork.dispose();

  neuralNetwork.input_weights = tf.tensor(neuralNetworkData.input_weights);
  neuralNetwork.output_weights = tf.tensor(neuralNetworkData.output_weights);

  let neuralNetworks = [];
  for ( let i = 0; i < ai.totalGames; i++ ) {
    neuralNetworks.push(neuralNetwork);
  }

  let games = neuroEvolution.pausedGames;
  neuroEvolution.pausedGames;
  neuroEvolution.reset();

  neuroEvolution.start(games, neuralNetworks);
};

We also need to add the below method into the Ai class.

js/ai/Ai.js

get totalGames(){
  return this.#totalGames;
}

Load from local storage

Now to load from localStorage into memory, add the below into ui.js

js/ai/ui.js

document.querySelector("#btn-ml-load-neuralnetwork-localstorage").addEventListener('click', function (event) {
  cachedLevelSections = [];
  let games = neuroEvolution.pausedGames;
  neuroEvolution.pausedGames;
  neuroEvolution.reset();

  let neuralNetworkData = localStorage.getItem('neuralNetwork');

  loadNeuralNetwork(JSON.parse(neuralNetworkData));
});
We also need to add the reset method into the NeuroEvolution class.

js/ai/NeuroEvolution.js

reset() {
  this.#bestGames = [];
  this.#generation = 1;
  this.#pausedGames = [];
  this.#pausedBestNeuralNetworksByFitness = [];
  this.#pauseBeforeNextGeneration = false;
}

Load from disk

Now to load from disk into memory, add the below into ui.js

js/ai/ui.js

document.querySelector("#btn-ml-load-neuralnetwork-disk").addEventListener('change', function (event) {
  let file = this.files[0];
  let reader = new FileReader()
  let textFile = /application\/json/;
  let fileText = '';

  if (file.type.match(textFile)) {
    reader.onload = function (event) {
       let importedNeuralNetwork = JSON.parse(event.target.result);

       loadNeuralNetwork(importedNeuralNetwork);
    }
  }

  reader.readAsText(file);
});
Reload your browser, and click the 'start evolution' button. You will notice if you inspect Chrome DevTools you will see a localStorage key called 'brain' once a level is passed.


You can also now also use the buttons in the left hand menu to save and load the best NeuralNetwork to disk.

Within the GitHub codebase within the models/ directory you will see 3 existing models that can be loaded up to pass levels 1, 2 & 3.

Try it yourself and get your NeuroEvolution implementation to pass Level 1, then Level 2, then finally Level 3.

I get consistent results along the lines of:

  • Level 1: Takes 5-20 generations
  • Level 2: Takes 5-20 generations
  • Level 3: Takes 40-700 generations (as it has to learn to jump blocks and gaps).

Congratulations!

I hope this tutorial was useful for you to learn how to use TensorFlowJS to build a NeuroEvolution implementation. Any questions leave them in the comments below, or tweet me on twitter at @dionbeetson

Source code

All source code for this tutorial can be found here https://github.com/dionbeetson/neuroevolution-experiment.

Part 3 - coming soon...

Coming soon and will be using image recognition to solve the same browser based game.

NeuroEvolution using TensorFlowJS - Part 1

Introduction


This tutorial will walk you through how to implement NeuroEvolution using TensorFlow JS. This NeuralNetwork will learn how to play a simple browser based game that requires a player to jump over blocks and gaps. It is based on the source code found on my GitHub account here https://github.com/dionbeetson/neuroevolution-experiment.

The difference in this solution compared to other solutions out there is that instead of building ML directly into the core game source code (like I saw in a lot of examples); the ML and Game source code are completely decoupled. This simulates a much more realistic real world example, as you would rarely have direct access to the source code when applying ML (you would only have access to specific inputs). I created an an API/SDK for the browser based game to expose some key functionality (the inputs the NeuralNetwork needs), but end state is to use image analysis so this solution is more adaptable to other applications.

References

Although I wrote this codebase myself I took a lot of input/influence from a huge range of great tutorials that already exist. You can see a list of the key tutorials/repos I learned from on the GitHub Readme for this project here.

Let's get started!

Setup

Clone this repo from GitHub:
git clone git@github.com:dionbeetson/neuroevolution-experiment.git
Then run in terminal the below to setup the repository for this tutorial:
npm install

npm run setup-tutorial
This basically moves the js/ai directory to js/ai-source, and leaves everything else in place. If you ever need to refer back to the original source code use js/ai-source as reference.

Now run the below to startup the app:
npm run dev
The browser will load up the application, but you will see 404 errors within the DevTools console. You will though however, have a working browser game. Click 'Play game', and use the spacebar to jump to test things out. Throughout this tutorial you are going to be building a NeuroEvolution implementation to learn how to automatically solve this game.

Quick overview of the UI

  • Left section: Includes base controls for Manual and AI interactions. In order from top to bottom
    • Level: You can select the level (there are currently 3 levels available in the game in order of complexity)
    • Play game: Play an user interacted game
    • Enable drawing: Whether you want to render the drawing on canvas
    • Speed: How fast the game will run
    • Start Evolution: Start the NeuroEvolution
    • Save to localStorage: Save best current NeuralNetwork into localStorage
    • Save to disk: Save best current NeuralNetwork to disk
    • Load from localStorage: Load current NeuralNetwork in local storage into memory and start NeuroEvolution
    • Load from disk: Load a NeuralNetwork from disk into memory and start NeuroEvolution
    • Pause after generation: For debugging, pause after each evolution so you can see / debug it
  • Middle section: The game(s) render within the large middle column
  • Right section: Is used to display debugging information for the NeuroEvolution implementation

This tutorial has 4 key files

For the entire tutorial we will be working within the js/ai/ directory.
  1. ui.js: Controls the UI interactions
  2. NeuralNetwork.js: Is the base neural network
  3. Ai.js: This class instantiates (by default 9) games & corresponding NeuralNetwork instances
  4. Neuroevolution.js: This class will run up to 1500 generations of Ai.js until it successfully passes the selected level

Setup base structure

Let's start to build out enough base logic to be able to predict if we should jump or not using TensorFlowJS.

Create a directory js/ai, and create a file called js/ai/ui.js which will handle basic UI controls. Within this file we want to instantiate the NeuroEvolution class (that we are about to create, and bind a UI button to start the evolution process).

js/ai/ui.js

let neuroEvolution = new NeuroEvolution();

document.querySelector("#btn-ml-start").addEventListener('click', function (event) {
  neuroEvolution.start([]);
}, false);
Now we need to create the skeleton of NeuralNetwork.js, Ai.js & Neuroevolution.js.

For the NeuralNetwork let's just start with a constructor that allows us to send input_node/hidden_node & output_node count arguments.

js/ai/NeuralNetwork.js

class NeuralNetwork {
  constructor(input_nodes, hidden_nodes, output_nodes) {
    // The amount of inputs (eg: player y position, height of next block etc..)
    this.input_nodes = input_nodes;
    // Amount of hidden nodes within the Neural Network)
    this.hidden_nodes = hidden_nodes;
    // The amount of outputs, we will use 2 (will be needed for level 3)
    this.output_nodes = output_nodes;

    // Initialize random weights
    this.input_weights = tf.randomNormal([this.input_nodes, this.hidden_nodes]);
    this.output_weights = tf.randomNormal([this.hidden_nodes, this.output_nodes]);
  }
}
Now we need to create the Ai class. This will include a method that will create 1 game for now and link it with a NeuralNetwork instance. We will start with a start() method to create instances of a NeuralNetwork, a checkGame() method that will be called every 50ms which will call the think() method that we will expand to make the actual prediction to jump or not jump.

js/ai/Ai.js

class Ai {
  #totalGames = 1; // Will increase to 9 games later
  #inputs = 5;
  #neurons = 40;
  #outputs = 2;
  #games = [];
  #gamesRunning = 0;
  #sectionsToSeeAhead = 1;
  #timeTakenDateStart = null;

  start(useImageRecognition, neuralNetworks, completeCallback) {
    this.#timeTakenDateStart = new Date();

    for ( let i = 0; i < this.#totalGames; i++ ) {
      let neuralNetwork;

      if ( undefined !== neuralNetworks && neuralNetworks[i] instanceof NeuralNetwork ) {
        neuralNetwork = neuralNetworks[i];
      } else {
        neuralNetwork = new NeuralNetwork(this.#inputs, this.#neurons, this.#outputs);
      }

      let gameApi;

      if ( useImageRecognition ) {
        gameApi = new GameImageRecognition();
      } else {
        gameApi = new GameApi();
      }

      this.#games[i] = {
        gameApi: gameApi,
        neuralNetwork: neuralNetwork,
        interval: null
      }

      // Debug look ahead
      this.#games[i].gameApi.setHighlightSectionAhead(this.#sectionsToSeeAhead)

      // Start game
      this.#gamesRunning++;
      this.#games[i].gameApi.start();

      this.#games[i].interval = setInterval(this.checkGame.bind(null, this, this.#games, this.#games[i]), 50);
    }
  }

  checkGame(ai, games, game) {
    if( game.gameApi.isSetup() ) {
      ai.think(game);
    }
  }

  think(game) {
  }
}
Now create the NeuroEvolution class that will be responsible for running multiple evolutions of Ai.js until we get an evolution that passes the level.

js/ai/NeuroEvolution.js

class NeuroEvolution {
  #generation = 1;
  #maxGenerations = 1500;
  #useImageRecognition = false;

  start(games, bestPlayerBrainsByFitness) {

    if ( this.#generation < this.#maxGenerations ) {

      for ( let i = 0; i < games.length; i++ ) {
        games[i].gameApi.remove();
      }

      games = undefined;

      this.#generation++;

      const ai = new Ai(this.finishGeneration.bind(this));
      ai.start(this.#useImageRecognition, bestPlayerBrainsByFitness);
    } else {
      this.enableSpeedInput();
    }
  }

  finishGeneration(games, timeTaken) {
   // TODO
  }

  updateUIRoundInformation() {
    document.querySelector("#round-current").innerHTML = this.#generation;
    document.querySelector("#round-total").innerHTML = this.#maxGenerations;
    document.querySelector("#round-progress").style.width = '0%';
    document.querySelector("#generation-progress").style.width = (this.#generation/this.#maxGenerations)*100 + '%';
  }
}
Now you have your base structure in place.

Reload your browser (http://127.0.0.1:8080/), and click the 'Start evolution' button. You should see 1 game playing, and failing (no jumping), no matter how many times you reload the page. That is because we haven't implemented the prediction logic. Let's implement that using TensorFlowJS in a moment.

Quickly, before that, in the Ai class, let's create 9 games at once instead of 1, as NeuroEvolution will be incredibly slow with only 1 NeuralNetwork at a time. Depending on your computer specs you can increase this to a higher number. I did find that 9 worked quite well though.

js/ai/Ai.js

#totalGames = 9
Reload your browser, and click 'Start evolution' button again. You should see 9 games playing.

Predicting whether to jump or not

To use TensorflowJS to predict to jump, we need to modify a few files. First in Ai.js in the think() method add the below logic in. Essentially we are accessing public information that the JS game exposes in js/game/GameAPI.js (like player position, next block height etc..) and then normalising all inputs to be between 0-1 as TensorFlow JS requires this.

js/ai/Ai.js

think(game) {
  let inputs = [];
  let inputsNormalised = [];

  // Player y
  inputs[0] = (game.gameApi.getPlayerY());
  inputsNormalised[0] = map(inputs[0], 0, game.gameApi.getHeight(), 0, 1);

  // Player x
  inputs[1] = game.gameApi.getPlayerX();
  inputsNormalised[1] = map(inputs[1], inputs[1], game.gameApi.getWidth(), 0, 1);

  let section = game.gameApi.getSectionFromPlayer(this.#sectionsToSeeAhead);

  // 2nd closest section x
  inputs[2] = section.x + section.width;
  inputsNormalised[2] = map(inputs[2], inputs[1], game.gameApi.getWidth(), 0, 1);

  // 2nd closest section y
  inputs[3] = section.y;
  inputsNormalised[3] = map(inputs[3], 0, game.gameApi.getHeight(), 0, 1);

  // 2nd closest section y base
  inputs[4] = section.y + section.height;
  inputsNormalised[4] = map(inputs[4], 0, game.gameApi.getHeight(), 0, 1);

  // Call the predict function in the NeuralNetwork
  let outputs = game.neuralNetwork.predict(inputsNormalised);

  // If input is about 0.5 then jump, if not, stay still
  if ( outputs[0] > 0.5 || outputs[1] > 0.5 ) {
    game.gameApi.jump();
  }
}
We also will need to create the predict() method in the NeuralNetwork class. This method creates an input_layer, hidden_layer and output_layer and returns 2 predictions (which are both numbers between 0-1).

js/ai/NeuralNetwork.js

predict(user_input) {
  let output;
  tf.tidy(() => {
    let input_layer = tf.tensor(user_input, [1, this.input_nodes]);
    let hidden_layer = input_layer.matMul(this.input_weights).sigmoid();
    let output_layer = hidden_layer.matMul(this.output_weights).sigmoid();
    output = output_layer.dataSync();
  });
  return output;
}
Reload your browser, and click the 'start evolution' button.

You will now see 9 games playing, and some should be jumping, and some not. This is completely random. Reload a few times if you need to to ensure this is the behaviour you are seeing.

Once all of your players die you will notice the game stops. As of now, we have used TensorFlow JS to make a prediction about whether to jump or not. This is based on a set of inputs (player X, player Y & section ahead height/Y).

Now we need to add in the NeuroEvolution aspect so that we pick the best progressed games and start a new evolution with those NeuralNetworks (but we will evolve/mutate them slightly before hand).

In NeuroEvolution add a method called calculateFitness(). This method iterates through all games once finished, creates a fitness rating which is just the % progress of the game. It then has logic to increase the fitness of better performing games, so that later on in our logic, there is a higher chance the better performing NeuralNetworks are chosen for the next evolution. Hope that all makes sense.

js/ai/NeuroEvolution.js

calculateFitness(games) {
  for ( let i = 0; i < games.length; i++ ) {
    let game = games[i];
    games[i].fitness = game.gameApi.getProgress() / 100;
    games[i].score = game.gameApi.getScore();
    games[i].progress = game.gameApi.getProgress();
  }

  // The below code makes the better progressed games have a higher fitness so they have a higher chance of being selected for next generation
  games.sort(this.sortByFitness);
  games.reverse();

  let prev = 0;
  for ( let i = 0; i < games.length; i++ ) {
    games[i].fitness = this.#discountRate * prev + games[i].fitness;
    prev = games[i].fitness;
  }

  games.sort(this.sortByFitness);

  return games;
}
In NeuroEvolution.js add a method that will check if at least 1 game has passed the level in the current evolution.

js/ai/NeuroEvolution.js

didAtLeastOneGameCompleteLevel(games) {
  for ( let i = 0; i < games.length; i++ ) {
    if (games[i].gameApi.isLevelPassed() ) {
      return games[i];
    }
  }

  return false;
}
In NeuroEvolution add a method that will pick the exact best player with the highest fitness. We use this to display and keep a track of the best performing NeuralNetwork.

js/ai/NeuroEvolution.js

pickBestGameByActualFitness(games){
  let game;
  let prevFitness = 0;
  for ( let i = 0; i < games.length; i++ ) {
    if (games[i].fitness > prevFitness) {
      game = games[i];
      prevFitness = game.fitness;
    }
  }

  return game;
}
In NeuroEvolution add a method that will pick one (not always the best like the above method) of the best players with the highest fitness

js/ai/NeuroEvolution.js

pickBestGameFromFitnessPool(games) {
  let index = 0;
  let r = random(1);

  while (r > 0 ) {
    if( undefined !== games[index] ) {
      r = r - games[index].fitness;
      index++;
    } else {
      r = 0;
    }
  }
  index--;

  let game = games[index];

  return game;
}
In NeuroEvolution we can now improve the finishGeneration() method with the below logic. This code will:
  1. Calculate fitness for all 9 finished games
  2. Store the best player in a local variable
  3. Add the best player to the bestGames[] array
  4. Ensure we only keep the best 5 games (for memory/performance reasons)
  5. Iterate over all games and mutate the best performing NeuralNetworks into new NeuralNetworks for the next evolution
  6. Start the next NeuroEvolution

js/ai/NeuroEvolution.js

finishGeneration(games, timeTaken) {
  games = this.calculateFitness(games);

  // Did one of the games finish?
  let gamePassedLevel = this.didAtLeastOneGameCompleteLevel(games);

  let bestPlayerByFitness = gamePassedLevel;
  let bestPlayerBrainsByFitness = [];

  if( false === bestPlayerByFitness ){
    bestPlayerByFitness = this.pickBestGameByActualFitness(games);
  }

  this.#bestGames.push(bestPlayerByFitness);
  this.#bestGames.sort(this.sortByFitness);

  // Only keep top 5 best scores
  if( this.#bestGames.length > 5 ) {
    this.#bestGames = this.#bestGames.slice(0, 5);
  }

  // Breeding
  for (let i = 0; i < games.length; i++) {
    let bestPlayerA = this.pickBestGameFromFitnessPool(games);
    let child;

    child = this.mutateNeuralNetwork(bestPlayerA.neuralNetwork.clone());

    bestPlayerBrainsByFitness.push(child);
  }

  this.start(games, bestPlayerBrainsByFitness);
}
Lastly, in NeuroEvolution you will need to add the below variable declarations.

js/ai/NeuroEvolution.js

  #discountRate = 0.95;
  #bestGames = [];
Reload your browser, and click the 'start evolution' button. You should again see 9 games playing, some will also be jumping like last time. However, it still wont progress past the first evolution. This is because we need to wire up Ai.js to call the callback method in the checkGame method and add some logic to check if the game is over. Let's update the checkGame() method to look like the below.

js/ai/Ai.js

checkGame(ai, games, game) {
  if( game.gameApi.isOver() ) {
    clearInterval(game.interval);

    ai.#gamesRunning--;
    document.querySelector("#round-progress").style.width = ((games.length-ai.#gamesRunning)/games.length)*100 + '%';

    if( ai.areAllGamesOver(games) && 0 == ai.#gamesRunning ) {
      let timeTakenDateComplete = new Date();
      let timeTaken = (timeTakenDateComplete - ai.#timeTakenDateStart) / 1000;

      ai.#completeCallback(games, timeTaken);
    }
  } else {
    if( game.gameApi.isSetup() ) {
      ai.think(game);
    }
  }
}
We also need to add the following variable declarations to Ai class.

js/ai/Ai.js

#completeCallback;
Reload your browser, and click the 'start evolution' button.

You should see an error as we didn't declare the method areAllGamesOver(). Let's quickly add the below to Ai

js/ai/Ai.js

areAllGamesOver(games) {
  for ( let i = 0; i < this.#totalGames; i++ ) {
    if( false == games[i].gameApi.isOver() ) {
      return false;
    }
  }

  return true;
}
... Another error, we forgot to set the completeCallback. In Ai, create a constructor up the top after the variable declaration.

js/ai/Ai.js

constructor(completeCallback) {
  this.#completeCallback = completeCallback;
}
Reload your browser, and click the 'start evolution' button.

Ok, we are making progress, but we are now missing the clone() method. We need to be able to clone NeuralNetworks after each generation so we don't interfere with previous NeuralNetwork objects.

In NeuralNetwork class add the clone() method as well as the dispose() method, as that is called from within the clone() method.

js/ai/NeuralNetwork.js

clone() {
  return tf.tidy(() => {
    let clonie = new NeuralNetwork(this.input_nodes, this.hidden_nodes, this.output_nodes);
    clonie.dispose();
    clonie.input_weights = tf.clone(this.input_weights);
    clonie.output_weights = tf.clone(this.output_weights);
    return clonie;
  });
}

dispose() {
  this.input_weights.dispose();
  this.output_weights.dispose();
}
Reload your browser, and click the 'start evolution' button. You will see we are close now, we are just missing the mutateNeuralNetwork() method. This method is responsible for slightly tweaking the cloned NeuralNetwork so that you get a slightly different result in the next evolution. Let's go ahead and add the mutateNeuralNetwork() method into the NeuroEvolution class. I'm not going to go into more detail on this, but you can google it and find this method in a few other examples out there. I also wasn't the original author of this, I just adjusted it to work for my implementation. See GitHub for reference to original source code.

js/ai/NeuralEvolution.js

mutateNeuralNetwork(b) {
  function fn(x) {
    if (random(1) < 0.05) {
      let offset = randomGaussian() * 0.5;
      let newx = x + offset;
      return newx;
    }
    return x;
  }

  let neuralNetwork = b.clone();
  let ih = neuralNetwork.input_weights.dataSync().map(fn);
  let ih_shape = neuralNetwork.input_weights.shape;
  neuralNetwork.input_weights.dispose();
  neuralNetwork.input_weights = tf.tensor(ih, ih_shape);

  let ho = neuralNetwork.output_weights.dataSync().map(fn);
  let ho_shape = neuralNetwork.output_weights.shape;
  neuralNetwork.output_weights.dispose();
  neuralNetwork.output_weights = tf.tensor(ho, ho_shape);
  return neuralNetwork;
}
Reload your browser, and click the 'start evolution' button. Now after each of the 9 games fail the first time, the UI will start a new evolution. If you let this go for a few minutes you should see the game get solved - it normally takes around 30-50 generations with this current implementation.

Congratulations!

This is a very simple implementation of NeuroEvolution. In Part 2, we will go through making improvements to really speed things up including:
  • Implementing crossover within TensorFlowJS
  • Using the best progressing NeuralNetwork to ensure faster NeuroEvolution
  • Saving and loading models
  • Adding debugging information

Source code

All source code for this tutorial can be found here https://github.com/dionbeetson/neuroevolution-experiment.

Part 2

Continue on to NeuroEvolution using TensorFlowJS - Part 2