Итак

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

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

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

^[4]

Чтобы жизнь нам не казалось излишне сладкой, разработчики, помимо недетерминированности игрового мира, ещё и раздробили игровой тик на 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 с нитро :)

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

^[5]

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

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

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

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

Автор: lamik

Источник ^[6]