Итак

Меня, как и в прошлом году, зовут Андрей Рыбалка, только в этот раз мне 33. И, раз уж я оказался в десятке лучших, я решил снова поделиться своим подходом к написанию игрового бота для Russian AI Cup 2018.

В этот раз заданием был футбол. Сама задача несколько напоминала RAIC 2014 года, когда был хоккей, но вот решение было совсем другим.

Мир в этот раз был трёхмерным и эта трёхмерность использовалась по полной программе. Сама игра больше всего напоминала Rocket League.

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

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

Также, нужно сказать, что чемпионат делится на раунды, которые наверное правильнее было бы называть турами.

Кратко о турнирной системе

Для начала даётся 2 недели на разработку. Затем проходит первый раунд. 300 лучших из него проходят дальше.

После раунда правила игры меняются (а конкретно, в игру добавляется нитро) и даётся ещё 2 недели, по истечению которых проходит второй раунд.

Затем правила снова усложняются (добавляется третий футболист), даётся ещё неделя и играем финал.

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

Истории участия

Техническая часть будет ниже. Кому история неинтересна, можно скроллить вниз, пока не станет хорошо.

Первый раунд

Начал, как и большинство, с недели беты. Времени тратил много, по 4+ часа каждый вечер.
Прежде чем залить первую версию, прошёл несколько итераций
кодим, пока не начнёт обыгрывать предыдущую версию — собираем — считаем текущую версию предыдущей — повторяем.

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

В общем, первый проигрыш у меня был, кажется, на 12-м месте, по таймлимиту, а первая проигранная по счёту игра уже в топ 10.

Короче говоря, я понял, что шансы попасть во второй раунд, куда проходит топ 300, у меня есть.
Поэтому я не стал гнаться за позицией в нём и ничего уже больше для раунда не заливал, а просто продолжал работу.

На тот момент я видел, что ещё много пространства для улучшения и без подключения нитро (которое появлялось после 1-го раунда), поэтому сосредоточился на основной части стратегии, понимая, что до второго раунда ещё 2 с лишним недели и нитро я успею прикрутить.

Второй раунд

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

За следующие 3 недели до конца чемпионата над стратегией поработал в сумме может часов 20.

В результате, во втором раунде мой бот в принципе не знал, что в игре есть нитро, но каким-то образом всё равно занял 16 место.

Финал

В финале добавлялся третий футболист.

Я писал на медленном Java, а не на C++, как 7 из 8 человек выше меня в рейтинге, и мой бот и до этого нередко падал в таймаут, так что с появлением третьего игрока, падать стал в 100% игр. К счастью, игры в песочнице создаются в случайном формате, так что я автоматически
проигрывал только каждую третью игру и потому улетел вниз не слишком сильно. Кажется, упал до 18 места.

Если не считать программированием правку коэффициентов в оценочной функции и запуск тестов, то впервые, после начала болезни, я сел за бота в вечер за день до финала. Добавил совсем простое нитро, направленное строго вверх, сделал так, чтобы два атакующих прекратили бежать в одну и ту же точку и сталкиваться там друг с другом, и урезал для игры 3х3 всё, что мог, начиная от глубины просчёта и заканчивая точностью симуляции, чтобы только бот не умирал по таймауту.
В таком виде оно и играло финал.

В перерыве между половинами финала я снова засел за бота и потратил добрых часов 10. По большей части, правки касались динамического подбора коэффициентов, раннего прерывания генетики и т.д. В общем, искал баланс между точностью и глубиной просчёта и быстродействием.
Кроме борьбы с быстродействием, внёс ещё пару изменений:

• Отправлял дальнего (относительно мяча) атакующего в точку посередине между мячом и воротами противника
• Немножко исправил нитро (описание будет в тех. части). Оно по-прежнему было предельно простым, но работать стало гораздо эффективнее.

Итого, прогнав тесты и увидев счёт 395:254 против предыдущей версии, на этом успокоился. Это позволило мне взять 9-е место в финале.

Финал песочницы

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

Единственное крупное изменение — это то, что я откопал свою ветку в Git трёхнедельной давности, в которой у меня была симуляция движения противника упрощённым моим алгоритмом. На тот момент оно работало плохо, но я довёл её до ума, прогнал тесты, увидел,
что выигрывает у предыдущей версии почти вдвое по счёту и залил. Итого, на момент остановки я был на 10-м месте в общей таблице, что соответствует 4-му в финале песочницы.

