Recently, I participate in the awesome coding contest The Accountant in CodinGames. This contest was a 2-week optimization challenge, where it was not necessary to succeed all of the given test cases to have a good score. Unfortunately, I didn't use the 2 week because I was travelling. I only used 5 days.

It was my second time in this kind of contests, and I finished in the position 1774/6214 ( you can see the report in The Accountant report for my user cguzman ). Not so bad for a second time :)

I am not an expert in Genetic Algorithm (GA), but I decided to implement one for this solution. Thus, now I will explain how was my approach for this challenged.

1. Small description of the problem

The game is played in a zone 16000 units wide by 9000 units high (the top‑left point is 0 0). You control a man named Wolff. Wolff must defend a given number of data points from a given number of enemies that are placed across the game zone.

The basic commands of Wolff are:

• MOVE X Y, that move Wolff to the specified coordinate X Y. Wolff will move exactly 1000 units towards the target coordinates, or onto the target coordinates if he is less than 1000 units away.
• SHOOT id of an enemy. Enemy's damage is 125000 / x1.2, rounded to the nearest integer; x is equal to the Euclidean distance between Wolff and the enemy.

Attempting to shoot an enemy who is already dead or does not exist will cause a game over. You score zero points.

If Wolff comes within 2000 units of any enemy, he is killed by the enemy, and you lose the game. You score zero points.

The complete description of the problem can be seen at the end of The Accountant report.

In essence, this is an optimization problem where you have to get the maximum score within a response time per game turn <= 100ms.

2. Genetic Algorithms

GAs are commonly used to generate high-quality solutions to optimization and search problems by relying on bio-inspired operators such as selection, mutation and crossover. Essentially, GA replicate the way in which life uses evolution to find solutions to real world problems, such as, search through different combinations of materials to find the perfect final product (mirrors designed to funnel sunlight to a solar collector [1] or antennae designed to pick up radio signals in space[2]); design of computer algorithms (walking methods for computer figures[3]); schedule tasks, and to solve global optimization problems.

2.1. How they work

GA takes the fundamental properties of natural selection and apply them to the problem we are trying to solve. The basic process for a GA is described in the following figure:

1. Initializate the population: We create randomly an initial population. The size of the population depends on the size of the problems search space, and the computational time it takes to evaluate each individual. Normally, you will be dealing in population counts of about 50 up-to a 1000.
2. Evaluation: The evaluation function determines the fitness value of an individual (member of the population). This is the most important part for the GA. The fitness value is calculated by how well it fits with our desired requirements. For instance, for evaluating distances between cities you may return the total distance traveled as a fitness score, for a classifier you can return the number of correct classifications, or for our problem we can return the score that we get with the simulation of executing all commands of Wolff :)
3. Selection: This step helps us to keep the best individuals in the population. There are a few different selection methods: fitness proportionate selection, tournament selection, and truncation selection.
4. Crossover: Until this step, we have selected a set of individuals also known as parents. Now, during the crossover we created a new population of children by combining aspects of the parents. The hope is that by combining certain traits from two or more parents we will create an even 'fitter' offspring which will inherit the best traits from each of it's parents.
   
   The basic crossover operators can be seen in the next figure:
5. Mutation: It allows the algorithm to introduce diversity into the population, expanding the opportunity to search unexplored areas in the search space for fitter solutions. Mutation typically works by making very small changes at random to the individuals.
6. Repeat: We can start again from the step 2 until we reach the termination condition, e.g. in our problem we stop when we reach 100 iterations. We can also stop when the time exceeds the time limit of 100 ms.

2.2. Limitations

The limitations of an GA are that we can never know if we achieve the optimal solution. Thereby, we are often never able to guarantee that our GA has found the global optimum solution to our problem.

3. Creating the Genetic Algorithm for the accountant problem

For the GA I created the next set of clases:

• GAManager: Manages the evolve of the population such as selection, crossover and mutation.
• Population: Manages each individual of the population.
• Plan: Manages an individual. The plan holds the initial current state (Game class) and the set of commands that Wolff has to execute (ArrayList of Command classes).

Another required classes:

• Command: Represent the command that Wolff can execute: SHOOT, MOVE, or ESCAPE. ESCAPE produces the same functionality of the command MOVE. I implemented only an essential ESCAPE functionality where I try to find a possible empty path to escape from the enemies (function escapeWolff(....) in the Game class). The Command class is an inner class of Plan.
• Game: Holds the current initial state of the game. I use this class like the simulator of the game. Some particularities of this class are:
  • I use a Binary Search Tree (BST) to hold the enemies and the data points where the order key is the distance of the enemy or data point with respect to a given specific point that I use as the root node of the BST. The point (0,0) in my case. Thinking about it I do not know why I selected the point (0,0) as my reference. I think it would be better to select the current position of Wolff as the root node of the BST. Big mistake to fix :)
  • I implemented one function to simulate the execution just to test the GA, and another function to be used for the GA to execute the plan in order to get the fitness value (function getFitness() of the class Plan).
  • I implemented a function to predict the move of the enemy. I use this function to fix the X and Y values of a MOVE command used to go near an enemy.
  • This class is used as a global class. That is, I use only one instance of this class during all my execution.
• GameActions: Create all the possible commands that are going to be used for the GA. This class also holds the enemies and the data points. All the attributes of this class are static. 

 The complete source code can be downloaded from my GitHub. I am not proud of my code. I think I can do it better, but I did it in five days.

 Another user of Codingames also implemented a solution using GA, his solution can be downloaded here.

4. Final comments.

This contest was a lot of fun. I think 2 weeks is so much time for this kind of contest.

Things that I did not consider:

• move onto the target coordinates if he is less than 1000 units away.
• A better ESCAPE strategy in order to avoid the situation when Wolff comes within 2000 units of any enemy, because he is killed by the enemy and we lose the game by scoring zero points.
• Create a separated simulation algorithm.

Please, don't forget to give your comments !!

Add comment