I’m already at level 10 just in a couple of days (not bragging btw) but have no idea where to start with this question.
inputs: checkpoints, checkpointIndex, x, y, vx, vy, angle.
“Every turn it takes a new command given a position and a THRUST indicating where to drive.”
thrust is not given. is my understanding correct?
Thrust is the acceleration to apply towards a given point. As the car commands are done as follow:
- Turn up to 18 degrees
- Accelerate THRUST in the pointing direction
- Move car
As a start you can look at the distance to your next checkpoint, use low thrust with short distances and 200 when you are far away and see how it drives 
4 Likes
That would be a great puzzle.
Constant rounding problems was killing half the pleasure. But, I’d managed this by overshooting different rounding functions and writing ugly new functions like:
def careful_truncate(number):
result = math.trunc(number)
if number - result > 0.99999: return result + 1
return result
Now I’m facing a new issue. My car barely touches the checkpoint circle, start and end points are behind the border, but the referee says that I got a hit. Reading source code (Unit.java#L36) has shown me that there is some quadratic equation with some geometry/physics math.
I’ve graduated in physics but I still do not understand what it is about and, damn, it is not described in rules.
It’s the formula for finding the intersection of a line and a circle (https://mathworld.wolfram.com/Circle-LineIntersection.html). You convert the position and speed of the unit to be relative to the checkpoint (checkpoint becomes a 600 radius circle at 0,0 and pod becomes a point moving in a straight line relative to that) and then find out where that line intersects the checkpoint. The final part then calculates if the intersection is in this turn or not. You don’t need to solve both parts of the quadratic as you only need to know when you enter the checkpoint, not when you leave.
It can be simplified slightly for search race as checkpoints don’t have a velocity but I assume it was taken from a proper csb simulation where you need to worry about collisions with other moving pods as well as checkpoints.
3 Likes
Yeah, with a pen and paper I’ve understood it by myself. But when we are talking math, I suppose that is a big assumption that the car trajectory is polygonal chain and its speed changes immediately at vertices.
This should be noted in rules.
Sorry for the inconvenience about unclear rules. The rules state:
On each turn the car movement are computed this way:
* The car rotates to face the target point, with a maximum of 18 degrees.
* The car's facing vector is multiplied by the given thrust value. The result is added to the current speed vector.
* The speed vector is added to the position of the car.
* The current speed vector is multiplied by 0.85
* The speed's values are truncated, angles converted to degrees and rounded and the position's values are truncated.
This means every point happens instantly after the previous one, and that speed change is immediately occurring after the instant rotation.
If you find this unclear, let me know how I could clarify it
2 Likes
Hey man,
I was in your shoes about 6 hours ago, passing all tests but one (98% score). It turns out that I had to rebuild my algo from the ground up in order to pass the missing one, and each change broke other validators.
So when you say that you passed all tests but one, it may actually mean that you need to change everything. 6 hours later, I’m at 100% finally!
Check Illedan’s demo to see all validators: https://www.codingame.com/ide/demo/86268346300c0d4ef2ce9a07b7325d27dc4a5e
To others who may have completed this challenge in Python and got a final time < 20,000 seconds, are you able to post your code? I cannot see other people’s solutions which is really unfortunate.
3 Likes
Well. Aren’t you a ray of sunshine? 
Eh, I suspected as much. I have played around with my settings only to do far worse than 98% on submission. You fix one problem, it caused ten others. I’ll come back to it later after I’ve had time to let it percolate.
This may help you, I know it was a game changer for me. But don’t read if you don’t want to be spoiled!
Summary
I was able to pass most validators by fine-tuning my settings but more importantly by aiming the car towards the next checkpoint BEFORE hitting the previous one. I would check the distance & speed and once the car was close enough, I’d turn it around and it would still drift into the checkpoint. But this allowed me to save a few seconds here and there and it worked.
I’ve just got 100% with monkey behind a wheel - feel my pain https://www.codingame.com/replay/513788020
I’ve started with proper math, that calculates angles, directions and checkpoint hits to predict next state. It took me two or three days. Then I wrote a dumb algorithm with constant thrust + angle pointed on the next checkpoint, select the best thrust, and climbed up to 96%.
Today I’ve written my first genetic algorithm and suddenly, I’m 84/311. Woo-hoo!
Didn’t expect that stochastic can be so good. And certainly, there is room for improvement.
As a reference I used https://www.codingame.com/playgrounds/334/genetic-algorithms/ and https://en.wikipedia.org/wiki/Simulated_annealing
4 Likes
Hi,
Thanks Illedan, great puzzle, I tried a genetic algorithm for the first time !
In the results pane, it’s written : “The validators differ from the puzzle test cases to prevent hard coded solutions. This is why you can have some fails here even if all of the tests provided in the IDE have been successfully passed.”
My bot can’t get below 12k6 
, so I checked here, and … 
I just read that people train a network (or whatever actually) over the entire set of tests !!!
This is contrary to the red message on the result pane 
I understand from your post that you wanted to train a NN, but still, imho this is overfitting, and a NN should be able to generalize or it’s not really AI, as it may be worth nothing outside the training set.
Please, next time don’t publish all test cases
And you can train a NN with all test-cases to give an estimate the best theoretical performance.
Anyway, thanks again for this opportunity to learn 
4 Likes
I know the security on CodinGame is not good enough to 100 % secure the validators. And you can also learn 1 bit of information about each validator on every submit, meaning you can reverse engineer them. This would cause an unfair advantage for those knowing how to extract this information. Also, I’m just happy players want to go the distance with the puzzle with offline training It’s all about learning 
2 Likes
So I actually came back to this (mostly because trying to get the last 50 spots from Gold to Legend in CSB is driving me nuts and I needed a break). And after some tinkering with my formula for thrust = f(distance to checkpoint) I was able to pass all validators. My time is dreadful (over 20k) but thanks @Illedan for making the validators available in the other spot, that was critical for me playing around with the parameters to pass 100%.
That out of the way, a side note, I have never done GA and would love to learn how to apply it here. If anyone would be willing to share their code (I use Dart but others are fine), I would really appreciate the kick start. Kind of wish you could see code once you pass like on other parts of CG. (Edit: I guess if that’s maybe too much to ask, perhaps some advice on what a good gene for this would be and any advice on crossover/mutation.)
1 Like
This is some initial code that could be used for a GA or SA, all you need to do is to finish the implementation on how the car drives and then implement the search around the Evaluate function to score a Genome. Hope it helps
(I recommend using it with the EXPERT output, to only turn integer degrees. )
public class Search
{
public const int Depth = 6;
public double Evaluate(Genome genome, Game game)
{
for(var i = 0; i < Depth; i++)
{
var action = genome.Actions[i];
game.Car.Rotate(action.Angle);
game.Car.Thrurst(action.Thrust);
game.Simulate();
}
var score = Score(game);
game.Reset();
return score;
}
private double Score(Game game)
{
if(game.NextCheckpoint >= game.Checkpoints.Count)
{
return 100000 + game.Car.Distance(game.Checkpoints[game.Checkpoints.Count - 1]);
}
return - game.Car.Distance(game.Checkpoints[game.NextCheckpoint]);
}
}
public class Genome
{
public Action[] Actions = new Action[Search.Depth];
}
public class Action
{
public int Thrust, Angle;
public static List<Action> PossibleActions = new List<Action>()
{
new Action{ Thrust = 200, Angle = 0},
new Action{ Thrust = 200, Angle = -18},
new Action{ Thrust = 200, Angle = 18},
new Action{ Thrust = 0, Angle = -18},
new Action{ Thrust = 0, Angle = 18},
};
}
public class Position
{
public double X, Y;
public double Distance(Position p2) => Math.Sqrt(Math.Pow(X - p2.X, 2) + Math.Pow(Y - p2.Y, 2));
}
public class Car : Position
{
public double Vx, Vy, Angle;
public void Rotate(int angle)
{
//...
}
public void Thrurst(int thrust)
{
//...
}
}
public class Game
{
public int NextCheckpoint;
public Car Car;
public List<Position> Checkpoints = new List<Position>();
public void Simulate()
{
// check collisions with checkpoints
// move car
// Apply friction
// Round positions
// See: https://github.com/Illedan/CGSearchRace/blob/master/SearchRace/src/main/java/com/codingame/game/Game.java#L43-L45
}
public void Reset()
{
// Set car position back to initial state and reset checkpoint counter
}
}
3 Likes
Your scoring looks suspicious. It tends to 0 just before reaching the checkpoint and goes largely negative right after. Not very rewarding.
Yeah, I didn’t want to make it 100 % perfect. You also need a high extra score for each checkpoint reached. Guess I shouldn’t have left it out
You’re right about the information extraction, but that’s also a usefull skill. I guess that’s why tests are random in some challenges, but I’m not sure if it’s possible for puzzles
Going further on the reverse engineering / information extraction, I didn’t look if there was exercices in this direction, but it would be an interesting one : no information on how to win, just expose possible actions, and ask the competitors to learn from win/loss results : could be solved by information extraction to build a model, or through reinforcement learning.
Anyone wants to create such a puzzle ?
I’m running a ga where I check at a depth of 25, population of 50 every turn for my next move, and I keep getting timed out randomly on my next move unless I set my time limit for the ga function to be super low like 15-17ms. How does it start counting the time limit for the next turn, is it as soon as you console.log your input for the current turn?
I’m also really not making good use of the 1s time limit on move 1 but my ga usually cant see all the way to the end in that time frame on larger test cases so I don’t really know how best to use it, have some other people who used a ga been able to see all the way to the end of the game on turn 1 in every test case, or am i right to just run the ga every turn?
To answer your question, some test cases are really long so I did not try to compute a solution until the end. Instead I am using a fixed depth of 25, considering that it’s long enough to compute an optimal trajectory to the next checkpoint while taking into account the second next.
Regarding timeouts, a good rule of thumb is to avoid any memory allocation/deallocation during your search. Allocate everything you need during the first turn and you will be safe. Of course, it’s more difficult when using a garbage collected language such as C# or Java because you have almost no control on memory operations. In this case, warming up your data (making sure your allocated data is really available by writing to it) may also help.
1 Like
Hi, do the checkpoints always are in numeric order ? I mean, if the current checkpoint is n°5, can I anticipate than the next is N°6 ?
It is true for the tests, I don’t know if it’s true for the validators.
Thank you for the answer.
4 Likes