Solving Mastermind using Evolution!
How it all started
Not so long ago I've been attending some classes on artificial intelligence and game theory, and I really liked what I've learned during that time. I was amazed how you can make an "intelligent" system that will, for example, play chess on professional level, just by implementing some moderately simple algorithm. It's called MINIMAX and it's quite interesting how it works, however I'm here to talk about something even more fascinating and powerful, GENETIC ALGORITHMS, and how I discovered them.
Finding a challenge
I was really motivated at the time, and wanted to improve my problem solving skills, and eventually build an AI that can play some reasonably complex game against human opponent. Huh, I set my bars high.
I remember playing that game with colored pegs. You have to guess the right combination of colors in order to win the game. All you get as feedback on each guess is how many colors you've guessed right, and how many of them are on the right spot. It's called Mastermind game, and it's quite popular one. So I decided I'll try to come up with an algorithm of my own which can play this game like human would do, or at even greater level. Looks like I've found my challenge!
Algorithm!!
It took me a while to come up with something that works, but not quite as I expected, I quickly realized the more effort I put into making my algorithm better more it's starting to look like brute forcing the solution, and I didn't wanted that kind of outcome. I preferred something more elegant and clever. After a lot of trying I lost all hopes. It seemed to me that brute-forcing and eliminating solutions was the best performing method for this kind of problem. You can find the details just by searching "Knuth five-guess algorithm". It's quite simple and it finds solution in less than 6 steps for the case when there are 4 pegs, 6 colors. But I wasn't satisfied, I knew there has to be something more elegant. And then I found Genetic algorithm approach. It's even described right beneath the Knuth's algorithm on Wikipedia, as an alternative approach to solving Mastermind.
Genetic what?!
Cool name for an algo, but what is it?! I was all into that, my browser had million tabs opened, searching for the term, I wanted to know what the hack are those Genetic algorithms! I almost forgot why I was here in the first place. Oh, yeah, mastermind game.. Oh wait! Ok, I think I know what it's all about. These algorithms are trying to use same principles as natural Evolution to solve problems. Let me be more precise, search optimization problems. What?!
When somebody says Evolution, this is what first comes into my mind. And guess what, it gives you completely wrong impression on what Evolution actually is. This is what they've taught us in school. And they were wrong. This is not the whole picture, it's only a slice of it. And if I give u a thin vertical slice of the book, can you guess what the book is about?!
Things are changing
So I figured out how algorithm manages to find a solution for the game using Evolution. I starts with a population, which is an arbitrary sized set of possible solutions. Solutions are like our genome, one combination of colors is like one DNA. Holy s**t, this is crazy, how is this ever going to find solution, I wandered, over and over again.. But let me just finish coding and let the program run. Will I was coding I noticed more and more similarities with natural evolution, those combination from the current population that were more likely to become solution, were kept in the next generations, and their offspring was added to the population by using crossover, mutation, and gene permutation.
Other combinations that where classified as being far from actual solution were rejected, like natural selection. Iterating this same process over many generations per each guess it makes. I thought this is amazing, but is it really going to work?
Let's try it out!
I wasn't convinced till the end that Genetic algorithm approach will actually work. But I was wrong, due to my previously poor understanding of what Evolution actually is! Finished my coding, and I was ready to challenge my first AI made with Evolutionary algorithm. It nailed it. Every single time! And what's even more important it beats Knuth's algorithm when you increase the number of pegs. How fun is that!
The code is on GitHub, I made a pretty UI so you can play around and really enjoy the game.
Conclusion
This experience definitely changed me in a way I never could imagine. The fact that you can solve complex problems just by utilizing techniques which Evolution is using for millions of years is astounding. Understanding the true power of Evolution, offered me ability to answer questions about us, and world in general, that I couldn't answer before. Mainly philosophical questions. Questions regarding our purpose as humans, our future and our past.
Thank you.