Evolution and Beam Search

01A plan is a list of moves

Mad Pod Racing is one of CodinGame's permanent bot games: pods race laps around a track of checkpoints. Each turn your bot prints, for each of its pods, a point to steer toward and a thrust. The pod turns toward that point by at most 18°, the thrust adds to its velocity, and only 15% of the velocity bleeds away each turn. A choice made now is still moving the pod several turns later. A pod that reaches a checkpoint too fast swings wide, and the turns it spends coming back are lost.

The game ran as a contest in 2016 under the name Coders Strike Back,^[1] and 2,530 players finished on its leaderboard,^[2] so most write-ups about it use that name. Limits depend on the league. The starting league allows thrust from 0 to 100 and 75 ms per turn;^[3] the top league allows thrust 200,^[4][5] and the 2016 contest gave bots 150 ms a turn.^[6] The demos here use the Gold league's limits: thrust up to 100 and one BOOST, a single burst of 650, per pod.

The minimax and Monte Carlo tree search pages build a tree with one branch per move. Here a move is any angle from −18° to +18° and any thrust from 0 to 100, for each of two pods, and the tree explodes.

So planners skip the tree and search over plans directly. A plan is the next few moves for your pod, six on this page, each a turn angle between −18° and +18° and a thrust between 0 and 100. Evolutionary search calls this list a genome. To score a plan, run it through your simulator, the copy of the referee's rules from Referees and Simulators, and rate where the pod ends up, as Evaluation Functions rates a position.

One turn of those rules, for a pod alone on the track, goes like this. The pod turns toward its target by at most 18°, or by any amount on its very first turn. It adds the thrust along its new heading to its velocity, then moves by that velocity. The referee rounds the position to whole units, multiplies the velocity by 0.85 and truncates it toward zero.^[6] A checkpoint counts as passed when the pod's center gets inside its 600-unit radius anywhere along this turn's path.^[3]

A whole plan is six such turns. The first widget scores a plan by its progress along the route through A to B: the route's length at the start minus what's left of it at the end. From the pod above, three 18° turns to the left at full thrust and then three moves straight ahead pass through A and make 3,766 units of progress. Six moves straight ahead never come within 600 units of A and make 1,748.

A race needs a score that works on any track. A common one counts checkpoints passed first and uses the distance to the next checkpoint to break ties: Psyho, 8th in the 2016 contest, ranked plans by "(laps, checkpoint, distance_to_next_checkpoint)".^[7] One number does the same job. The search calls it the plan's fitness.

In words: simulate the plan, count the checkpoints the pod has passed, multiply by 50,000, and subtract how far the pod ends from its next checkpoint. No two points on the 16,000 × 9,000 field are 50,000 units apart, so one more checkpoint always beats being closer. Between plans that pass as many checkpoints, the one that ends nearer the next one wins.

02Improve a plan by trial

The bot has a fixed time each turn, and a fast simulator fits thousands of rollouts into it. A rollout is one plan simulated from the current position to its last move; Jeff06's winning 2016 bot ran about 15,000 six-turn rollouts a turn.^[8] The question is which plans to spend them on.

Random search draws whole plans at random and keeps the best one it has seen. It never builds on what it found.

Hill climbing keeps one best plan and tries small random changes to it. Changing some of a plan's moves by a random amount is a mutation; when the changed plan scores higher, it becomes the new best.

A genetic algorithm (GA) keeps a population of plans and improves all of them together, one generation at a time. The best plan of each generation survives unchanged, which is called elitism. The rest of the next generation are children. Each child gets two parents, each the better of two plans drawn at random. It takes each of its six moves from one parent or the other, which is crossover, and then mutates.

In the widget all three methods get the same budget: as many new plans per generation as the population size. The GA's surviving best plan isn't simulated again, so it tries one plan fewer per generation.

On one pod and one decision, the GA does no better than hill climbing. Crossover can only help when two parents are good for different reasons and their parts combine, for example one parent's opening moves with another's finish, or one pod's moves with the other pod's. Jeff06 put both of his pods' next six turns into one 36-gene genome so the search could find moves where the pods help each other.^[8] Three of the top seven in the 2016 contest described evolving plans:^[2]

Jeff06 and pb4608 also tilted their random draws toward extreme moves. Jeff06 turned gene values below 0.25 into the minimum and above 0.75 into the maximum; pb4608 drew angles from −40° to +40° and clipped them to ±18°, so a full-lock turn comes up 55% of the time. Owl, 2nd, went further and kept only seven moves per pod, reasoning: "How often do you accelerate only moderately? How often do you steer just slightly?"^[10]

03Keep the plan from turn to turn

After the bot plays a move, the world has advanced one turn along the plan it chose. The other five moves are probably still good. Starting the next search from random plans throws that work away.

