Building An AI That Can Play Games - Part I

Hi everyone!
As this is my first post in this new blog, I wanted to write about a cool project that combined two separate areas I love - AI & Game development.

So, without further ado -

How did I build an AI that can play 2D games? #

I attempt to explore every aspect of development as a software developer, but my passion has always been game development. I created numerous tiny tech demos and multiple mini-games, one of which included a proposal to my wife, but more on that later.

I studied machine learning two years ago and became interested in neural networks after reading an interesting book. I will do my best to provide a brief overview of those, but for anyone who would like to read more, I will provide links.

The primary objective is to develop a 2D, simple Mario-style game in which an AI player can navigate the level from beginning to end.

Background #

What are Neural Networks? #

if you know the basics of Neural Networks, just skip to the next section
Neural Networks are computing systems vaguely inspired by the biological neural networks that constitute our brains. Such systems “learn” to perform tasks by considering examples, generally without being programmed with task-specific rules. For example, in image recognition(Image classifier), they might learn to identify images that contain cats by analyzing example images that have been manually labeled as “cat” or “no cat” and using the results to identify cats in other images

It is a collection of connected units (nodes) called artificial neurons, which loosely model the neurons in a biological brain. Each connection, like the synapse in a biological brain, can transmit a “signal” to other neurons. An artificial neuron that receives a signal, processes it, and can signal neurons connected to it.

Each synapse (connection) has a weight, and that weight represents its relative importance. Some neurons have a Bias value, which is a constant value we add to signals passing through it. The value of each neuron is updated using something called an Activation Function. The Activation function receives inputs and weights (the Neuron’s data) and passes on a value to the next neuron until it arrives at the last layer (output) and passes the final result.

If you want more information, I highly recommend checking out this youtube video, it has a very clear explanation on the complete flow.

Survival of the fittest #

a term used to explain the mechanism of Natural Selection that dates back to Darwinian evolutionary theory. One important mechanism of evolution is natural selection, which is the process by which organisms with advantageous features have a higher chance of procreating and flourishing. In other words, the organisms with the highest Fitness have a higher probability of thriving.

let's consider a population of mice that moved into a new area where the rocks are very dark. Due to natural genetic variation, some mice have black fur, while others have tan fur. Tan mice are more visible to predatory birds, than black mice.

some mice were eaten by birds, this occurs because Tan mice are more visible to predatory birds, thus, tan mice are eaten at a higher rate than black mice. This means only the surviving mice reach reproductive age have offspring.

Because black mice had a higher chance of leaving an offspring than Tan mice, the next generation contains a higher number of black mice than the previous generation.

Combining evolution with Neural Networks #

There are many methods for training a neural network, but I chose to use evolution and Survival of the Fittest. Essentially, until our neural network reaches its maximum potential, we will need to “evolve” it by creating successive generations and choosing the most fitted of them.

The Process - Combine Neural Network with Evolution #

1. Step I

   Create Neural Networks

   create several ANNs with weights and biases, and choose their input at random, letting them compute whatever result.

2. Step II

   Compute and Rank them

   Step 2: After they were all done computing their result, rank them, using a fitness function. The fitness dictated who was the “best” ANN out of all of those ANNs.

3. Step III

   Choose Best, Delete and Copy

   Choose the one with the best Fitness. Delete 50% of the worst Neural Networks (lowest scores), and copy the best in their place (with a twist)

Here’s the concept graphically

Step 1 - Create Neural Networks #

Step 2 - Compute and Rank them #

Step 3 - Choose Best, Delete and Copy #

Best is 95, so we delete the lowest scores and replace them

The “twist” I added #

With a 10% chance, we mutated something in each of the new networks.
Meaning, that for each new network we copy, there is a slight chance of it being a bit different from the original network it was copied from. We gave them new (random) input, and again chose the best.

This process continues until we reach the most satisfying score/state. At the end, we simply take the best Neural Network.

So, what’s all that has to do with an AI that knows how to play games? #

Follow part II of this to find out!