History 3 places Russian AI Cup 2017
Hello! In this article, I want to briefly outline the key points of my strategy during the last Russian AI Cup programming competition in artificial intelligence.
The essence of the event is that it was necessary to write a bot for the game, the rules of which were set by the organizers and changed during the event.
')
The peculiarity of the task of this year was that it was necessary to create an artificial intelligence that controls a large number of combat units.
Rules can be found here .
My profile is Leos .
I took part in a similar event for the second time.
The first experience was in 2015 - Russian AI Cup 2015, CodeRacing. Then all I achieved was getting into the second round. And this could have ended and there would be no story, but one day on Habré I came across an article from one of the winners who radically changed my idea of what should have been done. From that moment I waited for the next opportunity to take part in such an event.
2016 had to be missed - the army.
I started participating in this competition almost from the very start of the open beta test.
The first sensible strategy was a simple sandwich plus fighters who acted independently.
However, it was clear that in the second round, sandwiches would not be effective, so it was necessary to look for something else. Potential fields suggested themselves and after I saw them in action from GreenTea , it became clear that I would use them.
The second strategy was the small sandwiches (big buter broke into 10 groups). Fighters still acted independently.
Here are some examples of how she worked against various opponents' strategies in the first round:
The enemy has several groups: russianaicup.ru/game/view/106992
Opponent sandwich: russianaicup.ru/game/view/124483
The main advantage of this strategy was that groups with a large number of wounded units could be diverted to a safe distance and all ARRVs were expelled.
But the shortcomings were more significant:
The third strategy was to use 5 groups as is. Probably, this is the most optimal strategy for splitting troops, since most of the participants in the final have come to this.
In the first versions I went in groups every 10 ticks in turn, and the order was broken only by the enemy’s nuclear strikes.
In the final version for each group I calculate the need for a move. The need for a move is determined by the maximum potential difference for the corresponding group, and the enemy’s nuclear strike is taken into account separately. If there is no group with sufficient need for a move, then we do nothing.
Here it is also worth noting that some actions require several actions in a row (for example, selecting and moving a group). Therefore, I started the monitor, which is captured if the action does not consist of a single command, and when the monitor is captured, only its owner can perform actions.
I didn't have any queues for the teams. In order not to re-allocate an already selected group, I always remember which group is currently selected.
Potentials counted for all their groups.
Went through 64 different directions. First the formula:
Where
- the potential of the group in the center,
- potential at the k -th point,
- the number of ticks needed to get to the k -th point.
Actually
- this is a relative potential difference. I counted it for each direction. Points - these are just some points on this direction that are remote for a given distance.
Using the same formula, I calculated the relative potential difference for the current direction of movement -
.
Considered the top priority group with the maximum difference
.
I focused on the selection of potentials. In fact there should be a lot of mathematics here, but I will write only the essence:
There were 3 types of potentials:
There were 4 objects generating potentials:
1) the boundaries of the map
Highly decreasing, repulsive potential, so as not to be driven into a corner, not to crash into the edges of the map.
2) Allied units
Here, the last two capabilities were added with the introduction of the fog of war, so that air forces cover ground forces by default.
3) Enemy units
Medium decreasing potential, for which the sign and the coefficient was calculated using his battle simulator.
4) Facilities
Weakly decreasing potential, about the coefficient for which I will write in more detail.
I calculated the coefficients from each structure for all my groups. The emphasis is on the following things:
I did not invent anything abstruse here, I registered everything with ifems, then I selected more or less adequate coefficients by trial and error.
The type of equipment produced was determined using the battle simulator.
The merging of technology into new groups took place when the potential difference for a new group was quite large. At the same time, for these groups, only the enemy potentials and the potentials of the structures were taken into account (this was corrected on the day between the finals, because of which I suffered a lot of unpleasant defeats on the first day of the final).
Already mentioned twice, but nothing special about it. The goal of the simulator was to determine how much one group is stronger than another.
2 groups take part in the battle. I consider their full health and damage taking into account all the features (ground / air, type of equipment, ARRV).
After that, I run an iterative process. Damage at each iteration is proportional to current health. Health at each iteration decreases by the amount of damage to the enemy.
The number of iterations in the latest version was 10.
In general, it worked well and my units did not climb into losing clashes.
Naturally it was necessary to determine the enemy group. Here I made a simple algorithm as a stub, which remained with me to the end.
I divided the region into 8x8 tiles, and if there are enemy units in the neighboring tiles at a distance of less than 9, then I combined them into one group.
Approximated adversary groups with an ellipse. Deliberately wrong algorithm, which again used as a stub, but came to the end with me.
Defined the main axis and the normal to it, which passed through the center of the group in the direction of the most distant technology in the group and in the perpendicular to it, respectively. Then determined the radii.
Nothing special came up with the introduction of the fog of war. I memorized the positions of the enemy, added additional potentials, so that the air forces covered ground forces.
With the visualizer did not bother much. Draw only potential fields. And when analyzing games I used it in conjunction with the locale runner.
I will add a few examples to have pictures.
Here the fat green spot is my helicopters, and a potential field is built for them.
Blue color corresponds to positive potentials, red - negative, black on a red background - very large in absolute value negative.
Right-below three enemy ground groups that attract my helicopters. In the center are enemy fighters that my helicopters fear. A big black spot - my fighters, which can not be encountered.
Another example in which the actor is my IFV. Here, all enemy groups, as well as the two on the right, are positive charges.
Black spots correspond to places that are undesirable to move because of collisions with their groups. The lower left structure has no effect, since the ARRV group has already moved to capture it.
Both examples are taken from this battle - russianaicup.ru/game/view/310222 , 730 and 1800 ticks, respectively.
Here is the link to my repository.
Wrote in Java. The quality of the code is what it is when I wrote, I did not expect that someone would see it. Well, I'm not a javist, Java courses took place at the same time as ai cap.
Total: a lot of crutches and stubs, no abstruse algorithms.
It turned out completely without emotion and dry, but I hope someone will find something useful for themselves.
PS I almost forgot, all happy New Year! :)
Update: Corrected formulas to be visible on a mobile phone.
A bit about Russian AI Cup
The essence of the event is that it was necessary to write a bot for the game, the rules of which were set by the organizers and changed during the event.
')
The peculiarity of the task of this year was that it was necessary to create an artificial intelligence that controls a large number of combat units.
Rules can be found here .
Something about me
My profile is Leos .
I took part in a similar event for the second time.
The first experience was in 2015 - Russian AI Cup 2015, CodeRacing. Then all I achieved was getting into the second round. And this could have ended and there would be no story, but one day on Habré I came across an article from one of the winners who radically changed my idea of what should have been done. From that moment I waited for the next opportunity to take part in such an event.
2016 had to be missed - the army.
I started participating in this competition almost from the very start of the open beta test.
Strategy
The first sensible strategy was a simple sandwich plus fighters who acted independently.
However, it was clear that in the second round, sandwiches would not be effective, so it was necessary to look for something else. Potential fields suggested themselves and after I saw them in action from GreenTea , it became clear that I would use them.
The second strategy was the small sandwiches (big buter broke into 10 groups). Fighters still acted independently.
Here are some examples of how she worked against various opponents' strategies in the first round:
The enemy has several groups: russianaicup.ru/game/view/106992
Opponent sandwich: russianaicup.ru/game/view/124483
The main advantage of this strategy was that groups with a large number of wounded units could be diverted to a safe distance and all ARRVs were expelled.
But the shortcomings were more significant:
- Firstly, the construction of these sandwiches took about 1500 ticks at the start, and when the facilities appeared, it was important to begin to act on the map as quickly as possible.
- Secondly, the sandwiches were forced to move with a minimum speed in order not to disturb their structure.
- Finally, the sandwiches themselves were quite vulnerable, and if my fighters died at the beginning of the battle, the enemy fighters and helicopters were enough to completely destroy my troops.
The third strategy was to use 5 groups as is. Probably, this is the most optimal strategy for splitting troops, since most of the participants in the final have come to this.
Turn sequence
In the first versions I went in groups every 10 ticks in turn, and the order was broken only by the enemy’s nuclear strikes.
In the final version for each group I calculate the need for a move. The need for a move is determined by the maximum potential difference for the corresponding group, and the enemy’s nuclear strike is taken into account separately. If there is no group with sufficient need for a move, then we do nothing.
Here it is also worth noting that some actions require several actions in a row (for example, selecting and moving a group). Therefore, I started the monitor, which is captured if the action does not consist of a single command, and when the monitor is captured, only its owner can perform actions.
I didn't have any queues for the teams. In order not to re-allocate an already selected group, I always remember which group is currently selected.
Selection of priority groups based on potential difference
Potentials counted for all their groups.
Went through 64 different directions. First the formula:
Where
- the potential of the group in the center,
- potential at the k -th point,
- the number of ticks needed to get to the k -th point.
Actually
- this is a relative potential difference. I counted it for each direction. Points - these are just some points on this direction that are remote for a given distance.
Using the same formula, I calculated the relative potential difference for the current direction of movement -
.
Considered the top priority group with the maximum difference
.
Potential calculation
I focused on the selection of potentials. In fact there should be a lot of mathematics here, but I will write only the essence:
There were 3 types of potentials:
- Strongly decreasing (set by exponent)
- Medium decreasing (asked
) - Weakly decreasing (asked
)
There were 4 objects generating potentials:
1) the boundaries of the map
Highly decreasing, repulsive potential, so as not to be driven into a corner, not to crash into the edges of the map.
2) Allied units
- Highly decreasing, repulsive potential for groups that may encounter.
- ARRV generated a moderately decreasing attracting potential for air groups.
- TANK and ARRV generated a moderately decreasing attracting potential for FIGHTER.
- IFV generated a moderately decreasing pull potential for HELICOPTER.
Here, the last two capabilities were added with the introduction of the fog of war, so that air forces cover ground forces by default.
3) Enemy units
Medium decreasing potential, for which the sign and the coefficient was calculated using his battle simulator.
4) Facilities
Weakly decreasing potential, about the coefficient for which I will write in more detail.
Capture facilities
I calculated the coefficients from each structure for all my groups. The emphasis is on the following things:
- Do not run a crowd to capture one building.
- Protection of their facilities, while capturing the enemy.
- Not to seize facilities that the enemy protects, including retreating, throwing a grip if I am attacked.
I did not invent anything abstruse here, I registered everything with ifems, then I selected more or less adequate coefficients by trial and error.
Manufacture of machinery
The type of equipment produced was determined using the battle simulator.
The merging of technology into new groups took place when the potential difference for a new group was quite large. At the same time, for these groups, only the enemy potentials and the potentials of the structures were taken into account (this was corrected on the day between the finals, because of which I suffered a lot of unpleasant defeats on the first day of the final).
Battle simulator
Already mentioned twice, but nothing special about it. The goal of the simulator was to determine how much one group is stronger than another.
2 groups take part in the battle. I consider their full health and damage taking into account all the features (ground / air, type of equipment, ARRV).
After that, I run an iterative process. Damage at each iteration is proportional to current health. Health at each iteration decreases by the amount of damage to the enemy.
The number of iterations in the latest version was 10.
In general, it worked well and my units did not climb into losing clashes.
Clustering
Naturally it was necessary to determine the enemy group. Here I made a simple algorithm as a stub, which remained with me to the end.
I divided the region into 8x8 tiles, and if there are enemy units in the neighboring tiles at a distance of less than 9, then I combined them into one group.
Approximation of enemy groups
Approximated adversary groups with an ellipse. Deliberately wrong algorithm, which again used as a stub, but came to the end with me.
Defined the main axis and the normal to it, which passed through the center of the group in the direction of the most distant technology in the group and in the perpendicular to it, respectively. Then determined the radii.
Fog of war
Nothing special came up with the introduction of the fog of war. I memorized the positions of the enemy, added additional potentials, so that the air forces covered ground forces.
Visualizer
With the visualizer did not bother much. Draw only potential fields. And when analyzing games I used it in conjunction with the locale runner.
I will add a few examples to have pictures.
Here the fat green spot is my helicopters, and a potential field is built for them.
Blue color corresponds to positive potentials, red - negative, black on a red background - very large in absolute value negative.
Right-below three enemy ground groups that attract my helicopters. In the center are enemy fighters that my helicopters fear. A big black spot - my fighters, which can not be encountered.
Another example in which the actor is my IFV. Here, all enemy groups, as well as the two on the right, are positive charges.
Black spots correspond to places that are undesirable to move because of collisions with their groups. The lower left structure has no effect, since the ARRV group has already moved to capture it.
Both examples are taken from this battle - russianaicup.ru/game/view/310222 , 730 and 1800 ticks, respectively.
Code
Here is the link to my repository.
Wrote in Java. The quality of the code is what it is when I wrote, I did not expect that someone would see it. Well, I'm not a javist, Java courses took place at the same time as ai cap.
And all?
Total: a lot of crutches and stubs, no abstruse algorithms.
It turned out completely without emotion and dry, but I hope someone will find something useful for themselves.
PS I almost forgot, all happy New Year! :)
Update: Corrected formulas to be visible on a mobile phone.
Source: https://habr.com/ru/post/345956/
All Articles