AI contest notes - Coders Strike Back

Short notes on the AI contest held by Codingame.com. The goal of the game was to race one of player's two pods to finish through set of waypoints. The simulation was discreet and programs were to provide outputs consisting of target destination and thrust level for each owned pod for each turn.

Saturday 27/02

Started by writing trivial solution -- both pods are moving towards the center of next waypoint. I tried to tinker with thruster power a bit. Found out, that having one pod going at 95 power and the other at 110 improves the bot performance significantly. It probably screws with trajectories of 2x100 thruster pods, which most people use at the moment. I've done some reverse engineering math to find the friction coefficient. I gathered the data by having pods with truster speeds 10, 50, 100 and 200 go horizontally, vertically and diagonally for 10 turns. The formula was pretty obvious after plotting the data into line charts. I am thinking about evaluating multiple options to make parabolic trajectory through the pod's current position and 2 next waypoints. Metrics could be number of turns to reach waypoint#2 and exit speed on waypoint#2. The computational complexity seems a bit high, so I need to find some heuristics to comb the possibilities down. Ending the day at 270/1000 position.

Sunday 28/02

Pods now calculate, if they reach the next checkpoint with current speed in reasonable time and if so, they start to rotate towards next checkpoint. Having trouble with pods orbiting the checkpoints. Initial solution is to subtract triple velocity from destination coordinates to compensate for sliding. This takes me from 430th to 250th place. Additional tweaks are done to pod AI when near checkpoint and not quite on the correct trajectory. Thrust levels are set (0~50) depending on angle difference and distance to checkpoint. This moves me from 250th to 200th place. In the evening I try to fiddle a bit more with near-checkpoint behavior and find out some trigonometry errors (swapping sin and cos) and array manipulation errors, when I forgot to clone the pod coordinates array in simulation section. I also noticed that having one pod delay its start helps a lot. The pods will not bump into each other and the delayed pod often times ends up being in the lead after first checkpoint, due to using other pods to slow down and rotate. Ending the day at 35th place.

Sunday 29/02

The biggest feature added today was turning pod's shields on when approaching checkpoint. Pods rotate towards next checkpoint while on cooldown after shield usage. I also fixed pod's rotation when overshooting checkpoint to resolve pods orbiting issue. Originally, the pods were turning towards the center of checkpoint, which would lead to never actually hitting the checkpoint if their speed was high enough. The fix was to alter target coordinates in such a way, that rotation outwards from speed vector would use the maximum rotation allowed per turn, instead of using only such rotation to face towards the center of checkpoint. I started the day around 60th place and ended up at 35th.

Monday 01/03

Yet another fix to pods orbiting checkpoints. This time I apply zero thrust in situations, when ratio of distance to checkpoint and current speed is too small. I implemented a simple simulation to see, if using max rotation and full thrust would put the pod into checkpoint area. Previously, I only simulated moving in straight direction. Ending at 75th place.

Wednesday 03/03

I notice, that using shield everytime a pod reaches checkpoint is not needed and on some maps, where angle change between checkpoints in not that big, is heavily disadvantageous. I make a predictor to detect potential collisions and the pods turn their shield on only when collision is expected. Initially, I wanted to make the predictor using some math, but I ended up with simple iterative method, because my analytic geometry and calculus suck. I draw a straight line between current and expected position of each pod, split it into set of 10 points and for each combination of pods, i check distance between their n-th point on their respective line. If the distance is shorter then 2*pod_radius, collision is assumed. Yet another orbiting fix and I end the day at 70th place.

Thursday 04/03

I write some logic to help my pods avoid each other. Pod in the lead stays on the same course and the other pod tries all combination of rotations with the same thrust level to see, if any of them would ended up dodging the collision. The algorithm is successful in ~50% cases. I could improve on it by having variable thrust level, or modifying the leader's movement, but I believe, this issue would be solved later by designating one of the pods as fighter. 46th place.

Friday 05/03

I hate my program structure. Implementing fighter AI is really tough and I overload several of the core methods just to make them work a bit more generally. The idea is to select the best opponent's pod and block them on the next checkpoint. The main problem is to get pod into position, since I don't have support for "get there, rotate towards pod and wait" behavior. I still don't have that working at the end of the day, but the idiotic fighter helps me from 100th to 40th anyway. I assume it is thanks to the random lucky bump into opponent and the fact, that my 2 pods are not competing against each other.

Saturday 06/03

Fighter logic seems good in theory, but the AI has terrible performance in real situations. The idea is to find a checkpoint, which should be reached faster by my fighter than the enemy racer. Fighter will then rotate towards the previous checkpoint, disable thrust and wait for enemy to approach. When the enemy is close enough to make a collision in 3 turns or less, Fighter starts to accelerate towards enemy's predicted position in next turn. Usually the fighter decides to chase enemy before getting into defensive position, which is probably due to bug in logic behind its camping behavior -- I rely heavily on differences in angle and velocity to determinate whether the enemy pod is heading towards me (or the pod that is guarded by defender). It is also common to miss the target. I should have probably compensate for drift and adjust the target position depending on defenders velocity.

Sunday 07/03

I just clean up the code and make some comments in case I want to improve the code later. I resubmit the code with added comments and I fall from 30th to 80th place due to that. I suspect, that my AI is volatile in some cases and plenty of matches are needed to stabilize the rank. Matches are really slow to complete. Just about 100 matches were played 2 hours after submission. I regret resubmitting and I hope to place in top 100 to be granted additional matches. Many people entered fresh code just before the end of contest and it takes another 2 hours for all competitors to gain 100% validation matches. My AI falls to 95th position but stays in top 100 in the end. After another round of matches, the contest is done and my final rank is 68.