Hi, Now that the contest is over, what were your ideas for Coders Strike Back ?
For me :
Try to make a parabola out of the three points (Your position, Next_checkpoint, Next_Next_checkpoint) ? ( I thought axis y of the parabola could be the bisesctor of the angle u,v where u = Your Position - Next Checkpoint and v= NextNextCheckpoint - NextCheckpoint. I had issues computing the distance of a point to the parabola, it implies solving a polynomial equation of degree 3, which was too heavy, perhaps one could use an approximation ?) ?
I only explored on 4 moves and decided which sequence of moves was the best (with an evaluation fonction - I think thereās an interesting debate about that function, it could be the key of the pb)
Then about collisions, nothing special, i estimated the acceleration of the opponent, assuming it was the same than the turn before, (an = an-1) and decided whether or not there would be a collision and whether or note it would be violent.
With this, I got to top 200 only, I tried to add a new feature in the end and submitted it, but I donāt even know if itās bugged or whatever so quite a risk, anyway I was far from the first places so ā¦
What about you ??
[edit moderation: most of the CodinGamers do not understand French, please answer in English]
My pod starts rotating just before it reaches a checkpointā¦ Thatās the only thing I managed to do. I also tried Bezier curves but it didnāt work as I expected.
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.
I just sped towards the next pod with a simple math formula determining which point on the podās disc is the good target to go to and how much thrust to use to get there. No collisions handled (my pods even collide between themselves and that cost me some races), no rotations to get properly set-up for the next pod, no look-ahead, no nada.
But it reached the goal of being in top 10 in Haskell category, exactly what I have set up to obtain on this contest. I will advance the bot later when I get more time and it becomes a multiplayer challenge in the AI arena.
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.
What I did was to make a prediction of in how many game turns I would reach my target with a given thrust. Ran this 200 times for each thrust value and used the minimum. This worked nicely, my pods never overshoot their target if there is no collision.
However, I had no collision avoidance, which has cost me many races.
Hello 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 paremeters, 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
I tried to implement an attack bot but it lacked efficiency so I have not kept it, I was lacking time to do it properly.
@Nergal : thatās exactly what i did in the end ! except my angles were only -18,0,18 (and thurst 0 or 200). About collisions, you know the speed of your opponent but not his acceleration, did you estimate it or simply assumed it was 0 (if you only consider his speed it comes to this), perhaps one could use a heuristic to predict opponentās next moveā¦
As I scored poorly compared to you, Iād be quite interested to know a little more about your evaluation function, if it doesnāt bother you !
Mine was the following :
If I cross a checkpoint, i pick the solutions that crosses it in the minimum amount of steps (perhaps it was not a good idea)
If i donāt or if solutions crosses the CP in the same amount of turn (very frequent) then I calculate the distance to the next checkpoint
If itās equal (it happens for instance when you brake) i pick the solution that has the best angle.
I didnāt consider the angle between my speed and the next CP which may have been a strong improvement.
But, how did you combine those parameters in the score ? (my score was only lexicographical actually)
Yes, I did not consider the time it took to reach the target if it was reached, if a checkpoint was crossed during the evaluation, this gain is fixed (a constant) and I just focus on reducing the time to go to the following CP instead, so I considered the distance to the following CP, and the angles that need corrections (speed vector angle, and pod heading), both having negative effect on my score considering a direct pattern to the next CP.
So a solution could prove to place my pod at a greater distance, but with a better angle to keep an high speed for reaching next checkpoint. I also have several factors applied on range of detection to limit impact of collisions or rounding errors (I spent some time trying to figure out some āorbitalā errors where a pod was circling around a CP, just fixed by using a round()
This way my pods will start slowing down and turning before reaching the checkpoint.
Of course, when approaching the last CP of a game I just focus on reaching it as fast a possible
Using monte carlo technique iāve learnt from Code VS zombies, Iāve used a similar approach to simulate the game. I wrote a fairly accurate simulator that was able to predict the positions of the pods when being fed with directionX directionY and Speed/Shield.
Using that simulator each turn, the racing drone does the following:
copy the game state
pick a pseudo-random point in the map and a pseudo-random speed
thrust toward it until that checkpoint is reached - or until too many turns have been processed (since that point is pseudo-random iām very likely to miss it)
trust toward the next checkpoint at moderate speed until it is reached.
repeat that for half of the time weāre given (save the other half for my other drone)
The best results are applied. This gives my racing drone a very good trajectory because it tries to reach the checkpoint in a way reaching the next one would also be fast.
The drone is only aware of others for the next turn and assume they go at full speed. the racing drone will therefore detect collisions and see if enabling the shield would be a better choice here, assuming the other does it.
The battle drone looks for which of the opponent drones is leading and slowly move toward one of their future checkpoint (I didnāt have much time left to improve this).
Once the target is near, a similar simulation is run to find a collision that would cause the opponent to rebound with the most backward possible angle. This again wasnāt perfect (I felt deep asleep trying to go for a nap 5 hours before the end of the challenge and only woke up 20 minutes after the finish)
Basically, it does the same thing: test for directions near the opponent and see how effective collision with it would be. It simulates collisions for each turn, assuming the other is not shielding.
Again, itās not perfect and its biggest flaws would be the fact it misses many situations where it could really block the opponent. But when given the chance, itās quite deadly and potentially turn the tables with a single opportunity. https://www.codingame.com/replay/84853150 (yellow)
I was able to finish at the 25th position 1st in Javascript, and for those who are interested I have written a Google Docs explaining a little bit about my strategy.
I really wish I had more time to adjust all the parameters and plug in some more AI. But well, I will not complain about my result.
this was my first contest and I finished as 287th.
Iām 27 and a professional Java backend developer.
I spent a lot of time on the game the first weekend and got really hooked. I have not much of a maths or physics background, so at the beginning I had great trouble predicting future positions of the pods but I thought that this would be key in order to make nice fast circles.
First, the only thing that came to my mind was the Pythagorean theorem and that led to quite an heuristic approach. My method was called something like āgetThrustByDistanceAngleAndSpeedā. The target point was always fixed on the next checkpoint and the angle wasnāt the way more interesting velocity angleā¦ I didnāt optimize the different values of thrust I had (around 30, because 4 different thresholds for distance, angle and speed, but if the angle is totally wrong nothing else could counter for that) because I felt it was too cheap for a real solution.
Reading the chat got me thinking about vectors and later in vectors! It then took about 4-5 days in which I refreshed my pretty rusty knowledge of those. And boy, if school math would have been this graphic I might have actually understood some things way better. My motivation wasnāt as high, because the learning took some time. But I knew, I could do it until the end. Although I still donāt understand much about sin, cos or tan, I got the prediction of the next position almost perfectly (sometimes off by 1 unit, but totally fine!) Ironically this method wasnāt applied in my final solution. The thing that really made a difference for me was knowing whether my pod would cross a checkpoint given its current velocity and no further thrust.
I ended with no collision detection, no simulating of x future rounds with random values and measuring the different outcomes, never used the shield and both my racers had the same strategy:
Check if the current velocity is good enough to reach the next checkpoint and the ādistance to speedā ratio was small. If so, use 0 thrust and start rotating towards the next checkpoint.
Unless the velocity angle is already perfect (guess thatās almost never the case), rotate the target point (checkpoint coords) by 18% undercutting the target because velocity drag will do itās work (I saw that on others racers on the first day but I only got it in the last hours of the contest).
Given my ādistance to speedā ratio I used different thrust values. Something that happend from time to time was infinite circling around the same checkpoint because the thrust was too high to reach it. I played around with some values and hope that didnāt happen anymore as I submitted my solution.
In hindsight Iām very proud of my ranking, as I was very overwhelmed by the physics at first (though now I see how simple it is in 2 dimensions with not that many variables). There are some easy fixes I could have done, like if the next target would be in a straight line, my racers wouldnāt need to slow down ā¦ but the time was limited and as an amateur numberwizard, I believe my moves fullfilled their purpose good enough.
First of all : I really loved this contest ! Thanks Codingame
My report/reflexion during the contest
First push - basic strategy : finish the race
My two pods are simply going to the next checkpoint with a constant thrust.
I tried different values for the thrust but finally I keep Thrust = 100.
Second push - 2 pods, 2 strategies
Pod#1 : First push strategy (go to next CP with Thrust 100)
Pod#2 : This pod aim is to block AN opponent pod (the first given in entry). I tried different thrust to do that and finally choose Thrust 200.
Third push - 2 pods, 2 strategies (blocker pod improvement)
Pod#1 : First push strategy (go to next CP with Thrust 100)
Pod#2 : Second push strategy with an improvement. I change the target of this pod to the best opponent pod. Still with Thrust 200.
Fourth push - 2 pods, 2 strategies (runner pod improvement)
Pod#1 : I do not wait my pod reach the center of the CP to change the CP targeted. So when my pod is in the validation zone of the CP, it targets the next CP to reach.
Pod#2 : Third push strategy (go to best opponent pod with Thrust 200)
Fifth push - 2 pods, 2 strategies (runner pod improvement #2)
Pod#1 : Using the speed of my pod, I compute its next position for the next turn and continue to use the fourth push strategy.
Pod#2 : Third push strategy (go to best opponent pod with Thrust 200)
RESULTS - 30.26 points and 993/2530
I hesitate a lot between my fourth and fifth pushes because results were identical. Finally, I decide to submit the fourth one (because it seems better ranked for me)
During the last hour of the contest I was wondering if it would be interesting to :
Change the role of my pods during the race analyzing their rank in the race so my runner could became the blocker and vice versa
Change my blocker pod behavior according to its rank in the race : if its #1 or #2, than no need to be a blocker.
What do you think about it ?
Iām opened to any comment or advice !
All those sharings are great, itās a pleasure to read you.
@ kazrakel, mostly, your racer pod doesnāt perform well enough, you need to think his movements with thrust and angle but not just target the checkpoints, it wonāt perform well !
I have another question btw, a parenthesis : Iām note sur I understood, there is an āetended contestā that begins in 2 days ? Iām looking forward to fix my bot to see where it can get
If no one else does it before me, next week iāll write a big article / pdf / forum post / whatever to explain all the formulas and how some of the top 10 codes works (at least how pb4608, Jeff06, Neumann and my code works, i canāt say for others).
The only problem is that iām french and my english is not always good. Maybe iāll write it in french and iāll ask someone to translate it.
Thanks for your advice.
I agree with you but I donāt take the time to do that (child sick , i do the 3 last days at the hospital )
Moreover, I donāt get how to do that. I need to study my Maths and my Physics
1st in Javascript, and for those who are interested I have written a 
, i do the 3 last days at the hospital