Geekly Articles each Day
📜 ⬆️ ⬇️

Russian AI Cup 2017 - History 11 places

My name is Andrei Rybalka, I'm 32, I do web development, and also, from time to time I participate in various championships on writing game AI (usually in Java). And I would like to talk about my approaches to writing a bot for the Russian AI Cup 2017. I decided to describe both the history and the technical part, but for those who are interested in implementation, you can safely scroll to the appropriate subtitle.


So..


general description


On the championship, in general, have already written a lot , so I will not repeat. Specifically, this year also has an article from the winner, GreenTea .
But I still briefly describe the essence of the problem.


This year it was necessary to write a bot for Real-Time Strategy (RTS), which fought in a duel mode against the bots of other participants.


The map was a square field measuring 1024x1024. The territory was divided into sectors of size 32x32. Each sector could contain one of three types of terrain - Plain, Forest or Swamp, as well as one of three types of weather: Clear, Cloudy, Rain.
Types of terrain and types of weather, in fact, performed the same function, only the terrain - for ground troops, and the weather - for air. The function consisted in the fact that they reduced (or did not decrease) the speed of movement, the range of sight, and the probability of being seen in a given cell.


In general, in my opinion, the presence of these conditions did not justify itself - they had little effect on the game and I personally ignored them, except for checking visibility when throwing a nuclear bomb.


The game was available 5 types of troops, divided into 2 categories:



At the beginning of the game, both players were given 500 units: 100 each type. It looked like this:


Rules during the championship traditionally complicated. In the first round, they played with purely starting sets of troops, in the second - buildings appeared on the map, in the final - fog of war was added.


A little bit about the buildings. They were of two types:



Well, now the main thing. The game had a key feature, which, it must be assumed, was introduced so that people could not use ready-made solutions with RTS bots: the control in it was close to controlling a man with his troops in games of the RTS genre. namely, the troops were highlighted with a rectangle, it was possible to assign the selected units of the group and then quickly activate them, the number of actions was very limited. Thus, you could not control each unit separately. In fact, even managing five groups of 100 units, the action was still not enough for normal microcontrol.
In addition to all this, there were many more nuances, but I will not focus much on them. Who cares more, here's a page with the rules


First round


I, like many other participants, waited for the championship all year and was delighted when they announced in the announcement that there would be an RTS. But it so happened that just before the start of the championship I had a great personal misfortune, which was why I had very little time with my free time in the first weeks. In addition, after reading the rules, I was upset by the task - I didn’t like this restriction of actions.


But when I was still able to set aside time and sat down to bed, I opened the rating and saw that the entire top consisted of strategies that the group in the telegram dubbed "sandwiches": at the beginning of the game, all troops, hardcodes, are mixed so as to make one a large group in which they all alternate. This group walks around the map and destroys everything.



When the organizers saw this, they added another function to the game - a tactical nuclear strike. Any unit could drop a bomb, causing great damage, to any point in its range. But it did not really help, because it was possible to cause a nuclear strike rarely enough and he did not kill healthy units, but only significantly damaged them. And, with a competent "sandwich", during the time between two blows, BREM-s had time to completely repair all the damaged equipment.


In general, I sat down several times and tried to write a sandwich. I did it, but it annoyed me a lot. So even realizing that after the first round, when buildings appear in the game, the sandwiches will no longer be effective, I still couldn’t force myself to write it and already thought that my participation was over. But 4 days before the 1st round, I saw that there were at least 2 people who did not make sandwiches and at the same time occupied quite good places. One of them , by the way, eventually won the entire championship, and the second was in the top10.


So, on the clock 4 days before the round, and I delete everything I managed to write in the few hours I allocated for the first 2 weeks, except for the visualizer and the wrapper classes, and start from the beginning. I decided to make canapes. these are small mixed groups. And there are several of them, so this is more fun than a sandwich. It looked like this



My canapes (yellow) against the enemy sandwich. Technical details will be below.
This simple strategy gave 57th place in the first round, that was enough for passing further.


Second round


There are buildings in the game.


Shortly after the start of work on it, it became clear that you need to rely on the plants. Moreover, they must be captured quickly and tanks should be built first of all.
I also tried to build canapeshka right in the factories, but this did not give the expected result - in order to make a normal canapeshka, it had to wait until 55-66 units were produced, and that was too long. In addition, I, like almost everyone else, had to give up canapeshek, because their assembly took too much time and the enemy during that time managed to seize the factories. It was thought to collect them on the move, in parallel capturing plants, but it was too difficult to implement and it was not clear if it would work, so I refused it. In general, from the beginning of the second round to the very end, I was not bothered by the fact that I, like almost everyone else, however, practically did not use BREM for their intended purpose - for treatment. They only treated air units that could just hang on top and stay there until recovery. But with ground units it did not work out that way. for this you need to drive close, that after the first battle, or movement on the map, it became almost impossible. The formation broke, and evenly mixing two formless crowds of units, using only frame-selection and a very limited number of actions, was unrealistic.


Also, experimented with different types of division groups. I stopped at splitting the BREM-ov into two groups, helicopters - by 4 (later, in the final, I began to leave them in one group), and the others left as is. The rest of the time basically experimented with different priority rules for capturing buildings. What happened, I will describe below in the technical part.


In general, all this gave me 10th place in the second round, and I got to the final.


The final


For the finale a fog of war was added. To be honest, I didn’t spend much time specifically on working with fog, because those ideas that came to mind either seemed to be not very effective, or they didn’t fit well with the concept of potential fields (hereinafter, PP). For example, GreenTea in his article wrote about the control of those parts of the map that had not been seen for a long time. I also thought about it, but it seemed to me that this would not be of great use, because if you still do not control the map, then you should try to capture other people's buildings, and not drive the fog, and if you already control, then you are fine. But all sorts of ideas like "sitting in a small group in the fog and seizing the enemy building, as soon as there are no large groups of the enemy next to it, in my understanding, required something different from the PP. I decided to try to navigate the map as much as possible It was on them. I thought it would be more beautiful code. I was young and stupid.


In the final, I, after the first half, seemed to be in 13th place (I don’t remember exactly). But during the break, I improved the strategy well, so in the second half I went up. But there were not enough games, so I managed to get only to the 11th place. Moreover, scored as many points as the participant in the 10th place. But in this situation, the one who previously filled the strategy wins, and it was not me. Moreover, at the time of the start of the second half of the final, I had a decent lag from him - a few dozen points. So once equaled, then, apparently, my strategy was stronger, and if there was another wave of games, you probably would have gotten into the top10.


By the way, this year I had a rather classic situation for me personally, which I repeat almost every year: my strategy often won against the guys from the top 5-10, but regularly lost to the guys who were much lower than me in the table.


Sandbox final


At the end of the finals, I found that at the moment I get into the prizes of the sandbox.


The bottom line is that a week after the championship finals, the sandbox stops, and the top 6 of it, excluding the final medalists, is also awarded prizes, only more modest. The key difference from the final is that in the sandbox the games take place in all three formats mixed up - without buildings, with buildings, and with the fog of war.


In general, at that time I was on the 5th out of 6 prizes and I needed to stay there for another week, so even though I was tired by that time, I decided to improve something else, but at a more relaxed pace. In general, my strategy played well in the mode with buildings and in the mode with fog of war, but I was extremely weak in the game without buildings, because I hadn’t tested it at all since the end of the first round. But in games with buildings, I won more than 50% of games against guys with 8.9.10 places. Also, I won about half of the games against Milanin, who held on the 3rd place of the sandbox. And so, two days before the end I had a statistical crisis. Namely, it was assumed that the probability of dropping any of the three types of games was 33.3%. that is, my strategy with a probability of 66.6% was supposed to get the game in a format in which it plays well, which suits me perfectly. So, two days before the final, I had a series of games, where out of 20 consecutive games, 15 were played in a format without buildings. 12 of them I lost. The statistical probability of this is about 0.0001, but it happened to me one way or another and it hit my rating very hard. Like that:



