# Coders Strikes Back

## 1 Introduction

The purpose of this document is to help you create a "good" artificial intelligence for the "Coders Strike Back" game from CodinGame. I will try to keep this document agnostic with respect to programming language. There will therefore only be "pseudo code" and no working code. This pseudo code will 95% resemble C++ because it is the language I used. Do not expect to find entire classes that you would then be able to copy paste, if you want to implement what is described here you'll have to code.

## 2 Prerequisites

Here are the few things you need to be familiar with in order to not be completely lost whilst reading this document:

- Know object oriented programming (classes,inheritance...)
- Basic algorithms
- How a puzzle works on CodinGame
- Some knowledge of maths

## 3 Conception

Before going any further, it will be simpler for me to just show you a UML diagram that represents all the classes I used.

More detailed explanations:

`Point`

: This class is only used to represent a point on the map. Most of my classes inherit from`Point`

because it is much simpler for what follows.`Unit`

: I created this class for Poker Chip Race but I pretty much used it as is for this contest. This class simply represents a "unit" which possesses a unique id, a radius, a speed along x and y. It inherits from`Point`

, to have the x and y attributes, but also for practical reasons in functions.`Checkpoint`

: Represents a checkpoint.`Pod`

: Represents a pod.`Collision`

: Represents a collision between 2`Unit`

with the time`t`

at which the collision will happen.`Solution`

and`Move`

will be detailed in the section of this document concerning genetic evolution.

Further details:

- Why does
`Checkpoint`

inherit from`Unit`

when it can't move? : They can't move but I use the`Unit`

class in my prediction of collisions. And to know if I pass a checkpoint, I consider it as a collision with the checkpoint. You will see in what follows that this simplifies things. - Why is
`r`

a float when it can only have two different integer values(400 and 600) ? : For performance reasons. Multiplying and dividing integers with floats implies a cast of the integers to floats. So instead of casting it over and over, I keep it as a float. - Why no
`Vector`

class ? : The answer is simple. Even if having a`Vector`

class would have made my code "cleaner", clean code and performance are often mutually exclusive. In my code there are only 3 or 4 very specific spots where vectorial operations are used. But these specific spots are called hundreds of thousands of time every turn. Using a`Vector`

class just to make 4 places more "clean" would have lost me allot of performance.

## 4 Simulation

To make an efficient artificial intelligence, we need to be able to simulate the upcoming turns to be able to tell what is going to happen. At a minimum we need to be able to predict movements. Being able to predict collisions is obviously even better.

We will start by the movements as they are simpler. In a turn each pod will do the following things in this order:

- The pod will turn towards its target. If the pod wants to turn by more than 18° to face its target, it only turns by 18°.
- We then apply the requested thrust to the speed of the pod (between 0 and 200)
- The pod moves according to its new speed
- We reduce the speed of the pod by 15%, in other words we multiply the speed by 0.85
- The x and y attributes of the pod are rounded to the nearest integer
- The vx and vy attributes of the pod are truncated

In order to easily simulate I recommend you clone all the pods at the beginning of the turn. This will allow you to get back to the initial state very easily after having simulated several turns. Some languages have built-in `clone`

methods, otherwise you will have to code it yourself.

### 4.1 Some reminders

Before diving in, here is the pseudo code for some simple utility methods of my classes:

#### 4.1.1 `distance`

and `distance2`

methods of `Point`

```
float distance2(Point p) {
return (this.x - p.x)*(this.x - p.x) + (this.y - p.y)*(this.y - p.y);
}
float distance(Point p) {
return sqrt(this.distance2(p));
}
```

Why 2 functions for the distance ? Just because `sqrt`

is slow, whatever the language. Performance will be better if you can avoid it. Sometimes we need the square of the distance for some calculations, so we will call `distance2`

directly.

### 4.2 Rotation

To know how a pod will turn you must first know the angular difference between the current angle of the pod and the target. The current angle of the pod is given in the inputs of the program between 0 and 359. An angle of 0 corresponds to facing east, 90 is south, 180 west and 270 north. Here is the pseudo code for the `getAngle(Point p)`

method of the `Pod`

class:

```
float getAngle(Point p) {
float d = this.distance(p);
float dx = (p.x - this.x) / d;
float dy = (p.y - this.y) / d;
// Simple trigonometry. We multiply by 180.0 / PI to convert radiants to degrees.
float a = acos(dx) * 180.0 / PI;
// If the point I want is below me, I have to shift the angle for it to be correct
if (dy < 0) {
a = 360.0 - a;
}
return a;
}
```

This function returns the angle that the pod would need to face the given point. So if the point is exactly at the top right of the pod this function will return `315`

. We then need to know by how much (and in which direction) the pod must turn to face that point. This is the goal of the `diffAngle`

method:

```
float diffAngle(Point p) {
float a = this.getAngle(p);
// To know whether we should turn clockwise or not we look at the two ways and keep the smallest
// The ternary operators replace the use of a modulo operator which would be slower
float right = this.angle <= a ? a - this.angle : 360.0 - this.angle + a;
float left = this.angle >= a ? this.angle - a : this.angle + 360.0 - a;
if (right < left) {
return right;
} else {
// We return a negative angle if we must rotate to left
return -left;
}
}
```

We therefore have an angle and a direction in which to turn. The direction is given by the sign of the result. If it is negative we turn to the left, otherwise the right. The only thing left to do is to actually turn, which is done by the `rotate`

method:

```
void rotate(Point p) {
float a = this.diffAngle(p);
// Can't turn by more than 18° in one turn
if (a > 18.0) {
a = 18.0;
} else if (a < -18.0) {
a = -18.0;
}
this.angle += a;
// The % operator is slow. If we can avoid it, it's better.
if (this.angle >= 360.0) {
this.angle = this.angle - 360.0;
} else if (this.angle < 0.0) {
this.angle += 360.0;
}
}
```

### 4.3 Applying the thrust

Now that the pod is turned we need to apply the thrust. This is the role of the `boost`

method :

```
void boost(int thrust) {
// Don't forget that a pod which has activated its shield cannot accelerate for 3 turns
if (this.shield) {
return;
}
// Conversion of the angle to radiants
float ra = this.angle * PI / 180.0;
// Trigonometry
this.vx += cos(ra) * thrust;
this.vy += sin(ra) * thrust;
}
```

### 4.4 Moving

The only thing left to do is to move the pod with the `move`

method:

```
void move(float t) {
this.x += this.vx * t;
this.y += this.vy * t;
}
```

What is the purpose of this `t`

parameter ? It will be useful later when we'll want to simulate an entire turn while taking into account collisions. It is used to indicate by how much the pod should move forward. If `t`

is `1.0`

then the pod will move for a turn's worth. If it's `0.5`

it will only move for half a turn's worth. If you don't want to simulate collisions you can replace `t`

by `1.0`

.

### 4.5 After the move

Once the pod has moved we need to apply friction and round (or truncate) the values. This is what the `end`

method does:

```
void end() {
this.x = round(this.x);
this.y = round(this.y);
this.vx = truncate(this.vx * 0.85);
this.vy = truncate(this.vy * 0.85);
// Don't forget that the timeout goes down by 1 each turn. It is reset to 100 when you pass a checkpoint
this.timeout -= 1;
}
```

**Warning**: This is pseudo code, `truncate`

doesn't exist. But if you don't want to have rounding errors I advise you don't use `floor`

. Why? It's very simple, just run the following code in the language of your choice:

```
print(floor(1.5));
print(floor(-1.5));
```

The output will be something along the lines of `1.0 -2.0`

. Indeed, `floor`

doesn't do what you'd like on negative numbers. If your language allows it, it is better to cast `this.vx`

and `this.vy`

to integers, this will truncate all the decimal places. If you can't cast then you'll need to `floor`

or `ceil`

depending on whether the number is positive or negative.

## 4.6 Simulating an entire turn

You are now able to simulate the motion of a pod for an entire turn and therefore to predict which position the pod will be in, in the following turn, assuming it aimed for a specific point with a specific thrust. This is the `play`

method:

```
void play(Point p, int thrust) {
this.rotate(p);
this.boost(thrust);
this.move(1.0);
this.end();
}
```

You are not yet able to predict collisions and their effects, but just with this you will be able to test several angles and speeds and choose the best. If you do predictions over several turns to choose the best path for your pods you should be able to reach top 50 easily.

