At first this text was written in the form of the comment to a subject of the winner of this tender. But as a result the volume of the text became such big that it was decided to select it in a separate subject. So it is supposed that the reader is aware about tender and read a subject of the winner. Also you can read history of the 30th place.
At once I will give the reference to a repository with the source code: bitbucket.org/skolotienko/coderacing — in addition to directly source codes is all history of kommit in the same place. For example, time in which it was made can seem interesting kommit with the comment "it is time to sleep".
In general, there was such feeling that most of leaders had approximately identical main ideas for final strategy:
- Search of a way in the card between veypointa
- Simulation of the movement, collisions and other physics
- Search of different actions which lead to different trajectories from current position in the future
- The choice of the best action or trajectory on the basis of some function of an assessment
So in this subject I will tell slightly in more detail about how these ideas were implemented in my case.
Search of a way
I considered a problem of search of a way a little more widely, than can seem. There was a wish to make such data structure and algorithm that it was possible to learn quickly the answer to a question of the following type: "if I am in a point of X, Y and my N following veypoint, then how many to me remained to the following veypoint?". Such requirement came that similar requests will arrive from "pereborshchik" several thousands of times during one decision-making to evaluate the received trajectories.
The first version worked just with the help of search of a way from any cage where the point of X Y to the following veypoint got, and as the answer issued length of a way. At the same time for a relative arrangement of a point of X Y in a cage some bonus was also given to make an assessment a little more similar to continuous.
Somewhere to the second round cards where such simple search of a way in cages had problems began to appear. For example:
— From what party to approach a veypoint?
— To make as if so that when taking a veypoint the machine did not try to go a backing to the following if it is possible just to pass almost without loss directly and to make a small hook?
— How to make search of a way taking into account a turn for a backing?
As a result there was an idea to change a data structure and request: "if I am in a point of X, Y, my corner of A and N following veypoint, then how many to me remained to the finish?"
To respond to such request, it was necessary to construct the device of the graph on which there will be a search of a way. As a result the following turned out:
— The node of the graph is a "subcage with the direction" — a cage of 400х400 in size, with 8 possible directions (with a step of 45 degrees).
— Neighbors such node had 6 pieces: 1 neighbor — to go "directly", 2 neighbors — to go "directly with turns", 1 neighbor — to go "back", 2 neighbors — to go "with turns back".
— Length of edges respectively was 1 for the direct movement, sqrt(2) for diagonal, and for a backing — was multiplied by some konsnanta. This constant was equal in the final version to 15. Such value was picked up by hands that the car not strongly long went a backing and at the first opportunity was developed, but at the same time allowed to take any idiotic veypointa which are on couple of tayl behind from current, without turns.
— Accounting of walls from "big" 800х800 cages not to generate excess neighbors at the level of "subcages" 400х400.
There were many bugs with such search of a way. In particular because the way was looked for beginning not from a request point, and beginning from the finish. That is if asked us "if I am in a point 0, 0, my corner 0 and following veypoint 1", then it was necessary to find at first distance from the finish (0 veypoint) to the previous veypoint (N-1-y veypoint), then from the previous veypoint recursively to find a way to the 1st veypoint and only then to look for a way from the 1st veypoint to a request point. Because such search happened since "end" in "beginning", there was a lot of confusion with determination of neighbors for a node — it was especially difficult to define the direction at neighbors.
Above — an example of neighbors for a node with the direction of multiple 90 degrees. A little in a different way neighbors for the "diagonal" directions, but the same essence look.
Closer to the final it was succeeded to debug such mechanism and on unknown cards the car selected quite interesting ways that it was possible to go round veypointa in the correct order and with the minimum backing. At the same time at first the penalty for a backing was not such high and in lack of noises such solution even went quicker. But in the final on "problem" veypointa constantly there was a dump and chaos so it was better to slip such veypoint without deceleration and to make a hook — it will allow to avoid a second-hand market on a veypointa and to take more bonuses on the road. It is also necessary to understand that the trajectory is not obliged to follow the way received from a point with the car — the main thing that the best trajectory displayed in a point which "will be closest to the finish".
Here somehow the "best way" found from the current point of the car in the future so looked. It is possible to notice that the car decided to turn not at once "greedy" to a veypoint, and to come to it "behind".
The search algorithm of a way — it was lazy implementation of algorithm of Dijkstra where all ways were considered on demand and were cached. In the final the cache was sometimes reset if new unknown cages opened.
The source code — see the class CWaypointsDistanceMap
Initially the physics worked only in the form of the following mechanism: on an input "machine" + "action" moved, on an output "the machine on the following tic" turned out. The code of simulation was fairly borrowed from Mr.Smile from its message at a forum and adapted further, having added proisteyshy checks on collisions with walls — in that case search just stopped. Then the correct calculations of braking, nitro, oils were slowly fastened to this code. Eventually there was a need of the correct calculation of collisions since some turns were more profitable to be passed with collisions, than without. Especially on start at an unsuccessful position.
Generally, somewhere to the termination of the second round it was succeeded to understand a code of collisions from notreal2d, to achieve almost absolute accuracy, and then even to simplify a code — notreal2d it is too "general" engine, and in our world walls are only 3 types — the direct vertical or horizontal line, a circle with a radius of 80 and a concave arch. Concave arches it was decided to chuck in since the code with them did not manage to be debugged that it worked steadily and precisely.
But also my head was not left by thought of simultaneous simulation of all objects in the world — all cars, shells, etc. Eventually the simulator of one machine turned into the simulator of "world", i.e. to it on an input "world" + "actions of all cars" moved, and on an output "the world on the following tic" turned out. Actions of enemy cars were assumed how "slipper in a floor" :)
On implementation and debugging of such simulator the most part of all time left probably. Friction coefficients were selected manually, the code of search and permission of collisions was copied and corresponded from notreal2d, and eventually search of collisions was written manually for optimization. There was a huge number of the bugs connected with collisions from "ends" of walls — as a result I just got rid of the ends of walls. Also it was necessary to debug accurately collisions of machines with each other and with buses. And collisions with bonuses were not written correctly. Many weak places on speed the profiler who is built in VS 2015 — huge to it helped to find thanks.
The source code — see the class CWorldSimulator.
Comparing to what was made by santa324 it is possible to tell that a pereborshchik — it was the weakest place of my strategy. There were ideas to make something it is essential new: the genetic algorithm, or the "mutating" trees, or still something, but forces did not remain any more.
In general, the main idea of that pereborshchik who as a result was used was that trajectories will be looked for by means of search of some fixed set of actions. For example:
- To go directly/on the left/to the right 0/7/15/40/60 tics with a brake / without brake
- Then to go 0/40 tics directly/on the left/to the right
- Then once again to go 0/40 tics directly/on the left/to the right
- And as the last action — to go directly before the termination of depth of search
One of the first versions was able to touch only one turn and one braking and it was insufficiently for execution of maneuvers like "to be rebuilt far away from turn then to come into turn with a big radius" or a drift. Eventually the structure described above with three turns / braking and driving directly before the termination of depth of search which was equal to 150 tics was selected. But even such structure had to be cut down significantly when simulation of physics was changed from one car without collisions before simulation of "whole world" with collisions. To keep within in taymlimit some branches joined and switched off with chance of 50%. And also lengths of actions were spread by means of a random.
Significant improvement of trajectories happened when the best found sequence of actions on the current tic remained to remember it on the following tic and to evaluate again with correction of dlitelnost of all actions on minus 1. It "storing of the best trajectory" added an element of evolutionary algorithm in a pereborshchik and helped to drive more or less adequately even then when because of a random several tics in a row were not a new good trajectory.
Function of an assessment in a pereborshchik was served by the sum from different composed. The basic composed — that "how many remained to the finish if I appeared in a point of X Y with a corner A and my N following veypoint?". Then were added composed for bonuses, entrance to pools, loss of lives etc. — it allowed to select perhaps not the most optimum trajectories from the point of view of distance to the finish, but to select bonuses, to turn aside from shells and to go round pools.
Also in the end the pereborshchik as follows was succeeded to move heuristics on nitro / to a shooting/pools to this — for the best found trajectory checked "and what will be if I include nitro right now / will shoot/will pour a pool?" and for each type of such action the own assessment was considered. If this assessment overcame a threshold, then operation was performed.
In a pereborshchik "the long backing" was added to the latest moment before the final, it was started if the best way from the current cage was "back". Unfortunately, my tests did not show essential deceleration from it "a long backing" since on all cards which I was tested locally the backing was practically not used. And that code which was responsible for a backing before — was a set of crutches in style smartgy and respectively practically did not eat off time. The increased consumption of time of strategy missed by me led to falling on a taymlimita in the first wave of cards of the final, but about it will be lower.
A lot of time for a backing and experiments with function of an assessment was spent. Such "simulation of the whole world" gave huge opportunities. For example, as a result of some experiments the jeep could shoot the bus at the ally that that went quicker. Or the jeep could slow down specially that the opponent going behind with 1% lives crashed into the jeep and died. Or when cars on start tried to push out the extreme opponent that that faced a wall. But much to my regret at me it was not succeeded to debug such composite functions of an assessment. And I was not able to afford deep simulation of all collisions — miscalculated the final version "fair physics" only the first 40 tics with an accuracy of 2 subtics. And is farther already collisions were not considered, and the subtic was only one.
Roller with visualization of the best found way and trajectory for the jeep (at the others it is drawn we are assumed a trajectory on 40 tics).
The source code — see the class CBestMoveFinder
On the first part of the final my strategy lost 40 games because of taymlimit which I by the carelessness did not check — strategy ate off on average 42 ms on a tic, at the taken-away 30 ms on average on a tic. The first wave of cards in the final differed from all others in the fact that was about - about - very slow and the majority of cards was passed "end-to-end" on the taken-away tics, and in my case — even end-to-end it was not possible since allowed processor time came to an end. On other cards most often it was possible to finish quicker than the allowed time since it was taken away "with a stock".
On KDPV just a screenshot of a typical case — strategy did not reach to the finish. But in this game I was practically dotolkat to the finish by the participant under Antmsu nickname :)
So I was very strongly baffled, angry and practically in a depression because of
It was this time absolutely not clear how to test strategy and to make decisions on whether it became better or worse. So scripts for start of local tests on all cards, and also for continuous start of games with the closest rivals via the website interface were in addition written. Plus separate scripts for downloading and analysis of results. Also the strategy code that there was opportunity "was a little modified to save cards from repeater-and" which in the final were completely accidental.
There was still a silly attempt to rewrite a class - in - a class completely all notreal2d engine, on it was killed hours 10 and everything was deleted.
Still there was an attempt to remake a pereborshchik on the genetic algorithm where the gene is one action with duration. But something working did not manage to be reached, as well as to think up adequate operation of crossing.
A little more offensively, but in MyStrategy there was a kostylny code for a backing if the machine long did not move, and also for the front course in style smartgy if for some reason the pereborshchik did not find good trajectories at all. It was not succeeded to make fair shortchanging of such situations in a pereborshchik.
As a result very large number of time was spent for all tender. Not less than 100 hours, and it is rather even 150 or more. Of course, not all this is coding time, but the brain boiled and worked continuously, even in a dream. In general it is happy with result and is very glad that it was succeeded to pull out a prize. My previous participation in tender was only in 2013 and was limited 30 - what place.
Many thanks to organizers — in my opinion, it was the most spectacular and perhaps the most interesting tender from last. Rivals were very strong, it was necessary "to run at full speed only to remain on site", to them thanks too. Well and separate thanks of Mr.Smile for earlier vykladyvaniye of "physics of the movement" of the car, JustAMan for a convenient visualizer on sockets, Romka for interesting video news and the colleague of Angor for the carried-out breynshtorma :)
This article is a translation of the original post at habrahabr.ru/post/273745/
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: email@example.com.
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.