History of participation (and almost victory) in the annual competition Russian AI Cup 2016
Hi, Habr! My name is Dichkovsky Alexey, and I want to tell you about how I spent a month and a half of my life writing a bot for a simplified version of DotA.
Every year, Mail.ru holds an online game strategy programming championship ( Russian AI Cup 2016 ). I took part in this competition in 2012 (odeTanks) and, quite a bit, in 2013 (odeTroopers). This year, pretty much fed up with web development, I decided to try to get involved again. I did not initially hope (but, of course, I really wanted) to take some kind of prize, and in general it was more of a test for me, as far as I can realize something interesting. About what came out of this, you can read under the cut.
It is no coincidence noticing the announcement of the upcoming competition on the site russianaicup.ru, I began to prepare. Having experience of participation earlier, I thought that the template for my custom visualizer would be very useful for me and save some time during the competition itself. The whole preparation as a whole consisted in writing his visualizer, who initially knew how to draw only a few basic shapes.
')
November 7, the day of the start of the RAIC 2016, the first thing I did was open the rules and read what the organizers had prepared for us this year. DotA? Oh well, it can not be ... Yes, for sure DotA! After reading the rules, there is a persistent feeling that it will be necessary to write a lot of code ... A lot. And the realization of this at the very beginning did not give much inspiration. Also this year, the start of the competition coincided with the birthday of my wife, so I had to postpone the start of development for a day, because in the next six weeks it will be difficult for me to pick out because of the PC. Perhaps it also helped me to understand a bit more precisely what my bot would be in this competition.From the very beginning I had a plan, and I stuck with it.
The first three evenings were spent on creating the project, screwing up the lines along which we will go on the attack, poor choice of one of the three lines (at the start of the game - like the quick start guy - the basic strategy provided by the organizers, after death - where there are more enemies and fewer ones ), as well as screwing the visualizer, the “skeleton” of which was written a week before RAIC. Then I had to learn to walk somehow ... It was terribly lazy to do a lot of geometry, but I still wanted to crawl into the “gap” between minions, magicians and trees ... Since no other options came to mind, then I decided to make a local “grid” on which you can walk, and at the same time to put in it a calculation of the danger and usefulness of being at one point or another.
The scheme of the game card. The lines that should attack the enemy base (top / bottom / middle lane) are separated from each other by a forest.
Friday and the weekend were spent thinking about whether it was worth it or not to get involved in this business ... But still, on Sunday evening something with the movement was realized. The first grid version was in 2 steps of 401 * 301 points (600 distance forward along the battle line, 300 to the side and 200 back). At each point of this grid, scores were calculated — the “utility of finding” minus the “danger of being” in it. In the final version, the grid cell consisted of many fields and took into account the danger from minions, the danger from magicians, the danger from buildings, the utility of being in a zone from which I can attack enemies (were divided into two different variables for melee and ranged combat, in each they took into account only the best value), the usefulness of being in the zone around crippled enemies (to gain experience for killing them) and the additional two variables, otherDanger and otherBonus, for realizingcrutches of cases like collecting bonuses, creating a dangerous zone in places the appearance of enemy creeps, the prevention of unnecessary care in the forest, clogging cards in the corner, etc. Each move did not want to recreate such a matrix, so when updating its coordinates (it moved along with the magician), all these values ​​were reset.
The original version of the matrix. The distance to the front edge of the matrix is ​​600 “pixels”. Right and left - 300, back - 200. The distance between the points is 2. The matrix turned out to be too big. The number of points in the matrix itself is 401 * 301. It is always directed along the battle line, regardless of the orientation of the mage.
Launches to the local runner showed that something was too slow in my approach ... Under the terms of the competition, 10 ms were allocated for each tick of the strategy, and according to my measurements on the local machine it was significantly more. Filtered the world to the necessary minimum: live units and towers at a distance of 600 to my local grid, trees - so that the calculation counts them as obstacles, but adds as little as possible “extra” trees. Additionally increased the grid step to 3, and got the performance more similar to the one you need. Optimizations were still needed, but for the first time I decided thatit would do enough. Still, almost a week has passed, and I wanted to throw out something of my own on the battlefield. The point to which he moved was chosen as simply the best among the points on the matrix by the score value. I arranged the search for a priority queue, where the weight of the rib was not the distance (although as a second factor it was taken into account), but the danger of getting a slap from the enemy team, while not taking into account the usefulness of being in it. With this approach, such a path can be found, which, although it will be short, if the bot could walk only along the points of the matrix, it would be broken, which greatly hinders rapid movement. I solved this problem by binary search along the entire path, where I checked the ability to go from my point to the desired one directly (before launching the search, the reachability of the end point of the path was checked). So if there were no obstacles in the way, the bot just went straight to the destination point.
Well, we can walk, a little afraid of the enemy magicians and minions are able to ... But what about the battle? Hmm ... Created a list of targets, filtered them so that the trees did not interfere with shooting (forgetting that the trees were filtered so as to count them as an obstacle on the danger grid, which is clearly not enough if the target is right behind the tree), set the priorities depending on what% hp goals remained. The priority of magicians and towers for the first time set 5 and 6 times higher than that of minions. Then I teach the bot to turn for a shot - if we can shoot from the current position and the number of ticks before recharging is already somewhere on the verge of how much we can “stick” on the target - we turn to the goal, otherwise turn in the direction of movement.
Having worked with the locale runner, I sadly understood that the option of the path is not very good ... While exiting the “dangerous” zones, we immediately try to run to the optimum point, but after all, you can simply run away from the minion’s strike (the speed of the minions’s movement is equal to and sideways), if you run strictly from him. We learn to run away from enemy minions - now we are trying to run in a straight line not to the end point, but to such an intermediate point on the way, the danger of which is significantly less dangerous at the current point of my magician. I changed the search for the point to which we are moving - now it is not chosen immediately, but as we search for paths across the whole matrix, taking into account, apart from the score, the target point, the danger we will undergo on the way to it. At this stage, it was a trite sum of all the dangers * 0.02 (all coefficients were selected from the very beginning to the end, rarely changed).
After the implementation of the new path selection and more detailed testing in the locale runner, we aresad and we are thinking of leaving a bad idea (RAIC), I noticed that the code does not fit again in the time frame. Turning on the profiler of the java code, I saw that after all, at least the search for the path and eats a lot, but the main load is the calculation of the score for each point of the matrix. After all, for each point of the matrix, there is a check on all units with the calculation from them of the distance to this point, even if this distance is much larger than the one on which this unit can affect my matrix ... Hmm. He carried out the counting of hazards in cycles separate from the grid coordinate updates, created a structure for applying the influence of the unit on the score points of the grid. Before counting the distance from the unit to each point of the next row of the matrix, I began to check the distance from the unit to the segment, the ends of which are the ends of this line. Now, if a unit is guaranteed not to affect the score points in this row of the hazard matrix - just skip the entire line. And this optimization has already allowed locally quite tolerable invest in limits. It all seemed terribly crooked, but somehow it worked ...
And still, perhaps, the bot is not ready for the first battles. In the melee, the magician does not know how to beat amatch with a staff, trees are an insurmountable obstacle, enemy magicians and minions constantly drove me out of the line into the forest ... I add a check that there is someone or something nearby that you can knock and if There is no need to turn now for a shot - let's knock it with a staff. I correct the problem of not wanting to shoot trees at all (although the priority of the shot was set to 0, but if there are no other goals). I add a penalty for moving away from the center of the line ... Significantly reduced the matrix in which I count the glasses (up to a distance of 351 forward and 150 back and sides. The size did not seem to affect the behavior much) and the first version went into battle!
A pitiful sight, a heartbreaking sight ... The magician becomes stupid when an enemy magician approaches (because it becomes too dangerous throughout the search matrix), his minions are clamped, he gets stuck trying to run away from the edge of the map, runs into the corner of the map, from where you can only run away base through 1.2k ticks (time for rebirth) ... I correct all these shortcomings by adding additional penalties for being at points near the edge of the map, adding the edge of the map as an obstacle, removing stunned if it is very dangerous everywhere (the sum of the dangers is more than my magician's). All this helps a little, and now, although the effect is still not very, somehow you can live. In the meantime, the tops are already running for bonuses.
How to teach the bot
Well, I also need to learn to run for bonuses ... They give quite a lot of points for them. Only now it is not clear how. First I decided to learn how to use the speed to the maximum ... At the same time, the groundwork for the future is to learn to take into account all auras and passive skills, HASTENED status (acceleration) - and now, if the minions suddenly push me for a bonus, I will run faster! Then, watching the battles with other rivals, I realized that I constantly get under the enemy towers ... And one shot is more than a third of the hp mage. Added their position in the world and remembered the time until the next shot. At the same time I made it so that during the reloading of the towers my magician came a little closer. Still badly we run away from minions, since we run strictly along our own grid, and its direction rarely coincides with the direction in which it would be necessary to run away from the minion. As a result, it turns out that my bot runs away from the minion “slightly obliquely”, and the latter, heading strictly at me, is constantly reducing the gap. Solution - added locally consideration of several directions of one step approximately in the direction in which my bot believes that it is worth moving (direction to the nearest points on the way + angle, which can be considered further) ... Here are the structures for calculating points at the point useful. We choose a point from this set first of all with a greater utility of finding it in it for ourselves, and secondly closer to the desired direction of movement ... Now you can normally bypass the dangerous zones around the beautiful circumference, rather than twitch according to the principle "step forward - step aside" , and now you can run away from the minions much more efficiently in a straight line. We will also add danger to the matrix from the zone of appearance of enemy minions for a certain amount of time before they appear, so that you can get out of there in time and not be surrounded by them ...
(Clickable, inside gif-ka)
Screenshot from the visualizer. A green circle slightly from the edge of the center of the decorated rectangle (around which there is no “white” zone into which it is impossible to step) is a magician who is governed by a strategy. Red - enemies, green - their own. The blue uneven line from the center of my mage is the way we are going now. Black stripes from the center of the magician - what angle is considered when trying to find the best step. Pink - the direction in which at the moment most likely to go. Red is the selected direction for the next step.
When I woke up on Saturday morning, I was determined to come up with something with bonuses, but I found out that my bot reached about the top 100, and there they suddenly started shooting not at the center, but at the edge of my magician, almost in every rating battle, cruelly and confidently beating him until he could answer nothing. However, I didn’t want to do the same, because even though the tops do not know how to dodge, they will be soon, but I want to go up there ... The plan came to mind is simple and difficult at the same time - and I will not do the same, I will try to just dodge, good for the 12 ticks that flies projectile, you can quite well go away ... The speed of a magician is not enough if they shoot at the center, but it can help with such a problem.
First you need to memorize the tick of the appearance of all the shells, so that later you can calculate where each of them can reach the maximum. In the finals as a whole, it will be possible to ignore all the shots from the allies, but in the first two rounds you should not ignore the shots of not very allied magicians. Since competition on points also works within the same team, “allied” magicians also often like to kill their own (ardent greetings mortido ). Then we check if the projectile intersects with me if I stand still (the distance to the projectile flight segment is less than the sum of the radii of my magician and the projectile, to which the distance that I can step additionally, in order not to accidentally step under the projectile) is added . If at least one projectile can hit me - we are trying to dodge. First of all, I’ll calculate how much the bot will “catch” if it just stands still (an option when it’s just afraid to step under the projectile). I take this basic damage for the initial damage and try to move away in any direction with speed, as if I was going sideways or backwards. It also takes into account the total number of points at the points through which we will pass during the evasion (if we stand still, we add the same point to the number of ticks that will be needed). If at this stage it was not possible to dodge the projectile - I try to run in all directions at the maximum possible speed (turning in the chosen direction). When trying to move away or run away from the projectile, I also check that I do not run into an obstacle, assuming that all the minions move straightforwardly all the time, and magicians, buildings and trees stand still. If on the current tick I have rested against an obstacle, on the next tick I will still try to repeat the step. Suddenly, someone will leave ... Did you manage to dodge the projectile? Block the search path, moving in the direction where the damage would be smaller and be safer. And if, at the same time, a turn in a certain direction helped to escape, we block the control of the turn of the bot on this tick and turn it in the direction we are running (turns mine last, after calculating the shot).
Along with writing the dodge algorithm, it came to the realization that shooting at the center is not the best option ... It is better to shoot a point a little in front of the center of the magician, then you have to run away longer and equally long and forward and backward. Decided to leave this knowledge for the future.
So, step by step, writing a heap of improvements (including another improvement in the method of determining when it is worth cutting these trees I hated with the bot), I still sat down to write exactly the hike for bonuses. By that time, a real fight started in the top for them and it was not often possible to take any bonus calmly and with impunity. I began to memorize where the last time the enemy magicians were seen, so as not to go in the direction of the bonus, in case they are more likely to be able to pick it up before me. On ticks multiples of 2500, the probability of finding bonuses in their places was set to 1. If any enemy magician out of sight could reach the bonus in the time it was not visible, then the probability of finding the bonus at a point gradually decreased. And the closer the magician was to the bonus one last time before he was seen - the more likely the bonus fell that the bonus was still in its place. Also began to memorize the position of enemy minions, so that you can return to a point on the line of their movement for the distance of your shot. The fourth “line” was added in the code - it just set the direction in which I want to go. Also, when activating this line, in the hazard matrix the points closer to the target, added an extra bonus. Now the bot was moving in the wrong direction and was not stuck too much to finish off enemy minions, magicians or towers.
(Clickable, inside gif-ka)
The switch to the fourth "pseudo" line. She set the direction of the matrix strictly to the point to which it was necessary to go. In this case, the magician went a little advance to the nearest bonus through the forest.
Along with writing campaigns for bonuses, I added the ability to change the line of attack except at the time of death (the initial implementation did not imply such an opportunity in other situations). Since now I have memorized data on the location of all units that were in sight, then the bot began to better understand which line our defense was weaker than the attackers (the temporary exit of enemy magicians and minions from view was no longer affected by this). In general, from this point until the end of round 2, the line choice looked like “we go where there are more enemies, and our magicians are smaller”.
As a final touch, but still a bit detached, I still rewrote the algorithm for finding the best position and the path to it for the third time. In his last and final iteration, the best point was considered the one where the sum of the average score on the way to it and the score at the point itself was maximum. To do this, again, again, the priority queue looked for a path through the matrix, in which the score value for this search was reduced by its maximum value (to avoid positive “loops”). After such a change in the walking of the bot, a serious drawback was revealed - he began to love to run around enemy minions and buildings, often stepping behind them, than he cut off the path to retreat from enemy magicians. I divided the danger fields from minions into 2 parts: now, in addition to the attack zone, an additional zone in which the minion will attack me (at least from the view range and the distance to the nearest allied unit to me) was allocated. By this I managed to get rid of this problem, and the path chosen by my bot now began to look significantly more logical than before.
(Clickable, inside gif-ka)
Screenshot from the visualizer. In this case, the dodge algorithm has blocked control of the mage's rotation and turns itself to the side of the run (status RUN_FROM_PROJECTILE). You can also see that the bot remembers the last position of one of the enemy magicians. In addition, the approximate maximum distance that this magician could have escaped is drawn.
From this point until the very first round, no more special improvements have been made. Corrected bugs and serious shortcomings in the coefficients. Gradually, the rating of my bot grew until it settled in the top ten. At this stage, it could be noted that the% of victories of my bot is very small compared to other participants from the sandbox top. Apparently a cautious attitude to the bonuses did not allow him to score the maximum number of points, but the wizard’s survival rate was at a more or less acceptable level, due to which he consistently scored his points.
At the end of the first round, I took 8th place in the ranking, which was a pleasant surprise for me. The rules for round 2 differed from the rules for round 1 by the possibility of learning and applying skills. On the last day before launching the games in the sandbox according to the rules of Round 2, the possibility of shooting with ice arrows was bolted. On the first evening, against the background of the fact that few strategies knew how to use skills and dodge, it looked very impressive. However ... After just 1 day, it became obvious that against the bots that chose the fireball as the first ulta, it turns out bad to fight. Attempts to correct this with coefficients and adding accounting for the blast radius from the fireball to the dodge algorithm did not lead to anything. You can not defeat the enemy - lead him. The next step was writing fireball shooting.In general, nothing better than busting a shot around minions standing in place (so as to touch the latter with the edge of a fireball and the edge of an explosion), buildings and all enemy magicians (assuming that the latter are always optimally trying to escape from the explosion) did not quickly come up as temporary option was made just such a bust. Only those variants of the shot that I can do with the current casting radius were taken into account. But ... There is nothing more permanent than temporary. Until the very end, the brute force algorithm remained exactly the same, with the exception of specifying whether the enemy magician could escape from my fireball or not.that the latter are always optimally trying to escape from the explosion) was not quickly invented, and just such a search was made as a temporary option. Only those variants of the shot that I can do with the current casting radius were taken into account. But ... There is nothing more permanent than temporary. Until the very end, the brute force algorithm remained exactly the same, with the exception of specifying whether the enemy magician could escape from my fireball or not.that the latter are always optimally trying to escape from the explosion) was not quickly invented, and just such a search was made as a temporary option. Only those variants of the shot that I can do with the current casting radius were taken into account. But ... There is nothing more permanent than temporary. Until the very end, the brute force algorithm remained exactly the same, with the exception of specifying whether the enemy magician could escape from my fireball or not.
, , . WizardsInfo, , , . , , . , , . 30% , . , - , .
, , , 180 (.. , ), , (, ). ( , , , ). score . — , . , , (, , , ? ). . — , , ( ). , . , .
-, , , , , “ ”, , - , , . . , , .
After correcting the problem in the dodge algorithm, the rating began to grow again, and I stopped being afraid not to qualify for the final. However, in the time it takes to prepare for round 2, I would like to learn how to use all the ultas so that you can use them in the final. But first ... My magician is still very passively standing on the line and not really making attempts to attack the enemy magicians, who keep their distance. And I would like to fix it. Last week, the targeting system was rewritten, and nowthis crutch could be more or less easily inserted into it. . , . , , , .
… , , ( 2), … , , , , , . , 0:00:01, .. . — 2 , . 2 3, (.. , , ), 1 2 . , .. , 1, .. , . .
( ), (, ). , . 2 ( , .. , . , ).
, , . , — 2 , , 2, .. , . …. , , , , « »… , . — , . , ??? ,With the help of scrap and some mothers, the sources that are not in active development were mined by minifiers, the visualizers for the first two rounds were thrown out and the required megabyte was reached. Subsequently, the system expanded the possibility of sending source codes to 2MB and this item was reflected in the rules, but that night, in order to send a trial version of the strategy to the final (all their magicians were sent to the center line), they had to spend a lot of time. As a result, I sent an unverified version and went to bed. In this version, all my magicians had to learn different branches of skills and attack through one central line (the so-called “push across the midsection”). And in the morning I found that such tactics quite well manifest themselves, even taking into account the fact that at 2 am I filled in the version with a bug and my magicians did not want to learn any skills at all.
( ), . ( ), . 1 2 , .
, “ ”, , . — , , . , - , “” . — 600 , , .
(, gif-)
2*5. Since , «» — , “” . “”. .
, “ ”, tyamgin , 4 , . , 4 , . , , . , , .
“” — , - , ( 350 ). — (~900 ) , ( , ). , , , .. . — ,
— , , , . , , . , , — , “ ”, ( , , .. ).
2*5 , , - . - .
— . , . , , , . ( Antmsu ), , . , , . , , , . NighTurs , , … , .
Git . 4.30 PM, , .
, - , . , . Antmsu NighTurs , , .
( ) ( core2duo ), 6 6, 6 NighTurs, , , 2. , , , . , , .
russian ai cup 2016. P — , G — . Russian Ai Cup — Commandos. .
After examining the interim results of the final after the first part, everyone, including me, agreed that the participants from the top 2 would sort things out “between themselves”, and I would most likely retain the third position. To some extent, this comforted me, because the results showed that at least third place is already relatively difficult to lose, but ...Ipad? Why do I need an iPad? I want a macbook! At least Air ... In general, having spent a relatively depressed state all Friday, I decided that it was impossible to lose the last day before the second part of the final. And I definitely want to go higher. However, several hours were spent in thought, how to get the desired result. Only 12 and 13 games were lost by the current deuce of the final leaders, and I lagged behind them by as many as 12 and 11 games, respectively. Even if I start to win them with a 100% chance, which seemed unlikely, this is still not enough to catch up with them and even more overtake them. And I decided to review the losses with all the players and fix it. I needed almost a 100% result. Oh well, this is impossible, maybe better for corporate go.
The first, of course, attracted the attention of the core2duo strategy. Managing the magicians at the micro level, he was quite weak and it was possible with almost 100% guarantee of victory to go on him in the attack in the forehead. This, in my opinion, is an ideal tactic in this case, but still I wanted something more universal in case of the appearance of clones of this strategy. The solution was simple - if there are too many enemy magicians on the lines other than the central one, I greatly increased the bonus for finding my magicians at points from which they can do damage. With this approach, my strategy almost always won when playing with core2duo, but while waiting for new pitfalls from the latter, for added safety, added a check: if (“core2duo”. Equals (playerName)) - we go to direct attack on the nearest enemy mage, no matter where . In addition to about 100% probability of winning with current strategies, this also brought additional confidence that he would not be able to do anything else to me.
The second item was my only loss to the GreenTea member strategy. In this game, my magicians very stubbornly did not want to go to the final assault with an equal number, but much, much more battered opponent. When examining this game more closely with the help of debug, one more bug was found - when searching for the “cluster” of my magicians to create an attacking group, if at least one magician was too far away, the group could not be found due to a problem in updating the average the arithmetic positions of the cluster “magicians” while excluding the most distant one. Having fixed this bug and added logic to force an attack on an enemy base in the event that the defending opponent has a much smaller number of hit points, I went on to consider the following problems.
Then came the losses to the participants TonyK and tyamgin. Testing with the latest TonyK versions at that time didn’t reveal how many defeats, and I thought that something was broken in his strategies. Just in case, the same slightly more aggressive tactics, which were played in the first part of the final only with Antmsu and NighTurs, also checked on it. Since visible problems have arisen - left everything as is. The same minor change was applied in fights with tyamgin. Visually, it gave a slight positive effect, and according to the results of the checks it was also left as is.
The remaining 4 participants, with whom I had defeats in the first part of the final, stood out from the general heap with the fact that all of them, like me, with all five magicians were walking along the center line. It was the lion's part of my defeats (of course, if we forget about the core2duo strategy), and it was very unlikely to solve all this by selecting coefficients and minor edits in the micro control of magicians, as I tried to do it on Friday against Antmsu. Inspired by the experience of core2duo, I decided to try to do something special for them. It was easy enough to see that 3 of 4 of these strategies at the time of the first part of the final (and before the second part of the final, all 4, which helped me quite well), without stopping, attacked the first tower of the enemy right up to melee. The plan was simple - but what if you try to split the whole group of attackers into two parts? In addition, when they run up to my tower, they become vulnerable to entering from the flank ... According to the plan, not all of them will have the opportunity to retreat in one direction, and the fastest possible attack in an attempt to squeeze a part of the opponent’s magicians to the forest can, in theory, bring desired result.
Plan of attack from the flank. The red arrows indicate my planned movements, the blue arrows indicate the expected behavior of the opponent. Clickable
To test this theory, I initially modified my version so that it ignored the danger from the first tower and went on it to attack. Then my changed strategy was launched using local-runner against my own version, which already knew how to make a call from the flank for this case. The results were very convincing - even with losses in the form of a tower, and sometimes also 1 mage, but a reckless attack from the flank most often resulted in a tangible advantage at the beginning of the game, and this turned out to be enough for the rest of the battle to take place almost steadily favor of a fresh update. Encouraged by local success, I decided to test how this idea would work in combat conditions on mortido and ud1, since according to my assumptions, they will not waste time on serious attempts to write something that would break my approach. Testing in combat conditions was also successfully passed, and I replaced this strategy with the previous option, so asnot to shine, to increase the likelihood of surprise for the participants of the top 2. Further grinding of trifles took place with the help of local-runner, and by about 4 o'clock in the night the implementation of the new attack was completed.
To check on the top 2 participants, I uploaded the updated version at 11.39, i.e. 21 minutes before the start of the second part of the final. Testing for the top 2 was successful (1 loss of 4 games, but as it turned out, the chance of my victory was even higher), and in this form the strategy remained until the end.
After launching the games, I was already in a state of squeezed lemon and went to take a nap. After a short rest, two news awaited me, one pleasant and one not so much. Pleasant - my strategy was really almost unbeaten (only one defeat in two waves, which is 118 games). Unpleasant - testing was noticeably slower than on the first day, and it was rather doubtful that there would be as many waves as the previous one ... And according to the results of the first waves, it seemed that it was almost impossible to overtake one of the first two participants. Nevertheless, even for 5 waves, with a great deal of luck, my strategy still managed to take the second line in the final result.
The results of the best participants of the second part of the final russian ai cup 2016. Clickable.
The final results of the best participants of the final russian ai cup 2016. Clickable.
Despite falling out of life for a month and a half, I definitely do not regret that I did not abandon the idea at the very beginning. The task turned out to be very voluminous and, as it was being implemented, it was constantly necessary to choose which features of the rules and in which cases to take into account, and which ones should be ignored. It was practically impossible to take into account all the nuances in the final implementation, which, perhaps, was an additional interesting and difficult point in the competition, although the final algorithm left a feeling of incompleteness. I would like to express gratitude to the organizers of the RAIC for holding such a large-scale and fascinating competition, and, practically by tradition, I would like to give special thanks to Roman Udovichenko ( Romka ) for creating a general chat, where many participants found useful information for themselves, very informative tables with intermediate results (can be seen in the screenshots above), which helped me in preparing for the last part of the final, and for the initial reading of this post.
UPD. Partially restored repository . I had to cut a couple of first commits. I also did not bring back all the dead brunches to life.
Every year, Mail.ru holds an online game strategy programming championship ( Russian AI Cup 2016 ). I took part in this competition in 2012 (odeTanks) and, quite a bit, in 2013 (odeTroopers). This year, pretty much fed up with web development, I decided to try to get involved again. I did not initially hope (but, of course, I really wanted) to take some kind of prize, and in general it was more of a test for me, as far as I can realize something interesting. About what came out of this, you can read under the cut.
It is no coincidence noticing the announcement of the upcoming competition on the site russianaicup.ru, I began to prepare. Having experience of participation earlier, I thought that the template for my custom visualizer would be very useful for me and save some time during the competition itself. The whole preparation as a whole consisted in writing his visualizer, who initially knew how to draw only a few basic shapes.
')
November 7, the day of the start of the RAIC 2016, the first thing I did was open the rules and read what the organizers had prepared for us this year. DotA? Oh well, it can not be ... Yes, for sure DotA! After reading the rules, there is a persistent feeling that it will be necessary to write a lot of code ... A lot. And the realization of this at the very beginning did not give much inspiration. Also this year, the start of the competition coincided with the birthday of my wife, so I had to postpone the start of development for a day, because in the next six weeks it will be difficult for me to pick out because of the PC. Perhaps it also helped me to understand a bit more precisely what my bot would be in this competition.
First week, or “what am I getting involved in ...?”
The first three evenings were spent on creating the project, screwing up the lines along which we will go on the attack, poor choice of one of the three lines (at the start of the game - like the quick start guy - the basic strategy provided by the organizers, after death - where there are more enemies and fewer ones ), as well as screwing the visualizer, the “skeleton” of which was written a week before RAIC. Then I had to learn to walk somehow ... It was terribly lazy to do a lot of geometry, but I still wanted to crawl into the “gap” between minions, magicians and trees ... Since no other options came to mind, then I decided to make a local “grid” on which you can walk, and at the same time to put in it a calculation of the danger and usefulness of being at one point or another.
The scheme of the game card. The lines that should attack the enemy base (top / bottom / middle lane) are separated from each other by a forest.
Friday and the weekend were spent thinking about whether it was worth it or not to get involved in this business ... But still, on Sunday evening something with the movement was realized. The first grid version was in 2 steps of 401 * 301 points (600 distance forward along the battle line, 300 to the side and 200 back). At each point of this grid, scores were calculated — the “utility of finding” minus the “danger of being” in it. In the final version, the grid cell consisted of many fields and took into account the danger from minions, the danger from magicians, the danger from buildings, the utility of being in a zone from which I can attack enemies (were divided into two different variables for melee and ranged combat, in each they took into account only the best value), the usefulness of being in the zone around crippled enemies (to gain experience for killing them) and the additional two variables, otherDanger and otherBonus, for realizing
The original version of the matrix. The distance to the front edge of the matrix is ​​600 “pixels”. Right and left - 300, back - 200. The distance between the points is 2. The matrix turned out to be too big. The number of points in the matrix itself is 401 * 301. It is always directed along the battle line, regardless of the orientation of the mage.
Launches to the local runner showed that something was too slow in my approach ... Under the terms of the competition, 10 ms were allocated for each tick of the strategy, and according to my measurements on the local machine it was significantly more. Filtered the world to the necessary minimum: live units and towers at a distance of 600 to my local grid, trees - so that the calculation counts them as obstacles, but adds as little as possible “extra” trees. Additionally increased the grid step to 3, and got the performance more similar to the one you need. Optimizations were still needed, but for the first time I decided that
Well, we can walk, a little afraid of the enemy magicians and minions are able to ... But what about the battle? Hmm ... Created a list of targets, filtered them so that the trees did not interfere with shooting (forgetting that the trees were filtered so as to count them as an obstacle on the danger grid, which is clearly not enough if the target is right behind the tree), set the priorities depending on what% hp goals remained. The priority of magicians and towers for the first time set 5 and 6 times higher than that of minions. Then I teach the bot to turn for a shot - if we can shoot from the current position and the number of ticks before recharging is already somewhere on the verge of how much we can “stick” on the target - we turn to the goal, otherwise turn in the direction of movement.
Testing with local runner.
Having worked with the locale runner, I sadly understood that the option of the path is not very good ... While exiting the “dangerous” zones, we immediately try to run to the optimum point, but after all, you can simply run away from the minion’s strike (the speed of the minions’s movement is equal to and sideways), if you run strictly from him. We learn to run away from enemy minions - now we are trying to run in a straight line not to the end point, but to such an intermediate point on the way, the danger of which is significantly less dangerous at the current point of my magician. I changed the search for the point to which we are moving - now it is not chosen immediately, but as we search for paths across the whole matrix, taking into account, apart from the score, the target point, the danger we will undergo on the way to it. At this stage, it was a trite sum of all the dangers * 0.02 (all coefficients were selected from the very beginning to the end, rarely changed).
After the implementation of the new path selection and more detailed testing in the locale runner, we are
And still, perhaps, the bot is not ready for the first battles. In the melee, the magician does not know how to beat a
A pitiful sight, a heartbreaking sight ... The magician becomes stupid when an enemy magician approaches (because it becomes too dangerous throughout the search matrix), his minions are clamped, he gets stuck trying to run away from the edge of the map, runs into the corner of the map, from where you can only run away base through 1.2k ticks (time for rebirth) ... I correct all these shortcomings by adding additional penalties for being at points near the edge of the map, adding the edge of the map as an obstacle, removing stunned if it is very dangerous everywhere (the sum of the dangers is more than my magician's). All this helps a little, and now, although the effect is still not very, somehow you can live. In the meantime, the tops are already running for bonuses.
How to teach the bot to go for bonuses to do anything, but not what is necessary.
Well, I also need to learn to run for bonuses ... They give quite a lot of points for them. Only now it is not clear how. First I decided to learn how to use the speed to the maximum ... At the same time, the groundwork for the future is to learn to take into account all auras and passive skills, HASTENED status (acceleration) - and now, if the minions suddenly push me for a bonus, I will run faster! Then, watching the battles with other rivals, I realized that I constantly get under the enemy towers ... And one shot is more than a third of the hp mage. Added their position in the world and remembered the time until the next shot. At the same time I made it so that during the reloading of the towers my magician came a little closer. Still badly we run away from minions, since we run strictly along our own grid, and its direction rarely coincides with the direction in which it would be necessary to run away from the minion. As a result, it turns out that my bot runs away from the minion “slightly obliquely”, and the latter, heading strictly at me, is constantly reducing the gap. Solution - added locally consideration of several directions of one step approximately in the direction in which my bot believes that it is worth moving (direction to the nearest points on the way + angle, which can be considered further) ... Here are the structures for calculating points at the point useful. We choose a point from this set first of all with a greater utility of finding it in it for ourselves, and secondly closer to the desired direction of movement ... Now you can normally bypass the dangerous zones around the beautiful circumference, rather than twitch according to the principle "step forward - step aside" , and now you can run away from the minions much more efficiently in a straight line. We will also add danger to the matrix from the zone of appearance of enemy minions for a certain amount of time before they appear, so that you can get out of there in time and not be surrounded by them ...
(Clickable, inside gif-ka)
Screenshot from the visualizer. A green circle slightly from the edge of the center of the decorated rectangle (around which there is no “white” zone into which it is impossible to step) is a magician who is governed by a strategy. Red - enemies, green - their own. The blue uneven line from the center of my mage is the way we are going now. Black stripes from the center of the magician - what angle is considered when trying to find the best step. Pink - the direction in which at the moment most likely to go. Red is the selected direction for the next step.
Neo mod.
When I woke up on Saturday morning, I was determined to come up with something with bonuses, but I found out that my bot reached about the top 100, and there they suddenly started shooting not at the center, but at the edge of my magician, almost in every rating battle, cruelly and confidently beating him until he could answer nothing. However, I didn’t want to do the same, because even though the tops do not know how to dodge, they will be soon, but I want to go up there ... The plan came to mind is simple and difficult at the same time - and I will not do the same, I will try to just dodge, good for the 12 ticks that flies projectile, you can quite well go away ... The speed of a magician is not enough if they shoot at the center, but it can help with such a problem.
First you need to memorize the tick of the appearance of all the shells, so that later you can calculate where each of them can reach the maximum. In the finals as a whole, it will be possible to ignore all the shots from the allies, but in the first two rounds you should not ignore the shots of not very allied magicians. Since competition on points also works within the same team, “allied” magicians also often like to kill their own (ardent greetings mortido ). Then we check if the projectile intersects with me if I stand still (the distance to the projectile flight segment is less than the sum of the radii of my magician and the projectile, to which the distance that I can step additionally, in order not to accidentally step under the projectile) is added . If at least one projectile can hit me - we are trying to dodge. First of all, I’ll calculate how much the bot will “catch” if it just stands still (an option when it’s just afraid to step under the projectile). I take this basic damage for the initial damage and try to move away in any direction with speed, as if I was going sideways or backwards. It also takes into account the total number of points at the points through which we will pass during the evasion (if we stand still, we add the same point to the number of ticks that will be needed). If at this stage it was not possible to dodge the projectile - I try to run in all directions at the maximum possible speed (turning in the chosen direction). When trying to move away or run away from the projectile, I also check that I do not run into an obstacle, assuming that all the minions move straightforwardly all the time, and magicians, buildings and trees stand still. If on the current tick I have rested against an obstacle, on the next tick I will still try to repeat the step. Suddenly, someone will leave ... Did you manage to dodge the projectile? Block the search path, moving in the direction where the damage would be smaller and be safer. And if, at the same time, a turn in a certain direction helped to escape, we block the control of the turn of the bot on this tick and turn it in the direction we are running (turns mine last, after calculating the shot).
Along with writing the dodge algorithm, it came to the realization that shooting at the center is not the best option ... It is better to shoot a point a little in front of the center of the magician, then you have to run away longer and equally long and forward and backward. Decided to leave this knowledge for the future.
And yet - bonuses.
So, step by step, writing a heap of improvements (including another improvement in the method of determining when it is worth cutting these trees I hated with the bot), I still sat down to write exactly the hike for bonuses. By that time, a real fight started in the top for them and it was not often possible to take any bonus calmly and with impunity. I began to memorize where the last time the enemy magicians were seen, so as not to go in the direction of the bonus, in case they are more likely to be able to pick it up before me. On ticks multiples of 2500, the probability of finding bonuses in their places was set to 1. If any enemy magician out of sight could reach the bonus in the time it was not visible, then the probability of finding the bonus at a point gradually decreased. And the closer the magician was to the bonus one last time before he was seen - the more likely the bonus fell that the bonus was still in its place. Also began to memorize the position of enemy minions, so that you can return to a point on the line of their movement for the distance of your shot. The fourth “line” was added in the code - it just set the direction in which I want to go. Also, when activating this line, in the hazard matrix the points closer to the target, added an extra bonus. Now the bot was moving in the wrong direction and was not stuck too much to finish off enemy minions, magicians or towers.
(Clickable, inside gif-ka)
The switch to the fourth "pseudo" line. She set the direction of the matrix strictly to the point to which it was necessary to go. In this case, the magician went a little advance to the nearest bonus through the forest.
Along with writing campaigns for bonuses, I added the ability to change the line of attack except at the time of death (the initial implementation did not imply such an opportunity in other situations). Since now I have memorized data on the location of all units that were in sight, then the bot began to better understand which line our defense was weaker than the attackers (the temporary exit of enemy magicians and minions from view was no longer affected by this). In general, from this point until the end of round 2, the line choice looked like “we go where there are more enemies, and our magicians are smaller”.
As a final touch, but still a bit detached, I still rewrote the algorithm for finding the best position and the path to it for the third time. In his last and final iteration, the best point was considered the one where the sum of the average score on the way to it and the score at the point itself was maximum. To do this, again, again, the priority queue looked for a path through the matrix, in which the score value for this search was reduced by its maximum value (to avoid positive “loops”). After such a change in the walking of the bot, a serious drawback was revealed - he began to love to run around enemy minions and buildings, often stepping behind them, than he cut off the path to retreat from enemy magicians. I divided the danger fields from minions into 2 parts: now, in addition to the attack zone, an additional zone in which the minion will attack me (at least from the view range and the distance to the nearest allied unit to me) was allocated. By this I managed to get rid of this problem, and the path chosen by my bot now began to look significantly more logical than before.
(Clickable, inside gif-ka)
Screenshot from the visualizer. In this case, the dodge algorithm has blocked control of the mage's rotation and turns itself to the side of the run (status RUN_FROM_PROJECTILE). You can also see that the bot remembers the last position of one of the enemy magicians. In addition, the approximate maximum distance that this magician could have escaped is drawn.
From this point until the very first round, no more special improvements have been made. Corrected bugs and serious shortcomings in the coefficients. Gradually, the rating of my bot grew until it settled in the top ten. At this stage, it could be noted that the% of victories of my bot is very small compared to other participants from the sandbox top. Apparently a cautious attitude to the bonuses did not allow him to score the maximum number of points, but the wizard’s survival rate was at a more or less acceptable level, due to which he consistently scored his points.
After the first round.
At the end of the first round, I took 8th place in the ranking, which was a pleasant surprise for me. The rules for round 2 differed from the rules for round 1 by the possibility of learning and applying skills. On the last day before launching the games in the sandbox according to the rules of Round 2, the possibility of shooting with ice arrows was bolted. On the first evening, against the background of the fact that few strategies knew how to use skills and dodge, it looked very impressive. However ... After just 1 day, it became obvious that against the bots that chose the fireball as the first ulta, it turns out bad to fight. Attempts to correct this with coefficients and adding accounting for the blast radius from the fireball to the dodge algorithm did not lead to anything. You can not defeat the enemy - lead him. The next step was writing fireball shooting.In general, nothing better than busting a shot around minions standing in place (so as to touch the latter with the edge of a fireball and the edge of an explosion), buildings and all enemy magicians (assuming that the latter are always optimally trying to escape from the explosion) did not quickly come up as temporary option was made just such a bust. Only those variants of the shot that I can do with the current casting radius were taken into account. But ... There is nothing more permanent than temporary. Until the very end, the brute force algorithm remained exactly the same, with the exception of specifying whether the enemy magician could escape from my fireball or not.that the latter are always optimally trying to escape from the explosion) was not quickly invented, and just such a search was made as a temporary option. Only those variants of the shot that I can do with the current casting radius were taken into account. But ... There is nothing more permanent than temporary. Until the very end, the brute force algorithm remained exactly the same, with the exception of specifying whether the enemy magician could escape from my fireball or not.that the latter are always optimally trying to escape from the explosion) was not quickly invented, and just such a search was made as a temporary option. Only those variants of the shot that I can do with the current casting radius were taken into account. But ... There is nothing more permanent than temporary. Until the very end, the brute force algorithm remained exactly the same, with the exception of specifying whether the enemy magician could escape from my fireball or not.
, , . WizardsInfo, , , . , , . , , . 30% , . , - , .
, , , 180 (.. , ), , (, ). ( , , , ). score . — , . , , (, , , ? ). . — , , ( ). , . , .
-, , , , , “ ”, , - , , . . , , .
2.
After correcting the problem in the dodge algorithm, the rating began to grow again, and I stopped being afraid not to qualify for the final. However, in the time it takes to prepare for round 2, I would like to learn how to use all the ultas so that you can use them in the final. But first ... My magician is still very passively standing on the line and not really making attempts to attack the enemy magicians, who keep their distance. And I would like to fix it. Last week, the targeting system was rewritten, and now
… , , ( 2), … , , , , , . , 0:00:01, .. . — 2 , . 2 3, (.. , , ), 1 2 . , .. , 1, .. , . .
( ), (, ). , . 2 ( , .. , . , ).
.
, , . , — 2 , , 2, .. , . …. , , , , « »… , . — , . , ??? ,
( ), . ( ), . 1 2 , .
, “ ”, , . — , , . , - , “” . — 600 , , .
(, gif-)
2*5. Since , «» — , “” . “”. .
, “ ”, tyamgin , 4 , . , 4 , . , , . , , .
“” — , - , ( 350 ). — (~900 ) , ( , ). , , , .. . — ,
— , , , . , , . , , — , “ ”, ( , , .. ).
2*5 , , - . - .
The final
— . , . , , , . ( Antmsu ), , . , , . , , , . NighTurs , , … , .
Git . 4.30 PM, , .
, - , . , . Antmsu NighTurs , , .
( ) ( core2duo ), 6 6, 6 NighTurs, , , 2. , , , . , , .
russian ai cup 2016. P — , G — . Russian Ai Cup — Commandos. .
The last stand.
After examining the interim results of the final after the first part, everyone, including me, agreed that the participants from the top 2 would sort things out “between themselves”, and I would most likely retain the third position. To some extent, this comforted me, because the results showed that at least third place is already relatively difficult to lose, but ...
The first, of course, attracted the attention of the core2duo strategy. Managing the magicians at the micro level, he was quite weak and it was possible with almost 100% guarantee of victory to go on him in the attack in the forehead. This, in my opinion, is an ideal tactic in this case, but still I wanted something more universal in case of the appearance of clones of this strategy. The solution was simple - if there are too many enemy magicians on the lines other than the central one, I greatly increased the bonus for finding my magicians at points from which they can do damage. With this approach, my strategy almost always won when playing with core2duo, but while waiting for new pitfalls from the latter, for added safety, added a check: if (“core2duo”. Equals (playerName)) - we go to direct attack on the nearest enemy mage, no matter where . In addition to about 100% probability of winning with current strategies, this also brought additional confidence that he would not be able to do anything else to me.
The second item was my only loss to the GreenTea member strategy. In this game, my magicians very stubbornly did not want to go to the final assault with an equal number, but much, much more battered opponent. When examining this game more closely with the help of debug, one more bug was found - when searching for the “cluster” of my magicians to create an attacking group, if at least one magician was too far away, the group could not be found due to a problem in updating the average the arithmetic positions of the cluster “magicians” while excluding the most distant one. Having fixed this bug and added logic to force an attack on an enemy base in the event that the defending opponent has a much smaller number of hit points, I went on to consider the following problems.
Then came the losses to the participants TonyK and tyamgin. Testing with the latest TonyK versions at that time didn’t reveal how many defeats, and I thought that something was broken in his strategies. Just in case, the same slightly more aggressive tactics, which were played in the first part of the final only with Antmsu and NighTurs, also checked on it. Since visible problems have arisen - left everything as is. The same minor change was applied in fights with tyamgin. Visually, it gave a slight positive effect, and according to the results of the checks it was also left as is.
The remaining 4 participants, with whom I had defeats in the first part of the final, stood out from the general heap with the fact that all of them, like me, with all five magicians were walking along the center line. It was the lion's part of my defeats (of course, if we forget about the core2duo strategy), and it was very unlikely to solve all this by selecting coefficients and minor edits in the micro control of magicians, as I tried to do it on Friday against Antmsu. Inspired by the experience of core2duo, I decided to try to do something special for them. It was easy enough to see that 3 of 4 of these strategies at the time of the first part of the final (and before the second part of the final, all 4, which helped me quite well), without stopping, attacked the first tower of the enemy right up to melee. The plan was simple - but what if you try to split the whole group of attackers into two parts? In addition, when they run up to my tower, they become vulnerable to entering from the flank ... According to the plan, not all of them will have the opportunity to retreat in one direction, and the fastest possible attack in an attempt to squeeze a part of the opponent’s magicians to the forest can, in theory, bring desired result.
Plan of attack from the flank. The red arrows indicate my planned movements, the blue arrows indicate the expected behavior of the opponent. Clickable
To test this theory, I initially modified my version so that it ignored the danger from the first tower and went on it to attack. Then my changed strategy was launched using local-runner against my own version, which already knew how to make a call from the flank for this case. The results were very convincing - even with losses in the form of a tower, and sometimes also 1 mage, but a reckless attack from the flank most often resulted in a tangible advantage at the beginning of the game, and this turned out to be enough for the rest of the battle to take place almost steadily favor of a fresh update. Encouraged by local success, I decided to test how this idea would work in combat conditions on mortido and ud1, since according to my assumptions, they will not waste time on serious attempts to write something that would break my approach. Testing in combat conditions was also successfully passed, and I replaced this strategy with the previous option, so as
To check on the top 2 participants, I uploaded the updated version at 11.39, i.e. 21 minutes before the start of the second part of the final. Testing for the top 2 was successful (1 loss of 4 games, but as it turned out, the chance of my victory was even higher), and in this form the strategy remained until the end.
After launching the games, I was already in a state of squeezed lemon and went to take a nap. After a short rest, two news awaited me, one pleasant and one not so much. Pleasant - my strategy was really almost unbeaten (only one defeat in two waves, which is 118 games). Unpleasant - testing was noticeably slower than on the first day, and it was rather doubtful that there would be as many waves as the previous one ... And according to the results of the first waves, it seemed that it was almost impossible to overtake one of the first two participants. Nevertheless, even for 5 waves, with a great deal of luck, my strategy still managed to take the second line in the final result.
The results of the best participants of the second part of the final russian ai cup 2016. Clickable.
The final results of the best participants of the final russian ai cup 2016. Clickable.
Despite falling out of life for a month and a half, I definitely do not regret that I did not abandon the idea at the very beginning. The task turned out to be very voluminous and, as it was being implemented, it was constantly necessary to choose which features of the rules and in which cases to take into account, and which ones should be ignored. It was practically impossible to take into account all the nuances in the final implementation, which, perhaps, was an additional interesting and difficult point in the competition, although the final algorithm left a feeling of incompleteness. I would like to express gratitude to the organizers of the RAIC for holding such a large-scale and fascinating competition, and, practically by tradition, I would like to give special thanks to Roman Udovichenko ( Romka ) for creating a general chat, where many participants found useful information for themselves, very informative tables with intermediate results (can be seen in the screenshots above), which helped me in preparing for the last part of the final, and for the initial reading of this post.
UPD. Partially restored repository . I had to cut a couple of first commits. I also did not bring back all the dead brunches to life.
Source: https://habr.com/ru/post/318878/
All Articles