🉑 👊 👨🏼‍🎤 My bot for Russian AI Cup 2019 📊 💏 🍲

It just so happened that this championship was the first for me where I was able to take a worthy place, for which I am not ashamed, so I decided to write the article just now too. The path that I went to this place: 1192th place in the championship of the 13th year, 241st in the championship of the 17th year, 91st in the championship of the 18th year and, finally, 16th (and 5th e in the sandbox) place on that.

General thoughts

I believe that one of the main reasons for the relatively successful performance at RAIC was a change in the approach to writing your strategy.

Before, I tried to immediately write something big and complicated, without intermediate steps, and the first version could only be filled in two weeks after the start of the championship, but in the past I couldn’t put it in all the time allotted and the first version was filled in only after the final .

All this led to the fact that while other participants could test their strategies for living, I still did not have a ready-made solution, albeit a bad one. Therefore, when it was possible to fill in, it turned out that the chosen approach does not work or works poorly, and since a lot of time and effort was invested, it was not possible to change it radically.

Therefore, I decided that this time I would do differently. Based on the experience of previous participations, I noticed that the starting bot, despite all its primitiveness, was written quite rationally, and, developing it, you can slowly add and test new features, and immediately check against the strategies of other participants. Especially I was convinced to try this approach last year’s article by T1024.

I also decided for myself that the more complex the approach, the less effective it is in my hands. For example, it makes no sense to use genetics where it is possible to do exhaustive search, and if there is a choice to sort out fewer options, but all, or more, but genetics, it is better to choose the first option. Plus, from reading Commando articles, I concluded that specific optimizations for the task will always be more effective than the general algorithm.

Nevertheless, even now I was three or four days late, before I managed to fill in the first version of the bot, at that time they were already at war in the sandbox.

What did I do at this time? I wrote a simulator, the importance of which I learned from past championships. Unlike last year, where the pseudo-code of the simulator was immediately available, this year all the mechanics had to be read from the documentation. Fortunately, as a compensation, the game mechanics were not quite complicated and straightforward, so I didn’t have any special problems.

Early versions

So, having in my hands a ready-made, albeit crooked, crude simulator, the first thing I did was screw up the dodges (Dodge function). Since this time I decided to act as simple as possible, the evasions were made as simple as possible - we check the movement in nine directions (4 axial, 4 diagonal and standing in place) and look at which of these directions the unit will receive the least damage.

The rest of the bot’s functionality remained almost completely like Quickstart. Target designation was also as primitive as possible - a chain of ifs that select the most suitable action for the unit: to the enemy, from the enemy, to the first-aid kit, to weapons, etc.

Surprisingly, this approach, gradually becoming more complicated, but not changing its essence, made it possible to get almost to the very top before the first round (once the bot was even in second place in the sandbox) and generally stay somewhere around the first ten places.

Nevertheless, this could not last forever, and the bot had to be improved. However, there was no idea what and how to improve, all attempts to change something in the strategy led to the fact that she was losing the old version. Minor changes were made, but nothing more.

The lack of ideas led to the fact that in rounds 1 and 2 I took 29 and 19 places respectively, and although I went to the finals, it became clear that something had to be changed radically. It was before the finale (and after the finale) that the largest number of significant changes were made.

Already somewhere from the middle of the championship I tried to experiment with smarter movement, but all attempts were unsuccessful. The initial idea was to choose the direction where the difference from the chance of hitting his bot on the enemy and the enemy on his bot was maximum. For this experiment, I spent almost all the time allotted to the final, with a zero result.

Therefore, for the final multi-level maps, the bot turned out to be completely unprepared. The chain of ifs gave relatively good results on single-level maps from rounds 1 and 2, but turned out to be unsuitable for multi-level maps of the final, I also did not have a navigation system for complex maps, since on simple maps it was possible to do with moving from start-up code.

— .

All firing control is in the AimHelper function.

Everything described below implies that the target is the visible enemy unit closest to the bot.

There are only three types of weapons, however, each of them requires its own approach. It’s better to just shoot more often from a machine gun, to aim better from a pistol, and then it’s important to shoot from a rocket launcher to do more damage to the enemy than to yourself.

Initially, there was no aiming at all, the bot just aimed at the center of the unit. Later, a prediction of the unit’s movement was added if it is in an uncontrolled flight (falls or flies from the jumppad). To do this, I simply simulated the movement of the unit until the distance that the bullet can fly for N ticks becomes equal to the distance to the unit.

