Tank maneuvers on the Russian AI Cup

A small story about participating in one of the IT contests Mail.ru group.

I received a letter: “We invite you to the Russian AI Cup and CodeTanks!”. I have long wanted to participate, went to register. The form was surprisingly simple, but the received letter did not make happy ((((


On this day, everything ended at the registration, because time was 0:27, and in the morning to work. I decided to sit on the weekend to learn and write an algorithm.
')
The weekend came, I began to read manuals, I will not retell everything. Who is in the subject, and so everyone knows, and who does not, enough for a brief excursion. There is a field of a given size on which 6 tanks fit, each with its own strategy (algorithm). Here, just the strategy and write participants of the competition. The strategy has many objects and parameters on the field that can be monitored: bullets, tanks, bonuses, object coordinates, engine power per track, and more. other



Of the built-in mathematical functions, there are only 2 — this is the distance between the objects and the angle between the straight line passing through the center of one object and the straight line connecting the centers of the objects, the angle between which should be calculated. Everything else falls on the hands of the one who writes the strategy.

The main point is to score as many points as possible, and not to stay alive. Points are given for hitting other tanks and destroying them.

The first algorithm I came up with was very simple. Ride on the field, collect the nearest bonuses that appear on the field, and shoot at the tanks, the angle of rotation of the tower to which is minimal.

size_t selected_tank = all_tanks.size(); for(size_t i = 0; i < all_tanks.size(); ++i) { //     Tank tank = all_tanks[i]; if (!tank.teammate() && tank.crew_health()) { //       :)     double angle_to_enemy = fabs(self.GetTurretAngleTo(tank)); //        if (angle_to_enemy < min_angle_to_enemy) { //   min_angle_to_enemy = angle_to_enemy; selected_tank = i; } } } 

This algorithm was not super good, but it showed good results.


Everything would be fine if there was stability in games, but as can be seen from the diagram, then the first, then the last places.

Optimization of this algorithm has begun. In the first optimization, I added a rectilinear motion if there was no more than 40 ticks and a super bullet shot if the target is closer than 500 pixels.

  if (self.GetDistanceTo(all_tanks[selected_tank]) < MIN_DISTANCE_FOR_PREMIUM_AMMO || self.premium_shell_count() > 2 || all_tanks[selected_tank].crew_health() < 35 || all_tanks[selected_tank].hull_durability() < 35 ){ move.set_fire_type(PREMIUM_PREFERRED); //   ,   } else{ move.set_fire_type(REGULAR_FIRE); //   ,   } ) <MIN_DISTANCE_FOR_PREMIUM_AMMO || self.premium_shell_count ()>  if (self.GetDistanceTo(all_tanks[selected_tank]) < MIN_DISTANCE_FOR_PREMIUM_AMMO || self.premium_shell_count() > 2 || all_tanks[selected_tank].crew_health() < 35 || all_tanks[selected_tank].hull_durability() < 35 ){ move.set_fire_type(PREMIUM_PREFERRED); //   ,   } else{ move.set_fire_type(REGULAR_FIRE); //   ,   } <  if (self.GetDistanceTo(all_tanks[selected_tank]) < MIN_DISTANCE_FOR_PREMIUM_AMMO || self.premium_shell_count() > 2 || all_tanks[selected_tank].crew_health() < 35 || all_tanks[selected_tank].hull_durability() < 35 ){ move.set_fire_type(PREMIUM_PREFERRED); //   ,   } else{ move.set_fire_type(REGULAR_FIRE); //   ,   } <  if (self.GetDistanceTo(all_tanks[selected_tank]) < MIN_DISTANCE_FOR_PREMIUM_AMMO || self.premium_shell_count() > 2 || all_tanks[selected_tank].crew_health() < 35 || all_tanks[selected_tank].hull_durability() < 35 ){ move.set_fire_type(PREMIUM_PREFERRED); //   ,   } else{ move.set_fire_type(REGULAR_FIRE); //   ,   } 

These changes did not give positive results; on the contrary, the results became worse.

After analyzing several fights, it was decided to push off from the edges of the field, for this I attached to the center of the field in such a way that I broke it into 4 quarters.



And depending on which quarter I find myself applying certain rules for exiting the corners and leaving the edges.

  if( self.GetDistanceTo(640,400) < 50 || last_tick_stright_move + 60 < world.tick() && all_shels.size()){ move.set_left_track_power(1.0); //     30  move.set_right_track_power(1.0); //     if( last_tick_stright_move + 80 < world.tick()){ last_tick_stright_move = world.tick(); counter_tick_straight_move++; } } else if (angle_to_center > MIN_ANGLE) { //    , move.set_left_track_power(1*mod_l); //   , move.set_right_track_power(0.5*mod_r); //    . } else if (angle_to_center < -MIN_ANGLE) { //    , move.set_left_track_power(0.5*mod_l); //   move.set_right_track_power(1*mod_r); //   . } else { move.set_left_track_power(1.0*mod_l); //     30  move.set_right_track_power(1.0*mod_r); //     counter_tick_straight_move++; if(counter_tick_straight_move > 30){ last_tick_stright_move = world.tick(); counter_tick_straight_move=0; } } 

Thus, the problem was defeated so that the tank at the edges would not spend a lot of time on the turn.


(on the chart, the drop is 1 optimization, and after it the take-off is the second)

Again a little analysis. And it became clear that I was dodging the edges, but as long as I do this I do not react to anything else. And then there was a radically new idea. Forget about the old algorithm and write a new one, the secrets of which I will publish after the end of the competition, but the graphics are ready to be shown now.


The latest growth, just due to pouring a new strategy. Of the 14 games there was 1 game in which I took 4th place, 2 games in which I took 3rd place, 1 game in which I took 2nd place and 10 games in which I became the leader, but to my disappointment I realized that in the chosen The player rating algorithm has a miscalculation. And then with writing algorithms, I
I switched to the study of the selected rating system. From the documentation it turned out that they use the Elo rating system, ran to read .
Aha it turns out this system is used to calculate the relative strength of players in games in which two participate, for example chess. Digging deeper, I will not give quotes - mnogabukaf. But the point is that this system does not take into account the dramatically changed player’s fitness at a particular moment, which means that if you drastically improve your tank control algorithm, you will still be trampling near your closest rivals, and given that the rating increases while the tank gaining more than the system predicted, and the system will always have a maximum forecast because all opponents are close by strength, then the rating will not grow much.

The most annoying thing is that I read it a couple of hours before the start of the first round of the competition, and only 900 algorithms passed from the sandbox to it. And I immediately quickly rushed to create a new account, where I filled in my algorithm, but I didn’t have 1 fight! In order to get 900 passable places.

At the same time, as always, the administration, did not respond to posts in their blog. And after 3 days, at the moment when I wrote this article, they release updates to their rating system! Where they recognize, to say the least, the imperfection of the chosen system:
? , , , , , , .
.

But the selection of the best 900 algorithms has already passed! Plus, in the same post, they change the environment of the tanks, and their combat characteristics, which of course causes a flurry of both the positive and negative emotions of the participants ...

In the conclusion, we should thank the organizers for providing a chance to take part in good competitions, and obmater those who chose the rating system of players. However, having made a discount on who is the organizer, they do not swear at such people, but simply treat them with understanding. So just thank you.

Published at the request of shulyakovskiy