For those who have read my article on a MinMax AI, you will know that I had a slight problem. I had a lot of numbers to pick and no way to pick them. Thankfully, genetic algorithms came to the rescue!

The full source code is available on Github.

Biological Inspirations

Despite the name, genetic algorithms are based more on evolution than genetics - but there is still a link there. If you stop to think about it, copying evolution makes perfect sense. It is an unintelligent system that is able to optimise incredible amounts of data very effectively. In fact, every living creature on Earth is the result of evolution working upon unimaginably long genetic codes. If it can succeed in creating thriving ecosystems, surely it can teach an AI the best way to play games?

Implementation

As a reminder, evolution is a remarkably simple concept. Animals have genetic codes which, during breeding are mixed with another animals genetic code to produce offspring. Animals poorly suited to their environment do not survive long enough to reproduce, so only the 'good' animals survive.

Reproducing this within a computer program is also surprisingly simple. First, we need a genetic code. In my case, this was the long list of weightings for the AI. Secondly, we need a way to rank the 'fitness' of each genetic code. To calculate this, I simply got the AIs represented by each code to play against each other. Those that won the most were considered more fit. In addition to this, I had to add some performance constraints as things such as how far ahead the AI would think were included within its genes - any AI that took longer than 10 seconds to choose a move instantly lost.

Now the computer has decided how good all its various genetic codes are, we simply need to calculate a new (hopefully better) gene pool. Instead of using a biologically based reproduction system, I instead chose to use a system in which each new gene was chosen individually from one of the corresponding genes in any of the parents. The parent to take the gene from was chosen with a weighted random sample so that it was more likely to pick genes from successful parents. In addition, there was also a chance that a gene would be generated entirely at random instead of choosing from a parent. This would maintain genetic diversity so that improvements could still be made even if they didn't already exist in the gene pool.

Considerations and Genetic Diversity

The primary consideration for genetic algorithms is that they are slow. Even on a powerful i7 processor, I had to leave this running overnight for a week before I was satisfied. On the other hand, it can be stopped at any point and just have the current best taken from it - there is no end to the algorithm, only stagnation. One thing I regret from a performance standpoint is that I only had a pool of 3 AIs at any time. This seriously limits genetic diversity, which is a bad thing.

Great pains should be taken to maintain genetic diversity. This is because genetic algorithms are a type of hill-climbing optimisation. The algorithm is very good at making small improvements, but it will not make any changes that disadvantage the AI. If we think of finding a good AI as like trying to climb up the tallest mountain in heavy fog, it will only go up the mountain it is on and have no idea of any nearby and potentially taller mountains. The higher your genetic diversity, the more mountains you can explore at the same time. As I only had 3 AIs in my gene pool, I would not be at all surprised to find there is a higher evolutionary hill that my algorithm simply missed out.

While I have not tried any of these methods I am about to suggest, I expect at least some of them will help to maintain genetic diversity. Firstly, use a large gene pool. This will allow a greater variety of genetic codes to exist at any one time. Secondly, during the breeding process, encourage breeding between similar genes. This will simulate speciation, which allows multiple species to climb their own hills independently. Just because they aren't as high up the hill at any one point doesn't mean they can't go any higher.

Miscellaneous Thoughts

Biology is incredible. There are so many things we can see in reality that are far more efficient than any system we could design. I have talked about optimisation algorithms based on evolution, but in addition to that, packet routing on the internet is based on ant pheromone trails, efficient network layout (anything from purely abstract layouts to the road systems) can be based on slime mold.

It is easy to get lost in the computer screen when developing algorithms, but just remember that mother nature has been working for millions of years. Maybe she already has the answer.