This year in Russian AI Cup it was necessary to program a bot for control of the machine (and in the final even two!), and I decided to participate for the first time as the subject seemed close and native: the fan of races, periodically I go to roll to karting (though without outstanding results), I spend often evenings, riding across virtual Hawaii in Test Drive Unlimited or Nurburgring in GTR Evolution.
I as a result did not take the high place (the 30th place in the final, finished a sandbox on the 48th place), but small time between the second round and the final was in top-10 sandboxes. Also, judging by a competition forum, as at me more nobody used a set
The detailed description of tender can be read on the website, but shortly the essence can be transferred as follows:
- There is a card broken into tayla of different types (a straight line, turn, the Tee intersection, the intersection, empty tayl).
- There are 4 machines. One of them (in the final — two of them) the player manages. Each tic of the server is transferred to the bot strategy managing the machine information on the world, and strategy has to answer what actions she wishes to make. Not so there is a lot of possible actions: to change engine capacity, to turn a wheel, to shoot shells, to pour an oil pool, to include nitro, to click a brake
- For completion of race it is necessary to pass through all control points-tayly in a certain order (actually, to pass two circles of the route). Coordinates of points are known, the way builds everyone independently. In the first two rounds of competition all card is known, in the final the player sees only the small neighborhood about the cars.
- On a trass bonuses are in a random way scattered: if to run over them, then, depending on bonus type, it is possible to fill up quantity of shells for firing, amount of oil for creation of difficulties to rivals, nitro-acceleration charges, to repair the machine, or to receive additional 100 points.
- The player receives points for passing of control points, for damages of rivals, for selection of bonus points, and also receives additional 512/256/128/64 points for the finish on 1/2/3/4 place respectively.
- After the end of game participants are arranged by the number of points. Who gathered more — that and the winner, everything is simple. Because of bonuses and points for damages of rivals the one who came to the finish earlier not always wins: for example, it is enough to pick up only one bonus on 100 points, and already to overtake the player finishing the third.
Decision-making by strategy can be broken into several rather independent parts:
- Search of a way
- The miscalculation of an optimum trajectory on the selected way
- Control of the machine for following of a trajectory
- Oil use
- Nitro-acceleration use
Search of a way
Originally for search of a way the normal wave algorithm was used: we start a wave on tayla from each control point, we cover all card, and the shortest way from each point-tayla of the card to each control point is known now. Unfortunately, everything is not as simple as it would be desirable: the shortest way can be not too successful for one of the following reasons:
- Contains abrupt turns or too many normal turns
- Does not pass through tayla with bonuses
- Demands a turn
- The way to this control point is optimum, but when following to the following control point the way which (see above) will turn out
As a result of thoughts was decided to try a method which frightened me by the essence, but it was rather effective: complete search.
At the beginning (almost) all possible ways (the sequence in a row the going tayl beginning from flowing), the total length of N where N had to be selected equal 11 are under construction to keep within time limits on work of strategy. I will specify that "honor" it: ways are under construction in the assumption that in the same tayl it is not required to be twice if from the previous visit any control point was not passed. Thus, if at a stage of creation of a way next perhaps it turns out what tayl already is in way, then creation of the current way stops and begins creation of the following.
After receipt of the list (almost) all possible ways there is an assessment of each of them as far as it is convenient. At an assessment a large number of the constants which are picked up at the level of common sense and a method "by eye" is applied. The way receives points by the following criteria:
- For each two turns in one party in a row to impose a penalty of 30 points. Turns by 180 degrees are fined since at the machine very big radius of turn and it is difficult to fit into abrupt turn, especially if rivals actively "help".
- For everyone two in a row going a tayla on which it is necessary to move directly, to add 10 points. Everything is simple: it is directly simpler to go, than to turn.
- For everyone two alternating like turns (turn on the left, and at once behind it turn to the right, or on the contrary) to add 12 points (the movement on diagonals of tayl happens quickly therefore such ways are rather profitable).
- If it is necessary to be unrolled, impose a penalty of 150 points.
- If on an estimated trajectory of following on tayla the bonus contains, to add the number of points corresponding to bonus type. If a bonus — 100 points then to add 55 points; the first-aid kit (at the same time the machine is less than 50 has some of points of health) — 25, a charge nitro — 35, oil — 15, shells — 15.
- To add 10*cos (a) of points to a way where a — a corner between the direction of the movement of the machine and the center of the first tayl along the line. At the expense of it the machine thinks a lot less often halfway that it needs sharply to turn and crashes into a wall.
- If the first 5 tayl of a way match the way calculated in the previous time, then to add 10 points. The idea consists in the same, as at the previous point: not to change sharply a way.
- If the way to the start moment is considered, then to the ways which are going straight 3 and more cages the bonus in 10 points is charged. If there were no other machines, then this point would not be required, however on many cards it is possible as much as strongly to want to turn at once on the left/to the right, but artful rivals interfere with just fact of the existence.
For calculation of bonuses for turns/straight lines and penalties for abrupt turns the last are also considered 4 visited tayl.
I will cut out that means under "on an estimated trajectory". For each tayl of a way, besides, in which there is a machine now, the corner on which there is a turn (0, +-90, 180 degrees) is calculated. If on a tayla there is a movement directly, then the bonuses located at distance 250 from a movement axis are considered as potentially selected. If on the tayl there is a turn, then the bonuses located at distance 200 are considered as potentially selected < r < 500 от центра поворота (угла тайла). Чтобы было понятнее, привожу картинку; серым цветом закрашены участки выбранного пути, в которых бонус считается потенциально подбираемым (отладчик позволяет рисовать только окружности, поэтому не обращайте внимания на лишние части красных кругов). Как можно видеть, участки даже не совпадают на границах тайлов, но для примерной оценки можно ли подобрать бонус или нет, такой метод подходит.
After an assessment of all possible ways the way with the greatest number of points is selected, and on it there is a miscalculation of a trajectory of the movement.
In the final all route is not known, and only tayla at distance 2 from each of the player's machines, and also all earlier seen tayla are visible. It was not necessary to modify algorithm practically: recalculation of distances was added by wave algorithm when opens new tayl, and also was considered that on an unknown tayl can be passed in any direction.
Miscalculation of a trajectory
Perfectly, the way is received as now on it to pass how to construct an optimum trajectory? Let's make to Google an inquiry of Racing line AI … or still some similar … and we will receive not really much. There is one video on Youtube, there is mentioning of article in the book Game AI Pro 2: Collected Wisdom of Game AI Professionals, and source codes of a bot to the game TORCS with mentioning of algorithm of K1999. It is a little more efforts, it was also succeeded to find the disk which is applied to the mentioned book on which source codes to articles lie though I could not find article. Fluent viewing of what is available allowed to come to a conclusion that process of creation of a trajectory in all three cases — iterative. We take as a basis though something, and then we smooth and we optimize, and so N times.
So, what to take in quality "though something" for further optimization? After some thoughts decided to try to make as follows: in taylakh-turns we put a trajectory end closer to the center of turn, in all other cases we consider that the trajectory lies through the center of a tayl which we need to pass. After that we split up a trajectory for smaller parts by adding on one point in the middle between everyone two already available, and then once again.
The received approach should be smoothed somehow. It was decided to use the approach described in video and source codes to article: to consider a trajectory as sequence of the hinges connected by springs. Between each couple of consistently going points "spring", with rigidity of k and which length in a quiet status is considered equal to distance between points is created. Speed of each point of a trajectory is initially equal to zero.
Now on each iteration of optimization each three consecutive points of a trajectory of A, B, C are considered. If the corner of ABC is not equal to 180 degrees, then "hinge" in a point of B aims to be straightened, and to points of A, B, C the corresponding forces are applied. Also to a point of B forces aiming to lead springs of AB and BC to initial length are applied. Elastic forces are calculated on Hooke's law: F=kx, where x — a difference in length between the current and initial length. Forces which are applied to points are given in the picture; it is supposed that the spring of AB is extended, and the spring of BC is compressed. Forces aiming to straighten the hinge (Fab, Fba, Fbc, Fcb) are proportional to a corner of ABC and length of the corresponding segment. Elastic forces of springs are applied only to B point as elastic forces for points of A and C are considered when processing the previous and following three of points of a trajectory respectively.
After calculation of forces for each point its speed on a trivial formula V = 0,9 * Vprev + F where Vprev — speed after the previous iteration, and F — the sum of all forces operating on a point miscalculates. The coefficient 0,9 is added that process met quicker. For each point its new location Pos + by V are determined by a formula Pos =. If new location appears outside the route, it is reset on the previous value, and speed decreases twice.
After several such iterations something similar turns out on an optimum trajectory of the movement. On the picture the black line designated an initial trajectory, and red — after 500 iterations of optimization.
However an optimum trajectory an optimum trajectory, but also bonuses somehow should be selected. One option which remained as a result was tested. Through a half of iterations of optimization once there is a following:
- For each bonus lying in tayla of a way the closest point of a trajectory is looked for.
- If the distance from a trajectory point to a bonus less than 250, then a point moves to the place of a bonus, and its weight increases in several tens times.
- Optimization continues.
The idea is as follows: if forces operating on a point with bonus coordinates are very big, then it means that the trajectory through this point is inconvenient for the movement, and even despite new big weight will gradually attract it to more convenient place if forces are not big, costs for picking up this bonus, are rather small, and it is profitable to take it.
The described approach to creation of a trajectory has several problems:
- Upon transition through border of a tayl the trajectory can sharply change as initial approach which is optimized further changes, and the current speed and the direction of the movement of the machine is not considered in any way that is visible on the attached gif image:
Partially it was succeeded to solve this problem adding of one more point of the optimized trajectory behind the machine, at the expense of it the current direction of the movement is considered and smoothness improves.
- Process is vychislitelno very expensive: judging by the profiler, the bot spends about 80% of time for calculation of a trajectory as a large number of operations with a floating point is used (especially on calculation of a corner and taking of a root).
- Process is not always stable, and the trajectory counted on the following tic can differ from previous. Usually it happens because of inconveniently located bonuses: on one tic it is convenient to take them, on the following is not present any more, and the trajectory can sharply change because of it, and the machine begins to brake and rush about on the left/to the right.
- Unfortunately, because of laziness and a lack of time it was not succeeded to get rid of one bug which led to such trajectory in certain cases:
Fortunately, usually at the following recalculation of a trajectory everything returns to a normal state so I left everything as it is. Most likely, it is a lack of implementation, but not a conceptual problem, unlike the previous three points.
After the miscalculation of a trajectory it is necessary to pass somehow on it. It is, perhaps, the most just implemented part of my bot, and it is surprising that ETO in general works.
The bot does not control engine capacity and always presses the accelerator pedal in a floor, and the wheel directs to the first point of the counted trajectory.
For a solution to brake or not the school physics a class approximately for 7 is used. For the next 4-5 points (the quantity depends on the current motion speed of the car) path curvature radius is considered. As approach of radius of curvature the radius of the circle described about three consecutive points of a trajectory undertakes. After that the speed of the car is squared and shares on minimum of the received 4-5 radiuses. As a result centripetal acceleration with which it is necessary to move to pass on this trajectory for what, in turn it is necessary that friction force (coupling with the road) allowed to make it turns out. If to consider the greatest possible friction force of a constant (that, as far as I understand, not absolutely the truth, but I did not study in detail physics of the movement), then if centripetal acceleration exceeds some value (strictly speaking, mu*g, where mu — friction coefficient, and g — free fall acceleration), then to pass on such trajectory with the current speed it will not turn out, and it is necessary to reap on a brake that the bot and does if the value of the counted acceleration exceeds 0,37.
Firing is implemented very simply: the bot considers that it will be in the closest n of tics in case of a shot if to assume that all machines drive at constant speed. If in one of tics the distance from a shell to the rival appears less than 50, then the bot shoots. Firing is made only if the estimated distance passed by a shell does not exceed 2000. Also the first 300 tics after the beginning the bot shoots only if at the rival's machine less than 30% of health as for murder give additional 100 points, and at the beginning of arrival often occur a situation when one machine shoots ahead, rivals are discharged in it, and it has few points of health.
The oil poured on the road throws the machine which passed on it in the accidental direction, and some time after zoom-in for it at the machine coupling properties of wheels worsen. At making decision on whether it is worth spilling oil, at a bot every time wakes up megalomania: he considers that all other rivals go on the shortest way to the following control point, and the machine of a bot is on an ideal trajectory. And if is a little more specific, then every time when the bot clicks a brake, occurs calculation of an approximate trajectory for everyone rivals on the next 10 tayl (without search, just on the basis of normal wave algorithm) and if it passes through a point where now there is a bot car, then it spills oil.
For use nitro the path curvature radiuses counted for braking are used. If the minimum radius of curvature on the closest 9 points of a trajectory more than 4000 (i.e. the trajectory obviously does not contain abrupt turns), then the bot includes nitro.
Writing of a bot was interesting occupation, though very strongly prevented work and a dream, but the Tolstoyan of the finalist obviously cost these tortures. The main feature of a bot in comparison with many to participants consists in almost total absence of the miscalculation of physics. There is still a quantity of the undescribed moments, for example, as the bot is selected from situations when got stuck or as I tried to optimize a code to keep within time limits on work, but they are insignificant. The bot lacks ability to try to go round oil pools, and there are especially not enough attempts to turn aside from other machines, but for it there were not enough forces and time; perhaps, it would turn out to implement it by adding of repellent forces at a stage of the miscalculation of a trajectory.
I want to express gratitude to organizers of competition for sleepless nights and interestingly spent time, to colleagues at work and to friends who motivated on participation and did not allow to throw when there was already a strong wish, and also to the participant of http://russianaicup.ru/profile/JustAMan for the convenient interface for drawing in Local Runner.
P.S.: We wait for the detailed story from the winner, he promised!
This article is a translation of the original post at habrahabr.ru/post/273579/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: firstname.lastname@example.org.
We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.