I fell into 15th place and already thought that I would not have time to recover. But still the black line stopped, I crawled up and managed to get to the 11th place. Should I have crawled higher, or is this my objective position, at the moment I don’t know, because the sandbox has stopped at this place, and with it my participation story And therefore, I turn to the most interesting.


Technical part


All this business works on the good old potential fields (abbr., SDPP, then just PP). For those unfamiliar with the concept, it makes sense to read an article from the silver medalist last year . Also, on Habré somehow there was an article about potential fields in the RTS .


Roughly speaking, the grid is built, which is superimposed on the game world. for each cell of this grid is considered its score, which is equal to the total bonus (the utility of being in this cell) minus the total penalty (danger). Bonus and penalties are "radiated" by emitters. Unlike last year, this time, in most cases, they were linear. That is, the effect of an emitter on a point falls linearly with distance from it. Only in a couple of other places there were other options.


Each game tick performed the following actions:


Avoid nuclear strike


For this, I took all the units in the affected area and, using the SCALE action, dispersed them in different directions relative to the epicenter. In general, just like at all.


I also had a simple empirical function of assessing whether, instead of evading a nuclear strike, it makes sense to attack the unit that launched it, because if this unit died before the bomb landed, the strike was canceled.


We process actions in the queue


The gaming environment allowed to perform only one command per tick. Thus, in order to select and send a group of units to a certain point, it was necessary to perform two actions sequentially. A queue was used for this. The set of possible actions was somewhat expanded compared to the standard one:



We split enemy troops into groups


For this, the k-means algorithm was used. I chose such a radius so that if the enemy has a group of troops of an irregular shape, it would “split” into several groups, so that my troops in that case could, say, be afraid of the main part, but not be afraid of attacking the “tail”.


Ground and air units are always considered different groups, even if they were close.


Check if there is a need to perform an action ahead of time


In order not to spend all the actions at once, I proceeded from performing some kind of action once in N ticks. The rules gave 12 actions for 60 moves, i.e. on average, one in 5 moves, but since most of the teams required at least two actions - select a group and do something with it, then 10 ticks were selected as N. Later this number dropped to 7. So, at this stage, I had this feature: for each of my groups, I took the closest group of the enemy and checked if it was moving along the previous trajectory. If the actual position was different from the predicted one, I concluded that the group received a new order and initiated an early response to this order.


In general, what kind of group will be walking, I determined a weighted random. For example, groups closer to the enemy received a weight bonus. Also, aircraft received a bonus, catching up with enemy helicopters, and vice versa, my helicopters escaping from enemy aircraft, and, say, BREM in most cases received lower priority.
In the case of an early move, the group was also chosen randomly, but only from those groups for which the condition described above was fulfilled.


Once in 50 ticks the homeless collector was launched


No, not to knock out overdue loans from the homeless.


Quite often there was a situation when the enemy threw a nuclear bomb on my plant, as a result of which I dismissed the units on it in different directions to evade. In this case, units that do not belong to any group, could remain outside the plant. my HomelessCollector connected these units to the nearest group.


Check if we should run the kernel


Worked as follows:


I took a group of enemies, found my nearest more or less healthy unit. He built a separate PP for nuclear around a group of enemies, in an area where my unit can "drop" it. each cell of PP received a bonus for all enemies who got into it. Moreover, the bonus depended on their health. I tried two opposite approaches - priority on finishing off the wounded, and vice versa, priority on healthy ones (assuming that if a nuclear can do 90% damage, then there is no sense in dumping it on units from 10% of health). As a result, stopped in the middle - gave priority to units with health from 33% to 66%.


Then, having decided exactly where I want to reset it, I searched in my group for a unit that was as far as possible from this point (but no further than 90% of its scope) and was not too broken. This was done in order to make it more difficult for the enemy to kill my bomber, thereby interrupting the nuclear strike.


Also, I fined each cell for hitting my units in the affected area, in order to dump a nuclear weapon on myself only if it gives much more benefit than harm.


By the way, if less than 100 ticks remained before the enemy's nuclear recharge, I tried to keep 2 actions in reserve for evading nuclear attack.


Run the combat simulation


If the enemy formation is close enough so that it can be considered a battle, go into battle mode.