### 4.7 Predict a collision

We now discuss the most complicated part of simulating an entire turn: collisions. We have 2 objects of the `Unit`

class and we want to know when these 2 objects will collide during the turn. This is what the `collision`

method of `Unit`

does. But before discussing the code in detail, a little bit of theory.

First of all there are collisions we can immediately detect because the two objects are already touching each other. If the distance between 2 objects is less than the sum of the two radii they collide immediately.

But how do we detect that 2 moving objects will collide ? We can start by simplifying the problem. We can change reference frame and place ourselves in the reference frame of one of the two units. Doing this simplifies the problem: we now have to detect whether a moving object will collide with a stationary object. This is where geometry comes in.

The moving object moves along a line. To know if the objects will collide we have to look at the shortest distance between the stationary object and that line. If this distance is less than the sum of the two radii, they might collide. To confirm whether or not they will, we have to look at the speed of the moving object to check if it is moving towards or away from the stationary object. If it is moving towards it then we need to look at how long it will take for the moving object to reach the stationary one. If a collision takes a time `t`

longer than `1.0`

then we know the collision will take place in the next turns and we can ignore it.

As a start here is the code of the `closest`

method of `Point`

. It allows us to find the closest point on a line (described by two points) to another point.

```
Point closest(Point a, Point b) {
float da = b.y - a.y;
float db = a.x - b.x;
float c1 = da*a.x + db*a.y;
float c2 = -db*this.x + da*this.y;
float det = da*da + db*db;
float cx = 0;
float cy = 0;
if (det != 0) {
cx = (da*c1 - db*c2) / det;
cy = (da*c2 + db*c1) / det;
} else {
// The point is already on the line
cx = this.x;
cy = this.y;
}
return new Point(cx, cy);
}
```

Now we can discuss the code the `collision`

method of `Unit`

:

```
Collision collision(Unit u) {
// Square of the distance
float dist = this.distance2(u);
// Sum of the radii squared
float sr = (this.r + u.r)*(this.r + u.r);
// We take everything squared to avoid calling sqrt uselessly. It is better for performances
if (dist < sr) {
// Objects are already touching each other. We have an immediate collision.
return new Collision(this, u, 0.0);
}
// Optimisation. Objects with the same speed will never collide
if (this.vx == u.vx && this.vy == u.vy) {
return null;
}
// We place ourselves in the reference frame of u. u is therefore stationary and is at (0,0)
float x = this.x - u.x;
float y = this.y - u.y;
Point myp = new Point(x, y);
float vx = this.vx - u.vx;
float vy = this.vy - u.vy;
Point up = new Point(0, 0)
// We look for the closest point to u (which is in (0,0)) on the line described by our speed vector
Point p = up.closest(myp, new Point(x + vx, y + vy));
// Square of the distance between u and the closest point to u on the line described by our speed vector
float pdist = up.distance2(p);
// Square of the distance between us and that point
float mypdist = myp.distance2(p);
// If the distance between u and this line is less than the sum of the radii, there might be a collision
if (pdist < sr) {
// Our speed on the line
float length = sqrt(vx*vx + vy*vy);
// We move along the line to find the point of impact
float backdist = sqrt(sr - pdist);
p.x = p.x - backdist * (vx / length);
p.y = p.y - backdist * (vy / length);
// If the point is now further away it means we are not going the right way, therefore the collision won't happen
if (myp.distance2(p) > mypdist) {
return null;
}
pdist = p.distance(myp);
// The point of impact is further than what we can travel in one turn
if (pdist > length) {
return null;
}
// Time needed to reach the impact point
float t = pdist / length;
return new Collision(this, u, t);
}
return null;
}
```

With this method, we can therefore know if 2 objects of `Unit`

type will collide during a turn, and more importantly, when they will.

### 4.8 The consequences of a collision

Here we have to distinguish several types of collisions. First and foremost a very easy collision type is the collision of a `Pod`

and a `Checkpoint`

. There is no bounce, we just need to increment de checkpoints-passed counter of the pod and reset its timeout to 100.

Now the complicated case: 2 pods collide. The collisions in this contest are perfect elastic collisions with a half-momentum of 120. You didn't understand? Me neither. Frankly I would've never found this code without the help of Neumann and pb4608. But here is the code of my `bounce`

