Главная » Хабрахабр » Создание бота для участия в Russian AI Cup 2018 CodeBall

Создание бота для участия в Russian AI Cup 2018 CodeBall

Из его статьи конечно же многое можно почерпнуть для будущих соревнований.
Но вот про участие в текущем соревновании на стадии бета тестирования думаю статей мало, понятно, что нельзя публиковать код решения, неизвестно еще как хорошо это решение и вообще много еще неизвестно ведь сейчас по сути только начало турнира, но в этом и прелесть. Сложилась традиция, что после соревнований по спортивному программированию победитель или просто игрок выкладывает на Хабре статью, чтобы рассказать как здорово было участвовать в соревновании и как вариант победить в нем. Автор дает читателю шанс заскочить на отправляющийся поезд и насладиться новогодней поездкой в мир игровых стратегий.

А пока как уже написал выше добро пожаловать в путешествие по Russian AI Cup CodeBall. Во первых спасибо, что открыли статью, сразу хочу поделиться секретом: это будет цикл статей, в котором надеюсь затронем и генетические алгоритмы и нейронные сети.

Так же на странице быстрого старта есть примеры уже написанных ботов для различных языков программирования, что сильно облегчает начальный старт.
Начнем с простого, с названия чемпионата CodeBall.
Приятное сочетание слов code и ball, почти football. Ссылка на страницу быстрого старта чемпионата
По вышеуказанной ссылке читатель сможет найти правила чемпионата, правила самой игры и основную часть математического аппарата необходимого для создания бота. Правила и логика игры тоже похожи на футбол, но с каждым раундом усложняются/ поэтому за основу возьмем начальные условия проведения игр.
Суть игры как говорилось в недавней песне: игроки должны забивать, а вратарь отбивать мячи.
Схематично игровое поле

Обращаю внимание, что боты двигаются в плоскости пола арены XZ, ось Y отвечает за высоту игрового объекта.
Также схематично объекты игры (мяч и боты(организаторы их называют роботы))

Игровое поле это трехмерное замкнутое пространство, ни мяч ни боты не могут выйти за его пределы. Теперь немного текста в поддержку картинок. Для того чтобы гол засчитали, нужно чтобы мяч полностью оказался за линий ворот (на рисунке указана пунктиром).
Для упрощения расчетов столкновений(коллизий) игровых объектов (арена, мяч, боты) боты и мяч считают идеальными сферами(шарами), которые описываются следующими величинами: радиус сферы, координата центра сферы, масса, скорость. В этом пространстве существуют две области "ворота" при попадании в которые мяч считается забитым одним из игроков. Если пролистать правила чемпионата до конца, то там читатель обнаружит программу на псевдокоде, которая как и раз и отвечает за вышеуказанные расчеты. Арена также описывается идеальными математическими примитивами, так что расчет столкновений обходится без участия полигонов, что сильно упрощает задачу. Но об этом немного позже. Данный псевдокод после небольших физических усилий переводится на выбранный вами язык программирования и является вполне работоспособным.

Для придания достоверности происходящего на арене, введена гравитация, то есть на ботов и мяч постоянно действует сила гравитации направленная вниз относительно пола арены. Еще пару слов о физике игрового мира. При ударе о стенки арены мяч теряет часть энергии, но это не сильно усложняет мир и вполне понятно со стороны, нет возможности создать вечный двигатель в виде мяча.
Чтобы мир казался еще более правдоподобным применена схема расчетов с Тиками и Микротиками. Остальными формами физического взаимодействия такими как трение или угловые скорости(вращение) объектов организаторы пренебрегли в пользу простоты описания физического мира. В данном соревновании мы можем посмотреть на физический движок в исходных кодах, как уже говорил он нам пригодится в будущем, и обнаружить что для игроков существуют Тики, а внутри движка все происходит в Микротиках, по умолчанию 100 микротиков в одном тике, что дает возможность точнее описывать коллизии объектов и избегать таких неприятных вещей как провал объектов за пределы арены или провал объектов друг в друга приводящие к ошибкам во взаимодействии между ними. В первой своей статье автор подробно останавливался на понятии Тика игрового времени.

Мяч мы уже выше выяснили из правил соревнования является сферой. С миром(ареной) и игровым временем вроде разобрались, посмотрим на игровые объекты: боты и мяч. На данном этапе соревнований введено упрощение, что если бот находится в полете(не касается стенок арены), то у него нет возможности исполнять команды по изменению скорости. Если быть кратким, то бот это мяч меньшего радиуса и большей массы, которому можно отдавать команды: указать желаемую скорость(это трехмерный вектор содержащий как направление, так и длину или величину скорости) и силу прыжка, если прыжок в данный момент целесообразен с точки зрения логики игры.

