Coders Strike Back: Your ideas!


#42

Of course! :grinning:


#43

Hey.

My bot was kind of tree search with depth of 4 similar to the others already explained. Before ~6h of contest end it was on 16th place and the only thing it could do is driving – no shields no support pod whatsoever.

I had complete physics engine by Friday but didn’t really use it until the last minutes of the contest. I implemented defensive shielding based on it in about ~3m before contest end. That gave me ~1.0 TrueSkill points at the end.

So, the most important thing was to drive extremely good.

I want to share some simple ideas that increase the level of driving:

  1. In your local simulations (or estimations) check if your pod is going to cross a checkpoint midturn (and finish a turn outside of the checkpoint). This could help you to implement checkpoint “touching” behavior. You can find this formulas helpful.
  2. If you’re going to the last checkpoint – speed should be the main component in your evaluation. And you should totally ignore turning and slowing for the next checkpoint – there will be no next checkpoint.

Most of the bots in the top 100 tried to implement shielding, defender and so on, actually giving up on the most important aspect of racing – race.

This is how my pod drives with defensive shields: https://www.codingame.com/replay/85306956.

P.S. @MaximeC @aude I believe that things like SHIELD_FORCE = 120.0 (the hidden minimum impulse applied to the half of velocity after impact) shouldn’t exist. All mechanics should be explained (or at least hinted) in the ‘Expert Rules’.


#44

1st here

I’ve written a Google doc explaining my winning AI and how I developed it over the week:

Coders Strike Back Jeff06’s AI

And there is still a lot of things I would like to try with it once the contest is open in the AI Bots section!


#45

Hi Jeff! Congratulation and thank for explanations.

You wrote: “but we are limited to a single file…”. I programming with Go and solve this problem. Idea is “cat” all single files and maintane “package …” and "import " sections. Thanks Go there is tool like gocat that do this, but it can be done in many languages with “cat * | grep … -v | grep …” and so on. And than I just write build bash script that run every second and build final file. After this there is Codinggame sync plugin from chrome that just can use this file.


#46

Jeff, could you please describe a bit more how a “direct bot” works? Did you just use full thrust everytime or something like full thrust if angle between speed vector and target not more than 90 degrees and 0 thrust if it’s more or something more complex?


#47

Oryol, it’s more complex than just full thrust. Basically I first cancel out the normal component of my drone’s speed with regards to its target, then apply full thrust once it’s facing the target. This prevents the orbiting problem you get if you just do full thrust towards the target.


#48

Thanks for sharing your experience :slightly_smiling:
And of course, congratulation !


#49

Yes i forgot to mention it, it was almost the first thing I actually implemented, but I think almost everyone did !


#50

Oryol : in the context described by Jeff06, the most important thing is to have a fast computation for the direct bot.

I experimented with a “direct bot” that ignores the 18°/turn limitation. Such a bot already gave very satisfactory results !


#51

i used 3.5


#53

So @Jeff06, to make sure I understand correctly:

  1. Your first genomes were encodings of short-term controls, then later on you modified one gene so it would encode a more long-term strategic element. Is that right?

  2. Were you generating and evolving new individuals at every new turn, starting from the same “primordial pool” each time? Or was there learning happening between successive turns?


#54
  1. I’m not sure I understand your question… When I use to the “meta-gene” to give the control to the “direct bot,” it is only for one simulated round. For the next simulated round, the next triplet of genes in the sequence would be used.

  2. actually, I saved the best genone after giving out my output to CG, and added back to the pool in the next turn. Simply translating every gene 3 to the left, and setting random genes at the end, since the first 3 genes were already “consumed” in the previous turn.


#55

2nd:
I thought about racing games. How often do you accelerate only moderately? How often do you steer just slightly? So I limited all 4 pods to only 7 moves: Left, Right, Left+Shield, Right+Shield, Left+Full Speed, Right+Full Speed, Straight+Full Speed.

Based on this moves, I looked at one pod a time and simulated the 7 possible outcomes assuming the other 3 pods would simply repeat their last action.

Then I scored the outcome based on several factors:

  • The leading pods distance to the next checkpoint
  • The angle of the leading pod: is it facing the next checkpoint?
  • Is the blocking pod facing the opponent leader?
  • Is the blocking pod nearer to or even between the opponents leader and his next checkpoint?
  • and some more…

The move with the best outcome was then selected.

I did this with all 4 pods, saved the resulting moves and repeated the process with one, two, three and mostly four additional moves in depth.

As I said: The scoring function is key and you have to think really hard about the essence of this (or any) game to find a good one.


#56

Well done ! It seems really simple yet ultra efficient.
Did you really simulated each drones independently ? Even YOUR drones ?


#57

Thanks.
And yes I did. But the second drone obviously knew what the first was doing.


#58

I actually used “Splines” curves for the optimisation of trajectories. (I thought about Bézier (B-Splines) and finally came out using splines which are more appropriate)
It is actually chunks of 3rd degree polynomes that you find solving a linear system taking into account the position of the next 3 checkpoints + your current position + your current velocity + ensuring the continuity of velocity and acceleration at the junctions.
Then I simply computed the acceleration at t=0 to get the next thrust !
With only this I was 10-20th in the leaderboard during the second/third day of the contest.

Oh also, note that I used parametric equations using complex numbers (Complex are natively supported by python!). Using complex numbers is actually so convenient that I will probably consider this again for the next contests!

Then I made a defensive bot using the spline resolution.
The goal was to estimate the trajectory of the opponent using my spline resolution and then aim for the right position estimating the time for him to get there and for me to get there. The time estimation was very approximate but worked well enough so didn’t even try to improve it.

I had a total of a bit less than 200 lines of codes (Python3) and got 16th ! :slightly_smiling:


#59

I know this does not mean quite much, but how many lines did you write for this ?


#60

850 lines / 29kb


#61

This is actually the approach I wanted to use but I couldn’t get the math to work out. I had a function which would output a thrust trying to “match” a given target velocity which ended up working out pretty well. Then, I would only have needed to use the spline to figure out the ideal velocity I should have been traveling on the curve. I’m not sure if you’re willing to share the math with me but I’d be pretty interested in what you came up with. :slightly_smiling:


#62

When will the contest be opened again ?