When testing against the starting bot, he noticed his very unpleasant habit of constantly jumping up and down, and if the bot always aimed at the center of the enemy, this led to the sight constantly moving and the spread very quickly increasing to the maximum. For counteraction, a code was added that checked if the chance of hitting with the current aiming angle is better or equal to the chance of hitting with a new aim angle, then we do not change the point where we aim and do not increase the spread.

With shooting it was more difficult, one of the main problems of the starting bot was that he did not check whether he would touch himself with an explosion. For some reason, I liked the rocket launcher most of all three types of weapons, and therefore it was the first priority. It was necessary to teach the bot not to undermine itself.

The HitChance function was written, which divided the unit's firing sector into N rays, and checked each ray for a collision with a target. Also, when hit, the AOE of the explosion was checked, if it is a rocket launcher. Chance to hit = number of hits by ray or explosion / number of rays.

This allowed us to determine the static chance of hitting ourselves and the enemy, but did not take into account that the enemy himself could actively dodge. There were other problems, for example, the function did not take into account random firing at mines.

This was enough to fight against not-so-cunning enemies, but against tops that dodge bullets well, the function did not give any adequate result. A new approach was needed.

The HitPredict function also divides the firing cone into N rays, but instead of reycasting, we use a simulation where one bullet is fired at a time in one of the directions and it is checked whether the enemy can dodge.

To check the dodges, the Dodge function is also used, which the bot used for itself, but with very much cut off simulation time and the number of microtics. This method of assessment turned out to be quite accurate, but too pessimistic. If you use only it, then the bot shoots too rarely.

In the first version, the function returned only the chance of hitting, from 0-1, later it was added the calculation of the average HP value of the target, as well as the chance to kill by hit.

In the end, both functions worked together. The HitPredict function was used up to four times, one for each unit. The result of calculating each function was converted to speed, which showed how profitable / dangerous it is to shoot right now. Values added up. If the total value was less than zero, the shooting was blocked. For the rocket launcher, it was necessary that the speed was greater than zero.

It became possible to shoot more confidently in cases where an ally blocks firing or gets into the AOE of a rocket launcher, you can shoot him in the back knowing that the ally will either have time to dodge, or it is simply beneficial for us to shoot. For example, we will lose one unit, but we will take away two at once.

For the rocket launcher, the approach was also effective, one shot at the right time is much more effective than two shots, when the chance to hit is zero. In this form, the shooting was in the final, and this allowed to take 16th place.

Now the chips that were added after the final.

Accurate aiming: if the angle between the current sight and the desired one is not too large, we aim the sight at a data rate so as not to increase the spread.

Information angle for the pistol: oddly enough, the chip is very simple, but did not come to mind before. The prohibition to shoot if the scatter factor (scatter / max scatter) is greater than 0.6 provided the percentage of victories in the 1x1 mode in 3: 1 against the version that shot at the weapons CD. Reducing the factor to 0.3 provided the same percentage of victories against the version with the parameter 0.6. Thus, one of the simplest optimizations turned out to be one of the most effective.

Visualization of the operation of the HitPredict function, the trajectories where the hit is guaranteed are marked in red.

Navigation

Up to the finale of navigation there was no word at all. A slightly improved algorithm from the starting bot was used, and this was generally enough.

Therefore, when complex cards went, the bot had a very hard time. An urgent BFS search algorithm was written urgently, which looked for a path without taking into account its physical reachability, simply by tiles. In order for the bot to pass the found path, various crutches were used. All this worked very crookedly, and sometimes it didn’t work at all, but still the bot could somehow get to weapons and first-aid kits, and not jump on the spot.

After the finals, navigation was significantly improved and, according to my observations, it behaved even more efficiently than many participants with better path search algorithms.

Principle of work: the bot searches for the cell farthest on the way within the 5x5 square, visible from the center of the bot, and follows to this point.

Nevertheless, until the very end, it remained an incredibly crutch code that worked only on the final maps and fell on other, more complex ones.

Green marked path found diykstroy. The bot follows the point marked with a white square.

Moving and Estimating Function

Before the final, there was no evaluation function, instead of it a chain of ifs was used, which in order of priority set the bot to the target in accordance with the given conditions. For example, the first was a search for weapons if the bot does not have one, then a search for a first-aid kit if we are injured, etc.
This worked on simple maps, although it was crooked, because priorities changed very sharply and did not take into account various additional factors.

