The heuristic bot is somewhat simple. It first checks if it is the furthest along on its team. If is is, it plays offense, otherwise it plays defense.
On offense, the heuristic bot targets the point nextCheckPointPosition – 4 * velocity, and only thrusts if it is approximately facing the point it is targeting. The defense bot uses a similar formula to either block the opposing bot, or beat it to the checkpoint after the one it is currently passing. See if you can work out why this formula approximates correct behavior!
The minmax bot selects the closest enemy pod as the opponent it will minmax against. For each turn in the future, it considers four moves for itself, and four moves for the selected opponent, giving 16 combinations of moves per turn. The other two pods are controlled by the heuristic bot. These are each simulated recursively for three steps, giving 6500 positions. This is where the two level hierarchy comes in: to evaluate further into the future, the bots are assumed to all be controlled by the heuristic bot for an additional 4 moves. Each position’s score three moves in the future is given by a simple function of the predicted position after an additional 4 heuristic moves, giving a total depth of 7 moves.
Once each of the 6500 positions are evaluated, the bot simply selects the best using the standard minmax formula: maximizing the score, assuming that the opponent will select moves that minimize the score.
Obviously I have made some simplifications and omissions here, largely in the details of the “simple” score function and the details of simulating motion and collision. However, I think I’ve presented the important parts of the algorithm clearly.”
Frunit (Norway, Bash, Rank on Contest: 482)
“I didn’t have much time, but I made it to the Top 500. The first pod follows the checkpoints and the second pod attacks the best enemy pod. The calculations were quite easy. I measured the distance and angle to the next checkpoint (i.e. polar coordinates). The thrust was very basic: When the checkpoint is further than x units away, do full thrust, else go with a thrust of 100. If the checkpoint is not within 120 degrees of the flight direction, don’t accelerate (only turn). The aiming was a bit adjusted later because I saw that the pod would circle around checkpoints if coming too fast from a difficult direction.
No magic for the second pod: Just use full thrust directly to the best enemy pod. Not very effective, but hey, it was enough for mediocre AIs.”
Nergal (France, Swift, Rank on Contest: 43)
“I used a pretty simple approach:
For each turn and each of my pod:
– Check if will collide with an opponent pod next turn considering current speed of all pods, and if yes, and if speeds are different enough between the pods activate shield
– If no collision planned:
Generate target coordinates for a turn of -18°/-9°/0°/+9°/+18°
Have possible thrust list of 0,100,200 (I tried 0,50,100,150,200 also)
Now compute my next turn positions considering each combination between the above parameters, and for each of these positions, redo the same thing (total depth of 3 to 5 depending of the parameter list I choosed. at the end, compute a score for each position, considering if I have crossed a checkpoint, my distance to the next checkpoint (second next if I crossed one), my speed, the angle between my pod heading and the next checkpoint, and the angle between my speed vector and the ideal vector to next check point.
Then pick the best thrust/target combination for next turn.
Pretty simple but works fine when the evaluation function is good :)”
Psyho (Poland, C++, Rank on Contest: 8)
“The core of my strategy is pretty naive beam search for pathfinding (0/50/100/150/200 + -18/-9/0/+9/+18 first move and 0/200 + -18/+18 for subsequent). Without any big optimizations, I was able to get depth of 60 and width of 1000 with duplicates removal (interchanging left/right rotations). Evaluation is done based on (laps, checkpoint, distance_to_next_checkpoint). With 60 steps simulation, I can safely ignore rotations, etc. By default pathfinding ignores position of all of the ships. I’ve added “no go” zones to my beam search and a different evaluation function for tracking enemy player.
Overall, my AI did horrible job at blocking / pushing away enemy blockers (adding to my eval collision angles would help tremendously). I also didn’t simulate the collisions, so quite often my blocker helped enemy pod by pushing them into correct spot. On the flipside, when enemy didn’t have any good blockers (which wasn’t the case in top10), I was able to quickly race through the checkpoints.”
“Pretty vanilla for me; go to the next checkpoint, slow down if you have to turn or floor it if the next checkpoint was at a similar angle. Tried having a dedicated blocker but found that having 2 racers was generally a better choice. Built an AI module that would calculate 5 turns in advance but couldn’t get it tuned well enough to outperform what I already had. Ended up reverting it back a few hours before the contest ended…. Finished just inside the top 25%, so a pretty poor outing overall. This was my first contest and I learned a lot, so it wasn’t a waste of time by any means.”