In this mode, I took all the cells of the PP around, in a small radius, and tried to simulate what would happen if I sent troops there. Moreover, I counted only 10 ticks ahead and very approximately. I tried to count for a longer time, tried to count more precisely (according to the rules of the game, with the choice of a random opponent with priorities, etc.). It worked much slower and for some reason much worse. Maybe there was some kind of bug that I never found, or maybe it was something else, but the fact remains that less accurate and less deep simulation won the fight much more often than the more accurate one.


But in general, this year the fighting was not my fad, and some strategies from the top, when meeting two equal groups of units, consistently won me.


Also, closer to the end of the championship, a crutch was hammered into this place in order to keep away from enemy BMPs in a battle between aircraft. For closer to the end, top strategies tried to escape from enemy aircraft, flying in circles over their BMP, which were very strong against aviation. And I, as I mentioned above, the ground and air groups of enemies were separated, so without this crutch, I believed that the battle was only between aircraft and ignored the BMP.


At the same time, I hammered another similar crutch in order to do the same thing myself in battle - try to fly to the point on the way to which the enemy will have to fly over my BMP, if they are near.


Combining and breaking groups


2 processes were carried out:



Regrouping


A rather stupidly implemented function that I did not have time to finish. She sought to pull down the units in the group in a dense pile. This was done in the same way as in the majority - rotation + contraction of the group. It worked so-so.


The second function was the following: since tanks were the most popular unit in the game, and they and the aircraft were not able to attack each other, it very often happened that all of the aircraft on the field died, except for a few airplanes from one side, and these airplanes were flying near tanks and drop nuclear bombs on them.


In addition, many strategies (including mine), intentionally separated from the main group of aircraft one independent unit, which tried to stay away from everyone except tanks, and which was needed just for this purpose - in order to bomb its tanks in the rear of the enemy.
So, for at least partial opposition to these planes, I “dissolved” my tanks wider if there was an enemy plane next to them and if its nuclear weapons were almost recharged, and squeezed them back as soon as nuclear weapons were used.


Actually, the potential fields


It's all pretty trivial. The cell size is 8, the grid is square, with a width slightly greater than the diameter of the field of view.


Enemy groups immediately emitted a attracting field (at long range) and repulsive (at short), so that my troops would strive to stay close, but not too close. friendly groups emitted a repulsive field so as not to collide with each other. moreover, they emitted it not only from the current position, but also along the trajectory of movement. I did not bother with the calculations whether the two groups would collide at the given speeds, so I simply did not want to cross their trajectories.


Factories attracted much more than control centers. The force of gravity depended on the belonging of the structure and on the type of troops in the selected group. For example, BREM did not go to enemy factories, but went to neutral. And the tanks rarely went to the control centers, to the extent that in some situations it happened to me that the control center, located right next to the starting position, or near one of my factories, remained untapped. This was a significant drawback, but this is my payment for PP, because it happened in situations where there were many factories on the map, and their fields were collapsing, so that the force of attraction was very high.


Also, I gave a big bonus for moving to those buildings for which this group is the nearest. This was done so that groups of forces would seek to cover as many buildings as possible. For example, in a situation where there are several buildings in one corner of the map, only one group would go there (because it is the nearest one for all of them). In addition, I gave a bonus for capturing the BREM of buildings closer to the flanks of the map, and for tanks for capturing buildings in the center.


In order to somehow compensate for the problem of overlapping PP from several buildings, because of which the group could go not directly to the building, but somewhere between several, I firstly emitted another strong PP in the center of the buildings, which had a small radius , so that it could not overlap, and secondly, from the plants, on top of the circular radiation, I also allowed a straight line. in the end, something like a cone was obtained, where the greatest bonus was obtained by cells on a straight line between the group of units and the center of the building.


To implement all the "special cases", of which there were many, I had additional emitters - POIs - Points of Interest. Here are some examples of use:



And so on.


Finally


, , .


, - - , , " 284- ". 10, , -, - 10- , , -, .
.


, , .



')

Source: https://habr.com/ru/post/345598/

More articles:


All Articles