Neuro Evolution of Augmented Topologies

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
}

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 </input>

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:

</input> enable:

</input> disable:

</input> split link:

</input> new link:

</input>

### 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:

between

and

. Result:

Now we can proceed with mating.

from Hacker News https://ift.tt/3qTybO0