Как это всё работает (техническая часть)

Заранее прошу прощения в случае, если будут неточности в терминологии. Также, я пишу по памяти, так что возможно, что где-то я опишу не финальную версию.

Итак, в основе лежат генетические алгоритмы. Хромосома состоит из нескольких генов:

• Дробное число в диапазоне -PI..PI, задающее направление движения
• Целое число в диапазоне 0..10, задающее количество повторений этого действия
• Дробное число от 0 до 1. Если значение выше какого-то порога, делаем прыжок

Генотип может включать в себя разное количество хромосом, но таким образом, чтобы суммарное число действий (включая повторения) было равно 40.

Изначально создаю несколько десятков случайных генотипов. К ним добавляю:

• Траекторию прямо на мяч
• Прямые траектории во все стороны, всего 10 штук со смещением в 36 градусов
• Генотип, который просто ничего не делает (без него бот всегда куда-то бежит, даже если он уже стоит в оптимальной точке)
• Лучший генотип с предыдущего тика

Дальше это всё симулируется и прогоняется через оценочную функцию. N лучших генотипов "выживают" и клонируются M раз с мутациями. При мутации каждый ген изменяется в заданном диапазоне с вероятностью 10%. Ну и это повторяется на протяжении нескольких поколений.
Скрещивания нет, в этой задаче не вижу в нём никакого смысла.

Итого, максимально возможное число траекторий на тик на одного футболиста выходило порядка 800, но по факту, в большинстве случаев было гораздо меньше, т.к. в части случаев (к примеру, когда в близком будущем мы точно не сможем коснуться мяча) движение футболистов заменялось простыми эвристиками. К тому же, N, M и число поколений зависели от ситуации на поле. В первую очередь, от расстояния до мяча. Также, просчёт прерывается досрочно (но не ранее 5-го поколения), если найдена траектория с приемлемой оценкой.

Макро

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

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

Если мяч на стороне противника и летит в сторону его ворот, можем сходить за нитро.

Если мой вратарь может ударить по мячу раньше, чем мой атакующий (плюс ещё несколько условий), то атакующий игнорирует мяч и бежит в точку посередине между мячом и воротами противника. Я перебрал много вариантов, куда именно ему бежать. В моём случае этот работал лучше всего.

Иначе, если мяч слишком далеко, нападающий бежит по прямой к ближайшей точке касания мяча с полом, в которой он может перехватить мяч (если в точку первого касания не успеваем — проверяем следующую и т.д.)

В противном случае (когда мяч досягаем), атакующий бежит туда, куда скажет ему функция оценки. Да, и ещё, если недалеко лежит нитро и мы можем его подобрать, подбираем.

В игре 3х3, второй атакующий с большей вероятностью будет стремиться к мячу и с меньшей побежит вперёд, ожидая пас от вратаря. Но если всё же побежит, то точка выбирается другая — ближе к центральной линии.

Также я каждый тик разово симулировал мяч на 100 тиков вперёд со 100 микротиками (с кешированием).

Эта траектория использовалась во многих местах. К примеру:

• Для определения точек касания мяча с полом
• Для выяснения, угрожает ли мяч моим воротам и нужно ли переключать вратаря в режим симуляции

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

К слову, писать Footballist было лень, слова Player, Robot были зарезервированы стратегией,
так что мой класс-обёртка назывался просто Dude :)

Симуляция

В большинстве случаев она проходила с одним микротиком, но в некоторых ситуациях переключалась на accurate режим с большим числом микротиков (в начале на 100, затем снизил до 50 в игре 2х2, поскольку тесты показали, что разница в результатах в пределах погрешности, и до 10 в 3х3, ибо в противном случае улетал в таймауты).

В accurate режим я переключался либо в момент подпрыгивания, либо находясь настолько близко к мячу, что возможна коллизия на очередном тике. Причём, здесь тоже была масса мелких костылей-хаков-оптимизаций, в которых я уже и сам не разберусь.

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

