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:

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:

Further details:

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:

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:

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:

Possible bugs:

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:

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:

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:

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.