method from the `Pod`

class:

```
void bounce(Unit u) {
if (u instanceof Checkpoint) {
// Collision with a checkpoint
this.bounceWithCheckpoint((Checkpoint) u);
} else {
// If a pod has its shield active its mass is 10 otherwise it's 1
float m1 = this.shield ? 10 : 1;
float m2 = u.shield ? 10 : 1;
float mcoeff = (m1 + m2) / (m1 * m2);
float nx = this.x - u.x;
float ny = this.y - u.y;
// Square of the distance between the 2 pods. This value could be hardcoded because it is always 800²
float nxnysquare = nx*nx + ny*ny;
float dvx = this.vx - u.vx;
float dvy = this.vy - u.vy;
// fx and fy are the components of the impact vector. product is just there for optimisation purposes
float product = nx*dvx + ny*dvy;
float fx = (nx * product) / (nxnysquare * mcoeff);
float fy = (ny * product) / (nxnysquare * mcoeff);
// We apply the impact vector once
this.vx -= fx / m1;
this.vy -= fy / m1;
u.vx += fx / m2;
u.vy += fy / m2;
// If the norm of the impact vector is less than 120, we normalize it to 120
float impulse = sqrt(fx*fx + fy*fy);
if (impulse < 120.0) {
fx = fx * 120.0 / impulse;
fy = fy * 120.0 / impulse;
}
// We apply the impact vector a second time
this.vx -= fx / m1;
this.vy -= fy / m1;
u.vx += fx / m2;
u.vy += fy / m2;
// This is one of the rare places where a Vector class would have made the code more readable.
// But this place is called so often that I can't pay a performance price to make it more readable.
}
}
```

**Warning**: This method rests on the hypothesis that the 2 pods have moved to their respective impact points. The explanation of how to move your pods and play out collisions with the goal of simulating an entire turn is found in the "Simulating an entire turn" chapter.

### 4.9 The effects of the shield

As written in the comments of the `bounce`

method in the previous chapter, the only effect of the shield is to multiply the mass of a pod by 10. The consequence of this is that when a pod with its shield on collides with a pod without its shield on, the impact vector will apply 10 times more to the shieldless pod. Don't forget that the shield prevents the pod from accelerating in the next 3 turns after the shield. The pod can give whatever thrust it wants but it will be disregarded. You can however shield again during those 3 turns, but obviously the 3 turn counter is reset.

## 4.10 Predicting that a pod will pass a checkpoint

This is the reason why my `Checkpoint`

class inherits from `Unit`

. Passing through a checkpoint is nothing more than colliding with it. The only difference is that there is no bounce to apply. You only have to increment the checkpoint-passed counter and reset the timeout to 100.

### 4.11 Simulating an entire turn

With all the previously described methods, we can simulate an entire turn of the game. How do we proceed? We first need to look at all the collisions that will take place during the turn and keep the one that will happen first. We then move the pods until the time `t`

of that collision. We play out that collision and we then start over and over until we no longer have any collisions. We can then move the pods to the end of the turn. But be careful, when we play out a collision we have to recompute future collisions because a collision between 2 `Unit`

can prevent another collision from happening or lead to a new one.

To recompute the new collisions there are 2 ways:

- Run the same calculations again and take the collision that's happening the soonest
- Store the previously found collisions, get rid of collisions concerning the 2
`Unit`

that had the previous collision and recompute only the collisions of those 2`Unit`

with the others

On paper the second solution looks like it will lead to better performance. But in fact the first one was better for this contest because on average there are too few collisions per turn for the second solution to be faster. However if you want to apply this principle to a game like Poker Chip Race, I recommence you use the second solution.

With these principles in mind we can write the code of the `play`

function which will simulate an entire turn.