Кроме того, я также симулировал и других футболистов (и своих и чужих), если они находились в воздухе (а следовательно, их траекторию легче предсказать), либо были близки к мячу. Для противников в итоговой версии использовалась упрощённая версия моей же стратегии принятия решений, которая запускалась раз в 5 тиков (чаще не позволяло быстродействие).

При симуляции каждого персонажа, я просчитывал себя, мяч и других футболистов на 40 тиков вперёд (мой лимит количества действий в генотипе) и затем ещё на столько же тиков симулировал один только мяч.

Нитро

Простое до неприличия.

В финальной версии нитро включается всегда, если оно есть, если футболист находится в воздухе, и если он не бил мяч в последние несколько тиков.

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

Работало значительно хуже. Возможно, из-за недостатка глубины перебора.

Функция оценки

Сумма score-ов на каждом тике с затуханием на 2% в тик.

Самым большим весом, само собой, обладал гол. На его вес влияли несколько вещей:

• Расстояние от мяча до вражеского вратаря в момент гола (чем дальше — тем лучше)
• Y координата мяча (т.к. в верхней части ворот его гораздо тяжелее отбить)
• Скорость мяча по оси Z (которая направлена к вражеским воротам)

При атаке на меня, всё точно так же, только с противоположным знаком.

Далее, для атакующего, общий score зависел от:

• Расстояния от футболиста до мяча (чтобы он бежал к мячу даже если не может его ударить)
• Штрафа за прыжок (чтобы прыгал только если это принесёт столько очков, что они превысят этот штраф)
• Расстояния на очередном тике симуляции от мяча до противников
• Координаты Y мяча (чем он выше, тем меньше шансов у врага его перехватить)
• Косинуса угла между направлением мяча и центром вражеских ворот
• Флага, коснулся ли я мяча
• Флага, коснулся ли враг мяча
• Бонуса за подбор нитро

Также, был небольшой бонус за удар по вражескому игроку. Хотя по факту, это хоть и бывало, но редко.

Для вратаря:

• Бонус за расстояния до мяча, скорость мяча по Z, позицию мяча по Y
• Штраф за прыжок
• Штраф за нахождение мяча в зоне перед моими воротами
• Учитывалось расстояние до врагов и до моих нападающих (чтобы мяч летел от врагов подальше, но, по возможности, подлетел поближе к моим нападающим)
• И ещё несколько мелочей.

Machine Learning

Было самую малость в одной из веток гита в качестве эксперимента. Но мне кажется, упомянуть всё равно стоит. Довести до ума не успел (да и не уверен, что имело смысл).

В общем, я пытался с его помощью предсказывать, может ли враг перехватить мяч, исходя позиций и скоростей врага и мяча. Планировал использовать это в оценочной функции. Штрафовать траектории, которые возможно перехватить.

Но я сразу понимал, что не могу себе позволить не только нейросетку, но и вообще ничего серьезного, ибо это нужно было бы выполнять 80 раз на траекторию. Ну пусть даже 40 или 20, если считать не каждый тик, но всё равно, у меня не было вообще никакого запаса по времени, так что эти варианты я даже не рассматривал.

Вот что я сделал:

Я прогнал несколько игр с модифицированным ботом, в которых, при поиске траектории, я сохранял данные о себе и о мяче, а также флаг, была ли найдена траектория, при которой я перехватываю мяч.

Все координаты я считал относительно футболиста. Т.е. он у меня всегда был в координате [0,0,0], так что я сохранял всего 10 полей: относительную позицию мяча, вектор скорости мяча, вектор скорости футболиста, бинарный флаг перехвата. Сохранял датасет я только для центральной части поля, т.к. понимал, что простые алгоритмы не потянут ещё и учёт бортов.

Затем я этот датасет скормил DecisionTreeClassifier-у с max_depth = 7. Обученное дерево давало точность, насколько я помню, порядка 90%.

Далее я экспортировал дерево в набор if-ов (коим DecisionTree по сути и является).

Выглядело это примерно следующим образом:

public static boolean predict(double dude_vel_x, double dude_vel_y, double dude_vel_z, double ball_rel_pos_x, double ball_rel_pos_y, double ball_rel_pos_z, double ball_vel_x, double ball_vel_y, double ball_vel_z) {
   if (ball_vel_z <= 6.4765448570251465) {
      if (dude_vel_y <= -6.087389945983887) {
         if (ball_vel_z <= -20.188323974609375) {
            if (dude_vel_x <= 13.032730102539062) {
               if (ball_rel_pos_y <= -1.1829500198364258) {
                  return ball_vel_y <= 18.906089782714844;
               } else {
                  return false;
               }
            } else {
               return true;
            }
         } else {
// ............................

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

Шрёдинбаг

Где-то после первого раунда поймал я у себя этого редкого зверька.

Кто не знает, это такой баг, который находят только путём чтения кода, а найдя, разработчик недоумевает, как программа вообще могла работать. А в моём случае она ещё и в топ10 держалась.

В общем, баг был в том, что в функции копирования гена вызывался конструктор, в котором был пропущен необязательный аргумент, содержащий значение этого гена. В отсутствие этого аргумента, значение выбиралось случайным образом. Таким образом, при попытке скопировать ген, вместо копии, создавал новый рандомный экземпляр.

Фактически, вместо генетики у меня был случайный поиск, поскольку каждый тик просто генерировались несколько сот рандомных траекторий и выбиралась лучшая.

После исправления (заключавшегося в добавлении 2 символов в код), играть стала примерно в 3 раза лучше.

Ритуальные танцы

В какой-то момент времени я заметил, что футболисты иногда подпрыгивают без причины, находясь далеко от мяча, несмотря на штраф.

Объяснение оказалось таким, что момент прыжка я считал с точностью 100 микротиков. И иногда получалось так, что как раз на момент прыжка приходилась коллизия мяча со штангой. А в зависимости от точности расчёта именно в этот тик, предполагаемая траектория либо приводила к голу, либо нет.

Грубо говоря, мяч летит к воротам противника и ударяется в штангу. мой футболист, бегущий в другом конце поля, симулирует траекторию без прыжка (с 1 микротиком) и видит, что мяч не попадает в ворота.

Затем попадается другая траектория, с прыжком точно в момент удара мяча о штангу. А поскольку тик с прыжком я считаю с точностью 100 микротиков не только для футболиста, но и для мяча, вычисленный угол отскока мяча отличается от угла, полученного в траектории с 1 микротиком, и может случиться так, что мяч в этой более точной траектории попадает в ворота.

А следовательно, именно эта траектория будет выбрана и бот прыгнет.

В общем, путём исполнения ритуального танца с подпрыгиваниями, футболисты нашаманивали гол :)

Киллер-фича

Её нет

Тестирование

Гонял бесконечные игры в 8 потоков (по 4 на компьютере и на ноутбуке). Количество игр выбирал таким, чтобы оно было статистически значимым.

При значительном улучшении стратегии мог удовлетвориться полутысячей голов в сумме,
при более мелких правках, оставлял на ночь и тогда счёт уходил в тысячи.

Генетический подбор констант

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

Я пробовал играть партии по 100 000 тиков, но этого было совсем недостаточно. При небольшой разнице в силах (а обычно при подборе констант это именно так), на 100к тиков победитель слишком сильно зависит от случая. Нужно сыграть гораздо больше, чтобы быть уверенным в победителе. А я не мог себе позволить оставлять подбор на сутки и более, поэтому отказался от этой затеи.

В заключение

Традиционное спасибо организаторам. Задача была интересной. Жаль только что вынужден был пропустить почти половину чемпионата и толком ничего не сделал ни для нитро ни для трёх игроков.

В итоге, до самого конца наблюдал в песочнице, как моя стратегия выигрывает в режиме 2х2 без нитро со счётом 13:2 у какого-нибудь Mr.Smile, занявшего 3-е место в финале, а через несколько игр проигрывает ему же 12:2 в режиме 3х3 с нитро :)

Ну и конечно, видео из моего самописного визуализатора:

Только придётся наверное с этим визуализатором попрощаться в будущих чемпионатах.
Ибо с каждым разом всё больше убеждаюсь, что если претендуешь на нормальные места, единственный вариант — писать на ...

… ну вы поняли.

Надоело каждый раз упираться в медлительность Java и урезать силу стратегии, чтобы уложиться в отведённое время.

Надеюсь, кто-нибудь нашёл для себя что-то интересное или полезное в этом моём опусе с ноткой автобиографического характера :)