Note: If you like our article, don’t forget to click on alibaba Nanjing technology special issue! This article is reprinted from Alibaba Nanjing technology special issue – Zhihu, welcome danniu Niu niu to apply for the position of front-end/back-end development in Ali Nanjing, please see Ali Nanjing inviting front-end partners to join us.

Keywords: Tensorflow, JavaScript, AI, front-end development, artificial intelligence, neural network, genetic algorithm

First, the final effect

T-rex Runner is an Easter egg game hidden in Chrome. I recently developed a completely independent AI program running in the browser environment using the newly released Tensorflow. js. As shown in the picture below, THE AI can easily control T-Rex to avoid obstacles.

After 3 attempts, the AI gradually learned how to control the Tyrannosaurus to avoid obstacles

With the introduction of genetic algorithms, the AI learns to control after 2 attempts

View the online demo

  • Neuro – Only supported for Chrome Desktop
  • Genetic Algorithms + Neural Networks – Only supported for Chrome desktop

Download or bookmark my source code on Github

  • MagicCube/t-rex-run

An overview of the

About the T-Rex Runner Egg game

As a Chrome diehard, you’ve probably already spotted the “T-Rex Runner” game hidden in the Chrome “Cannot connect to the Internet” error page.

If you haven’t played T-Rex Runner yet, follow these steps to unlock the egg:

  1. Open Chrome, type Chrome ://dino in the address bar, and press Enter;
  2. You will see the error screen above, but it is still, don’t be afraid that this is the entrance of the egg;
  3. Hit the space bar and start the game!

Your task is to keep going without hitting cactuses or airborne pterosaurs, and the longer you hold out the more points you get and the more difficult it gets.

About TensorFlow. Js

TensorFlow, the open source organization that has been a hot topic in deep learning, finally released its first JavaScript version in March 2018. Tensorflow. js can perform basic tasks such as model training, execution, and retraining on the browser side, and with the help of WebGL technology, it is capable of GPU hardware acceleration just like Python and C++ versions.

Tensorflow.js is an example of how to use tensorflow.js, and how to use tensorflow.js.

About this article

The goal of this paper is to build an artificial neural network on the browser side based on Tensorflow. js, and make AI learn how to control tyrannosaurus to successfully avoid obstacles through repeated training. The structure of this paper is as follows:

  1. Revamp the game program: introduce the core code logic of the game, use ES6 and other technology stacks to reconstruct the game code, and introduce new game lifecycle events.
  2. Realization of algorithm model: focus on how to realize the AI algorithm model based on artificial neural network.
  3. Integrated algorithm model: Integrate the algorithm model with the game.
  4. Optimizing the algorithm model: By increasing the number of AI players and tyrannosaurus, we can easily improve machine learning without changing the algorithm model.
  5. conclusion

1. Reprogram the game

1.1 Reconstruction with modern front-end technology stack

The source code for T-Rex Runner can be found in the Chromium repository, but this little game was written in 2014 using ES5 era technology, and worse due to the lack of modularity, the entire game source code is in the same file, This greatly increases the difficulty of understanding and modifying the source code.

So I spent the first afternoon rewriting the T-Rex-Runner project with a modern front-end stack like ES6/ES7 + LESS + Webpack and introducing ESLint to ensure code quality.

I also got rid of sound, mouse controls, mobile support, GameOver graphics, and even put in a Multiplayer Mode for genetic algorithms later.

The code has been uploaded to Github and can be found in the SRC /game directory.

1.2 Game core code

