Creating a bot to participate in the Russian AI Cup 2018 CodeBall

It has become a tradition that after a competition in sports programming, the winner or just a player puts an article on Habré to tell how great it was to participate in the competition and how to win it. Of course, much can be learned from his article for future competitions.

But I think there are few articles about participation in the current competition at the beta testing stage, it’s clear that you can’t publish the decision code, it’s not yet known how good this solution is and in general it’s still unknown a lot, because now it’s basically just the beginning of the tournament, but that's the beauty. The author gives the reader a chance to jump on the departing train and enjoy the New Year's trip to the world of game strategies.

First, thanks for opening the article, I just want to share a secret: it will be a series of articles, in which I hope we will touch on genetic algorithms and neural networks. In the meantime, as already written above, welcome to the journey through the Russian AI Cup CodeBall.

Link to the quick start page of the championship.

By the above link the reader will be able to find the championship rules, the rules of the game itself and the main part of the mathematical apparatus necessary for creating a bot. Also on the quick start page there are examples of bots already written for various programming languages, which greatly facilitates the initial start.

Let's start with a simple, with the name of the championship CodeBall.

Nice combination of the words code and ball, almost football. The rules and logic of the game are also similar to football, but with each round they become more complex / therefore we take the initial conditions for the games as a basis.

The essence of the game as stated in a recent song: the players must score, and the goalkeeper to beat the balls.

Schematically the playing field:



I draw your attention that the bots move in the plane of the arena floor XZ, the Y axis is responsible for the height of the game object.

Also schematically the game objects (ball and bots (the organizers call them robots))



Now some text in support of pictures. The playing field is a three-dimensional closed space, neither the ball nor the bots can go beyond it. In this space, there are two “gate” areas when hit into which the ball is considered to be scored by one of the players. In order for the goal to be counted, it is necessary that the ball is completely behind the goal lines (indicated in the figure by a dotted line).

To simplify the calculations of collisions (collisions) of game objects (arena, ball, bots), bots and ball are considered ideal spheres (balls), which are described by the following values: radius of the sphere, coordinate of the center of the sphere, mass, speed. The arena is also described by ideal mathematical primitives, so that the calculation of collisions does not involve polygons, which greatly simplifies the task. If you scroll through the rules of the championship to the end, then the reader will find a program on pseudocode, which, as once, is responsible for the above calculations. This pseudocode, after some physical effort, is translated into the programming language of your choice and is quite workable. But more about that later.

Just a couple of words about the physics of the game world. To impart authenticity to what is happening in the arena, gravity is introduced, that is, bots and the ball are constantly affected by the force of gravity directed downward relative to the arena floor. The other forms of physical interaction, such as friction or angular velocity (rotation) of objects, were ignored by the organizers in favor of the simplicity of describing the physical world. When hitting the arena wall, the ball loses some of the energy, but this doesn’t complicate the world very much and is completely understandable from the outside;

To make the world seem even more plausible, a scheme of calculations with Tiki and Mikrotik was applied. In his first articleThe author dwelt on the concept of Tika playing time. In this competition, we can look at the physics engine in source codes, as he already said, it will be useful to us in the future, and find out that there are tics for players, and everything inside the engine happens in Mikrotik, 100 microtics in one tick by default, which makes it possible to more accurately describe collisions of objects and avoid such unpleasant things as the failure of objects outside the arena or the failure of objects into each other leading to errors in the interaction between them.



We sort of figured out the world (arena) and game time, let's look at the game objects: bots and ball. The ball we have already figured out above the rules of the competition is a sphere. To be brief, the bot is a ball of a smaller radius and a larger mass, which can be given commands: specify the desired speed (this is a three-dimensional vector containing both the direction and the length or magnitude of the speed) and the jump force, if the jump is currently expedient from the point of view game logic. At this stage of the competition, a simplification was introduced that if the bot is in flight (does not apply to the walls of the arena), then it does not have the ability to execute commands to change the speed.

We turn to the most difficult or vice versa simple, it all depends on the experience of the reader in working with three-dimensional vectors. Description of the location of game objects. Picture in support



We proceed to the bot.