Therefore, an evaluation function was nevertheless written.

main parameters

Unit health, the biggest bonus.
. — , — .
— , . (1 — / . ), , . , , .
. , , .
, , , .
.
, .
.
A big bonus if we can touch the enemy with self-blasting.

The last two parameters were not in the final.

All these bonuses are calculated for each tick, summed up and the total value is averaged. In addition, there are estimated parameters that are calculated once for each direction.

Bonus for moving towards the nearest enemy.
Bonus for moving towards the nearest first-aid kit. The less health we have, the stronger the bonus.
Bonus for moving to the nearest weapon if we don’t have a weapon, or for moving to a weapon with a higher priority than the bot.
Bonus for moving to lootbox min if the bot has less than two of them.
Bonus for moving to the first-aid kit closest to the enemy, if we are closer to the first-aid kit than the enemy.
The most interesting bonus. It was added after the final. Allows you to prevent the enemy bot from being treated. According to observations, it turned out to be quite effective.

Notes

The simulation depth is 30 ticks.
The behavior of enemy bots is not simulated. The game is very dynamic and adequately predicting the movement of the enemy is very difficult and not particularly necessary. It could be useful to avoid insane suicides, but it was never done.
To avoid problems with evading bullets, if they are on the field, we simulate with a quality of 100 microtics per tick (as in the game), otherwise we reduce it to 5.
You may notice that no attenuation coefficient is applied. Perhaps this was a mistake.

The old move option is in MoveHelperOld, the new one in MoveHelper.

My bot (on the right) guards the first-aid kit

Mines

About mines need to be told separately. If initially it was not a very important gameplay element, it was supposed to mine key points. After the beta test, the ability to explode mines was suddenly added if they were hit by a bullet or explosion. Moreover, it was possible to set the mine and undermine it in the same tick.

That is, if you spend only two ticks, you could take any enemy unit with you. The enemy received 1000 points for our death, but we received 1000 + his health at the time of the demolition for his death. If you repeat this two times, then you could secure a victory with a very high probability.

The exploit turned out to be so strong that one participant, who was somewhere in the 15th place in the overall rating, unexpectedly slipped to the 4th in the final, simply due to a competent kamikaze.

(The difference is that in the general ranking there are both simple and complex cards. On simple cards, suicide works worse.)

In the final, the strategy used mines, but did not use intentional self-detonation. After the final, when there was a struggle for additional prizes, the TryPlantMine2 module was added, which implements the demoman. At first, due to errors in the code, the module was not particularly efficient, but in the latest version it was possible to fix everything, and the strategy immediately began to climb steeply up the rating. It got to the point that she even flew into the top 3, although then she slipped somewhat.

Principle of work: if we are in a position that allows you to put a mine, and can shoot no later than five ticks, we simulate three options: just shoot down, put one mine and shoot, two mines and shoot. For enemies and allies, we simulate movement using the same Dodge function, checking if they can jump out of the explosion zone before we are ready to undermine (not sure how much it was needed). For each option, we check how beneficial it is for us on points, if we are in the black, we are undermined (in this way we can be undermined even knowing that two of our units and one enemy will die, but we will still win) The effect of self- undermining

on the rating

findings

Simple solutions can often be more effective than more complex ones, but this has its own limit. With this approach, you can reach quite high, but then fall into the trap when the potential for improving the strategy has already been exhausted, and without radical changes to increase the strength of the strategy is impossible. For the future, you should think about some kind of intermediate option.

Conclusion

In general, I liked this championship, although I am biased towards it, because this is the first time I managed to take any place. Nevertheless, without even considering my subjective feelings, this year a lot has been realized at a higher level.

For the first time it was possible to communicate in Telegram with a person who is responsible for the technical part, and who promptly answered all the questions, for which many thanks to him.
For the first time, a normal built-in visualizer was present in the localranner. Previously, to output debugging graphics, you had to write your own.
Finally, instead of the inconvenient and buggy utility Repeater, the button "Repeat game" is added in the LAN.

Of the minuses, of course, is a huge exploit with mines.

And I will hope that my achievements in this championship are not accidental and that next time I will be able to at least save a place, and even better to take a higher position (dreaming is not harmful).

The bot code can be viewed on the github: github.com/silentnox/CodeSide

My bot for Russian AI Cup 2019