```
void play(Pod[] pods, Checkpoint[] checkpoints) {
// This tracks the time during the turn. The goal is to reach 1.0
float t = 0.0;
while (t < 1.0) {
Collision firstCollision = null;
// We look for all the collisions that are going to occur during the turn
for (int i = 0; i < pods.length; ++i) {
// Collision with another pod?
for (int j = i + 1; j < pods.length; ++j) {
Collision col = pods[i].collision(pods[j]);
// If the collision occurs earlier than the one we currently have we keep it
if (col != null && col.t + t < 1.0 && (firstCollision == null || col.t < firstCollision.t)) {
firstCollision = col;
}
}
// Collision with another checkpoint?
// It is unnecessary to check all checkpoints here. We only test the pod's next checkpoint.
// We could look for the collisions of the pod with all the checkpoints, but if such a collision happens it wouldn't impact the game in any way
Collision col = pods[i].collision(checkpoints[pods[i].nextCheckpointId]);
// If the collision happens earlier than the current one we keep it
if (col != null && col.t + t < 1.0 && (firstCollision == null || col.t < firstCollision.t)) {
firstCollision = col;
}
}
if (firstCollision == null) {
// No collision, we can move the pods until the end of the turn
for (int i = 0; i < pods.length; ++i) {
pods[i].move(1.0 - t);
}
// End of the turn
t = 1.0;
} else {
// Move the pods to reach the time `t` of the collision
for (int i = 0; i < pods.length; ++i) {
pods[i].move(firstCollision.t);
}
// Play out the collision
firstCollision.a.bounce(firstCollision.b);
t += firstCollision.t;
}
}
for (int i = 0; i < pods.length; ++i) {
pods[i].end();
}
}
```

**Possible Optimisations**:

- This code could be further optimised. But I didn't have the time to do so. One thing is this code recomputes all collisions even when a pod collides with its checkpoint. This is unnecessary because such a collision doesn't change the speed vector of the pod. We could therefore just store the collisions and play out the next one without recomputing all collisions.
- if you want to use the 2nd solution suggested before this code, be careful and do benchmark the performance, there is a risk that by storing and sorting the collisions (or going through them to find the one that is happening the soonest) you will incur more overhead than by just recomputing everything.

**Possible bugs**:

- The most frequent bug here is the infinite loop, which can happen because of rounding errors and comparing floats. When you move the pods to their impact points in anticipation of a collision, it can happen that at the next iteration of the loop we detect an immediate collision (because the pods are touching), which leads to a nice infinite loop. This is a bug you can easily avoid by adding a security to the above function. You store the previous collision of the while loop and if you find a collision with a
`t`

of`0`

concerning the same 2`Unit`

, ignore it.

### 4.12 Simulating the future

With the function of the previous chapter you can simulate an entire turn. But if you've been paying attention you will have noticed that simulating a turn with pods that do nothing (they face their current direction and don't thrust) is useful but not so interesting. We want to test what will happen if we play this or that move. Here is a simple code you can adapt that will simulate the entire turn assuming the pods all aim for the `(8000,4500)`

point with a speed of `200`

:

```
void test(Pod[] pods, Checkpoint[] checkpoints) {
for (int i = 0; i < pods.length; ++i) {
pods[i].rotate(new Point(8000, 4500));
pods[i].boost(200);
}
play(pods, checkpoints);
}
```

### 4.13 How to manage the shield?

This is clearly not the hardest thing to manage. My `Pod`

class simply has a `activeShield`

method which changes the `shield`

attribute to `true`