At each game tick, your strategy will receive the following objects:

Ball:

classBall:
x: Float                      // Текущие координаты центра мяча
y: Float
z: Float
velocity_x: Float             // Текущая скорость мяча
velocity_y: Float
velocity_z: Float
radius: Float                 // Радиус мяча

and a list of bots, with data for each bot:

classRobot:
id: Int
player_id: Int
is_teammate: Bool             // true, если это робот вашего игрока
x: Float                      // Текущие координаты центра робота
y: Float
z: Float
velocity_x: Float             // Текущая скорость робота
velocity_y: Float
velocity_z: Float
radius: Float                 // Текущий радиус робота
nitro_amount: Float           // Текущий запас нитро робота
touch: bool// true, если робот сейчас касается арены
touch_normal_x: Float         // Вектор нормали к точке соприкосновения с ареной
touch_normal_y: Float               (или null, если нет касания)
touch_normal_z: Float

it is immediately obvious that it is inconvenient to work with this data, it is desirable to introduce a 3D vector class (object) and a 2D vector class. Here a lot will depend on the programming language of your choice. Usually these classes are already written and are easily found on the Internet for the desired programming language. The author is now writing a bot in c ++, but will try to limit it to pseudocode. If we introduce the full-fledged classes of vectors, by the operation on addition, subtraction, multiplication, normalization and other vector operations will remain inside the class, which greatly simplifies the work on the strategy.

There is also a player class that indicates which bots from your list, which opponents:

classPlayer:
id: Int
me: Bool                      // true, если это объект вашего игрока
strategy_crashed: Bool
score: Int                    // Текущий счет игрока

After transferring data about the game world to the input of your strategy, the game engine gives you control and starts the timer for calculations, the time for calculations is limited, on average about 20 milliseconds for all actions inside the tick. There is a suspicion that this time also includes the time for deserialization of the incoming data and serialization of the data sent by your strategy to the server. But since the number of bots is 4 (2 yours and 2 opponents, then in the final round the total number of bots will increase to 6) the time for these operations can be neglected.

It's team time.

For example, we want to give the bot a command to move in the direction of the ball. To find the desired direction vector of speed, it is necessary to subtract the position of the bot from the ball position, we get the direction vector to the ball, then it can be normalized and multiplied by the maximum speed of the bot from the world constants. On the picture in more detail.



Probably the reader noticed on the slide that calculations can be carried out for both 3D vectors and 2D vectors. If we take into account the fact that the bot spends more time on the arena floor plane, then simplifying the calculations to two coordinates will not greatly affect the accuracy of the calculations for intercepting the ball. Of course, you shouldn’t forget about the height of the ball, but taking into account gravity, it will sooner or later sink to the bot.

A bot's jump is the addition of vertical speed (vertical speed), the direction of the bot's jump will coincide with the direction of the bot's current speed with the addition of a component along the Y axis.

If you add more complex logic of movement to the above words, you can get the following behavior of bots:


Now the site has a sandbox where you can watch games, but nothing compares to the sensations, if you write your strategy and follow its games. It was established experimentally that even the simplest strategy consisting of several dozen lines of code may well play well.

Of the simple forms of strategies that come to mind, the strategy to allocate one bot to protect the gate, the second bot to make the attacker. The main task of the attacker is the pursuit of the ball and, with a successful position, a kick in the direction of the opponent's goal. The bot playing for the goalkeeper is usually limited in its movements across the field, and mainly operates in the goal area. All these things are easily described with the help of if-else constructions of your chosen language. In any case, to invent and create a strategy at this stage you will have my reader. Under the terms of the competition can not publish the source code of the strategy. But I think it is not forbidden to discuss approaches to strategy design.

It seems to me that the organizers of the competition have chosen an interesting topic for the tournament, the only site slows down a bit, but I hope this will be fixed soon.

some beautiful gaming moments from a championship participant:


I am waiting for comments in the comments on the article, on which to dwell in more detail.
In the next article I will try to describe methods for predicting the behavior of the ball in time for a more meaningful game of bots in your strategy.

In the meantime, congratulations on the upcoming New Year 2019!

To be continued.