AI Learns to Play Super Mario World Using Evolution

[00:00] Welcome back. Seeing here. You're watching a skilled player play Super Mario World. But this player is not human. It's a computer program I wrote called Mario. This program started out knowing absolutely nothing about Super

[00:13] right on the controller would make the player go towards the end of the level. neuroeolution. In this video, I want to teach you about how Mario learned to

[00:27] beat this level. Donut Plains 1. what his brain looks like and how it's all based on actual biological evolution. So, let's start out by actually looking at Mario's brain. Let's play it again, but this time we'll look at Mario's

[00:40] brain as it's making the decisions of what buttons to press. It's going to you. This structure of colored lines and blinking boxes is called a neural network. It's a simple mathematical model for how a brain works, but it can

[00:55] produce some very complicated behavior. With enough computational power, a neural network could come close to simulating a real human brain, but modern technology isn't there yet. On the left side, you have the inputs. This

[01:08] is what Mario sees. It's a simplified view of the level. The white squares moving objects like enemies or mushrooms. On the right side, you have the outputs. These are the eight buttons that Mario is able to press by using its

[01:23] neural network. In between the inputs and the outputs, all those lines and boxes, those are the neural network. Each free floating box is called a neuron. And the lines connecting those boxes are like the axons and dendrites

[01:36] in a human brain. At any given time, only some of these neurons and say you only use 10% of your brain. The neural network you're seeing is a pretty

[01:48] complicated one. And it got so complicated as a result of a 24-hour evolutionary learning session. So to explain how neural networks work, let's rewind about 24 hours and look at how the whole process started. This is what

[02:02] generation number zero. The program is probably even dumber than you thought at this point. Often it just stands there and doesn't even press any buttons. If Mario stands still for too long, it'll cut off the simulation and try the next

[02:17] neural network. So, it's mostly just jumping from one simulation to the next, player starts walking right. Behavior isn't complicated, but it's enough to make at least some progress in the level. Let's take a look at a sample

[02:32] neural network to understand just how that works. This is one of the randomly simulation. There are some green lines and a red line and one neuron in the middle. Here's how it works. A green line is a positive connection and a red

[02:47] line is a negative connection. A green line reading from a black or white square will turn its output the same color. A red line reading from a black or white square will turn its output the opposite color. In this case, the green

[02:59] neural network press the right button as long as the player is standing on it. However, when the red line reads a black square representing one of those caped Koopas, it presses the A button and makes the player jump. This this puts

[03:15] square. So the right button turns off and Mario just stands there. This is a might operate. The more lines and neurons you have, the more nuanced to

[03:30] the decisions can be. So how exactly do we get those more complicated neural networks? The answer is evolution. When Mario gets further right on the screen, its fitness goes up. In this case, fitness is a function of how far right

[03:44] it gets and how quickly it gets there. Only the neural networks that produce the highest fitness are selected to be bred, creating the next generation. It took 34 generations of genetic breeding and fitness evaluation before Mario was

[03:57] able to finish the level without dying and get a fitness score above 4,000. You always evolved out of those ruts. Let's take a look at a few of those ruts. You

[04:10] each rut occurred on. This process of picking the fittest individuals from each generation, breeding them together, and adding random mutations very closely

[04:22] matches the actual process of biological evolution that took single-sellled organisms and produced intelligent humans. That's the power of computational resources to produce something on the level of a human brain

[04:37] this way, it's kind of neat to see what it can do on one of my favorite games. I didn't come up with this idea on my own. This algorithm is called NEAT which stands for neuroeolution of augmenting topologies and it's based on

[04:50] a paper by Kenneth Stanley and Risto Miku Linen. It's a really great paper from barebones without presupposing the best structure for the neurons and their

[05:02] connections. It also includes some really cool ideas for separating genomes into species, which a lot of genetic algorithms don't really try and do. I wrote Mario from scratch in Lua as a plug-in for an emulator called Bisok. As

[05:17] I close out the video, let's take a look at the fittest neural network in each modifications to each other and improve performance, but sometimes an entirely new species becomes prominent and dominates the others. If you'd like to

[05:32] some links in the video description. I had a lot of fun working on this project and I learned a ton. Hopefully, you learned something, too. That's about it. Thanks for watching. [Music]