Хабрахабр

Russian AI Cup 2018, история 9 места

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

Сама задача несколько напоминала 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. В общем, искал баланс между точностью и глубиной просчёта и быстродействием.
Кроме борьбы с быстродействием, внёс ещё пару изменений:

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

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

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

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

На тот момент оно работало плохо, но я довёл её до ума, прогнал тесты, увидел,
что выигрывает у предыдущей версии почти вдвое по счёту и залил. Единственное крупное изменение — это то, что я откопал свою ветку в 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, ибо в противном случае улетал в таймауты).

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

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

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

Нитро

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

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

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

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

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

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

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

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

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

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

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

Для вратаря:

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

Machine Learning

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

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

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

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

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

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

Обученное дерево давало точность, насколько я помню, порядка 90%.
Далее я экспортировал дерево в набор if-ов (коим DecisionTree по сути и является).
Выглядело это примерно следующим образом: Затем я этот датасет скормил DecisionTreeClassifier-у с max_depth = 7.

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) else { return false; } } else { return true; } } else {
// ............................

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

Шрёдинбаг

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

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

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

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

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

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

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

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

Киллер-фича

Её нет

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

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

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

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

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

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

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

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

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

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть