I will tell you about my participation in the Russian AI Cup. I am a member with the nickname Hohol , who finished second in the finals.

I already had some experience writing a bot to control the tank. The fact is that I have been participating in ACM ICPC for five years now. The quarter-finals of our region are held within the walls of the Saratov State University, which, I recall, is one of the organizers of the Russian AI Cup. At the quarter-finals, an unofficial Code Game Challenge is held each time. The essence is the same - write a bot that will tear everyone. And although bots turn out to be wizards in a hat and with a staff, then racing cars, or hovercraft, we always called them tanks.

Since I participated in the CGC as many as five times, the competition did not cause me much enthusiasm at first.

But having got acquainted with the rules closer, I decided that I was still interested in the competition. Attracted the following items:

1. More than usual in CGC was the complexity of the game world. Tank tracks are driven separately. The tower moves separately from the hull. World objects are rectangular, not round. And the coolest thing is to control several tanks at once. All this promised a significant depth of the game, a variety of tactics, the ability to do something unrealistically cool.
2. Duration - a month (in contrast to only four hours that are given for writing a bot in CGC). During this time, strategies should develop very much. Even if you don’t participate yourself, it will be extremely interesting to observe the progress of the participants.
3. It is clear that there will be a lot of participants. Sports interest is very great.
4. Pleasant prizes, where without them.

Having started to deal with the system in more detail, he noticed that the organizers tried to make the entry threshold low. To view the battles on the server, you do not need anything except a browser. After downloading, the language pack just works right away (at least in my case, C #, Windows).
A low entry threshold will positively affect the number of participants. And the more participants, the more fun.

Round 1

Let me remind you that the contest began at midnight. To familiarize myself with the system, I sent some kind of trash, spinning in place and trying to shoot at enemies. For some reason, he got in about zero cases (it turns out, to determine whether to shoot, I used self.GetAngleTo, but I needed self.GetTurretAngleTo). However, I was convinced that the bot was moving, not falling, and went to bed. During the night, my rating was merged into minus infinity.

The next day I replaced this treshak with a slightly doped Quickstart (QuickStartGuy is a bot with a simple strategy, the code of which was posted on the site). He already chose bonuses according to the ratio of utility / distance and shot at enemies with a lead, considering that they move uniformly rectilinearly. This, with my merged rating, was enough to win almost all system fights. But here I ran into a problem that was subsequently discussed a lot among the participants: the first few battles, the rating changes greatly, and the next ones weakly. Accordingly, all the sharp jumps in the rating fell on the trash strategy, and then, despite the victories, the rating grew very, very slowly.

Engaged in movement. Learned to drive up to the bonuses backwards, if so closer. This dramatically increased survival. He tried to improve the trajectory so that he didn’t ride along broken lines like a quickstart, but along beautiful curves. I tried to make an effort on the caterpillar in proportion to the angle, in proportion to the square of the angle, in proportion to all functions of the angle and distance - nothing good happened. The tank stubbornly drove round dances around bonuses, and hesitated to pick up. He scored and quit the Quickstay movement.

By that time, a problem arose more important than crooked movement. There was a fashion to ride around the corners and shoot those in the center. For a long time I did not want to join this mainstream wave, wandered around the center and quickly died. In the end, I had to come to terms and go on about fashion - in a corner.

The next problem is that the tank often got stuck, fitting its nose into the edge of the map. I had to scream this - if we already have many ticks standing still, and at the same time we are not in a warm, cozy corner, it seems we are stuck, let's go to the center of the map.

I noticed that the cannon of my tank too often stands idle due to the fact that it does not have time to turn to the enemy. She almost turned, she’s ready to shoot, but then we picked up a bonus, we turn to the next one, the gun deviates from the enemy, and there’s nowhere to shoot again. I decided that it was necessary to help turn the gun with caterpillars as well. If the speed of rotation of the gun is not enough to turn to the target for the remaining recharge time, we turn to the target with the whole body. Now the gun has never been idle, the number of points scored per party has increased markedly. It also funny distorted the trajectory - now all the turns have become a little smoother, so that the gun was always aimed at the enemy. It seemed that the tank began to ride better, although the change seemed to relate to a completely different part of the strategy.

It seems that the description of almost all the features at that time fit into a couple of paragraphs, but this was already enough to rise somewhere to 10 places. Yes, after the drain, the rating grew very slowly, but surely. For several days I went home to a village where there was no Internet, and I forgot about the tanks. When I remembered, I decided to look from the phone - to see how the tank has merged over the past few days, and what the top looks like now. My tank was in first place. This crooked creature, traveling like a quickstart, somehow miraculously got to the top of the ranking. Then I realized that there is no turning back. If I was in first place, you need to get your tanks to the finals.

The first round was drawing near.

I decided to take up the movement improvement again. Too often, according to the Quikstartgaev algorithm, I drove past a saving bonus. Again, I sort through the dependence of the effort on the tracks on the angle. In proportion to the corner - already tried it, it turns out nonsense. In proportion to the square of the angle - the same garbage. What else to try? In proportion to the cube or something? Well ok, let's do it. Suddenly I find out that it looks pretty good. From afar, the tank rushes to the bonus along a pretty beautiful line. Only if the bonus is close, and the tank is not turned to it, does it move poorly. Well, if the bonus is close, we will move as best we can - like a quickstart. More past bonuses did not go.

Tops already knew how to more or less normally dodge. I was hopelessly behind in this regard. Sandbox space has dropped. I tried to implement a dodge using some strange heuristics, but nothing good came of it. As a result, all attempts were made to roll back, and enter the first half of the round, lagging behind the tops by a century in technical terms.

By the beginning of the break, I was somewhere in 25th place. This, of course, is the passage to the next round, but being obviously retarded is somehow unpleasant. It was clear that for the implementation of normal evasion, I lacked knowledge of local physics. I knew by what law the velocity of the shells changed, but I didn’t know the laws of the tank’s movement. So you need to find them out. Then I took advantage of the help of anonymous. I set up simple experiments - moving in a straight forward, moving backward - and found the characteristics of the tank in each tick. And anonymous on these characteristics figured out the laws of motion. I decided that for a start, dodging using full throttle back / forth would be quite enough for me. After clarifying these laws, I was ready to write the simplest evasion.

I implemented it like this: I imagined that my tank was moving in a straight line uniformly, checked whether a bullet would hit me in the next 100 ticks, and if so, checked if it would hit if I turned on the gas forward / back right now.

Such evasion worked already well. To increase the effect, being in the corner, I turned sideways to the enemy, who was now aiming at me.

These measures allowed me to rise to the 8th place by the end of the first round. The time has come for battles 2na2na2.

Round 2

Looking through the battles from the first round, I noticed several cases when the tank tried to dodge, but despite this the bullet overtook him. In this case, there was no interference with evasion. The expected behavior is to either dodge or not try to dodge at all. Obviously a bug. I'm running the fight in Repeater, debate. I find out that the acceleration of the tank during movement was much less than expected. But why? He drove into the mud chtoli, stalled? I’m sending an anonymous tank movement log - and so, check to see if I’m stupid. Confirms that the acceleration here is too small. “And your tank wasn’t accidentally hit?” - Well, there were half the crew hp, but what's the difference? - And the movement of the tank depends on the hp crew. - What? The movement depends on the crew? Where did you get this from? - The rules say ... "

I open the rules, read:

“With a decrease in the crew’s health, the control efficiency of the tank decreases: it begins to move more slowly, rotate the turret, and the reload time of the gun also increases.”

For some reason, rereading the rules several times, I have never noticed this phrase. And in the battles I never noticed that the wrecked tanks were somehow slowed down. RTFM, comrades.

And yet, what's up? Does the crew pedal so the tracks move? Turns the tower with your hands? Does shells manually reload? 21st century in the yard seems to be. Well, at least they don’t throw shells with their hands, otherwise they would fall directly under their tracks at low hp.

In general, finding out the dependence of the engine power on the hp crew, I corrected the evasion.

It's time to improve the movement again. I noticed that the tank often starts to shake its nose strangely when moving to the bonus, if this movement was preceded by a sharp turn. Because of this, the speed of movement was greatly reduced. This happened for this reason: we just turned to face the bonus and now we are driving forward, but before that we turned to it with a large angular velocity, and the angular velocity by inertia turns us away from the bonus, and quite strongly. Then we again forcefully turn to the bonus, this time in the opposite direction, and everything repeats again. Then I began to extinguish the angular velocity, if now it is directed to the bonus. Oscillations ceased, the speed of movement to bonuses increased.

No matter how I thought, no matter how I experimented, but I still did not understand how to optimally place two tanks. If we crouch on the side, it seems to be good along the vertical wall. Well, yes, in the case of a spawn on the side, in general everything works out well, because opponents who sleep on the other side kill each other. But if there was a spawn between the enemies, or at least on a vertical line with the enemy - I do not understand what to do. In the end, he began to somehow clog two tanks into a corner, but nothing particularly good came of it.

That is, now I know that nothing good happened. And then I was in the top five in the sandbox, and I thought that everything was in chocolate. The second round came up, and according to the results of its first half, I was in 75th place. In the final, 50 passed.

So, a break. Something needs to be improved urgently.

Tops clearly dodged better than me. I knew how to dodge only when riding backwards or forwards. This was not enough. But in order to correctly dodge a turn, you need to know the physics of the world in much more detail. I got ready for a new phase of reverse engineering, which would take me a lot of time. But then Noob gave me a link to a discussion of the contest on gamedev.ru - a multi-page topic that began simultaneously with the contest. People there long ago found out all the physics of the world by experiments or by decompiling the runner locale. It is clear that if this data was posted in the public domain, many may already have used it. And reluctantly, I used these ready-made data to write an accurate predictor of movement.

From now on, knowing the current state of the tank, and what efforts will be applied to the tracks, I could accurately determine its condition through several ticks. Now I went over not two possible ways of dodging a projectile, but 121 - 11 different efforts each on the left and right tracks. A rebound avoidance was also added - for this it was just necessary to determine at what angle the bullet would hit the armor. Dodge efficiency has increased dramatically.

Tired of missing out on well-evading enemies. It was often clear: if you shoot now, the enemy will easily dodge; however, after a few ticks, he found himself in a position from which he could no longer dodge. Maybe try to shoot only if the enemy just can’t dodge? Fortunately, we have an ideal forecaster of his position in various chosen escape routes. Implemented this. I got better, I was satisfied. But after a while, he noticed that for some reason he began to die faster. What nonsense is this? I improved the shooting, why did it worsen my survival? Having compared several battles before and after the improvement, I realized what was happening. It turns out that by spamming bullets, I often shot down bullets flying at me, from which I could not dodge. This happened from the very first versions, I never thought about it and simply did not notice that this was happening.a lot of dangerous shells. Now, rarely shooting, I often fell under bullets. Discouraged, I sawed out a feature for conventional shells, leaving it only for premium ones - for them it was absolutely appropriate.

He taught tanks not to take the bonus, which is more needed for teammate. Prior to this, the priority was always with TeammateIndex = 0, which, of course, is nonsense.

I started not to pick up the bonus corresponding to which hp is full, but to stand next to it, in case I get damage. And pick up if the enemy is nearby. Quite often, it turned out in this way to drag the bonus that I did not need right from under the nose of the enemy who needed it.

And now, the time has come for the second half of the round. As far as I remember, the first 8 hours of testing I staggered somewhere around 65 places, without any visible chance of an increase. I was ready to say goodbye to the competition and continue to live a normal life, but a dizzying series of victories in the last hours raised me to 48th place.

It’s a pity that some strong players that I remember, such as MrDindows and twrlx , did not qualify for the final .

The final

So, I went to the finals, and this is a serious business. Although I laughed at my friends that I could not guarantee the murder of at least one enemy tank in the finals, in fact I was immediately set to hit the top places. Even though the drain of the second round. Now I was a scientist - I knew that you can’t trust the sandbox, and you need to rely only on statistics on dueling.

We return to the idea of ​​accurate shooting. I refused her, as dangerous bullets were badly shot down with her. But what prevents me from checking if this bullet is dangerous, and if I shoot it with a shot? Nothing interferes, it is unclear why it did not immediately come to mind. Implemented, the shoot became much better.

Now you could completely concentrate on duels. At the moment, each of my three tanks considered himself part of a team of two tanks. They strangely wandered in search of bonuses and ridiculously fumbled in the corner, trying to accommodate themselves there, not realizing that there were three of them, not two. I had to create a separate three-tank strategy. But what will this strategy do? He again turned to the experience of current tops. I found out that the tactic of “occupying a wall and standing at it, dodging” is very fashionable. No matter how boring it may look, this strategy was apparently the most optimal in terms of complexity of implementation to efficiency.

So, it was decided - the tanks are evenly spaced along the vertical wall. At first, I tried to orient them with their faces towards the middle of the map - perhaps it will turn out to be effective in dodging a rebound. But it turned out only to effectively catch hits in the forehead. I had to arrange it vertically. Already at this stage, a version was obtained that was almost indistinguishable from the final with a naked eye. But in fact, there was still much work to be done.

It was the last day before the final.

It became clear that the recently improved shooting system no longer works. I only shot when I was sure of a hit. Before I moved on to the long-range strategy, such shooting worked well. But now the enemy was almost always far away. It turns out that I was almost never sure of a hit, and I almost never shot. At the same time, the enemy, from afar spamming shots at me, at least sometimes, but hit. I had to compromise - if the enemy is close, shoot only if I am sure of the hit, otherwise spam. With the shooting on this finished.

Further, it turned out that the importance of dodging has sharply increased. Other types of battles almost always ended in the destruction of all rivals, the remaining points usually had more, and he won. One accidental hit in you did not do weather - you could pick up a bonus, recover, and destroy the offender. In a duel, you can restore HP, but you won’t be able to take away the points that the opponent got for hitting. Like destroying him if he sits far away.

It was obvious that the current tops were dodging better than me again. What is the problem? After analyzing the fights, I found out.

I’ll tell you in more detail how I dodged at this time. I had a list of 121 possible pairs of efforts. There was a Boolean function that determines whether a bullet will hit me if I will use this couple of efforts in the next 100 ticks. It turns out that the bullet flying from me at a distance of 1 pixel did not threaten me. As a result, almost all the bullets touched the tank, but ricocheted. All I heard was the characteristic bounce of the ricochet from my tanks.

The problem was that by any chance - the wall prevented turning, the teammate pushed, the tank fired - the movement of the tank deviated slightly from the calculated one, and instead of a rebound there was a clear hit.

How did the tops dodge? Ricochet from them were rare. They tried to stay away from the bullet, with a margin of distance. How can I do the same? Maybe just consider your tank 10 pixels larger in all directions? Yes, in this case, the tank really tries to be at least 10 away from the bullet. But imagine that a bullet is flying at us, and we can dodge it, remaining at best at a distance of 5 from it. A tank that thinks it is 10 pixels larger will find there is no chance of dodging it. And with a calm soul, she will allow her to fall into herself.

I found the following solution: stop considering the danger of a bullet as a Boolean value and consider it material. Let minDist be the minimum distance from the tank that the bullet will visit. Then we assume that its danger is max (0,20-minDist). The problem is resolved. Now the tank is kept away from any bullet flying at least 20 pixels away.

Test fights have shown that the new dodge system really works much better. Now I almost consistently beat all but the tops - Milanin , Mr.Smile , SDiL , Romka .

Two hours before the start of the first half of the finals. Time after time I look through the fights in which I merge SDiL, in search of things that can be quickly improved. I find out that most hits on me occur when several bullets fly at me. The tank dodges only the nearest, and catches the next hit. It is necessary to write a dodge from several shells at the same time. Can I catch it in two hours? I will have time to write. And to test? To do this, send the strategy to the server. What if he then lays down (it happened before the start of the round), the version will be buggy, and I won’t have time to resend it? Take a chance.

After a while, the code is ready. I'm testing in the runner locale. Bugs are not visible, whether what works is necessary, it is not clear - smartgays do not shoot very friendly. I send it to the server, create fights with five tops, go away for a while from the computer. I come back, I refresh the page, and take my breath away when I see that all five fights are won. I create it again, beat everyone except Mr.Smile . I watch fights - dodges perfectly. Well, tanks are ready for the finals.

With the start of testing, he immediately came in first place. After watching for a while, pleased went to bed. In the morning I found myself on the second, Mr.Smile on the first. Indeed, his win rate is higher, and he kills me steadily. It seems that there is nothing to be done, we will try to keep the second.

The break began, it's time to improve the strategy. I was afraid that, following Mr.Smile, many would begin to decide on ranged strategies. This would mean the need for major changes in case of high efficiency of such rush. But so far nothing like this has happened. I decided to wait for changes in the tactics of the opponents, so that it was clear what to react to. In the meantime, look for obvious flaws in the existing strategy.

After reviewing several merged battles, I noticed in several cases a very strange spin of their tanks - not in the direction we would like at the moment. Repeater, debug. I go into several nested function calls, and I see the following code in one of them:

if (toy > 0)
    TurnTo(self.X, self.Y+1);
else
    TurnTo(self.X, self.Y+1);

Hmm, not bad for a strategy in second place. Of course, the else should be -1. Correct.

I continue to watch merged fights.
I find a battle in which two bullets fly into my tank, approximately in parallel, one flies to the bottom of my tank, the other to the top. Expected behavior - the tank rotates a bit and allows bullets to fly on opposite sides of itself. But instead, he makes some strange body movement, dodges one, and gets a second in the stern. Repeater, debug. After some time, I understand what’s the matter. I considered the danger from two shells as the sum of their dangers separately. Which, I recall, is equal to max (0,20-minDist). But then it turns out that a pair of bullets with distances (19.1) has the same danger as a pair with distances (10.10). Obviously, the first pair is still much more dangerous. Therefore, we will consider the final hazard as the maximum of individual hazards, and not the sum.

More that day almost did not change anything. I decided to go to bed early, wake up in the morning and check if my opponents wrote anything to block me overnight.

In the morning I see a Megabyte message on gamedev.ru, in which he says that he scammed me, Mr.Smile and Romka - now he will immediately rush us. Hmm, interestingly, check. I create five fights with him, and with a sagging jaw I watch him endure me in all fights. His tanks completely impudently come close to mine, and methodically in turn shoot them. I checked several other players - there seem to be no radical changes. Only at RomkaI found something interesting. If the initial location of the tanks is such that one of the players is directly above the bunker, the other under the bunker, Romka goes in a horizontal chain in the same direction as me, takes one of my corners before me, shoots the tank that goes to this corner, after which deals with the rest.

In general, I had to urgently finish the melee tactics. However, this completion was reduced only to increasing the priority of bonuses (especially premium shells) when we are under attack. And I thought that I was under attack, if there are at least two enemy tanks in my half of the field. MegabyteI was still merging. It seemed to me, due to the fact that too late to respond to his rush. I had to add the following code to the function that determines whether we are under attack:

if(enemies[0].PlayerName == "Megabyte")
    return true;

After such a hack, the response speed increased, and the win rate improved.

The second half of the testing did not present any surprises. There was only an intrigue, who will take 6th place (the last prize) - Romka or Commandos. Still, Romka kept his place.

Epilogue

In fact, a little disappointed with his own strategy in duels. Boring looks boring.

A typical battle with the same long-range strategy from valex :


The beginning of an epic battle.


The situation is heating up.


Nerves are strained to the limit.


Friendship has won.

Whether it’s Mr.Smile’s business - his rush in duels is simply beautiful. Killing almost any opponent faster than half the allotted time is something.

Let me remind those who are interested that the sandbox on the site will continue to work for several more months. Everyone who complained that it was too late to learn about the contest can play with the tanks, not really rushing anywhere.

Thanks to the organizers for the wonderful contest. We hope to see a follow-up in a year.

UPD: code .