I Wrote a Genetic Algorithm to Learn the Konami Code!

It's been a pet interest of mine for years to learn how to write Genetic Algorithms, but it was never quite clicking for me. I ended up stumbling upon this video (embedded below but if you don't see it it's also the previous hyperlink), and it finally clicked. This video is entirely no-code, just a simple and intuitive explanation. They said there'd be a code walkthrough video as well but unfortunately it doesn't look like they ever posted it.

My Genetic Algorithm to Learn the Konami Code is open source, available on github here. With a little work this could probably be fitted to an emulator to actually trigger in a game, or maybe even with a real game console if the controller inputs are programmable, that's a little outside my purview. It would be cool if somebody wanted to try that, but really this is just intended as a technical demonstration.

Genetic Algorithms use the principles of genetics; fitness, reproduction, and mutation, to converge on solutions given some task.

They have a lot of applications, such as robotics, neurocomputation, and machine learning, but this is just a simple Genetic Algorithm, no ML involved here.

I also have some ideas for using Genetic Algorithms for worldbuilding, TTRPG stuff, or quasi-videogames, but still need to give all of those some thoughts.

Keeping it simple, I thought it would be fun to train a Genetic Algorithm to learn the Konami Code.

I give a simple explanation of it here, but if you follow the link above to the github repo, the README explains it in more detail and also shows an example.

Konami Code

["↑", "↑", "↓", "↓", "←", "→", "←", "→", "B", "A", "START"]

The Konami Code is a common set of user inputs in videogames to activate cheats or secrets, most famously old Konami games.

We can think of these 11 inputs as the genes making up a strand of DNA.

Players

We have some number of players. We can represent each player as a strand of DNA composed of 11 genes of seven types: ↑, ↓, ←, →, B, A, or START.

Our initial population has entirely random genes; any 11 inputs among those seven values.

Fitness

We can imagine each player presses their controller inputs one by one (i.e. their genes), and each time their current input matches the Konami Code, their score goes up by one. If they press the wrong button, they lose a life, and they only have one life, so whatever score they had before the mistake is their final score. 

There are certainly more efficient fitness algorithms, but I like the simplicity of this one and the way it works for our metaphor, as if literally pressing the buttons one-by-one on a controller.

Selection and Crossover

We take the players with the top X score and drop the rest of them. 

Then, we generate new players, up to the number of the original playerbase size, by crossing the winners of the previous round. We take any two winners at random, and for each of our 11 genes of the DNA strand, we pick randomly from one parent or the other.

Since all of the new players were created from the selection of the highest scoring players of the previous generation, the genes they inherent are more likely to be correct, so they generally show improved performance over previous generations.

If all of the highest scoring players had a score of two or higher, this means they all inputted ↑ ↑ of the Konami Code correctly, and as a result all of the new players will also get at least a score of two, because they can only inherent ↑ for those first two genes.

On the other hand, if none of the starting players had START as their last gene, then no future generation of players will ever be able to win, because they can never inherent START in the final gene.

This is why we add Mutation.

Mutation

Mutation creates a percent likelihood that any given gene will change into any of our possible inputs, even if they did not inherit that input. With a mutation rate of 0.05, there is a 5% chance that any of the 11 genes of a player's DNA will mutate into any of the seven inputs.

Mutation can cause a good gene i.e. a correct input of the Konami Code to change, meaning it might take more generations of play before a sufficient number of players win. However, it also means that if you start with a low-scoring or non-viable starting group of players, that they can catch up more quickly, or succeed where it might otherwise have been impossible.

AND THAT'S IT!

If you want to know more about the particulars, check out the open source github project, or feel free to ask more questions here.

Sure this is cool I guess, but what's the big deal?

If you think coding and technology is black magic, nothing I say is likely to change that and while I think that's a shame, I'm not trying to change your mind.

All the same, if you're at all interested in natural philosophy or understanding the world, this is a cool demonstration. The fact that we can abstract the principles of genetics and use them to solve problems analogically demonstrates the existence of these systems and how they operate, and by extension informs our understanding of the world. The mathematical or algorithmic representation of them is just a language to make it easier to understand.

To me, conceiving of and training an algorithm to solve the Konami Code, it's like a puzzle, or a poem. It's a little piece of art. That's not to deny that these things can be used poorly, but both things can be true, and these systems exist in the world whether we use them or not, and also, people are using them, so isn't it better to find ways to find the beauty in them and use them for good? Even if you believe there is no good way to use them, if you really believe they're so powerful and so dangerous, isn't that all the more reason to understand what they are and how they work, so that you can better protect yourself from them?