NEAT is a machine learning algorithm that simulates evolution to train its brains. Let’s try to build a game, and then an AI that masters it.

The game

We will play a little game of snake. You can play with IJKL:





Now that’s all well an fun, but the computer isn’t as smart as you, and we need to transform that view into something it can reasonably understand from its inception. We start by centering the game on the player. That way the problem becomes relative to the snake, rather than absolute to the board:





Better. Now another problem is with directions. We have four, this is way too complex and redundant. We want to make things relative. So we’ll rotate the map accordingly so that forward is always up. Since directions are now relative, commands should also be: we’ll use U and O to turn left and right:





It gets harder, but also the problem we are looking at is standardized now: apples are passing by, and you want to turn to hit them, without hitting you tail.

Now we’ve got something working that we can feed the computer. Time to switch to the AI

Genomes

We will build a neural network that will learn how to play this game. In fact, we will build a bunch of these, kill the worse, keep the best, make them mate together, take their progeny and keep iterating till we find one that actually works.

The algorithm we’ll loosely follow is NEAT. There are a few bits we need to build.

  • Two entities: genomes, and networks. Networks take inputs, transform them to output. Like in biology, genomes are the encoding of the network.
  • A mechanism to transform a genome to a network.
  • A mechanism to handle our collection of genomes, including ablation (removing the least fit) and mating
  • A mechanism to iterate, run the game, etc.

We will start with the whole genome and network.

We’ll use this structure:

interface Link {
  innovationId: string,
  from: node,
  to: node,
  weight: number, // 0 .. 1
  enabled: bool
}

interface Node {
  type: "in" | "out" | "hidden",
  pos: {                    // when type = in
    row: number, 
    col: number 
  }, 
  dir: "left" | "right",    // when type = out
  nodeId: number  // when type = hidden
}

interface Genome {
    links: Link[],
    genomeId: number,
    speciesId: number,
    nodes: number // that's the count
}

First let’s look at an intelligently designed organism’s genome:

Each of the genes is indicating a link from a node to another. The nodes formatted like “1x2” are input nodes. Nodes indicating directions are output nodes. The number on top is called the “innovation number”. We’ll come back to it in a moment.

Here is a view of the topology it generates:

Let’s see what it can do. We’ll transform the genome into a set of functions. There will be one function per output, taking the board as input, and determine how much the output is activated, applying an activation function over the sum of the incoming signal.

For example if we simulate something on the right of our snake:

We now have a functional transformation of the genome into a decision function. The last step necessary is to build a player from that and let it play snake.





Now this is a pretty simple genome, but works relatively well. It turns whenever it sees an apple or when it’s gonna eat itself. Running it a few times already teaches us a few things. A) it’s much faster than you at snake. B) it’s not perfect, despite being intelligently designed. C) scores are not completely deterministic. In fact, let’s try to understand how much runs settle a good average, Monte Carlo style. (It’s mostly going to give us an indication for this species, but should give an order of magnitude).

iterations

This yields interesting results. First, we see a significant spread between min and max. Second, we see that the game is not terribly optimized, and iterations take a few ms each. Third, we observe that the average results are consistent to +/-5% over 5 iterations, +/- 10% over 10 iterations, and about +/- 2% over 100 iterations.

Figuring the right number of trial per species is a balancing game between obtaining precise results each round, and having more rounds. 10% fidelity seem enough for a variety of reasons.

Evolution

Let’s see if we can build species which can evolve genes that play the game, and maybe beat our simple intelligent design genome.

There are two aspects of evolution: variation (changing the species) and selection. Let’s focus on variation first.

Variation

Variation is the set of mechanisms changing the genome of a species. It introduces entropy in the system so that better fitted (and worse…) species appear.

Mutation

The first mechanism of variation is mutation, introducing random changes within a genome.

We can do so by changing the existing genes by activating deactivated genes or randomizing the weight of existing links. We can also create new genes, i.e. create new connections, and new nodes.

with probabilities ([0, 1]) for mutation on weight: enable: disable: split link: new link:

Mating

The second mechanism of variation is mating. It allows traits to be propagated between generations by crossing the genomes of two individuals. Randomly merging topologies is hard: how do you know if a node with the same id is the same between two genomes? How do you know if a given topology will make sense?

NEAT introduces the notion of innovation to handle this. Every time a new node or a new link is inserted, we give it an innovation. The innovation id is global, that means that if a new link between two given nodes, the new link’s innovation id will always be the same across individuals and species. Respectively, for nodes. This is how NEAT traces ancestry and allows simple mating between genomes: a given gene’s innovation id will be the same throughout genomes.

We implement a dictionary that will generate innovation ids accordingly. If the node or the link gene is indeed new, it gets a new id. If it creates a topology that we already encountered, we reuse the same innovation id.

between and . Result: <div id="innovation-id-demo-split-result" ></div>

between and . Result: <div id="innovation-id-demo-insert-result" ></div>

Now we can proceed with mating. This happens through matching two genomes. Matching genes are selected randomly. Excess genes are picked from the fittest parent. If fitness is equal, all are selected.

+

Fitness delta: (> 0 means genome on the left is fittest)

Viewed as graph:

+

=
<div id="mating-genome-res-graph" style="border: 1pt solid; display: inline-block; width: 45%; height: 300px; margin: auto"></div>

Selection

We have the basics of evolution at an individual level, now we’ll tackle the selection part. This will happen by having generation after generation compete in our game, eliminate the lowest performers, breed the rest, rinse and repeat.

NEAT introduces the concept of speciation in addition, so that new genes that could be beneficial compete “locally” and have more chances to survive their introduction. The idea here is that we group genomes that are similar, operate selection and ablation within a species, mate, reassemble species, then carry on.

Species

Compatibility distance is calculated based on the number of genes that differ, and the distance of weights.

Distance using coefficients: weight: excess genes count: disjointed genes count: gene pool total size:
Distance: 0

Calculating distance will allow to group genomes by species, and allowing the development of variations in a semi-protected environments. This happens by maintaining a list of species from a generation to the next. For each species an individual genome is picked randomly as a representative. Each individual from the new generation is placed with the first species with which it is compatible (i.e. compatibility > threshold). If it ain’t compatible, then a new species is created, with that genome as representative.

interface Species {
  id: number,
  representative: Genome,
  genomes: Genome[],
  speciesAge: number
}

Now we’ll switch to executing all of that. Starting with an initial population with all gene links between input and output, but disabled. We introduce a new entity: the genome

We make the population compete at snake and track their fitness:

    Then prune the lowest half of each species sorted by fitness. We also remove under-performing species older than a given number of generations.

    
    
    
    
    

    We’ll plug all of that into an evolutionary loop, in which:

    • Repopulate with offspring of the remaining species, introducing mutations as well
    • Re-sort into species

    FIGHT