Описанию местоположения игровых объектов. Перейдем к самому трудному или наоборот простому, все зависит от опыта читателя в работе с трехмерными векторами. Картинка в поддержку

Приступим к ботостроению.
На каждом игровом тике, ваша стратегия будет получать следующие объекты:
Мяч:

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

и список ботов, с данными по каждому боту:

class Robot:
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

Здесь многое будет зависеть от языка программирования выбранного вами. сразу видно что с этими данными неудобно работать, желательно ввести класс(объект) 3D вектор и класс 2D вектор. Автор сейчас пишет бота на c++, но постарается ограничиться псевдокодом. Обычно эти классы уже написаны и легко находятся в интернете для нужного языка программирования. Если ввести полноценные классы векторов, по операции по сложению, вычитанию, умножению, нормализации и другие векторные операции останутся внутри класса, что сильно упростит работу над стратегией.
Еще есть класс игрока, который указывает какие боты из списка ваши, какие противника:

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

Есть подозрение, что в это время входит и время на десериализацию поступивших данных и сериализацию отправляемых вашей стратегией данных на сервер. После передачи данных об игровом мире на вход вашей стратегии, игровой движок отдает вам управление и запускает таймер времени для расчетов, время на расчеты ограничено, в среднем около 20 микросекунд на все действия внутри тика. Но так как количество ботов 4 (2 ваших и 2 противника, далее в финальном раунде общее количество ботов увеличится до 6) временем на эти операции можно пренебречь.

Для нахождения нужного вектора направления скорости надо из позиции мяча вычесть позицию бота, получаем вектор направления на мяч, далее его можно нормализовать и умножить на максимальную скорость движения бота из констант мира. Пришло время команд.
Например, мы хотим дать боту команду двигаться в сторону мяча. На картинке подробнее

Если учесть тот факт, что бот большее время проводит на плоскости пола арены, то упрощение расчетов до двух координат не скажется сильно на точность расчетов по перехвату мяча. Наверное читатель заметил на слайде что расчеты можно проводить как для 3D векторов, так и для 2D векторов. Конечно про высоту мяча не надо забывать, но с учетом гравитации он рано или поздно опустится к боту.
Прыжок бота, это добавление скорости по вертикали(вертикальной скорости), направление прыжка бота будет совпадать с направлением текущей скорости бота с добавлением составляющей по оси Y.
Если к вышеуказанным словам добавить более сложную логику движения, то можно получить следующее поведение ботов:

Экспериментально установлено, что даже самая простая состоящая из нескольких десятков строк кода стратегия вполне может неплохо играть. Сейчас на сайте действует песочница, где можно посмотреть игры, но ничего не сравнится по ощущениям, если вы напишите свою стратегию и будете следить за ее играми.

Основная задача нападающего это преследование мяча и при удачном положении удар в сторону ворот противника. Из простых форм стратегий приходящих на ум, стратегия по выделению одного бота для защиты ворот, второго бота сделать нападающим. Все эти вещи легко описываются с помощью if-else конструкций выбранного вами языка. Бот играющий за вратаря, обычно ограничен в своих перемещениях по полю, и в основном действует в зоне ворот. По условиям конкурса нельзя публиковать исходные коды стратегии. В любом случае придумывать и создавать стратегию на данном этапе придется тебе мой читатель. Но обсудить подходы к проектированию стратегии думаю не запрещается.
Как мне кажется организаторы конкурса выбрали интересную тему для турнира, единственное сайт немного тормозит, но надеюсь скоро это исправят.
Жду откликов в комментариях касательно статьи, на чем остановиться более подробно.
В следующей статье попробую описать методы по прогнозированию поведения мяча во времени для более осмысленной игры ботов в вашей стратегии.
А пока поздравляю с наступающим Новым 2019 Годом!
Продолжение следует.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Киберпреступники пять месяцев контролировали ASUS Live Update

Злоумышленники разместили на сервере вредоносный файл с бэкдором, подписанный валидным сертификатом ASUS. Как сообщает «Лаборатория Касперского», хакеры из APT-группировки ShadowHammer 5 месяцев контролировали сервис обновлений ASUS Live Update и заразили более полумиллиона компьютеров по всему миру.Исследователи из «Лаборатории Касперского» обнаружили, ...

Kubernetes 1.14: обзор основных новшеств

14. Этой ночью состоится очередной релиз Kubernetes — 1. По сложившейся для нашего блога традиции, рассказываем о ключевых изменениях в новой версии этого замечательного Open Source-продукта. 14 и сооветствующих issues, pull requests, Kubernetes Enhancement Proposals (KEP). Информация, использованная для подготовки ...