How to look for a way to victory at the Russian AI Cup 2016, but in the wrong direction

    there are only two ways, to victory or to the forestsAfter not much persuasion, I was convinced that 30th place is not so bad, and it’s worth writing an article. I am a member with the nickname Stef , and took about 30 places in the sandbox.

    The picture drawn side by side has a deep meaning - instead of devoting enough time and becoming a prize winner of the competition, I went the other way - I spent one third of the time on what was not necessary to do. To be more precise, I took up the algorithm for finding a path in a space where there are no impenetrable walls, but there are only trees that can either be chopped or walk alongside them.

    What came of it, you can see in the video , and I ask those wishing to learn all the secrets of the forest under cat.

    First, I’ll talk a little about the competition itself.. This year, the rules of the competition were based on the MOBA computer genre, popular in the world . The basic concepts of this genre have been preserved - the appearance of creeps on 3 lines near the bases; river with runes; 5 heroes on each side.

    But despite this, it was not a full-fledged MOBA - it’s not enough to efficiently switch from line to line, to protect the base in fact, too, and the development was just in the form of pumping skills from a given limited set. The final among the tops was reduced to the fact that the game was held according to the principle: "whoever quickly demolishes the enemy’s base in the center line won", and it was demolished in a swoop, from 4 to 6 waves of creeps.

    As a person familiar with this genre firsthand, at the very beginning of the competition, I suspected something was amiss and suggested that in the finals there would be just such a tactic - all in the midst. Unfortunately, the balance has not changed for the better, and I decided to play my game, and not the one that will lead to victory.

    Architecture


    This year I wrote a strategy in C ++, which I thought was closer to me. I regretted such a decision - I did not have enough opportunities from high-level languages, I’m already used to them. By the end, my program included 141 .h or .cpp files. It looked like this: forests of architecture .

    From this picture you can see the main idea of ​​architecture:

    • General Purpose Layer - It includes such folders as: Algorithms, Common, Environment. The location of the classes between these folders is not entirely correct, especially between the Algorithms and Environment folders.
    • The command layer is a set of classes that implements one of three protocols: MoveCommand, AttackCommand, CastCommand. Responsible for the logic: where to go, whom to attack, what to cast.
    • Tactical layer - It includes the Strategy, Tactics, Role folders:

      • Strategy is an adder of team results and contains a basic set to simplify work with teams.
      • Role - the base classes that determine the behavior of the magician - just a set of numbers.
      • Tactics - Describes a strategy, and the roles for this strategy. Under each round they are different. And there are several of them in the finals.

    The architecture turned out to be quite large and redundant, especially the command layer. Which led to some cost overruns.

    Time


    Before the start of the competition, I installed a program for counting time (toggl), and I constantly used it. I will immediately answer one interesting question for many - is there a lot of time and effort spent on the Olympics? - Yes many. It is very difficult to combine with work and family, and in fact you have to sacrifice sleep for it. Students are simpler in this regard, but I think it is not easy either.

    Weekly time spent:

    • First - 26 hours
    • The second - 26 hours
    • Third - 27 hours
    • Fourth - 34.5 hours
    • Fifth - 38.5 hours
    • Sixth (before the final) - 10 hours
    • After the finals - 15 hours

    Total: 177 hours.

    In the second round, I took 103rd place, despite the fact that the sandbox was high in the ranking, and I wanted to get to the Final through the sandbox, but could not. Before the finals, I was in the 80-90th place with the understanding that I was already tired and could not continue to write further at night, for this reason I gave up writing the Olympiad for a week, and as a result, I did not go to the finals.

    After some rest and the end of the final, I spent about 17 hours editing bugs and minor improvements to the strategy, which helped me to rise from 80-90 places to 20-30. At this point, I finally realized that writing the Olympics at night was a bad idea - almost all of the code improvements consisted of corrections of typos, which in turn appeared due to inattention, which suffers greatly at night.

    Spent time on tasks:

    • Architecture Support - 28 hours
    • Writing a Path Finding Algorithm - 49 hours
    • Writing the Dodge Algorithm - 26 hours
    • The rest is 67 hours

    The list contains 3 main tasks that took the most time: Architecture, Path Finding, Dodge. Things like: balancing and adjusting constants, fixing bugs and algorithms that did not take a lot of time fell into the “rest”.

    Now we can move on to the most interesting part - the algorithms that I wrote quite a lot, and not all of them revealed their potential.

    Algorithms


    During the Olympics, the following algorithms were implemented:

    • Influence map - allows you to easily assess the balance of power along the lines and find the point where it now stands on the line
    • Prediction of the enemy’s presence in the invisible zone is necessary first of all for a more accurate calculation of the influence map
    • Evaluation of the outcome of a local battle - needed to understand when to attack and when to defend
    • Projectile evasion is one of the most important algorithms.
    • Finding the best position is the second most important algorithm. Estimates where it is better to go and turn in the current tick. The weakest link in my strategy
    • Finding a path - allows you to estimate the distance to a point and find which trees interfere to reach it
    • Obstacle avoidance - needed to avoid close obstacles along the shortest path

    Influence Map


    It was made after the first round. Originally created primarily for making tactical decisions in the final. In fact, its main purpose is to determine the front line, the point where the battle is now taking place.

    In addition, the influence map is important in assessing the outcome of a local battle, and assessing which line is best to stand on. It looks something like this:


    If you look carefully, you can see that the main influence is provided by creeps. Mages are a small influence due to their inconstancy, and the towers are weak, and are not able to fight back in case of attack. In principle, the weakness of the towers is one of the biggest reasons for a different balance in the game than in MOBA.

    It was built quite easily:

    We go through all the units, buildings, magicians on the map, and fill the grids around. There are two grids in total: friendly and enemy, both grids are 80x80 in size and the entire map.

    In order to find where the front line is now, the algorithm goes from its base to the enemy and checks the influence of enemies around the current checkpoint. If there is enemy influence around this point, then the front line at this point means.

    In fact, initially the algorithm acted on a different principle, and gave out points where the "yellow" zone from the enemy’s side was first encountered. But the participant under the nickname core2duo changed my mind about where the front line should be - his strategy in the final attacked the top tower, going around the forest and not going on the line, thereby creeps passed by his magicians without paying attention to them.

    An estimate on which side the forces are superior along the lines is obtained using the sum of all the influences on this line. And using the algorithm below, this estimate was accurate enough to say when the line starts losing or vice versa winning. True, because of my laziness, the sum of the influences is considered wrong, and it is not so easy to say how much stronger or weaker the line is.

    Prediction of the enemy in the invisible zone


    There are three predictions: finding enemy creeps, finding magicians, towers. The first prediction is quite accurate, but not directly used. It is only needed to evaluate the strength of the line, since without this the algorithm would almost always have thought that our lines would win.

    To predict enemy creeps, a fairly simple algorithm is used - once every 750 ticks, the time of the appearance of creeps, 4 creeps are always launched from the point of occurrence, always in the same group and at the same speed. As soon as they reach the zone where there is visibility, they disappear.

    The story is different with magicians - they have little effect on the map of influences, but at the same time it would sometimes be nice to be able to catch up with an enemy magician who escaped beyond the edge of the screen. Therefore, all enemy magicians after their first appearance in the zone of visibility are saved in the local world, and if they disappeared from the zone of visibility, then they are emulating their departure to the base. That is, the strategy always considers - if the magician is no longer visible, then he runs to the base.

    Also, due to the fact that the towers shoot at the same distance as the mage’s viewing radius, the positions of enemy towers are driven in symmetrically at the beginning of the game in order to always know about their existence. Also, the time to attack is automatically calculated for them. Here the truth must be taken into account that it is necessary to take away dt and not 1, because if the mage died or he was frozen, then the strategy does not gain control over this mage.

    Estimating the outcome of a local battle


    Before the advent of this algorithm, my strategy always played from defense, the only case when a mage could attack is in cases of a displacement of the front line strongly towards the enemy base. Or the enemy mage himself came to be killed.

    The appearance of this algorithm clearly gave an advantage among non-top strategies - top strategies almost do not make mistakes and you can rarely say that if you attack, you will definitely win, but weaker strategies will make a mistake sooner or later and at that moment the predictor of the outcome of the battle will say - all you can attack.

    Although he gave the main advantage in attack, he was created primarily in order not to make mistakes when there is an imbalance on the line, or, in another way, if there are more enemy magicians than their own. In this case, it is better to stand slightly away from the enemies, since if you make at least one mistake, then the chances are good that your mage will be killed.

    The method of calculating the outcome of a local battle is impossibly simple, but, despite this, quite effective.

    First we decide on the input parameters - at the entrance we have our mage and the point where we want to attack. There is also a more advanced option - your mage + enemy is fed into the entrance, in which case the function of assessing the chance of winning is called twice - once for your own and once for the enemy mage. This approach helps to more accurately assess the chances of winning, rather than through a point, because in case of equality of forces, he will give out a number closer to zero, and in the case of a big difference, on the contrary it will strengthen this difference even more.

    The main calculation function looks like this:

    1. If in the current tick, more damage can be inflicted on me than the magician hp, provided that everyone shoots at the same time, then we return a negative chance of victory
    2. We add the amount of danger to friendly mages who are approximately the same distance to a control point or closer than my mage.
    3. We take away the amount of danger of the enemy mages who are between their mage and the control point.
    4. We add an advantage in the circle of a given radius and in the center between the position of the magician and the control point.
    5. We normalize the resulting values ​​and voila - there is a chance of victory.

    The chance of winning is 100% if the allied forces are one and a half higher level mages more than enemy forces.

    Therefore, in games without a level, I do not often attack, since for an attack the chance of winning should be more than 50%, which does not happen so often, provided that the creeps make up about 20% of the strength of one mage, and the hp of the mages are often equal.

    The danger of the magician is estimated as the sum of 10 values: DPS, the presence of certain magic, the amount of hp, the presence of buffs and debuffs, magic cooldowns, the amount of mana. Each coefficient was selected by eye and then slowly adjusted. In principle, writing more accurate odds at this point may not significantly improve the strategy.

    Projectile evasion



    The most efficient algorithm of all, and at the same time almost the simplest.

    Initially, a function for emulating movement in a given direction was written for evasion. That is, the strategy estimates how many shells still have maximum ticks and emulates the movement of the mage in a certain direction, taking into account that he turns at each tick to him. If the shell hit the magician, then this direction is erroneous and you need to look in another direction. If a projectile hits in all directions, then it is impossible to dodge.

    Initially, the strategy counted in 3 directions, or in 6 if we consider the forward and backward movements in different directions. But after a while I realized that such deviations do not give time for an attack or retreat, and at first I began to consider where it is better to go, and then drive away the deviation for 60 directions in order to find the one that best matches the direction of movement.

    There is a weak point here, I consider the fact that when dodging I always move and turn in one direction. In theory, this algorithm can be improved and not the best deviation of the movement can be found, but the minimum deviation in angle. Such an approach would increase the chances of winning the battle, since in order to shoot at the enemy you need to make a turn at a smaller angle than with the current algorithm. This could save 2-3 ticks, which is very important provided that the magician can shoot every 60 ticks, and the projectile flies to the magician about 12 ticks.

    But I did not describe one nuance - when dodging, it is worth considering the obstacles around: trees, creeps, magicians, buildings. For these purposes, before considering the direction of movement, all intersections in this direction are searched, and the closest to us is selected. That is, the result is not a vector in which to move, but a segment. Since part of the objects each tick is shifted, but they have no inertia, so as not to once again cut off the possibility of dodging, the radius of the object each "tick" is reduced by the speed of the object. For magicians, this is their maximum speed, and for creeps it depends on their direction of movement. So, if the creep was moving in our direction, then its radius on the contrary will increase, not decrease. I took the “tick” in quotation marks, since there is no motion simulation, for the place of this there is a formula,

    Search for an optimal position


    If we consider the benefit of the algorithm as - 'the advantage given by the algorithm' / 'the number of lines of code', then this is the most unnecessary algorithm. But, unfortunately, without him, the magician would not be able to move. All commands located in the move and defense folder + a couple of attack are responsible for counting movement. More precisely, each team returns a vector where to move, the priority of movement in this direction, and the same pair for rotation. Often the rotation and movement coincide, but not always. The teams themselves are some complex functions that according to some criteria consider these vectors. In total there are 9 movement commands:

    • Chase the enemy mage
    • Run to attack melee
    • Keep your distance from the tower
    • Keep your distance from the creep
    • Dodge the shell
    • Keep your distance from the enemy mage
    • Run up to get experience
    • Run to the bonus
    • Run to the front line

    Almost each of them can be repeated, and they have a different priority, which in turn depends on various factors. For example, to attack in close combat, the chances of victory must be high. Or if the enemy mage can dodge the projectile, then we will shoot at it last. Describing all the priorities may take another article, but there is almost no point in it - they were all the same selected by eye.

    After counting all such vectors, the strategy finds among them mandatory with maximum priority. If this is not the case, then it finds among all the vector with the highest priority and averages it. Two types of vectors are considered mandatory - dodge from the projectile and escape from the tower. Averaging is the sum of vectors that are deviated from the maximum by no more than 45 degrees and taking into account their priority. This is done for greater accuracy, where to go if there are a lot of almost identical vectors next to the magician - for example, two enemy creeps are nearby. At the same time, it is not advisable to do this for mandatory vectors - they are calculated so that if you do not follow them, you can take damage.

    Search for a way


    The first version of the path search was quite simple, and it was written before round 1 - for given points, which were about 50, a static graph was created in which the shortest path to the point was located. Since the endpoint and the point where the magician is located were not on the path itself, then a perpendicular to the nearest given edges of the graph was built from these points.

    The biggest minus that I saw with this approach was far from the shortest way, and to estimate the time for which you can reach the point, a simple heuristic was written that gave a certain approximate coefficient - how theoretically the shortest way differs from the calculated one.

    Therefore, by round 2, a more complex, but also more accurate search for the path was written. In addition to a better estimate of the length of the path, he also made it possible to estimate the path taking into account the felling of trees, which in some cases saves time. The algorithm is a union of Lee and Dijkstra and the principle of its operation can be described as follows:

    Create a grid of size 125x125 with prices on the map. Where no one is there, the price is 1, at the edges of the map the price is endless. After that, the price for the passage through the tree is added to the price, which depends on the radius of the tree - in the center of the tree it is maximum, and decreases to the edges. For creeps and towers, almost endless prices are set. Also, the influence map for the enemy side also refuses a small influence on prices in the search for a way - this is necessary not to climb into the center of the battle, but to bypass it.

    After that, a wave was launched from the current point of the magician, similar to the wave from the Lee algorithm, but it was always triggered on the entire map, and took into account the weight of the transition into the cell. It is because of the transition weights that the algorithm itself is still more similar to Dijksta than to Lee:

    1. A weight map is created - all weights are infinite, and a stack of transition points is created.
    2. Set the current point to zero weight, and it is entered as a transition point
    3. In the loop, as long as there are transition points:

      1. We get the first transition point
      2. We look through all the neighbors (4 neighboring cells), and count the preliminary weights in these cells - the current cell weight + the price of the neighbor
      3. If the resulting weight is less than the current weight in the cell, then change the weight, and add the cell to the stack of transition points
      4. Move on to the next iteration

    If we analyze this algorithm, then such an implementation of the Lee algorithm, without taking into account the transition price, has an estimate of O (N * M), that is, the algorithm went around each cell exactly once. You can also add the factor `* 4` as the neighboring cells are being checked. Due to the presence of weights, the algorithm can visit each cell several times, but this is not critical. True, one limitation that Lee does not have is added - it is necessary to bypass the entire map. But for us this is not critical, since later on this map you can quickly find a way to any point, which on average per tick is about 5, and in extreme situations it can reach up to 10 or more.

    To further reduce the build time, this card is recounted every 30 ticks. If the magician during this time changes the cell in which he is now, then he will work out a quick weight change. A weight change can be briefly described as follows: in the new cell we make the weight zero, in the old cell we set the value slightly less than unity. The value is slightly less than one, depending on how many times we have changed the cell in the last 30 ticks. This is necessary so that in the future, when searching for a path, the algorithm can always get to the current point, which is with zero weight.

    The search for the path on the weight map itself is not difficult: From a point, we construct the path so that we always choose the lowest price from neighboring cells. True, there are already 8, not 4 neighbors, and for diagonal neighbors, the transition price is overestimated by sqrt (2).

    Felling


    After the path is built, you can request information about which trees you need to cut down. Any path is represented as a set of short segments that were built on a grid. These segments I will call segments. To obtain information about which trees interfere, the following algorithm is used:

    We follow the path and find the tree that is closest to our current segment of the path and at the same time not far from it. We are convinced that this tree actually suits us - it cannot be bypassed. To do this, figuratively divide our playing field into two parts - on one side of the path and on the other. If there is a tree that belongs to the other side of the path and it is impossible to go between these two trees, then the current tree must be cut.

    True, there is a problem - in places where the path passes close to the middle of the tree and the tree ends up in the wrong half of the path where it should be, the tree may not be marked as a log house, despite the fact that it is. The reverse situation is also possible, when the tree does not seem to interfere, but it is in the wrong half of the way.

    I turned a blind eye to this problem - it turned out to be not critical, although it can be solved in a not very complicated way.

    Obstacle avoidance


    The very first algorithm that was written and the most non-modifiable. In fact, the path search algorithm described above is not mandatory and was written from the calculations that the obstacle avoidance algorithm is already there and it is working.

    You can watch how the mage walks using only obstacle avoidance in the video . The video is slightly inhibited due to the fact that it was filmed in debug mode.

    The algorithm itself is based on the calculation of internal tangents between objects. This was possible, since all objects in the world are represented by circles.

    The first thing that catches your eye when watching a video is the constantly twitching purple lines. The lines themselves were not used in the algorithm, but such a mapping turned out to be the most effective in order to understand where a group of objects is. To understand what a group of objects is, you can watch a video for 40 seconds - there the magician goes into the forest and passes between the two groups. To give a definition, groups of objects are non-intersecting subsets of the entire set of objects on the map, such that a mage can pass between any two objects from different subsets, or the distance between two objects is greater than the diameter of the mage + radius of the first object + radius of the second object.

    The first part of the algorithm is building these groups. This is done as follows:

    First, we have many objects and an empty set of groups. We take an object from many objects and check - if it falls into one group, that is, it is close to one of the objects of the group, then we add it there. If it falls into more than one group, then we unite all such groups and add a new object to the new large group.

    Next is the definition of where to go in the current tick. This is done on the basis of: many groups, the position of the magician and the point where we want to come. I would call this algorithm so-called ray throwing, although in reality these are not rays, but segments, since they have a maximum length.

    1. First, throw the beam at the point where we want to come.
    2. We find the intersection with the group, the object from the group that is closest to us.
    3. We go through all the objects of the selected group and for each we consider both internal tangents.
    4. We find the tangents that will give the maximum angle of deviation from the current ray - there will be two (one to the left and the other to the right).
    5. Next, according to magic logic (see below), we choose one of two.
    6. The touch point, taking into account the radius of the magician, will be our new point where we need to move.
    7. Then again we cast a ray, but to a new point, having previously deleted that group with which we already intersected.

    To understand the reason for the existence of "magic logic", let's look at the picture:

    At first, the angle a1 is smaller than the angle a2, and it’s more logical to go towards the angle a1, since there should be a shorter path, but as you approach the touch point, the angle a1 starts to increase, and the angle a2, on the contrary, decreases. For this reason, all the magic logic was that not only the angle, but also the distance was taken into account. After the appearance of the search for the path, this problem disappeared, since the beam itself was already close to ideal.

    As a conclusion


    If you compare my solution with the Commandos solution (second place in the finals, but we know that it’s actually the first), then its solution is more concise and simple, but does not allow for tactical assessments, but it gives an almost perfect solution in local battles . All my algorithms are tied to the adoption of tactical decisions and to the game all over the map than for local battles. At the same time, those very local fights were very difficult and cumbersome for me.

    For this reason, I decided to describe my decision - it differs in my direction in comparison with the decisions of top players.

    For those who want to write the Olympiad next year, and the number of people is clearly growing from year to year, I advise you to sleep at night ... It is better to spend two hours on the code, but it will be good than writing at night and then looking for bugs in the code for a week. For myself, I made just such a conclusion when I looked at my code in a "sober" state. Actually, the code itself can be viewed here: github.com/ivlevAstef/CodeCupAI2016MOBA . There are many comments in Russian that can help sort out the code. True, an understanding of architecture will take time.

    The main files where these or those algorithms are located
    • 2d math - Common / C_Math
    • Path Finder - Algorithms / A_PathFinder
    • Obstacle Avoidance - Algorithms / A_Move
    • Building Groups - Environment / E_World
    • Evasion - Algorithms / A_Attack
    • Impact Map - Environment / E_InfluenceMap
    • Finding the optimal position - the entire Command and Strategy / S_CommandStrategy folder
    • Local Battle Score - Algorithms / A_WinPredictor


    I also want to note the participant with the nickname firano (Leonid Lobanov) for his overwhelming help with writing this article.

    And many thanks to Roman Udovichenko ( Romka ) for organizing the chat in a telegram and to all the active participants in this chat. Without you, writing an Olympics would be much more boring, albeit more productive.

    Also popular now: