Genetic algorithm brings evolutionary practices to programming : Xavier Das | feedback@digit.in
With the advent of Machine Learning, Artificial Intelligence
and Neural Networks a particular type of algorithm, Genetic Algorithms, have been used heavily. That is exactly what we are going to explore today and see how it can be used to build a game very similar to ‘Space Invaders’. In the field of Data Science, Genetic Algorithm is a heuristic method that emulates the Darwinian process of natural selection among a population where the fittest individuals are selected and are allowed to cross between themselves and mutate to produce better performing individuals, essentially bettering the entire population. It belongs to the superset of the evolutionary algorithms. It can also be thought of an optimization or a search technique.
ABOUT THE GAME
The invaders are going to multiply in every five second and our objective
should be to keep destroying them until none exists. The invaders learn from our behavior and keep developing immunity against our attacks. The game begins with 4 invaders which is also the minimum number and can get to a maximum of 100. It can thus be inferred that we can never win the game and if the number of invaders reach a hundred, we lose. To rephrase, the objective should be to keep the
invaders to number as few as possible on the screen. There are a few biological terms used in this context but they are easily relatable. Each invader has 4 genes (characteristics or attributes): speed, velocity, probability of its changing direction, size. At every 5 seconds, a few invaders are chosen from their entire lot by a measure of fitness following which they mate and produce children (which are supposedly better performing than their predecessors). A flowchart of the process helps for a better visualization as shown above.
We begin by initializing a population of solutions by a fitness value that is computed from a function. We select the individuals higher up in the ranks of their fitness (which may just as well be a numerical value). Thereafter comes the crossover stage where they are then made to reproduce
which leads to offspring which have qualities inherited from their parent. To give them variety, we allow them to mutate where a single individual characteristic may be altered by a bit. This procedure is carried on in a loop until the stopping criteria has been satisfied. In this case, the stopping criterion is reached if the number of invaders reaches its maximum. Let’s understand the code bit by bit now
The lowest level of the code, evolution.py is where the central genetic algorithm has been implemented which is basically our goal. However, we shall ride through the rest of the code to see how the structure of this game can be implemented in Python. We will use Python as our programming language for the generation of the code. There shall be four modules which we shall import, namely, sge, game, objects and os. The sge is a wrapper around pygame, which is one of the famous game building libraries in Python. The game object defines the essentials for the game logic. The objects stand for the players and the invaders and the os shall provide the operating system.
THE IMPLEMENTATION
We begin by setting the path to the repository of the game and then initialize the game object specific
parameters like the wall height and width, the color of the screen, resolution as a background layer and set the background layer as the background of the game.
Having done this much, we will initialize our participants in this game.The player and the invaders, respectively. We use the xrange function to loop over and create 4 identical invaders and create a singular player. Both of them are concatenated to an object in which the player comes first, followed by the invaders.
Thereafter, we initialize the session of the game calling the GameRoom function of the game class passing the above defined concatenated object (for the player and the invaders) and the background as parameters. It’s better if we disable the mouse pointer when the game loads as well.
With this done, we have almost set up the environment for the game to be run on. Now, we shall have to add details and functionalities (and attributes) to our participants (players and the objects). This is something similar to what a default constructor does and is necessary for the steps involved in the genetic algorithm, because it is on the basis of the values of these genes that we’ll be performing crossovers, mutation and checking fitness. We do that by setting the data members for the class Invaders with some values of our choice We achieve this by using the dictionary data structure in Python wherein the key value pairs stand for the attribute and its respective values.
For each attribute or a gene, we have a minimum value, a maximum value and a random number that is generated by a gamma distribution. The boundary values (the maximum and the minimum) ensure that the value of a gene stays within that range and if the value should exceed the upper
limit or fall below the lower limit, the value is set to the boundary value. The keys for the dictionary (genes) we’ve used are size, xvelocity (velocity along x axis), yvelocity
(velocity along y axis), the probability of changing direction along x axis and the probability of changing directions along the y axis.
In the init function, we assign the genes with values by generating them using the above approach. We also set a cool dynamic looking sprite around the player which adds to the visual aesthetics of the game play. Herein, we set the initial value of the fitness to zero which shall evolve over time.
We also use a function called event_step in which we increase the fitness by one. There is also the possibility of a direction switch and the invader bouncing off the walls.
THE LISTENER
To attain this, the directions are randomly changed at any instant on comparing a randomly generated number with the probability of change in direction of an invader along x and y axes. At any instant, the movement of the invader is also a factor that needs to be considered. An invader may keep moving without any hindrances and when it hits a wall, it needs to bounce back and that too has been handled by the code appropriately.
A point to note is that this function event_step has not been called from any other method or function. It behaves like a listener, establishing a channel which is always on the look for changes of any kind to the invader. Should any such change be encountered, this function is automatically called and the fitness is increased by
one following the other changes. To make it transparent, we understand that at any moment there lies a possibility for the invader to bounce at a wall and/or change its motion for whatever reason. And the longer the invader stays in the particular game, the more fit it is.
Like we have set the initial properties for the invaders, we do the same for the players. We set the basic movements (left and right) along with the start position. Again, with the help of the function event_step we capture the keypress (whether the player is to be moved left or right), find its speed and further animate the sprite to move in accordance with the direction of the keypress. Interesting, isn’t it? There is also a function that is going to take care of the shooting by the player for which the only prerequisite is that the number of invaders should be greater than the minimum and the number of bullets should be lower than the minimum.
We’ve also defined a class for the bullet wherein we set the sprite animation for the bullet and the velocity of the bullet at its initiation.
In the event_step function for the bullet, we deal with two possibilities, one of which is the destruction of the bullet itself, i.e., the bullet has been fired by the player but it has failed to
hit any target invader and has hit the boundaries. The other case is when the invader has been directly hit by the bullet and the invader count has been reduced by one.
Next up, we understand what the game class does. We import the game engines, the participants and evolutionary algorithm in the game class and define some global variables to handle the player speed, bullet speed,resolution, the minimum generation time, the maximum and minimum number of invaders possible, etc.
We also keep a method for a new generation in which at every new generation, the time between two consecutive generations are reduced, as a means to keep the game getting harder. As far as we are concerned with the events that shall occur at each event_step, we need to find if it’s game over or not. To do that, we calculate the number of invaders on the screen at any given moment and see if it exceeds the maximum. On the other extreme, if it strikes your memory, you would remember that we did talk of how one can never win the game. There shall always be a minimum of four invaders persistent throughout.
There are several other methods present that deal with key presses, game pauses, game exits, crossover animation, etc. A few of them are shown in the image above and can be used if you see fit.
RECOMBINE
Let’s move on to the crux of the matter in hand, the bit of the code that actually deals with Genetic Algorithm. In order of its sequence, the first is crossover, for which we have a method called recombinate.
The parameters that we are going to use for this function are the pairs of parents, the gene properties, the mutation probability and the effect.
We define a list to hold the offsprings. For each pair of parents we
shall have a child gene formed which
we are going to store in a dictionary. For each gene in the first parent’s gene in the gene values list (the value part of the dictionary), we store both the values of the parent’s gene. Now, for each of the child genes corresponding to the parent’s gene, we use a distribution function of the random class to find a value to be allotted to the child gene with the minimum and maximum values as bounds for the distribution function being used.
If the random number generated is less than the mutation probability, we believe that it is time to mutate. We store the minimum and maximum values for the parent’s genes. We already have the child’s gene from the value computed above.
For mutation, we would basically replace a specific parameter in the gene by a random value in between its boundaries, with the help of the random functions. Having done that, all we are left with is to append the children gene into the offspring gene. The next part deals with selection of the fittest individuals within the population.
SELECTING THE FITTEST
We begin by getting a summation of the fitness of all the individuals. We set up a separate list called selected which will contain the individuals that are selected. Next, we begin a while loop to until the length of the array is greater than a certain value. Inside the loop, we use a randomly generated uniformly distributed number with its limits as 0 and the sum calculated above, and this number is being subtracted by the evaluated individual’s fitness’ values. If the resultant value’s
function is less than zero, we consider adding that particular individual to the array selected that we have created earlier. This could have been done very simply by finding the top few individuals with the highest fitness functions but the interest of adding a random number distribution allows a broader scope of consideration keeping in mind the performance of the genetic individuals in the long run. What we see immediately may, only under the present circumstances, be perfect without any guarantee of a durable performance in the longer run. And this trend of adding a variety (be it in terms of a probabilistic distribution or something else) has always been used to improve the variety of the resultant individuals that will comprise the newer population. With this we have come to the end of this article, and at this point, the concept of a genetic algorithm should be quite clear.
