Genetic Racing

You will need the following zip file for this tutorial. Please download it now by clicking here.

Objective

The goal of this session is to build ontop of the provided code (see "Installation & Setup") to allow cars with set genes to "breed" - allowing for the successful cars to reproduce and mutate so that the next generation is improved.

Installation & Setup

We're using Python3. For this tutorial you will need to use an editor of your choice - whilst Notepad would technically work we recommend getting an actual IDE (or Integrated Development Environment; a fancy way of saying "code editor") such as PyCharm.

In terms of the libraries we will be using - this entire program does not use any specific Artificial Intelligence libraries. However, you will need to get the latest version of PyGame, Pillow and NumPy. These can be installed by entering the following commands into your terminal:

pip install pygame
pip install numpy
pip install Pillow

Now all you need to do is grab the pre-made code zip file if you haven't done so already and extract it to a new directory of your choice.

Understanding the pre-made code

This progam is made up of 3 files. pyparticles.py holds the objects for the program to function: the cars (particles) and the track (environment). gaming_assembly.py does most of the work when it comes to visualising what is going on; whether that be creating the game window or displaying the leaderboard. Finally, track.bmp is the track that the cars will be racing on, it's just a white track drawn on a black background stored in the BMP image format - if you wanted to make your own you could do so but you would have to change the location of the checkpoints in the gaming_assembly.py file.

Controls

At any given time, each car is choosing whether to press W, A, S or D. W causes the car to accelerate, A causes the car to turn left, D causes the car to turn right and S activates the brake. These are stored as boolean values within each car - you can see this in the pyparticles.py file:

Controls screenshot; found on lines 116 to 120 of the pyparticles.py file

But how does the car know how to move? Well, it uses a function aptly named "control", which you can find in pyparticles.py and also below. It looks daunting, but the mechanics of it are fairly simple.

The "inputs" variable takes the information the car is getting from the environment (how close it is to a given wall and at what angle the car is currently turning) and stores it in an array, which is treated as a matrix.

The "output" variable then takes the dot product of the inputs matrix and another matrix called "control_rods", and adds it to an internal "bias" variable.

"control_rods" is what the car stores about the environment - for example, what to do when it approaches a left turn.

"bias" is then a number generated by each car that is passed on between generations - that number acts as a method for making cars more / less sensitive to the environment. Too high of a bias would cause the car to spin in circles as it thinks it needs to turn too early whilst too low of a bias would cause it to turn too late.

Then, the program checks whether or not each of these outputted values are greater than a given threshold (1). If the output is greater than 1, it will push the button associated with that output.

def control(self, env):
        # Use inputs, control rods, and bias to determine if w, a, s, or d are pressed
        scaling = env.height / 10

        inputs = [self.distance_left / scaling, self.distance_front / scaling, self.distance_right / scaling,
                  self.speed, self.wheel]
        output = dot(inputs, self.control_rods) + self.bias

        threshold = 1
        if output[0] > threshold:
            self.w = True
        else:
            self.w = False

        if output[1] > threshold:
            self.a = True
        else:
            self.a = False

        if output[2] > threshold:
            self.s = True
        else:
            self.s = False

        if output[3] > threshold:
            self.d = True
        else:
            self.d = False
            

Measuring Progress

To decide which cars are doing best, we use a score function. This is a concept that will come up over and over within Artificial Intelligence as we go through the year. Score functions are pre-determined ways of measuring progress. In this example, we use the time taken to reach each checkpoint as our score function (lower is better).

Breeding Cars

Inside of gaming_assembly.py, you'll find two main functions: train() and race(). The train function will cycle through 40 one-minute generations, saving the best cars to a file each time. The race function would then take those best cars and race them around the track.

What we're interested in today is the train function.

If you run the program, you'll notice that some random cars will be created and begin to make their way around the track. These cars however, are entirely random and have no idea how to go around a track. Every 60 seconds, those cars will die and new ones will be created.

If go to line 165 you'll see how this works.

First, we create a list of all the cars, sorted by their score in descending order.

Second, we create a brand new copy of the track (or environment).

Then, we fill that new environment will random cars.

Finally, we store the best 10 cars in a file and begin a new generation (n += 1).

# BREEDING STARTS HERE
# create a list of cars, sorted by their score in descending order
sorted_list = sorted(env.particles, key=lambda particle: particle.score)[::-1]
env = pyparticles.Environment((width, height), image=track, checkpoints=checkpoints, colliding=False)

# [[[ insert code here ]]]

# fill the rest of the world with purely random cars
while len(env.particles) < generation_size:
    env.addParticles(1, x=checkpoints[0][0], y=checkpoints[0][1], speed=0, size=5)

# save these particles to file
with open('final_drivers', 'wb') as output:
    driver_list = sorted_list[:10]
    pickle.dump(driver_list, output)

    n += 1

However, this method does not actually breed the cars - it just randomly generates new ones. Let's change the code slightly so that it actually breeds the cars.

Copy and paste the following where the code currently says "[[[ insert code here ]]]". This will breed "n_to_keep" many pairs of cars, and add them to the new environment. What this achieves is that the best cars from the previous generation will be bred and then their children will continue on to the next. This is our "survival of the fittest" mechanic.

# loop through the best cars in pairs, breeding them (so that car0 breeds with car1 and so forth)
for i in range(n_to_keep - 1):
	parent_pairs = list(itertools.combinations(range(i + 1), 2))

	for pair in parent_pairs:
    	control_rods, bias, fov, colour = pyparticles.breed(sorted_list[pair[0]], sorted_list[pair[1]])
        env.addParticles(1, x=checkpoints[0][0], y=checkpoints[0][1], speed=0, size=5, control_rods=control_rods, bias=bias, fov=fov, colour=colour)

Now if you re-run the code, you'll notice that a small portion of the cars are actually getting better (hooray!).

But can we do better? One way we could improve this would be to randomly breed pairs of cars from a previous generation - this could take some desirable traits from cars that seem terrible on the surface allowing for beneficial mutations.

Let's implement that by copying the following below our code from before:

# randomly search through the cars from the previous generation and breed some of them
while len(env.particles) < (generation_size - 5):
    parent1 = sorted_list[random.randint(0, generation_size - 1)]
    parent2 = sorted_list[random.randint(0, generation_size - 1)]
    control_rods, bias, fov, colour = pyparticles.breed(parent1, parent2)
    env.addParticles(1, x=checkpoints[0][0], y=checkpoints[0][1], speed=0, size=5, control_rods=control_rods, bias=bias, fov=fov, colour=colour)

This will now randomly breed the rest of the cars, whilst leaving room for 5 more random ones.

If you run the code now, you'll notice that cars seem to be learning faster - this is because more breeding causes more traits to be transferred leading to a greater chance of good cars being bred.

Continuing on

How else could you improve this breeding function? Feel free to experiment - let us know if you come up with any interesting methods.