and which initialises the counter of 3 turns (to remember it can't thrust for 3 turns).

## 5 The brains of the pods

Now that we know how to simulate the next turns, we can see further. Technically we can see as far as we want! For example 10 turns later. But this wouldn't be so useful. From here there are many solutions. We can test allot of possibilities and look at the next turn to choose the best move, or even in 5 turns. We could be tempted to test all possibilities but there are way too many. In what follows I will describe one possible solution. There are others and I will give links at the end.

### 5.1 The evaluation function

Whatever the method we use, an evaluation function is mandatory. The evaluation function takes the state of the game at a certain time and gives it a score. This is the most crucial part of your code. This is the part that determines absolutely everything. It will determine the behavior of your pods, the way they move, defend, avoid others, help each other... It can also determine the way you will predict your opponent's moves.

Several high ranking players have explained their evaluation function. Here I will explain what I put in mine:

- If I have lost (the opponent finished the race or one of my timeouts is on 0), I return
`-Infinity`

. The worst possible score. - On the contrary if I have won (I finished the race or my opponent has one of his timeouts on 0), I return
`+Infinity`

. The best possible score. - For each player, I consider that there is a "runner" pod and a "hunter" pod. The "hunter" term isn't the most appropriate but it's the best I found.
- My score starts with a line like this:
`score += myRunner.score() - hisRunner.score();`

. The more I am ahead, the better. - I then try to keep my hunter close to the checkpoint of his runner:
`score += myChaser.distance(hisRunner.checkpoint());`

- I try to keep my hunter aiming for the enemy runner:
`score -= myChaser.diffAngle(hisRunner);`

The idea is then to apply different coefficients to these different parameters to reach something you like. You can add parameters, remove some, etc... For example in my case, I multiply the first parameter (the difference between the score of the runners) by 50 to make sure it is always the dominating term.

The `score`

method of my `Pod`

class is very simple. It looks like this:

```
float score() {
return checked*50000 - this.distance(this.checkpoint());
}
```

This is simply the number of checkpoints I have passed multiplied by `50000`

minus the distance between the pod and its next checkpoint. `50000`

is obviously an arbitrary value. We just need a big enough number for the number of checkpoints passed to always be the most important term.

At the beginning of every turn, I look at the score of all the pods. This allows me to choose who is my runner and who is my hunter. I do the same for the opponent.

### 5.2 Genetic evolution

Genetic evolution is one of the possible ways to choose which moves our pods will make. The principle is quite simple and is based on genetic evolution as is found in nature with survival of the fittest.

The basic idea is to start with a starting population of X solutions (in my code X is 5, but you can take other values). Every solution has a score and a capacity to adapt. The we take some of these solutions at random and we mutate them randomly. We can also cross them between each other to make new ones. From here there are several possible implementations of genetic evolution:

- We always keep the X best solutions. So when we generate a new solution (by mutation or crossing), we look at its score and if it is worse than our X current solutions we throw it away. But if it is better than one of them we keep it and we throw away the worse of the X+1 solutions.
- An other implementation is to never throw away solutions but to always evolve the current solutions. But if you do this, you have to be careful as to how you do your crossings and mutations as explained on this page page from wikipedia.

From having tried the 2 methods, the first one gave the best results for me.

We repeat for 150ms (the longest time your program can take to answer each turn). The pseudo algorithm looks like this:

```
Solution[] solutions = generatePopulation();
while (time < 150) {
Solution solution = solutions[random(0, X)].mutate();
if (solution.score() > minScore) {
keepSolution();
}
}
```

This code is obviously overly simplified. But the idea is there. We can go more into details now.

#### 5.2.1 What is a solution?

In my code a solution is a list of pairs of moves. A move for the first pod and a move for the second pod. For genetic evolution to work correctly, we need a move to be independent from the current state of the pod. In my code, my `Move`

class looks like this:

```
class Move {
float angle; // Between -18.0 and +18.0
int thrust; // Between -1 and 200
}
```

I added something special and not so clean to manage shields. In my code I defined the following constant: `const int SHIELD = - 1;`

. This avoids me having to manage an extra attribute in my `Move`

class and I gain in performance. If a `Move`

has a `thrust`

of `-1`

, the pod will activate its shield. Having a `Move`

class built this way allows me to have a move independent of the pod. The pod can be in any state, it will still be able to make a `Move`

whatever its situation.

My `Solution`

class is therefore simple as well:

```
class Solution {
Move[] moves1;
Move[] moves2;
}
```

`moves1`

are the moves of my first pod and `moves2`

are the movements of my second pod. You still have to choose over how many turns you want to test your solutions. I tried several values from 5 to 10. It's 6 turns that gave me the best results.

You also have to implement the `score`

method of `Solution`

, which will simulate the desired number of turns and use the evaluation function at the end of the simulation to return the score of the solution.

```
float score() {
// Play out the turns
for (int i = 0; i < moves1.length; ++i) {
// Apply the moves to the pods before playing
myPod1.apply(moves1[i]);
myPod2.apply(moves2[i]);
play();
}
// Compute the score
float result = evaluation();
// Reset everyone to their initial states
load();
return result;
}
```

The `apply`

method of my pods only applies a move to the pod. It turns the pod, applies the thrust (or the shield). Earlier I spoke of my `load`

function. After a simulation you need to put everyone back in their original state, this is what my `load`

function does.

#### 5.2.2 Mutations and Crossings

There are 2 ways to evolve a solution. One is by mutation and the other is by crossing.

Mutation is taking one or more moves at random in a preexisting solution and to change them randomly. Crossing is taking 2 solutions and from them to create one (or more than one sometimes) new solution by randomly picking moves from the 2 solutions.

But be careful, you can't do it any old way. For evolution to work properly, you first need to have "big" evolutions and as you go on, evolutions become smaller and smaller. To give an example, here is the `mutate`

method of my `Move`

class:

```
void mutate(float amplitude) {
float ramin = this.angle - 36.0 * amplitude;
float ramax = this.angle + 36.0 * amplitude;
if (ramin < -18.0) {
ramin = -18.0;
}
if (ramax > 18.0) {
ramax = 18.0;
}
angle = random(ramin, ramax);
if (!this.shield && random(0, 100) < SHIELD_PROB) {
this.shield = true;
} else {
int pmin = this.thrust - 200 * amplitude;
int pmax = this.thrust + 200 * amplitude;
if (pmin < 0) {
pmin = 0;
}
if (pmax > 0) {
pmax = 200;
}
this.thrust = random(pmin, pmax);
this.shield = false;
}
}
```

As the code shows, I have an `amplitude`

parameter which allows me to "dose" the random mutations of a `Move`

. At the beginning of a turn of my AI, this parameter is `1.0`

to have maximal mutations. The more I advance in my evolutions and my simulations, the smaller it gets. This produces better evolutions.

The shield is a case in its own right, I just have a constant `SHIELD_PROB`

which indicates the probability that a `Move`

will mutate into an activation of the shield. In my final version this constant was `20`

.

#### 5.2.3 Creating the starting pool of solutions

To create the starting solutions there are several methods:

- Completely at random
- Make solutions with a simple AI
- Take the winning solution of the previous turn (after having taken away its first
`Move`

of course, and after having added another move at the end either randomly or with a simple AI) - A mix of the previous 3 ways

In my code my starting population is composed of 3 random solutions, 1 solution made by a simple AI (`if`

based AI) and I take the winning solution from the previous turn.

## Predicting the enemie's moves

If you looked carefully at the code I gave for the `score`

method of `Solution`

, you will have noticed that we don't move the opponent's pods. We consider that they will just wait (they don't turn and they don't thrust). This is obviously wrong because the opponent will very often move. This is why we need a way to predict his moves. This is a crucial part of your code. The more accurate your predictions, the more ruthless your AI will be. In my case, my solution wasn't good and that's why my AI got crushed by Jeff06, pb4608 and Owl.

In my code I use a very simple AI to predict the moves of my opponent. And it doesn't work well. My AI is very simple and is often very far from the moves my opponent does. Note that this doesn't prevent cooperation between your pods (which rarely depends on the opponent's moves), But this could prevent your runner from avoiding the enemy hunter and could prevent your hunter from blocking the enemy runner.

Jeff06 went for another solution. He does a genetic evolution for the opponent (considering his own pods will wait) for 10ms. He keeps the best solution found for the opponent and then he evolves his own moves assuming the opponent will make those moves. Given that Jeff06 won the contest, I deduce that his solution is much better than mine!

### 5.3 Converting a `Move`

for output

The last step is to convert the first `Move`

of the best solution from the evolution to output it to stdout. But stdout doesn't take a `Move`

made up of an angle change and a thrust. We have to use some trigonometry:

```
void output(Move* move) {
float a = angle + move.angle;
if (a >= 360.0) {
a = a - 360.0;
} else if (a < 0.0) {
a += 360.0;
}
// Look for a point corresponding to the angle we want
// Multiply by 10000.0 to limit rounding errors
a = a * PI / 180.0;
float px = this.x + cos(a) * 10000.0;
float py = this.y + sin(a) * 10000.0;
if (move.shield) {
print(round(px), round(py), "SHIELD");
activateShield();
} else {
print(round(px), round(py), move.power);
}
}
```

## 6 Other solutions

I was not the only one who used a genetic algorithm. Jeff06, Neumann and pb4608 did it as well (with more success than me because they beat me). Owl used a minimax / alpha-beta method by reducing the possible moves to 7 per pod. You are welcome to go read their explanations on the forum and on the CodinGame blog.