История второго места в 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 — это сложный конкурс и призовые места даются участникам очень и очень непросто. Когда участник находится вверху таблицы, для него это не просто развлечение — это борьба. Во время написания сильной стратегии нужно учитывать множество мелочей. Каждое принятое решение может существенно повлиять на результат.
Исходный код стратегии будет доступен здесь.
