Table of contents

1. Disclaimer
2. Problem
3. Technical preparing
4. Dive into genetic algorithms
   • List of useful articles
5. Making our algorithm smarter
   • List of useful articles
6. Some useful information you must know about emulator and Mario
   1. Mario, where are you or what is your position?
   2. How high does Mario jump?
   3. How to control Mario?
7. Results
8. Conclusion

Disclaimer

I am a newbie in a genetic AI.

My initial goal was to learn the techniques involved in genetic AI algorithms and show other people how I did it, where I had found the information, which problems I had etc.

I am aware that some of the things that I have written may not be conceptually correct. I will be grateful if you prevent me from making mistakes in the future. I am always ready to listen to your advice. Please write me on the email - ilopatin3@gmail.com

Problem

Write a genetic AI algorithm which will be able to pass a level of a simple game like a “Super Mario Bros”.

Technical preparing

First of all, you must run the Mario on your machine. To achieve it you have to download a BizHawk emulator.

The next problem is to find the game. But don’t worry I have already done it for you. There is an excellent resource where you can find the one and even much more games.

I implemented the algorithm in Lua language. I did not know this language before but I was inspired how widely this lightweight, scripting language could be used. In addition, the BizHawk emulator run Lua with no hesitation.

Dive into genetic algorithms

I cannot teach you a genetic algorithm, because — as I have mentioned — I have been still learning it. But I am glad to share useful links, where you can find the information for beginners.

Do not think that it is too complicated for you. Because it is not! The main idea of each genetic algorithm is to evolve the best possible solution from a set of elements. All you need is to implement necessary functions. Then run the algorithm and .. that is all. The solution will be found by the algorithm. All you need is to wait.

The next figure will help you to imagine how the cycle of evolution looks.

List of useful articles

• Genetic Algorithms for Geometric Primitive Detection by Mark Grundland & Youenn Fablet
• Introduction to Genetic Algorithms  —  Including Example Code by Vijini Mallawaarachchi
• Was Darwin a Great Computer Scientist? by Louis Nicolle

Making our algorithm smarter

There are some types of Artificial Neural Networks. I decided to choose the easiest one - Feedforward Neural Network. Because it is understandable enough to use it for the first time.

As I’d chosen Lua language, I had to find the implementation of the neural network to use the one in my project and I did it.

Soulkiller implemented this type of neural network in Lua, a page no longer exists but I found a copy of the page on web.archive.org. You can find it here. And if you want to comment or make some changes in the algorithm, you can do it in gist by Cássio Souza.

It’s very easy to use. For example, if you need to create a neural network with 2 input neurons, 1 output neuron, 1 hidden layers with 4 neurons in it and 30% rate at which the neural network learns, you should write the next code

network = NeuralNetwork.create(2, 1, 1, 4, 0.3)

.. then you need to teach your “network”

network:backwardPropagate({0,0},{0})

.. the first parameter {0,0} in the function is the input of the network. Here are two numbers - two neurons - as we created the network with two input neurons. And {0} is the desired output. But it isn’t enough to teach it one time! You should repeat it much more times. You must test it by yourself.

And then, when our network is taught, we can use it

network:forewardPropagate(0,0)[1])

I recommend you to see some more examples here (at the bottom of the page).

List of useful articles

• A Beginner’s Guide to Neural Networks: Part One by Nehal Udyavar
• Understanding Feedforward Neural Networks by Vikas Gupta

Some useful information you must know about emulator and Mario

Some tips that can help to save your time.

Mario, where are you or what is your position?

We have to know the position of Mario. But how will we find it out? We cannot send a request to API to get that information. So we have to find another way to do it.

And here it is. Let me show you how to find out the X position of Mario. All we need is to find an address of a byte which contains this information.

To do this you must open Emulator, run the game and then go to Tools > RAM Search.

When you open it, you will see the next window:

So we can see a lot of addresses and their values but we don’t know which is the right. So we need to do a few steps to find it out.

First, select Previous Value and Equal To on the right as it is done on the picture above. Then click New button at the top.

Second, go to the game window and move your Mario to the left or right.

Then return to the RAM Search window and select Not Equal To and then click Search button at the top. This way you will eliminate a bunch of unnecessary addresses. Then return to the game window and keep changing Mario position while looking at Value row in RAM Search. This way you will find out the right address.

How high does Mario jump?

You can have a problem with “Why does Mario not jump?”. It’s because it isn’t enough to click “jump” button one time. You must keep pressing the button during several frames and the longer you press the higher Mario jump.

Look at the gifs below. In the first case, the button was pressed within 5 frames, in the second and third 15 and 30, respectively.

How to control Mario?

Another reason to write in Lua is there is an API for BizHawk emulator.

For example, if you need to write some debug information on a game screen, use gui.drawText

void gui.drawText(int x, int y, string message, [color? forecolor = null], [color? backcolor = null], [int? fontsize = null], [string fontfamily = null], [string fontstyle = null], [string horizalign = null], [string vertalign = null])

joypad.set sets the given buttons to their provided values for the current frame

void joypad.set(nluatable buttons, [int? controller = null])

Results

After 3 hours and 30 minutes, the algorithm was able to pass the level.

You can see the whole process (4h 40m) on YouTube here or the best populations (4m 20s) here.

The parameters of the algorithm were:

• Chance of mutation: 50%
• Number of a population: 20

Conclusion

I will be very happy if this article helps you in the beginnings of studying of genetic algorithms.

I very strongly recommend watching a video about MarI/O by SethBling.

And lastly,

• You can use my code. It is completely free.
• If you notice any inaccuracies, please let me know about it.
• If you have useful materials for studying this topic, please write to me, it will be useful for me.
• I plan to update/improve the algorithm.
• If you are new to this, read the articles that I mentioned above, they will really give you a basic understanding.