My strategy for the Russian AI Cup 2017
Hello.
Astrologers have announced a week. It will be about the competition Russian AI Cup 2017 , or rather about the bot written by me. I have been participating in this competition for the 6th year in a row - starting from tanchik. Some may know me by participating in the ML Boot Camp and HighLoad Cup.
The place was taken (again) not the first, but there is something to write about the habr. The article, first of all, may be of interest to the participants of this year, or those who want to learn some ideas for the next such competition, or just for those who are familiar with the subject of the Russian AI Cup.
')
I will not repeat the rules of the game. Who is familiar with them - he is familiar, and who is not familiar - can watch a couple of leaderboard games. Link to my profile.
The theme of this year was not very pleasant initially, but it was decided in advance that I would participate. It was worth sending the first version, as the interest woke up sharply, and at least some ideas began to appear. Therefore, who hesitates to participate or not in the next year, I advise you to send the very blockhead strategy. Opinion can change a lot.
The complexity of management has frightened off many participants, and especially newcomers. The number of participants is record low. And the majority of those who are in the top of the first three weeks, with obviously unpromising tactics. But all this is just for me.
Forces are spent on competition a lot. I post 100% of my free time. But this is not enough.
Lyrical digression ended, move on to the description of his strategy.
A full-time technical visualizer in the local runner is not enough. To draw debug information, you need to write your own, or use someone else's work. On the very first day, I started adapting my last year’s simple, unprecedented Windows Forms visualizer to the new rules.
It has a minimum of the necessary functionality: everything that a regular visualizer is able to do, as well as animation of selection, movement along a vector, capture of buildings, and other trifles.
A short video of what it looks like:
As I wrote above, in order to feel the API, and in order for ideas to start to appear, you need to write at least some strategy. Going ahead and clumsy "tornado" - a great strategy to test all subsequent versions, neatly "trimming" the enemy units.
According to the experience of the past Russian AI Cup, a necessary component of a successful strategy was a bust of moves + an exact simulation of the game world. What was most confusing was that a clear plan for the development of the strategy was not visible, as it was in past years. The bet was made on a good microcontrol, and you can then think up the tactics after seeing what the rivals are doing. While everything is settled there, you need to write a kernel that will not change much, and where it will be possible to increase the new functionality.
The code architecture is very simple. There is an object of type MyVehicle - a wrapper over the Model.Vehicle class, and a sandbox object (Sandbox). The latter, in fact, is the God object. He can be given any commands - all the same as Model.Move, and also simulate the world a few ticks ahead.
Decision making is based on a global evaluation function. There is one single function (hazard function), evaluating the state of the world, and returning a real number. For 1 move, we strive to change the state of the world so that this number is as low as possible.
I used the same idea in a previous CodeWizards competition. Since the wizard was only one (that is, two-dimensional space), it was possible to draw the value of the function in the form of a gradient scale ( link to last year's video). Here, 500 units (multidimensional space) with one common function, had to do without visualization.
It will be more detailed later on how I calculated this function.
Now you need to go through different moves. The final option is to go through the following moves for each unit:
This list was enough to cover all the variety of actions.
It consists of the sum of the following values ​​(with coefficients that were selected long and tediously):
All items above are calculated for each unit individually, regardless of belonging to any unit.
These are all melee factors. Further, the most difficult. How to make troops move to the enemy? To the nearest, or most meaty? How to make the troops flee from the enemy, hide the helicopters behind the armored personnel carriers? How to make troops move to grab buildings? How to make fly to be treated?
Here you will need information about splitting into groups. As well as clustering enemy units (only because debugging 5-7 groups is more convenient than 500).
In general, all this has one fat plus and one fat minus. Without crutches, you can add new items: nuclear, buildings, treatment. Odds need to be constantly customized: to repair under some situations, but to break on others.
To achieve high performance simulator data structure is needed, allowing you to quickly check the circle for collisions, and find neighbors in the vicinity of the battlefield.
Shortly before the start of the contest, I watched the activity in the github repositories of the contest developers. The QuadTree.java file was added to the codeforces-commons repository , and even then there were the first guesses that the competition would be with a large number of units. Only after I started to implement my simulator, I remembered this structure, and began to use it. After all, it is also used in the local runner. In the above implementation, there was a lack of methods for deleting a point, changing the coordinates of a point (deleting and re-adding is inefficient), tree cloning. I had to add them myself.
Checking units for collisions is the most expensive operation in my code, and I hardly fit into the time limit.
Team manager? Prioritized queue for units? Delayed and canceled commands? All this is not. As described above, all decisions are made only on the basis of the current situation, and knowing the last order for each unit. The available actions are spread over 60 ticks evenly according to the TickIndex principle% 10 == 0. Calculations are too expensive to make from each tick.
It took several evenings to somehow adapt units like Arrv. I decided to mix them with Tank and Ifv in a staggered manner. The construction is not optimal, but so far it will come down.
By the beginning of the first round, I consistently defeated many leaders. Involuntarily, one had to sharpen oneself for rivals like the “sandwich”, although realizing that they are not suitable for the final. Focused mainly on ud1 and GreenTea - their strategies were more similar to mine.
By the second round, they had to learn how to seize buildings and manage production. The kneading of Arrv units had to be thrown out. It took too long - an average of 900 ticks. Even with a potential optimization of 2 times it is still a lot, and the idea had to quit.
Starting troops Arrv, Tank, Ifv, as well as newly built, ran to seize buildings to minimize the total path length. This is a standard assignment problem solved by the Hungarian algorithm. More than the building selection algorithm has not changed. It was worth adding an account of the types of enemy equipment, but this did not seem to be a priority feature.
The performance problem came not the first plan. The number of units on the map has increased, the number of groups also, and therefore the number of various moves.
About a week I spent on optimization. It was necessary to optimize at the expense of accuracy. Instead of simulating actions on the entire map, I did a simulation in the neighborhood of each group separately, and then glued the results.
In order to avoid all kinds of embarrassment with nuclear bombs, I turned off these optimizations when there is at least one bomb on the map.
I had to go further, and turn off collision checks when the groups move in a straight line, or spin.
Well, the last thing - to sort through all 12 directions for the Move is meaningless if there are no enemies around.
But no, not the last. Groups with even numbers go on even turns, with odd numbers - on odd moves. Just built (aka bums) - every third move. There are exceptions for the detached units, both in the nuclear bomb mode and at the beginning of the game (<3000 ticks).
In the final, it was necessary to control the number of enemy units, and where approximately they are located. For each unit, Id remembered where it was last seen. There are 3 arrays:
Normal array of visible technology (visible)
An array of proven invisible technology (checked). It is known where each Id was last seen, but it is certain that it is no longer there.
An array of unverified invisible technology (unchecked). This means that we have to explore this territory for the presence of the enemy.
Filling arrays is as follows:
The radius of visibility is large enough to accurately determine whether the unit was killed, or disappeared from view. The exception is the destruction of a nuclear strike, but this is a very rare case. Therefore, "dead souls" almost did not remain.
The same QuadTree coped with a quick check for visibility, especially since it needs to be done 1 time per tick.
This is, perhaps, all that was done to support the game in the fog of war.
I did not overcome the time limits, my program is still with some opponents on some cards that does not fit into 220 seconds. But, nevertheless, he manages to ensure an advantage on points before a fall.
A little bit unlucky in the final - in the end I took the 4th place, and in the sandbox I took the 2nd. Next time will be stronger.
Thanks to all. See you in the Russian AI Cup 2018, and with someone, maybe even earlier.
Code
The place was taken (again) not the first, but there is something to write about the habr. The article, first of all, may be of interest to the participants of this year, or those who want to learn some ideas for the next such competition, or just for those who are familiar with the subject of the Russian AI Cup.
')
I will not repeat the rules of the game. Who is familiar with them - he is familiar, and who is not familiar - can watch a couple of leaderboard games. Link to my profile.
The theme of this year was not very pleasant initially, but it was decided in advance that I would participate. It was worth sending the first version, as the interest woke up sharply, and at least some ideas began to appear. Therefore, who hesitates to participate or not in the next year, I advise you to send the very blockhead strategy. Opinion can change a lot.
The complexity of management has frightened off many participants, and especially newcomers. The number of participants is record low. And the majority of those who are in the top of the first three weeks, with obviously unpromising tactics. But all this is just for me.
Forces are spent on competition a lot. I post 100% of my free time. But this is not enough.
Lyrical digression ended, move on to the description of his strategy.
Visualizer
A full-time technical visualizer in the local runner is not enough. To draw debug information, you need to write your own, or use someone else's work. On the very first day, I started adapting my last year’s simple, unprecedented Windows Forms visualizer to the new rules.
It has a minimum of the necessary functionality: everything that a regular visualizer is able to do, as well as animation of selection, movement along a vector, capture of buildings, and other trifles.
A short video of what it looks like:
First version
As I wrote above, in order to feel the API, and in order for ideas to start to appear, you need to write at least some strategy. Going ahead and clumsy "tornado" - a great strategy to test all subsequent versions, neatly "trimming" the enemy units.
It's time to write a basic strategy.
According to the experience of the past Russian AI Cup, a necessary component of a successful strategy was a bust of moves + an exact simulation of the game world. What was most confusing was that a clear plan for the development of the strategy was not visible, as it was in past years. The bet was made on a good microcontrol, and you can then think up the tactics after seeing what the rivals are doing. While everything is settled there, you need to write a kernel that will not change much, and where it will be possible to increase the new functionality.
The code architecture is very simple. There is an object of type MyVehicle - a wrapper over the Model.Vehicle class, and a sandbox object (Sandbox). The latter, in fact, is the God object. He can be given any commands - all the same as Model.Move, and also simulate the world a few ticks ahead.
Decision making is based on a global evaluation function. There is one single function (hazard function), evaluating the state of the world, and returning a real number. For 1 move, we strive to change the state of the world so that this number is as low as possible.
I used the same idea in a previous CodeWizards competition. Since the wizard was only one (that is, two-dimensional space), it was possible to draw the value of the function in the form of a gradient scale ( link to last year's video). Here, 500 units (multidimensional space) with one common function, had to do without visualization.
It will be more detailed later on how I calculated this function.
Now you need to go through different moves. The final option is to go through the following moves for each unit:
- Nothing to do. No orders are given, all continue to move in the same directions.
- Scale to the center of the squad.
- Scale from the center of the explosion of a nuclear bomb, if there is one. With different factor.
- Rotate by ± 45 °.
- For ground-based equipment Move to capture the structure.
- For Move helicopters in the direction of armored personnel carriers to shelter from aircraft.
- For air Move equipment towards Arrv for treatment.
- Move in 12 directions for a fairly large distance (say, a quarter of a map).
This list was enough to cover all the variety of actions.
The calculation of the hazard function.
It consists of the sum of the following values ​​(with coefficients that were selected long and tediously):
- The total amount of health of their equipment. It also took into account the hidden pool of health, which replenished Arrv, so that the technique had a desire to be treated.
- The total amount of health equipment of the enemy.
- The number of vehicles killed.
- The number of enemy vehicles killed.
- Potential damage from nuclear strikes. That is, it is as if a nuclear bomb would explode not through n ticks, but right now.
- The number of points to capture buildings.
- Potential damage. It turned out something like a fine (exponentially decaying) for being in the affected area, or near it. Namely, for each unit it is calculated (what damage it can do for 0 ticks) + (what damage it can do for 1 tick) / 2 + (what damage it can do for 2 ticks) / 4 +…. All this without taking into account the cooldown, to be afraid of resting opponents, and not to break through them.
All items above are calculated for each unit individually, regardless of belonging to any unit.
- Penalty for collision units. For the conflict of units, or "almost" a conflict. A fine for so much that it was more profitable to let a part of a detachment on cannon fodder than to go to the intersection with another detachment.
These are all melee factors. Further, the most difficult. How to make troops move to the enemy? To the nearest, or most meaty? How to make the troops flee from the enemy, hide the helicopters behind the armored personnel carriers? How to make troops move to grab buildings? How to make fly to be treated?
Here you will need information about splitting into groups. As well as clustering enemy units (only because debugging 5-7 groups is more convenient than 500).
- Attracting / repulsive enemy fields. Double cycle in my units, enemy units ... one of the weakest and most distressful places of my strategy ... in general, there is a function that depends only on the types of units and their size (mixed units are rare, therefore we believe that they are not). If, for example, I have 50 airplanes, the enemy has 50 helicopters, then the value of the function is very large positive. If 50 tanks against 50 tanks, then a small positive. If 50 helicopters against 50 aircraft, then a large negative. If 50 helicopters against 1 aircraft, then a small negative (suddenly! 50 helicopters will not fly to 1 aircraft).
This whole thing is multiplied by an exponentially decaying function of the distance between the groups. The greater the distance - the less influence on the total amount. It makes no sense to run to the goal on the opposite corner of the map, it is better to go to someone else closer.
Also, all this is multiplied by the sum of the densities of the units, namely (the sum of the areas) ^ 0.25. For heavily smeared units were compressed using SCALE. - Attractive fields to buildings. Here is the same scheme. About how the buildings were distributed in groups below.
- The attractive fields of helicopters to the BTR. Depends on the number of aircraft on the map, from the distance to the closest, the distance to the nearest “point of cover”.
- Attractive fields Arrv. Aviation in idle mode, or, when there is Arrv nearby, could use them. The greater the loss of health, and the closer Arrv, the stronger the attracting field.
In general, all this has one fat plus and one fat minus. Without crutches, you can add new items: nuclear, buildings, treatment. Odds need to be constantly customized: to repair under some situations, but to break on others.
Simulation
To achieve high performance simulator data structure is needed, allowing you to quickly check the circle for collisions, and find neighbors in the vicinity of the battlefield.
Shortly before the start of the contest, I watched the activity in the github repositories of the contest developers. The QuadTree.java file was added to the codeforces-commons repository , and even then there were the first guesses that the competition would be with a large number of units. Only after I started to implement my simulator, I remembered this structure, and began to use it. After all, it is also used in the local runner. In the above implementation, there was a lack of methods for deleting a point, changing the coordinates of a point (deleting and re-adding is inefficient), tree cloning. I had to add them myself.
Checking units for collisions is the most expensive operation in my code, and I hardly fit into the time limit.
Team manager
Team manager? Prioritized queue for units? Delayed and canceled commands? All this is not. As described above, all decisions are made only on the basis of the current situation, and knowing the last order for each unit. The available actions are spread over 60 ticks evenly according to the TickIndex principle% 10 == 0. Calculations are too expensive to make from each tick.
Round 1
It took several evenings to somehow adapt units like Arrv. I decided to mix them with Tank and Ifv in a staggered manner. The construction is not optimal, but so far it will come down.
Gif
By the beginning of the first round, I consistently defeated many leaders. Involuntarily, one had to sharpen oneself for rivals like the “sandwich”, although realizing that they are not suitable for the final. Focused mainly on ud1 and GreenTea - their strategies were more similar to mine.
Preparation for the round 2.
By the second round, they had to learn how to seize buildings and manage production. The kneading of Arrv units had to be thrown out. It took too long - an average of 900 ticks. Even with a potential optimization of 2 times it is still a lot, and the idea had to quit.
Starting troops Arrv, Tank, Ifv, as well as newly built, ran to seize buildings to minimize the total path length. This is a standard assignment problem solved by the Hungarian algorithm. More than the building selection algorithm has not changed. It was worth adding an account of the types of enemy equipment, but this did not seem to be a priority feature.
The performance problem came not the first plan. The number of units on the map has increased, the number of groups also, and therefore the number of various moves.
About a week I spent on optimization. It was necessary to optimize at the expense of accuracy. Instead of simulating actions on the entire map, I did a simulation in the neighborhood of each group separately, and then glued the results.
In order to avoid all kinds of embarrassment with nuclear bombs, I turned off these optimizations when there is at least one bomb on the map.
I had to go further, and turn off collision checks when the groups move in a straight line, or spin.
Well, the last thing - to sort through all 12 directions for the Move is meaningless if there are no enemies around.
But no, not the last. Groups with even numbers go on even turns, with odd numbers - on odd moves. Just built (aka bums) - every third move. There are exceptions for the detached units, both in the nuclear bomb mode and at the beginning of the game (<3000 ticks).
Preparation for the final
In the final, it was necessary to control the number of enemy units, and where approximately they are located. For each unit, Id remembered where it was last seen. There are 3 arrays:
Normal array of visible technology (visible)
An array of proven invisible technology (checked). It is known where each Id was last seen, but it is certain that it is no longer there.
An array of unverified invisible technology (unchecked). This means that we have to explore this territory for the presence of the enemy.
Filling arrays is as follows:
- At the beginning of the game we fill unchecked symmetrically to our units. This gives at least some starting point. Patterns in Id could not be found, but this is not a problem, you can generate them lazily by the first appearance.What it looks like
- At the beginning of each tick we shift from unchecked to checked, if the point has become visible, and also from visible to unchecked, if the unit has disappeared from the scope. If the unit remains in sight, but its Durability is 0, then it is killed.
- Game simulator puts Id in the order of the appearance of new technology. There is all the information to accurately determine where and when a new unit will appear, with which Id, and with what type. Collisions when in one tick several units appear are quite rare.
The radius of visibility is large enough to accurately determine whether the unit was killed, or disappeared from view. The exception is the destruction of a nuclear strike, but this is a very rare case. Therefore, "dead souls" almost did not remain.
The same QuadTree coped with a quick check for visibility, especially since it needs to be done 1 time per tick.
This is, perhaps, all that was done to support the game in the fog of war.
I did not overcome the time limits, my program is still with some opponents on some cards that does not fit into 220 seconds. But, nevertheless, he manages to ensure an advantage on points before a fall.
A little bit unlucky in the final - in the end I took the 4th place, and in the sandbox I took the 2nd. Next time will be stronger.
Thanks to all. See you in the Russian AI Cup 2018, and with someone, maybe even earlier.
Code
Source: https://habr.com/ru/post/345566/
All Articles