История второго места в Russian AI Cup 2018: CodeBall

    Всем привет!

    Я студент третьего курса, и в самом начале учёбы в университете я узнал про соревнования по искусственному интеллекту Russian Ai Cup, а позже и Mini Ai Cup, и начал в них активно участвовать, показывая неплохие результаты. В этот раз RAIC выпадал прямо на сессию, поэтому ничто не могло меня остановить :) И сегодня хочу рассказать вам, как мне удалось занять второе место.

    Правила конкурса можно почитать на сайте соревнования, а также в этой статье. Ссылка на мой профиль: russianaicup.ru/profile/TonyK.

    С одной стороны, задача в этом году была похожа на задачи прошлых лет, и казалось, что идейно решение будет очень похоже на предыдущие (Agar IO и Mad Cars); примерно через неделю я заскучаю и мне надоест участвовать.

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

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

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

    Первое, что я сделал, это переписал код симулятора из документации на С++, а потом замерил время работы симулятора на своём стареньком компьютере и на сервере. Во втором случае получилось вдвое быстрее, хотя это было ожидаемо. Прикинул, сколько раз и на какую глубину я смогу симулировать. Сразу стало понятно, что про честную симуляцию 100 микротиков (на сервере один тик физики разбивался на 100 «микротиков») придётся забыть, и нужно будет решать проблемы с точностью окольными путями.

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

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

    Траектория — это некий план действий. Изначально траектория представляла из себя вот что:

    • задаём действие под случайным углом;
    • на случайном тике траектории меняем угол на другой случайный;
    • прыгаем один раз в случайный тик траектории.

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

    В симулятор помещались все объекты: мои роботы, роботы оппонента и мяч. Оценка была наипростейшая: сумма расстояний от мяча до вражеских ворот во всех точках траектории и большие значения за гол кому-либо. Глубина симуляции 200 тиков. Враги предсказываются по последней скорости.



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

    Далее оказалось, что я считаю расстояние не до вражеских ворот, а до точки сбоку от центра поля (перепутал x и z), но на стратегию это никак не повлияло. Хорошо хоть, что после исправления хуже не стало. Такое часто бывает, когда пишешь бота.

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

    Оценка траекторий роботов в каждой точке умножалась на 0,9^глубина, я вывел этот коэффициент эмпирически, как и весь скоринг. Значения коэффициентов не менял очень долго по принципу «работает, и ладно».

    Начал побеждать топов и быстро подниматься в рейтинге. Закончился этап бета-тестирования.

    У меня долго не было идей по стратегии, версии отличались мелкими правками, исправлениями багов (оказалось, что среднюю силу отскока я считал как (MAX_HIT_E - MIN_HIT_E) / 2), а также оптимизировал симулятор. Важную роль играло количество траекторий, которые я успевал перебрать за тик, поэтому я сделал упор на оптимизацию. Поубирал синусы и квадратные корни. Добавил маловероятную нулевую скорость на траектории до или после смены угла. Незначительно изменил скоринг.

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

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

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

    Также в это время я начал выводить на сайте среди отладочной информации количество итераций, которые успевал выполнить. Их оказалось 250 по 200 тиков, итого у меня было 50 000 тиков симуляций за время, отведённое моей стратегии на тик.

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

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

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

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

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

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

    «Умный симулятор»


    Первым делом хотелось разобраться с точностью.

    Я симулировал по 100 микротиков за раз, хотя коллизия — или какое-нибудь другое событие, — происходила на каком-то одном из этих ста микротиков. Если это игнорировать, объекты сталкиваются позже, чем на самом деле (всегда на сотом микротике), и поэтому отскакивают иначе. К концу траектории эта маленькая ошибка может превращаться в большую неточность. Например, мы думаем, что мяч попадает во вражеские ворота, а в реальности в наши он отскочит от штанги.

    Нетрудно видеть, что в ситуации, когда коллизия происходит на i-ом микротике, вместо того чтобы считать все 100 микротиков, достаточно посчитать первые i - 1 микротиков за раз (по сути, шаг физики считается за определенное время dt, и сейчас это время будет t * (i - 1), где t — это время, соответствующее одному микротику). Теперь нужно просимулировать на 1 микротик (dt = t) и оставшиеся 100 - i микротиков. Получаем точно такой же результат всего за три симуляции вместо ста. Проблема только в том, что мы не знаем, на каком именно микротике произойдёт коллизия.

    Находясь на каком-то фиксированном тике симуляции, мы можем за одну симуляцию сделать любое количество микротиков от 1 до 100 и посмотреть, есть коллизия или нет. При этом картина будет такая: сначала касания нет, а начиная с определенного количества микротиков и вплоть до ста касание есть. Кроме очень редких случаев, когда вначале касания нет, потом на каком-то отрезке микротиков касание есть, а далее и до ста касания опять нет.

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

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

    Так были решены проблемы с точностью. Но из-за того, что в симуляции находилось 5 объектов, а по финальным правилам должно было находиться 7, и все они часто врезались, то в среднем дихотомии вызывались слишком часто, и это работало непозволительно долго. Поэтому я приступил ко второму этапу разработки симулятора — оптимизации.

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

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

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



    Теперь симулятор просчитывает не все объекты, а только динамические, а это, в среднем, полтора объекта вместо семи, и долгие дихотомии используются гораздо реже. Получилось очень быстро, и уже не придётся страдать в финале с дополнительными роботами — круто!

    26-я версия с новым симулятором и глубиной симуляций, уменьшенной с 200 до 100, была отправлена играть в первом раунде. Но она содержала некоторые баги, и явного преимущества не было.

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

    Далее я какое-то время оптимизировал, дебажил и, смотря на игры с более умными стратегиями, подобрал новые константы для скоринга. Стало сильно лучше, стратегия высоко поднялась в рейтинге и 37 версия достигла наилучшего результата из всех моих стратегий в песочнице за всё время до финала.

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

    С помощью решения уравнения научился вычислять последнее действие противника и начал прогнозировать его дальнейшее поведение. Добавил поддержку нитро: для действия выбирается случайная точка на поверхности сферы. Сделал много незначительных правок. Но особого прогресса не было. К началу второго раунда меня стабильно побеждали 4-5 топов

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

    Начиналась последняя неделя перед финалом.

    Первое сделанное мной улучшение заключалось вот в чем. В матчах в общем случае большинство проблем у моей, да и у любой другой стратегии возникает тогда, когда противник овладевает мячом. Он как-то бьёт по нему, пасует, в общем — контролирует. Предсказывать траекторию мяча и дальше планировать какие-то выгодные действия в этом случае невозможно, остается делать «что попало», пока противник не совершит ошибку и не передаст контроль над мячом моим роботам. А после этого надо стараться не совершать таких действий, которые могут привести к тому, что мяч опять окажется у врага.

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

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

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



    Оказалось, что можно без существенного ущерба для стратегии вычислять траекторию не каждый тик, а через один. Вдвое сократив время работы, я тем самым увеличил в 2 раза среднее количество итераций. Тут происходит некоторая магия. Кажется, что если считать траектории каждый второй тик и увеличить количество итераций в два раза, то среднее количество итераций не изменится. Но на самом деле, симулятор будет считать по два тика (200 микротиков) за симуляцию вместо одного. И траектории уже получатся глубиной 50, а не 100. Вот поэтому и увеличится вдвое среднее количество итераций.

    Оставалась пара дней до финала. Моя стратегия хоть и стала пропускать меньше голов из-за хорошего контроля мяча, но забивать лучше не стала. Поэтому пришлось её мотивировать коэффициентом при скоре за гол противнику. Чем быстрее будет забит гол, тем больше коэффициент. И этот коэффициент очень сильно растёт, чтобы превышать весь остальной скоринг и не бояться потенциального поля, когда до забивания гола осталось, например, 10 тиков.

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

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

    В финале у меня было 7 вариантов траекторий, когда робот находился на земле:

    • 2 угла без прыжка;
    • 2 угла с прыжком;
    • 2 угла с прыжком и нитро сонаправлено скорости;
    • 2 угла с прыжком и нитро компенсирует гравитацию;
    • 1 угол с прыжком;
    • 1 угол с прыжком и нитро сонаправлено скорости;
    • 1 угол с прыжком и нитро компенсирует гравитацию (не использовалось из за бага, заметил при написании статьи).

    и два варианта, когда робот находится в воздухе:

    • нитро в случайную точку на поверхности сферы и случайная сила удара;
    • случайная сила удара.

    За несколько часов до финала чувствовалась конкуренция, но моя стратегия явно была лучше. Казалось, что всё уже сделано, я не спал больше суток, и от меня уже ничего не зависело. Оставалось наблюдать. За два часа до финала Андрей заслал свой свежеиспеченный грааль и успешно занял первое место. С историей его участия можно ознакомиться здесь: habr.com/ru/post/440398.

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

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

    Исходный код стратегии будет доступен здесь.
    Mail.ru Group
    Building the Internet

    Comments 7

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

        Можно вот это подробней прокомментировать. Как именно это делается? Как роботы взаимодействуют друг с другом? Может ли один робот дать пас другому, например?
          0
          Да, пасы возможны. Но это не совсем пасы. Допустим один робот просто собирается ударить по мячу не зная, что будет делать второй робот. А после этого второй робот, зная что первый собрался ударить по мячу, как-то планирует свой удар, например бьет мяч в ворота, после того как по мячу ударит первый робот.
          На следущем тике игры первый робот уже знает, что если он не будет менять траекторию, то второй робот ударит в ворота и учитывает это. Это выглядит как пас, но на самом деле первый робот не собирался его давать, а просто бил мяч. В общем, получается, что роботы пытаются улучшить свои действия по очереди, и это часто приводит к пасам или другим многоходовочкам, когда например робот отпрыгивает от своего тиммейта, чтобы ударить мяч.
            0
            Понял. Еще вопрос: вы говорили про растянутый во времени поиск. Допустим, вы нашли на одном тике траекторию, но она неоптимальная. Как робот может ее улучшить в следующем тике?
              0

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

          0
          Спасибо за статью и за выложенный код! Можно начинать готовиться к следующему raic 2019 ))
            0
            А ещё можно неплохо подготовиться участвуя в Mini Aicups!

          Only users with full accounts can post comments. Log in, please.