Хабрахабр

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

Всем привет!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Исходный код стратегии будет доступен здесь.

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

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

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

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

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