Planning a fixed number of turns ahead, playing only the first move, and planning again next turn with the window one turn further on is called a rolling horizon; the horizon is how far ahead the plan reaches. Perez, Samothrakis, Lucas and Rohlfshagen compared rolling horizon evolution with tree search in 2013; they note the idea is also called receding horizon or model predictive control.^[11] Their version started every decision from random plans. Jeff06's and Magus's 2016 contest bots carried the plan over instead. Jeff06 kept his best genome after printing his move, shifted every gene three places to the left (one turn's worth) and put random genes at the end.^[12] Magus seeds each turn with the previous winner minus its first move, plus one new move at the end.^[6]

The planner in the next widget plans from what the referee actually sends: position and velocity in whole units and the heading in whole degrees. Its six-turn prediction can drift a few units from what really happens, and planning again every turn corrects it.

Starting near a good plan saves rollouts, because the search refines that plan instead of finding it again. Magus also shrank his mutations during each turn, large at the start and small at the end,^[6] which suits a search that begins close to an answer.

04Plan against pods that move

Everything so far raced alone. In a real race four pods share the track, and a plan that drives through the spot where an opponent will be next turn is worth less than its score says.

A plan's fitness is only as accurate as the simulator's guess of what the other pods do. The cheapest guess is that they do nothing. Magus's guide says so plainly: "We consider that they will just wait (they don't turn and they don't thrust). This is obviously wrong". His own bot predicted the opponent with "a very simple AI", which he says "doesn't work well", and he blames it for losing to Jeff06, pb4608 and Owl.^[6]

The bots above him spent part of each turn on the opponent. Each row is the player's own description:

The search optimizes against whatever the simulator assumes. With a wrong assumption it finds a plan that wins in simulation and loses on the track, and more search only polishes that plan. So the first and third bots of 2016 spent a slice of every turn predicting the opponent before planning their own pods: 30 of Jeff06's 150 ms and 24 of pb4608's 140.

05Keep the best few partial plans

Some games offer a handful of discrete moves a turn: four directions on a grid, or Owl's seven pod moves. Then plans can grow one move at a time, and half-finished plans can be compared before they're complete.

Exhaustive search tries every sequence of moves; with four moves a step, ten steps is about a million sequences. Greedy search keeps only the single best next move each step. Beam search sits between them. It keeps the K best partial plans after each step, where K is the beam width, extends each of them by every legal move, scores all the children, and keeps the best K again.^[14] Psyho, 8th in the 2016 contest, put it in one line: "Beam Search is basically a BFS where you take only the best WIDTH states at every turn."^[7]

The widget below runs this on a 9 × 9 grid with 14 items worth 1 to 9 points. Plans are ranked by the points collected so far, plus a small bonus for a high-value item close by. Two plans that reach the same cell holding the same items are merged, since their futures are identical.

A wider beam isn't always better because the ranking of half-finished plans is a guess. A width-4 beam keeps the four best-ranked plans after each step, and the plan the greedy search keeps can be pushed out by four others that look better for a few moves. At 6 moves that happens at step 3: the greedy plan ranks fifth and drops out, and none of the four plans kept leads to more than 24 points.

The idea goes back to Harpy, a 1976 speech recognizer that searched "only a few 'best' paths in parallel" and ran 10 to 25 times faster than searching all of them. Its cut-off was a threshold on each path's probability, so the number of paths it kept varied from step to step.^[15] In Coders Strike Back, Psyho's pods used a beam of width 1,000, 60 turns deep. The first move chose among 25 options (thrust 0, 50, 100, 150 or 200 times turn −18°, −9°, 0°, 9° or 18°) and every later move among 4 (thrust 0 or 200, turn −18° or 18°). He scored intermediate and final states the same way, removed duplicate states, and didn't simulate collisions.^[7] Beam searches still place at the top of recent contests: MSz finished 2nd in Winter Challenge 2024 with a "nested beam search",^[16] and bowwowforeach won Spring Challenge 2022 with an attacker driven by a 15-turn "chokudai search", which he describes as "an algorithm similar to beam search".^[17]

Beam search and evolution suit different shapes of problem. A beam needs moves few enough to try every one, and an evaluation that can rank unfinished plans; in return it shares work, since each partial plan is simulated once and extended, and identical states can be merged. Evolution needs only a score for complete plans and handles continuous angles and thrusts, but every candidate is simulated from the start.

06Two pods, two jobs

The first player to finish all the laps wins.^[3] With two pods per team, only the first pod over the line counts, so a second pod racing behind its teammate adds little. It does more good slowing down the opponent's leader.

The top bots of 2016 gave each pod a role every turn. The pod further along the race is the runner and races; the other is the blocker and gets in the way of the opponent's runner. Magus calls them the runner and the "hunter", and picks them for both teams at the start of every turn from each pod's score.^[6] pb4608 begins each turn by naming his runner and blocker and the opponent's;^[9] Hastings's pod plays offense "if it is the furthest along on its team", otherwise defense;^[13] Psyho splits racer and blocker for both players with a smaller beam search.^[7]

Blocking works through collisions. Two pods that touch bounce off each other elastically, with an impulse of at least 120 even when they barely graze. A pod that raises its SHIELD weighs ten times as much on that turn, so it barely moves when hit and shoves the other pod hard, but it can't thrust for the next three turns.^[6] A blocker waiting on the line into a checkpoint costs the runner time to steer around it or speed lost in the hit.

07A rolling-horizon planner in code

These complete programs race one pod alone for three laps on 20 seeded tracks, once with the rule bot from Your First Bot and once with a rolling-horizon genetic algorithm. Both bots see what the referee sends, the heading rounded to whole degrees. From Gold on the referee sends each pod's velocity, so the rule bot here aims with the real velocity instead of the estimate the widget's early-league rule set uses. The planner has a budget of 48 six-turn rollouts a turn; with a population of 8 it runs 6 generations, 43 rollouts, because each generation's best plan isn't simulated again. The physics step follows the rules from section 01, and on 120,000 random commands it gives the same positions, velocities and checkpoint counts as the simulator behind this page's widgets.

The programs first replay the worked example from section 01 and check that the pod lands on (6,137, 5,090) with velocity (456, −93). Then they assert that both bots finish every race, that the planner never runs more rollouts in a turn than its budget, and that it's faster on average. It prints a mean of 227.4 turns for the rule bot and 203.9 for the planner, which is faster on 19 of the 20 tracks. The C++ and Rust programs print identical results.

// Rolling-horizon evolution for one Mad Pod Racing pod, raced against a rule bot on seeded tracks.
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <numbers>
#include <vector>

constexpr double Pi = std::numbers::pi;
constexpr double MaxTurn = Pi / 10;       // 18 degrees per turn, except on the first turn
constexpr double Friction = 0.85;         // share of the velocity kept at the end of a turn
constexpr double CheckpointRadius = 600;
constexpr int MaxThrust = 100;            // the Gold league's limit (Legend allows 200)
constexpr int BoostThrust = 650;          // one BOOST per pod per race
constexpr int Laps = 3;
constexpr int TimeoutTurns = 100;         // turns allowed without passing a checkpoint

constexpr int Horizon = 6;                // moves in a plan
constexpr int Population = 8;
constexpr int RolloutBudget = 48;         // simulated plans per turn: a stand-in for the clock
constexpr double MutationSize = 0.35;     // 1 would be the full range of angle and thrust

struct Point { double x, y; };
using Track = std::vector<Point>;

struct Pod {
    double x, y, vx, vy;   // whole numbers between turns
    double heading;        // radians; x points right and y points down, as on screen
    bool hasHeading;       // false before the first move, which may face anywhere
    int passed;            // checkpoints passed; the next one is track[passed % size]
    bool boostLeft;
};

struct Command { double targetX, targetY; int thrust; bool boost; };
struct Move { double turnDegrees; int thrust; bool boost; };
using Plan = std::array<Move, Horizon>;

// splitmix64: a small seeded generator, so every run repeats exactly.
struct Random {
    std::uint64_t state;
    std::uint64_t next() {
        state += 0x9E3779B97F4A7C15ULL;
        std::uint64_t mixed = state;
        mixed = (mixed ^ (mixed >> 30)) * 0xBF58476D1CE4E5B9ULL;
        mixed = (mixed ^ (mixed >> 27)) * 0x94D049BB133111EBULL;
        return mixed ^ (mixed >> 31);
    }
    double uniform() { return double(next() >> 11) * 0x1.0p-53; }   // [0, 1)
    int below(int bound) { return int(uniform() * bound); }
    double gaussian() {                                             // Box-Muller
        const double radius = std::sqrt(-2.0 * std::log(1.0 - uniform()));
        return radius * std::cos(2.0 * Pi * uniform());
    }
};

// The referee rounds positions the way Java's Math.round does: halves go up, even when negative.
double roundHalfUp(double value) { return std::floor(value + 0.5); }

double wrapAngle(double angle) {   // into (-pi, pi]
    while (angle > Pi) angle -= 2 * Pi;
    while (angle <= -Pi) angle += 2 * Pi;
    return angle;
}

// True when the segment from start to end passes within radius of point.
bool passesNear(Point start, Point end, Point point, double radius) {
    const double dx = end.x - start.x, dy = end.y - start.y;
    const double lengthSquared = dx * dx + dy * dy;
    double along = 0;
    if (lengthSquared > 0)
        along = std::clamp(((point.x - start.x) * dx + (point.y - start.y) * dy) / lengthSquared, 0.0, 1.0);
    const double gapX = start.x + along * dx - point.x, gapY = start.y + along * dy - point.y;
    return gapX * gapX + gapY * gapY <= radius * radius;
}

// One turn of the race rules for a pod alone on the track.
void step(Pod& pod, const Command& command, const Track& track) {
    int thrust = command.thrust;
    if (command.boost) {   // a BOOST with none left thrusts at the league maximum
        thrust = pod.boostLeft ? BoostThrust : MaxThrust;
        pod.boostLeft = false;
    }
    const double towardX = command.targetX - pod.x, towardY = command.targetY - pod.y;
    if (towardX != 0 || towardY != 0) {   // a target on the pod itself means no turn and no thrust
        const double wanted = std::atan2(towardY, towardX);
        const double difference = wrapAngle(wanted - pod.heading);
        if (pod.hasHeading && std::abs(difference) >= MaxTurn)
            pod.heading += difference > 0 ? MaxTurn : -MaxTurn;   // turn as far as allowed
        else pod.heading = wanted;
        pod.hasHeading = true;
        pod.vx += std::cos(pod.heading) * thrust;
        pod.vy += std::sin(pod.heading) * thrust;
    }
    const Point start{pod.x, pod.y};
    pod.x = roundHalfUp(pod.x + pod.vx);
    pod.y = roundHalfUp(pod.y + pod.vy);
    pod.vx = std::trunc(pod.vx * Friction);   // friction first, then truncation toward zero
    pod.vy = std::trunc(pod.vy * Friction);
    // One turn's path can pass more than one checkpoint, so test again after each pass.
    while (passesNear(start, {pod.x, pod.y}, track[pod.passed % track.size()], CheckpointRadius))
        ++pod.passed;
}

// What the referee sends each turn: whole numbers, and the heading in whole degrees.
Pod observe(const Pod& pod) {
    Pod seen = pod;
    if (pod.hasHeading) seen.heading = std::round(pod.heading * 180 / Pi) * Pi / 180;
    return seen;
}

// The rule bot from Your First Bot: aim at the checkpoint minus 4 times the velocity, thrust less
// the further the checkpoint is off the nose, and BOOST once when lined up far from it.
Command ruleBot(const Pod& pod, const Track& track) {
    const Point checkpoint = track[pod.passed % track.size()];
    const double dx = checkpoint.x - pod.x, dy = checkpoint.y - pod.y;
    const double offDegrees = pod.hasHeading ? std::abs(wrapAngle(std::atan2(dy, dx) - pod.heading)) * 180 / Pi : 0;
    const int thrust = offDegrees > 90 ? 0 : offDegrees < 45 ? MaxThrust : int(MaxThrust * (90 - offDegrees) / 45);
    const bool boost = pod.boostLeft && offDegrees < 5 && dx * dx + dy * dy > 6000.0 * 6000.0;
    return {checkpoint.x - 4 * pod.vx, checkpoint.y - 4 * pod.vy, thrust, boost};
}

// A move becomes the line a bot prints: a target 10,000 units away at the new heading.
Command toCommand(const Pod& pod, const Move& planMove, const Track& track) {
    double heading = pod.heading;
    if (!pod.hasHeading) {   // before the first move, angles count from the next checkpoint
        const Point next = track[pod.passed % track.size()];
        heading = std::atan2(next.y - pod.y, next.x - pod.x);
    }
    const double angle = heading + planMove.turnDegrees * Pi / 180;
    return {pod.x + 10000 * std::cos(angle), pod.y + 10000 * std::sin(angle), planMove.thrust, planMove.boost};
}

// Fitness: checkpoints passed come first (no distance on the field reaches 50,000), then closeness.
double score(const Pod& end, const Track& track) {
    const Point next = track[end.passed % track.size()];
    return 50000.0 * end.passed - std::hypot(next.x - end.x, next.y - end.y);
}

Move randomMove(Random& random) {
    const double turn = (random.uniform() * 2 - 1) * 18;
    const int thrust = random.below(2) == 0 ? MaxThrust : random.below(MaxThrust + 1);   // full thrust half the time
    return {turn, thrust, random.uniform() < 0.03};
}

struct Candidate { Plan plan; double fitness; };

const Candidate& bestOf(const std::vector<Candidate>& population) {   // the first of any ties
    const Candidate* best = &population[0];
    for (const Candidate& candidate : population)
        if (candidate.fitness > best->fitness) best = &candidate;
    return *best;
}

struct Planner {
    Random random;
    Plan previous{};
    bool hasPrevious = false;
    int rolloutsThisTurn = 0;

    Candidate evaluate(const Plan& plan, const Pod& start, const Track& track) {
        ++rolloutsThisTurn;
        Pod pod = start;
        for (const Move& planMove : plan) step(pod, toCommand(pod, planMove, track), track);
        return {plan, score(pod, track)};
    }
    Plan mutate(Plan plan) {
        for (Move& planMove : plan) {
            if (random.uniform() >= 0.5) continue;   // each move changes with probability 1/2
            planMove.turnDegrees = std::clamp(planMove.turnDegrees + random.gaussian() * 18 * MutationSize, -18.0, 18.0);
            planMove.thrust = std::clamp(int(std::round(planMove.thrust + random.gaussian() * MaxThrust * MutationSize)), 0, MaxThrust);
            if (random.uniform() < 0.02 * MutationSize) planMove.boost = !planMove.boost;
        }
        return plan;
    }
    Plan freshPlan() {
        Plan plan;
        for (Move& planMove : plan) planMove = randomMove(random);
        return plan;
    }
    const Candidate& tournament(const std::vector<Candidate>& population) {   // the better of two at random
        const Candidate& first = population[random.below(Population)];
        const Candidate& second = population[random.below(Population)];
        return first.fitness > second.fitness ? first : second;
    }

    Command decide(const Pod& seen, const Track& track) {
        rolloutsThisTurn = 0;
        std::vector<Candidate> population;
        if (hasPrevious) {   // last turn's best plan, one move on, with a fresh move at the end
            Plan shifted;
            std::copy(previous.begin() + 1, previous.end(), shifted.begin());
            shifted.back() = randomMove(random);
            population.push_back(evaluate(shifted, seen, track));
            while (int(population.size()) < Population)
                population.push_back(evaluate(random.uniform() < 0.5 ? mutate(shifted) : freshPlan(), seen, track));
        } else {
            while (int(population.size()) < Population) population.push_back(evaluate(freshPlan(), seen, track));
        }
        // Each generation keeps its best plan unchanged and breeds Population - 1 children.
        while (rolloutsThisTurn + (Population - 1) <= RolloutBudget) {
            std::vector<Candidate> next{bestOf(population)};
            while (int(next.size()) < Population) {
                const Plan& mother = tournament(population).plan;
                const Plan& father = tournament(population).plan;
                Plan child;
                for (int i = 0; i < Horizon; ++i) child[i] = random.uniform() < 0.5 ? mother[i] : father[i];   // uniform crossover
                next.push_back(evaluate(mutate(child), seen, track));
            }
            population = std::move(next);
        }
        previous = bestOf(population).plan;
        hasPrevious = true;
        return toCommand(seen, previous[0], track);   // play the first move only
    }
};

// A seeded track: 3 to 5 checkpoints at least 3,000 units apart, inside the 16,000 x 9,000 field.
Track makeTrack(std::uint64_t seed) {
    Random random{seed};
    const int count = 3 + random.below(3);
    Track track;
    while (int(track.size()) < count) {
        const Point candidate{1000.0 + random.below(14001), 1000.0 + random.below(7001)};
        bool farEnough = true;
        for (const Point& other : track) {
            const double dx = candidate.x - other.x, dy = candidate.y - other.y;
            farEnough = farEnough && dx * dx + dy * dy >= 3000.0 * 3000.0;
        }
        if (farEnough) track.push_back(candidate);
    }
    return track;
}

// Three laps alone on the track; returns the finishing turn, or -1 on a timeout.
template <typename Bot>
int timeTrial(const Track& track, Bot&& bot) {
    Pod pod{track[0].x, track[0].y, 0, 0, 0, false, 1, true};   // start on checkpoint 0, facing anywhere
    int lastProgressTurn = 0;
    for (int turn = 1; turn <= 500; ++turn) {
        const int before = pod.passed;
        step(pod, bot(observe(pod)), track);
        if (pod.passed > before) lastProgressTurn = turn;
        if (pod.passed > Laps * int(track.size())) return turn;
        if (turn - lastProgressTurn >= TimeoutTurns) return -1;
    }
    return -1;
}

int main() {
    // The worked example from section 01: turn 18 degrees toward the checkpoint at full thrust.
    const Track example{{8300, 3200}, {12400, 6800}};
    Pod pod{5600, 5200, 450, -60, -12 * Pi / 180, true, 0, false};
    step(pod, {8300, 3200, 100, false}, example);
    assert(pod.x == 6137 && pod.y == 5090 && pod.vx == 456 && pod.vy == -93);

    const int tracks = 20;
    int rulesTotal = 0, plannerTotal = 0, plannerFaster = 0, mostRollouts = 0;
    for (int seed = 1; seed <= tracks; ++seed) {
        const Track track = makeTrack(seed);
        const int rulesTurns = timeTrial(track, [&](const Pod& seen) { return ruleBot(seen, track); });
        Planner planner{Random{1000 + std::uint64_t(seed)}};
        const int plannerTurns = timeTrial(track, [&](const Pod& seen) {
            const Command command = planner.decide(seen, track);
            mostRollouts = std::max(mostRollouts, planner.rolloutsThisTurn);
            return command;
        });
        assert(rulesTurns > 0 && plannerTurns > 0);   // both finish every race
        rulesTotal += rulesTurns;
        plannerTotal += plannerTurns;
        if (plannerTurns < rulesTurns) ++plannerFaster;
        std::printf("track %2d, %zu checkpoints: rule bot %3d turns, planner %3d turns\n", seed, track.size(), rulesTurns, plannerTurns);
    }
    assert(mostRollouts <= RolloutBudget);   // the planner never spends more than its budget
    std::printf("mean: rule bot %.1f turns, planner %.1f turns; planner faster on %d of %d tracks\n",
                double(rulesTotal) / tracks, double(plannerTotal) / tracks, plannerFaster, tracks);
    std::printf("most rollouts in one turn: %d of a budget of %d\n", mostRollouts, RolloutBudget);
    assert(plannerTotal < rulesTotal);
}

// Rolling-horizon evolution for one Mad Pod Racing pod, raced against a rule bot on seeded tracks.
use std::f64::consts::PI;

const MAX_TURN: f64 = PI / 10.0; // 18 degrees per turn, except on the first turn
const FRICTION: f64 = 0.85; // share of the velocity kept at the end of a turn
const CHECKPOINT_RADIUS: f64 = 600.0;
const MAX_THRUST: i32 = 100; // the Gold league's limit (Legend allows 200)
const BOOST_THRUST: i32 = 650; // one BOOST per pod per race
const LAPS: usize = 3;
const TIMEOUT_TURNS: usize = 100; // turns allowed without passing a checkpoint

const HORIZON: usize = 6; // moves in a plan
const POPULATION: usize = 8;
const ROLLOUT_BUDGET: usize = 48; // simulated plans per turn: a stand-in for the clock
const MUTATION_SIZE: f64 = 0.35; // 1 would be the full range of angle and thrust

#[derive(Clone, Copy)]
struct Point { x: f64, y: f64 }
type Track = Vec<Point>;

#[derive(Clone, Copy)]
struct Pod {
    x: f64, y: f64, vx: f64, vy: f64, // whole numbers between turns
    heading: f64,      // radians; x points right and y points down, as on screen
    has_heading: bool, // false before the first move, which may face anywhere
    passed: usize,     // checkpoints passed; the next one is track[passed % len]
    boost_left: bool,
}

struct Command { target_x: f64, target_y: f64, thrust: i32, boost: bool }
#[derive(Clone, Copy, Default)]
struct Move { turn_degrees: f64, thrust: i32, boost: bool }
type Plan = [Move; HORIZON];

// splitmix64: a small seeded generator, so every run repeats exactly.
struct Random { state: u64 }
impl Random {
    fn next(&mut self) -> u64 {
        self.state = self.state.wrapping_add(0x9E37_79B9_7F4A_7C15);
        let mut mixed = self.state;
        mixed = (mixed ^ (mixed >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
        mixed = (mixed ^ (mixed >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
        mixed ^ (mixed >> 31)
    }
    fn uniform(&mut self) -> f64 { (self.next() >> 11) as f64 * (1.0 / (1u64 << 53) as f64) } // [0, 1)
    fn below(&mut self, bound: i32) -> i32 { (self.uniform() * bound as f64) as i32 }
    fn gaussian(&mut self) -> f64 { // Box-Muller
        let radius = (-2.0 * (1.0 - self.uniform()).ln()).sqrt();
        radius * (2.0 * PI * self.uniform()).cos()
    }
}

// The referee rounds positions the way Java's Math.round does: halves go up, even when negative.
fn round_half_up(value: f64) -> f64 { (value + 0.5).floor() }

fn wrap_angle(mut angle: f64) -> f64 { // into (-pi, pi]
    while angle > PI { angle -= 2.0 * PI; }
    while angle <= -PI { angle += 2.0 * PI; }
    angle
}

// True when the segment from start to end passes within radius of point.
fn passes_near(start: Point, end: Point, point: Point, radius: f64) -> bool {
    let (dx, dy) = (end.x - start.x, end.y - start.y);
    let length_squared = dx * dx + dy * dy;
    let mut along = 0.0;
    if length_squared > 0.0 {
        along = (((point.x - start.x) * dx + (point.y - start.y) * dy) / length_squared).clamp(0.0, 1.0);
    }
    let (gap_x, gap_y) = (start.x + along * dx - point.x, start.y + along * dy - point.y);
    gap_x * gap_x + gap_y * gap_y <= radius * radius
}

// One turn of the race rules for a pod alone on the track.
fn step(pod: &mut Pod, command: &Command, track: &Track) {
    let mut thrust = command.thrust;
    if command.boost { // a BOOST with none left thrusts at the league maximum
        thrust = if pod.boost_left { BOOST_THRUST } else { MAX_THRUST };
        pod.boost_left = false;
    }
    let (toward_x, toward_y) = (command.target_x - pod.x, command.target_y - pod.y);
    if toward_x != 0.0 || toward_y != 0.0 { // a target on the pod itself means no turn and no thrust
        let wanted = toward_y.atan2(toward_x);
        let difference = wrap_angle(wanted - pod.heading);
        if pod.has_heading && difference.abs() >= MAX_TURN {
            pod.heading += if difference > 0.0 { MAX_TURN } else { -MAX_TURN }; // turn as far as allowed
        } else {
            pod.heading = wanted;
        }
        pod.has_heading = true;
        pod.vx += pod.heading.cos() * thrust as f64;
        pod.vy += pod.heading.sin() * thrust as f64;
    }
    let start = Point { x: pod.x, y: pod.y };
    pod.x = round_half_up(pod.x + pod.vx);
    pod.y = round_half_up(pod.y + pod.vy);
    pod.vx = (pod.vx * FRICTION).trunc(); // friction first, then truncation toward zero
    pod.vy = (pod.vy * FRICTION).trunc();
    // One turn's path can pass more than one checkpoint, so test again after each pass.
    while passes_near(start, Point { x: pod.x, y: pod.y }, track[pod.passed % track.len()], CHECKPOINT_RADIUS) {
        pod.passed += 1;
    }
}

// What the referee sends each turn: whole numbers, and the heading in whole degrees.
fn observe(pod: &Pod) -> Pod {
    let mut seen = *pod;
    if pod.has_heading { seen.heading = (pod.heading * 180.0 / PI).round() * PI / 180.0; }
    seen
}

// The rule bot from Your First Bot: aim at the checkpoint minus 4 times the velocity, thrust less
// the further the checkpoint is off the nose, and BOOST once when lined up far from it.
fn rule_bot(pod: &Pod, track: &Track) -> Command {
    let checkpoint = track[pod.passed % track.len()];
    let (dx, dy) = (checkpoint.x - pod.x, checkpoint.y - pod.y);
    let off_degrees = if pod.has_heading { wrap_angle(dy.atan2(dx) - pod.heading).abs() * 180.0 / PI } else { 0.0 };
    let thrust = if off_degrees > 90.0 { 0 } else if off_degrees < 45.0 { MAX_THRUST } else { (MAX_THRUST as f64 * (90.0 - off_degrees) / 45.0) as i32 };
    let boost = pod.boost_left && off_degrees < 5.0 && dx * dx + dy * dy > 6000.0 * 6000.0;
    Command { target_x: checkpoint.x - 4.0 * pod.vx, target_y: checkpoint.y - 4.0 * pod.vy, thrust, boost }
}

// A move becomes the line a bot prints: a target 10,000 units away at the new heading.
fn to_command(pod: &Pod, plan_move: &Move, track: &Track) -> Command {
    let mut heading = pod.heading;
    if !pod.has_heading { // before the first move, angles count from the next checkpoint
        let next = track[pod.passed % track.len()];
        heading = (next.y - pod.y).atan2(next.x - pod.x);
    }
    let angle = heading + plan_move.turn_degrees * PI / 180.0;
    Command { target_x: pod.x + 10000.0 * angle.cos(), target_y: pod.y + 10000.0 * angle.sin(), thrust: plan_move.thrust, boost: plan_move.boost }
}

// Fitness: checkpoints passed come first (no distance on the field reaches 50,000), then closeness.
fn score(end: &Pod, track: &Track) -> f64 {
    let next = track[end.passed % track.len()];
    50000.0 * end.passed as f64 - (next.x - end.x).hypot(next.y - end.y)
}

fn random_move(random: &mut Random) -> Move {
    let turn = (random.uniform() * 2.0 - 1.0) * 18.0;
    let thrust = if random.below(2) == 0 { MAX_THRUST } else { random.below(MAX_THRUST + 1) }; // full thrust half the time
    Move { turn_degrees: turn, thrust, boost: random.uniform() < 0.03 }
}

#[derive(Clone, Copy)]
struct Candidate { plan: Plan, fitness: f64 }

fn best_of(population: &[Candidate]) -> Candidate { // the first of any ties
    let mut best = population[0];
    for candidate in population {
        if candidate.fitness > best.fitness { best = *candidate; }
    }
    best
}

struct Planner { random: Random, previous: Option<Plan>, rollouts_this_turn: usize }
impl Planner {
    fn evaluate(&mut self, plan: Plan, start: &Pod, track: &Track) -> Candidate {
        self.rollouts_this_turn += 1;
        let mut pod = *start;
        for plan_move in &plan { let command = to_command(&pod, plan_move, track); step(&mut pod, &command, track); }
        Candidate { plan, fitness: score(&pod, track) }
    }
    fn mutate(&mut self, mut plan: Plan) -> Plan {
        for plan_move in plan.iter_mut() {
            if self.random.uniform() >= 0.5 { continue; } // each move changes with probability 1/2
            plan_move.turn_degrees = (plan_move.turn_degrees + self.random.gaussian() * 18.0 * MUTATION_SIZE).clamp(-18.0, 18.0);
            plan_move.thrust = ((plan_move.thrust as f64 + self.random.gaussian() * MAX_THRUST as f64 * MUTATION_SIZE).round() as i32).clamp(0, MAX_THRUST);
            if self.random.uniform() < 0.02 * MUTATION_SIZE { plan_move.boost = !plan_move.boost; }
        }
        plan
    }
    fn fresh_plan(&mut self) -> Plan {
        let mut plan = [Move::default(); HORIZON];
        for plan_move in plan.iter_mut() { *plan_move = random_move(&mut self.random); }
        plan
    }
    fn tournament(&mut self, population: &[Candidate]) -> Candidate { // the better of two at random
        let first = population[self.random.below(POPULATION as i32) as usize];
        let second = population[self.random.below(POPULATION as i32) as usize];
        if first.fitness > second.fitness { first } else { second }
    }

    fn decide(&mut self, seen: &Pod, track: &Track) -> Command {
        self.rollouts_this_turn = 0;
        let mut population: Vec<Candidate> = Vec::new();
        if let Some(previous) = self.previous { // last turn's best plan, one move on, with a fresh move at the end
            let mut shifted = [Move::default(); HORIZON];
            shifted[..HORIZON - 1].copy_from_slice(&previous[1..]);
            shifted[HORIZON - 1] = random_move(&mut self.random);
            population.push(self.evaluate(shifted, seen, track));
            while population.len() < POPULATION {
                let plan = if self.random.uniform() < 0.5 { self.mutate(shifted) } else { self.fresh_plan() };
                population.push(self.evaluate(plan, seen, track));
            }
        } else {
            while population.len() < POPULATION { let plan = self.fresh_plan(); population.push(self.evaluate(plan, seen, track)); }
        }
        // Each generation keeps its best plan unchanged and breeds POPULATION - 1 children.
        while self.rollouts_this_turn + (POPULATION - 1) <= ROLLOUT_BUDGET {
            let mut next = vec![best_of(&population)];
            while next.len() < POPULATION {
                let mother = self.tournament(&population).plan;
                let father = self.tournament(&population).plan;
                let mut child = [Move::default(); HORIZON];
                for i in 0..HORIZON { child[i] = if self.random.uniform() < 0.5 { mother[i] } else { father[i] }; } // uniform crossover
                let mutated = self.mutate(child);
                next.push(self.evaluate(mutated, seen, track));
            }
            population = next;
        }
        let best = best_of(&population).plan;
        self.previous = Some(best);
        to_command(seen, &best[0], track) // play the first move only
    }
}

// A seeded track: 3 to 5 checkpoints at least 3,000 units apart, inside the 16,000 x 9,000 field.
fn make_track(seed: u64) -> Track {
    let mut random = Random { state: seed };
    let count = 3 + random.below(3) as usize;
    let mut track: Track = Vec::new();
    while track.len() < count {
        let candidate = Point { x: 1000.0 + random.below(14001) as f64, y: 1000.0 + random.below(7001) as f64 };
        let far_enough = track.iter().all(|other| {
            let (dx, dy) = (candidate.x - other.x, candidate.y - other.y);
            dx * dx + dy * dy >= 3000.0 * 3000.0
        });
        if far_enough { track.push(candidate); }
    }
    track
}

// Three laps alone on the track; returns the finishing turn, or None on a timeout.
fn time_trial(track: &Track, mut bot: impl FnMut(&Pod) -> Command) -> Option<usize> {
    let mut pod = Pod { x: track[0].x, y: track[0].y, vx: 0.0, vy: 0.0, heading: 0.0, has_heading: false, passed: 1, boost_left: true }; // start on checkpoint 0, facing anywhere
    let mut last_progress_turn = 0;
    for turn in 1..=500 {
        let before = pod.passed;
        let command = bot(&observe(&pod));
        step(&mut pod, &command, track);
        if pod.passed > before { last_progress_turn = turn; }
        if pod.passed > LAPS * track.len() { return Some(turn); }
        if turn - last_progress_turn >= TIMEOUT_TURNS { return None; }
    }
    None
}

fn main() {
    // The worked example from section 01: turn 18 degrees toward the checkpoint at full thrust.
    let example: Track = vec![Point { x: 8300.0, y: 3200.0 }, Point { x: 12400.0, y: 6800.0 }];
    let mut pod = Pod { x: 5600.0, y: 5200.0, vx: 450.0, vy: -60.0, heading: -12.0 * PI / 180.0, has_heading: true, passed: 0, boost_left: false };
    step(&mut pod, &Command { target_x: 8300.0, target_y: 3200.0, thrust: 100, boost: false }, &example);
    assert!(pod.x == 6137.0 && pod.y == 5090.0 && pod.vx == 456.0 && pod.vy == -93.0);

    let tracks = 20;
    let (mut rules_total, mut planner_total, mut planner_faster, mut most_rollouts) = (0, 0, 0, 0);
    for seed in 1..=tracks {
        let track = make_track(seed);
        let rules_turns = time_trial(&track, |seen| rule_bot(seen, &track));
        let mut planner = Planner { random: Random { state: 1000 + seed }, previous: None, rollouts_this_turn: 0 };
        let planner_turns = time_trial(&track, |seen| {
            let command = planner.decide(seen, &track);
            most_rollouts = most_rollouts.max(planner.rollouts_this_turn);
            command
        });
        let (rules_turns, planner_turns) = (rules_turns.expect("rule bot finishes"), planner_turns.expect("planner finishes"));
        rules_total += rules_turns;
        planner_total += planner_turns;
        if planner_turns < rules_turns { planner_faster += 1; }
        println!("track {:2}, {} checkpoints: rule bot {:3} turns, planner {:3} turns", seed, track.len(), rules_turns, planner_turns);
    }
    assert!(most_rollouts <= ROLLOUT_BUDGET); // the planner never spends more than its budget
    println!("mean: rule bot {:.1} turns, planner {:.1} turns; planner faster on {} of {} tracks",
             rules_total as f64 / tracks as f64, planner_total as f64 / tracks as f64, planner_faster, tracks);
    println!("most rollouts in one turn: {} of a budget of {}", most_rollouts, ROLLOUT_BUDGET);
    assert!(planner_total < rules_total);
}

08Where planners go wrong

A fitness that rewards the wrong thing. Score only the distance to the next checkpoint and the best plan can be one that slows down short of it, since passing it makes the distance jump to the next, far checkpoint. Weight checkpoints passed so heavily that no distance outweighs one.

Planning from your own idea of the state. The referee sends whole numbers and a heading in whole degrees. A planner that keeps its own floating-point copy of the pod drifts away from the real one; start every turn from the input.

Mutations of the wrong size. Too small and the search can't leave a poor plan; too large and it's random search. The first widget shows both. Magus's schedule, large at the start of the turn and small at the end, is one answer.

Reusing a plan without scoring it again. Last turn's best plan was scored from last turn's position. Shift it, then simulate it from the new position like any other candidate.

One-off actions in every move. BOOST and SHIELD each change several turns, so a genome that may fire them on any move wastes rollouts on plans that spend them badly. Jeff06's pods shielded only when that move's shield gene passed 0.95, about one move in twenty of a random plan, and pb4608's plan held a single shield turn.

09What's next

Every search on this page gets better with more simulations a turn, and a turn on CodinGame's machines may be slower than on yours. Fast Bots measures simulations per turn, budgets the turn with a safety margin, packs boards into bits, keeps allocation out of the hot loop, and builds the single file CodinGame accepts.

10Sources

Placements are from the Coders Strike Back contest leaderboard (2016) unless a source says otherwise. Widget readouts are measured in the page on the stated seeds.

1. 5DN1L, 2021. Mad Pod Racing puzzle discussion, post #538, CodinGame forum. "Coders Strike Back is the previous name of Mad Pod Racing".
2. CodinGame, 2016. Coders Strike Back contest leaderboard. 2,530 ranked; Jeff06 1st, Owl 2nd, pb4 (pb4608) 3rd, Hastings 4th, Magus 7th, Psyho 8th.
3. CodinGame. Mad Pod Racing, starting-league statement (retrieved 2026-10-30). Thrust 0 to 100, checkpoint radius 600, 75 ms per turn, elimination after 100 turns without a checkpoint, and the first player to complete all the laps wins.
4. RoboStac, 2024. Mad Pod Racing puzzle discussion, post #963, CodinGame forum. A BOOST with none left is converted to the maximum thrust, "100 / 200 depending on league".
5. Author's lab records, 2026 (private repository). The Mad Pod Racing runner-and-blocker bot and its live results: games/madpodracing/bots/blocker/, games/madpodracing/README.md, and the Gold and Legend rankings in experiments/live-submissions/mad-pod-racing/rankings.jsonl. The README also records the Gold rules confirmed on live games: thrust 0 to 100 and one BOOST of 650 per pod.
6. Magus, 2016. Coders Strikes Back (English translation by Agade). The physics of a turn, collisions and SHIELD, the 150 ms turn, his genetic algorithm (6 turns, 5 solutions, shrinking mutations, last turn's winner reused), runner and hunter roles, and his opponent prediction.
7. Psyho, 2016. Coders Strike Back: Your ideas!, posts #24 and #28, CodinGame forum. Beam search of width 1,000 and depth 60, its move sets and evaluation, and the racer and blocker split.
8. Jeff06, 2016. A Genetic Algorithm to Pilot Pod Racers, CodinGame blog (Internet Archive copy; the blog returned 503 on 2026-10-30). The 36-gene shared genome, extreme-biased genes, 30 ms evolving the opponent, and about 15,000 six-turn simulations a turn.
9. pb4608, 2016. Evolutionary Trajectory Optimization with a Genetic Algorithm, CodinGame blog (Internet Archive copy). The six-turn genome with a shield turn, the 10% and 90% evaluations, clipped random draws, and the 12, 12 and 116 ms split between opponent and own pods.
10. Owl, 2016. Coders Strike Back: Your ideas!, post #55, CodinGame forum. Seven moves per pod, one pod at a time, the others repeating their last move.
11. Diego Perez, Spyridon Samothrakis, Simon M. Lucas, Philipp Rohlfshagen, 2013. Rolling Horizon Evolution versus Tree Search for Navigation in Single-Player Real-Time Games, GECCO 2013 (DOI 10.1145/2463372.2463413). Evolving a plan in a simulator and playing its first action; their population restarts at random each decision.
12. Jeff06, 2016. Coders Strike Back: Your ideas!, post #54, CodinGame forum. Last turn's best genome shifted three genes to the left, with random genes at the end.
13. Hastings, 2016. Coders Strike Back: Your ideas!, posts #22 and #26, CodinGame forum. A minimax over a heuristic bot that aims at the checkpoint minus 4 times its velocity, and offense or defense by race position.
14. David L. Poole, Alan K. Mackworth, 2023. Artificial Intelligence: Foundations of Computational Agents, 3rd edition, Section 4.7. Beam search keeps up to k candidates and the k best successors at each stage.
15. Bruce T. Lowerre, 1976. The HARPY Speech Recognition System: Thesis Summary, Carnegie-Mellon University. Searching only a few best paths in parallel, chosen by a threshold, for a speed-up of 10 to 25 times.
16. MSz, 2025. Winter Challenge 2024 post-mortem, GitHub, linked from Winter Challenge 2024 feedback and strategies, post #96, CodinGame forum. Second place with a nested beam search over full turns.
17. bowwowforeach, 2022. Spring Challenge 2022 feedbacks and strategies, posts #60 and #70, CodinGame forum. First place with rule-based defenders and an attacker driven by a 15-turn chokudai search, a relative of beam search.