T-rex-runner is a pretty standard object-oriented programming game program, and in fact you can use it as a classic example of getting started with HTML5 game development. The reconstructed T-Rex-Runner project mainly includes the following types:

  • Runner class: This is the core of the game, in charge of the entire game lifecycle, the main class members include:

    • CurrentSpeed property: Indicates the current game speed. The longer the player holds the game, the faster the speed, and the higher the difficulty.
    • The init () method: is responsible for initialization according to the config parameterCanvas,Horizon,DistanceMeter,TRexGroupClass, and fired for the first timerestart() 和 update() 。
    • Restart () method: reset all run-time parameters to restart a new game.
    • The update () method: Refreshes and redraws the current framerequestAnimationFrame()Call, approximately 60 frames per second (byRuntime.getFPS()Method determined).

  • Trex: Represents a T-rex, or tyrannosaurus Rex. The main members of Trex include:

    • Jumping property: indicates whether the current Tyrannosaurus rex is in a jumping state (jumping, jumping, or landing medium)true).
    • The reset () method: Resets all parameters of tyrannosaurus fromRunner.restart()Called before the game restarts
    • StartJump () method: Control the tyrannosaur jump, used to avoid cactus.
    • SetDuck () method: control tyrannosaurus to crawl, used to avoid low-flying pterosaurs.

  • TrexGroup class: represents a population of n Tyrannosaurs, which was not present in the original code. The population concept was created to support multi-player mode, where n tyrannosaurs play the same game in their own way. In addition to supporting most methods of the Trex class, it also includes:

    • Method: Obtain the number of living Tyrannosaurs in the current population.

  • Obstacle class: represents obstacles, such as cacti of various heights and widths and pterosaurs in the air. The main groups include:

    • Type attribute: Indicates the current obstacle type, including CACTUS_SMALL/CACTUS_LARGE and PTERODACTYL.
    • Width and height properties: Indicates the size of the obstacle.
    • XPos and yPos properties: Represent the location of obstacles.

In addition to the above core types, others include:

  • Horizon: Represents the background or scene of the whole game. Those familiar with game development must know that it is similar to the concept of stage/scene/background in many frameworks. In this game, there are clouds, stars, moon and the most important Obstacles, like diction.
  • Horizononline Class: Represents the horizon, the bumpy road surface that helps you push out the current “speed.”
  • CollisionBox class: represents a rectangle. Usually, a Trex or Obstacle can use several rectangles to form an approximate polygon for calculating polygon collisions.
  • Cloud class: represents clouds, this is for future computer image recognition, used as interference items.
  • **DistanceMeter class: ** represents the DistanceMeter in the upper right corner.
  • ImageSprite module: Classic Sprite maps.
  • Constants module: Used to store default configuration parameters for the game.
  • Utils module: contains common tool methods.

1.3 Provide life cycle events

In order for the AI to participate in the game instead of humans, we need to have an output class method like trex.startjump (), but also provide the necessary events as inputs in the Runner class:

  • OnReset () event: This event is triggered when the game restarts, and the training of the AI model is normally completed in this event.
  • OnRunning () event: Every Tyrannosaurus rex without Crash will crash every timeupdate()After the event is triggered, the return value of the event will be used asactionwhenaction 为 1, indicates that the jump will be performed,0Is kept unchanged. This event can be used to monitor the state of the game and command the Tyrannosaurus rex to change its jump state at a specific time.
  • OnCrash () event: when tyrannosaurus collides with a cactus or pterosaur, this event will be triggered, which can be used to evaluate the effect of AI model execution. For example, in the genetic algorithm, it can be used to calculate the ranking of a tyrannosaurus model in a population.

Here is a sample program based on the above lifecycle events:

letrunner = null; / / noletrankList = []; // Initialize the game.function setup() {// create game run time runner = new runner ()'.game'{T_REX_COUNT: 10, // there are 10 tyrannosaurus dragons in each game. handleCrash } ); // initialize runner. Init (); }let firstTime = true; // This method is called every time the game restarts. // The tRexes parameter indicates the current tyrannosaur population.function handleReset({ tRexes }) {
  if (firstTime) {
    firstTime = false; Trexs.foreach ((tRex) => {// Randomly initialize each tyrannosaur model // minDistance in this case represents the minimum allowable distance between obstacles tRex. Model = {minDistance: Math.random() * 50 }; }); }else{// Print ranklist.foreach ((tRex, I) => console.info(I + 1, trex.model.mindistance)); // Clear the rank ranklist.splice (0); }} // While the game is running, a living Tyrannosaurus will continuously call this method to ask if it wants to jump. The tRex parameter represents the tyrannosaurus in the current context. // In the state parameter, obstacleX stands for the abscess of the nearest obstacle, obstacleWidth // stands for the width of the obstacle, and speed stands for the current global game speed. // The method returns 1 for jump and 2 for invariant.function handleRunning({ tRex, state }) {
  if(state.obstacleX <= tRex.model.minDistance && ! Trex.jumping) {// We use an artificial intelligence: // If the current obstacle reaches the threshold, the tyrannosaurus will jumpreturn 1;
  }
  return0; } const deadTrexes = []; // This method is called when the Tyrannosaurus crash.functionHandleCrash ({tRex}) {// Record the rank, last crashed tyrannosaur is first ranklist.unshift (tRex); } / / order DOMContentLoaded event to trigger the setup () method of the document. The addEventListener ('DOMContentLoaded', setup);
Copy the code

2. Implement the algorithm model

2.1 Algorithm model that junior high school students can understand

The word “algorithm model” may sound too high to be measured for the front end students who are new to AI. In fact, it is not. Let’s close the textbook and take a look at the following simple formula that we have learned in junior high school:

In the formula, X is inputs, Y is outputs, and F (x) is the core function of the model. Such as:

  • when

    When, because isLinear Function (Linear Function)So it is calledLinear ModelIn addition to the function formula, the model also containsweight,biasFor example, it is said that if there is one more formula in zhihu articles, there will be n fewer readers. This is a typical linear model **; 民运分子

In fact, AI’s decision to jump is also a linear model, expressed as a linear function:

ObstacleX and obstacleWidth are the inputs that come from the state argument to the handleRunning() method, where: – obstacleX stands for the abscess of the nearest obstacle. – obstacleWidth stands for the width of the obstacle. – Speed stands for the current global game speed. When y output is less than 0, a jump is required.

Where w1 and w2 respectively represent the weight of obstacleX and obstacleWidth, and B is the offset (Bias), both of which are parameters of the linear model.

Different from junior middle school mathematics, the input and output are usually vectors, rather than scalar ** and ** and mostly linear operations as in the previous examples. Don’t be scared off by linear math and formulas. “Algorithm” is not exactly “math”, let alone “arithmetic”. Read on.

2.2 Prediction, training and evaluation

Predict Prediction

In machine learning, when the input term x and the model y are given, it is called predict ** process.

Training Training

The process of adjusting parameters W1, W2 and B in the model until the “best effect” is known as the train process through known input x and output Y, while Y is also called label because it is a known output. Groups of X and Y together are known as training data sets. ** Training often needs to be repeated many times to achieve “optimal results”.

Evaluation of Evaluation

In the training process, x in the training data set is taken as the input item, the prediction process is performed, the prediction result is compared with the actual result of label Y, and a score is obtained through a function to represent the fitting ability of the current model. Known as the evaluatie process, this function is called the evaluatie function or loss function.

Machine learning is a model training process of continuous training and evaluation iteration. The better the training, the more accurate the future prediction.

The contents in section 2.1 and 2.2 are the summary of the author’s own working practice for many years. Please understand that there are unavoidable differences with the textbooks. The definitions of relevant terms shall be subject to the textbooks.

2.3 Define the abstract class of algorithm model

Before formally entering the implementation of AI algorithm, we also need to define a general object-oriented AI Model — Model Abstract class, whose members mainly include:

  • Predict (inputX) method: According to the giveninputXTo predictyValue and return it.
  • Train (Inputs, labels) method: Optimize model parameters based on inputs and labels.
  • Fit (inputs, labels) method: Repeated executiontrain()Method, the stop condition can be executed to a certain number of times, can also be whenloss()The mean square error returned by the method is less than a threshold.
  • Loss (predictedYs, Labels) method: According to the predicted value and the actual label value, an evaluation value is calculated. The smaller the value is, the better the current model fits. The default value is mean squared error, which is to subtract the label value from each predicted value and square it to find the average value of the square.

InputX, inputs, labels, etc. are vectors. You can use arrays. In tensorflow. js you need tf.Tensor.

In this project, the Model abstract class is the base class for all algorithmic models. Let’s look at the source code for the simplest Model, the random Model:

import Model from '.. /Model'; // Random models inherit from ModelexportDefault class RandomModel extends Model {weights = []; biases = [];init() {// initialization is a random process this.randomize(); } predict(inputXs) {const inputX = inputXs[0]; const y = this.weights[0] * inputX[0] + this.weights[1] * inputX[1]+ this.weights[2] * inputX[2] + this.biases[0];returny < 0 ? 1:0; } inputs, labels {// train(inputs, labels) { this.randomize(); }randomizeThis.weights [0] = random(); this.weights[1] = random(); this.weights[2] = random(); this.biases[0] = random(); }}function random() {
  return (Math.random() - 0.5) * 2;
}
Copy the code

Author’s note: Don’t underestimate this model, using genetic algorithms, random model can also control tyrannosaurus to avoid obstacles, but the learning efficiency is slightly lower, please watch the Demo on the desktop Chrome.

2.4 Define the input and output of the algorithm model

Input item

In simple terms, we first convert the state JSON parameter obtained by the handleRunning() method in Section 1.3 into a three-dimensional vector, namely a three-dimensional array, and normalize it. Normalize ** can be understood as a function that converts a scalar to a value between 0 and 1. The relevant codes are as follows:

functionhandleRunning({ state }) { const inputs = convertStateToVector(state); . }function convertStateToVector(state) {
  if(state) {// Generate an array of 3 digits, i.e. vector // digits normalized from 0 to 1 // for example [0.1428, 0.02012, 0.00549]return[state.obstaclex/CANVAS_WIDTH, // The distance of the obstacleWidth to the Dragon // Block width state.speed / 100 // current game speed]; }return [0, 0, 0];
}
Copy the code

Output item

The simplest way to define the output is a 2-dimensional vector, where the first dimension represents the probability that the tyrannosaur will remain in the same state and the second dimension represents the probability that the tyrannosaur will jump. Such as:

  • [0, 1]saidjumping;
  • [0.2158, 0.8212]saidjumping;
  • [0.998, 0.997]saidRemain the sameMove on;
  • F ([0.1428, 0.02012, 0.00549]) = [0.2158, 0.8212]Represents the predicted result isjumping;
  • ifstate 为 {obstacleX: 0.1428, obstacleWidth: 0.02012, Speed: 0.00549}When tyrannosaurus crash after jumping, it can pass during training[0.1428, 0.02012, 0.00549]Corresponding to the(1, 0)Tag to tell the AI not to do this againjumpingBut shouldRemain the same.

2.5 Artificial neural network model

Due to space limitations, it is impossible to retell the principle of neural network here. The following is an excerpt from Wikipedia:

Artificial Neural Network (English: Artificial Neural network (ANN), neural network (NN) or neural-like network, in the field of machine learning and cognitive science, is a kind of imitation of biological neural network (the central nervous system of animals, A mathematical or computational model of the structure and function, especially of the brain, used to estimate or approximate functions. A neural network consists of a large number of artificial neurons connected to perform calculations. In most cases, artificial neural network can change the internal structure on the basis of external information, which is an adaptive system. Modern neural network is a nonlinear statistical data modeling tool. A typical neural network has the following three parts: Architecture The structure specifies the variables in the network and their topological relationships. For example, variables in a neural network can be weights of connections and activities of the neurons. ** Most neural network models have a short time-scale dynamic Rule that defines how a neuron changes its own excitation based on the Activity of other neurons. The general excitation function depends on the weights in the network (that is, the parameters of the network). ** Learning rules specify how weights in the network adjust over time. This is generally regarded as a long time scale dynamic rule. In general, learning rules depend on the excitation value of neurons. It may also depend on the target value provided by the supervisor and the value of the current weight. For example, a neural network for handwriting recognition has a set of input neurons. The input neurons are fired by the data coming into the image. After the excitation values are weighted and passed through a function (determined by the designer of the network), the excitation values of these neurons are passed on to other neurons. This process is repeated until the output neuron is fired. Finally, the output neuron’s excitation determines which letter it recognizes.

The common neural network with multi-layer structure consists of three parts: Input layer and numerous neurons receive a large number of non-linear Input messages. The input message is called an input vector. In the Output layer, messages are transmitted, analyzed and weighed in neuronal links to form Output results. The output message is called the output vector. The Hidden layer, or “Hidden layer” for short, is the layer composed of many neurons and links between the input layer and the output layer. A hidden layer can have multiple layers, but it’s customary to use one layer. The number of nodes (neurons) in the hidden layer varies, but the more the number, the more significant the nonlinearity of the neural network. Therefore, the neural network can maintain certain performance after the system is disturbed by certain parameters such as structure or size. More significant. Nodes with 1.2 to 1.5 times the input nodes are traditionally selected.

2.6 Artificial neural network construction

As shown in the figure above, we will build a two-layer Neural Network (NN) in this section. The input term is a matrix composed of three-dimensional vectors, and the output is a matrix composed of two-dimensional vectors. The hidden layer contains six neurons, and the excitation function is SigmoID.

Here is the source code for NNModel:

import * as tf from '@tensorflow/tfjs';

import { tensor } from '.. /.. /utils';
import Model from '.. /Model'; /** * Neural network model */exportdefault class NNModel extends Model { weights = []; biases = []; Constructor ({inputSize = 3, hiddenLayerSize = inputSize * 2, outputSize = 2, learningRate = 0.1} = {}) {super(); this.hiddenLayerSize = hiddenLayerSize; this.inputSize = inputSize; this.outputSize = outputSize; // This. Optimizer = tf.train. ADAM (learningRate); }init() {this.weights[0] = tf.variable(tf.randomNormal([this.inputsize, this.hiddenLayerSize])); this.biases[0] = tf.variable(tf.scalar(Math.random())); Tput layer this.weights[1] = tf.variable(tf.randomNormal([this.hiddenLayerSize, this.outputSize])); this.biases[1] = tf.variable(tf.scalar(Math.random())); } predict(inputXs) { const x = tensor(inputXs); // Const prediction = tf. Tidy (() => {const hiddenLayer = tf.sigmoid(x.matMul(this.weights[0]).add(this.biases[0])); const outputLayer = tf.sigmoid(hiddenLayer.matMul(this.weights[1]).add(this.biases[1]));return outputLayer;
    });
    returnprediction; } train(inputXs, This. Optimizer. Minimize (() => {const predictedYs = this.predict(inputXs); // Calculate the loss value, which the optimizer's goal is to minimizereturnthis.loss(predictedYs, inputYs); }); }}Copy the code

If you’ve used the Python version of TensorFlow before, you’ll notice that the code above is either a linear mathematical formula or a Python translation into JavaScript code. Unlike the Python version, JavaScript lacks the Python language feature of operation overloading, so it is cumbersome to express formulas, such as mathematical formulas:

In Python, it can be directly expressed as:

y = tf.sigmoid(tf.matmul(x, Weights) + biases)
Copy the code

JavaScript, due to its lack of plus overloading, writes:

y = tf.sigmoid(tf.matMul(x, weights).add(biases));
Copy the code

3. Integration algorithm model

In Chapter 2, we reconstructed the code structure of T-Rex Runner and exposed life cycle events so that AI could intercept and control the behavior of Tyrannosaurus Rex. At the end of Chapter 3, we constructed a neural network based on tensorflow. js with 50 lines of code. Now we just need to combine the two together to make the AI play the game. Here are the steps:

  1. inhandleRunning()In event processing, invoking the model’spredict()Method, based on the currentstateDecide if a jump is needed;
  2. inhandleCrash()In event processing, if the tyrannosaurus crash was caused by “jump”, it would be recorded as “remain unchanged” in the training data set; otherwise, it would be recorded as “jump”, which is the so-called “lessons learned” and “overcorrection” process in education.
  3. inhandleReset()In event processing, execute the modelfit()Methods Repeated training was performed according to the latest training data set.

The specific code snippet is as follows:

let firstTime = true;
functionConst tRex = tRexes[0]; const tRex = tRexes[0];if(firstTime) {// Initialize the model firstTime =false;
    tRex.model = new NNModel();
    tRex.model.init();
    tRex.training = {
      inputs: [],
      labels: []
    };
  } else{// Retrain trex.model. fit(Trex.training. Inputs, trex.training. Labels) according to the latest training data collected; }}function handleRunning({ tRex, state }) {
  return new Promise((resolve) => {
    if(! tRex.jumping) {letaction = 0; const prediction = tRex.model.predictSingle(convertStateToVector(state)); // the tensor.data() method is an asynchronous evaluation of tensor. It returns a Promise: prediction.data(). Then ((result) => {if(result[1] > result[0]) {// should jump action = 1; Trex. lastJumpingState = state; // Record the state of the last "jump" in case handleCrash() is used. }else{// Leave it unchanged and record the last "left unchanged" state value for handleCrash() to use trex. lastRunningState = state; } resolve(action); }); }else{ resolve(0); }}); }function handleCrash({ tRex }) {
  let input = null;
  let label = null;
  if(trex.jumping) {// Wrong hop, should stay the same! Remember that next time! input = convertStateToVector(tRex.lastJumpingState); label = [1, 0]; }else{// Should not be conservative, should jump! Remember that next time! input = convertStateToVector(tRex.lastRunningState); label = [0, 1]; } tRex.training.inputs.push(input); tRex.training.labels.push(label); }Copy the code

See the Demo of the AI model based on artificial neural network on Chrome.

4. Optimize the algorithm model

If you observe the online Demo, it is not difficult to find that usually after 4-5 crashes, AI gradually learns the time and skills of jumping obstacles, but sometimes it may need more than 10 times if “bad luck”, so is there any way to optimize the algorithm? The answer is yes:

  • One way to do this was to play an artificial neural network model AI in a Multiplayer Mode, in which three tyrannosaurus dragons played in the same game against each other and shared the same defeat lesson. The optimization led to a higher success rate and shorter training time because of the “greater knowledge”. But there’s still a certain amount of randomness. Watch the Demo on the desktop version of Chrome
  • The alternative is still a multi-player game with 10 tyrannosaurs, but we introduce Darwinian “survival of the fittest” mechanism, where the two tyrannosaurs that last the longest crossover offspring at the end of each game. The Genetic Algorithm is called Genetic Algorithm, in which young people inherit their chromosomes from their parents and mutate some genes randomly to ensure biological diversity. With genetic algorithm, the optimal parameters of neural network model can be almost guaranteed within 4 generations. Watch the Demo on the desktop version of Chrome.

5. To summarize

This paper introduces how to reconstruct game code and build artificial neural network using Tensorflow. js through the example of AI playing T-Rex Runner.

In the future, this project plans to analyze the state of handleRunning() directly by capturing image information in HTML Canvas through CNN convolutional neural network. If you are interested in this project, please follow it on Github and I will continue to update it.

You may have noticed that the project works like a Test Bench model, but yes, you can design new algorithm models and Test them yourself.

Feel free to talk to me in the comments section below.

Finally, check out our column:

  • < front-end zero stack /> : Let’s talk about “front-end technology” and “front-end ARTIFICIAL intelligence”.
  • Alibaba Nanjing Technology Magazine: the official technology exchange channel of Alibaba Nanjing R&D Center

Alibaba Nanjing R&D center is looking for front-end technology experts and senior engineers (only available), welcome to join our team!