Хабрахабр

[Из песочницы] История участия (и победы) в Russian AI Cup 2018 — CodeBall

Была среда, шло обычное скучное заседание на работе. Дизайнер чесал за ухом, а тестировщик уткнулся в телефон. За окном завелся автомобиль, и мне пришло письмо на телефон — стартовал Russian AI Cup 2018. Вокруг никто ни о чем не подозревал, а я в этот момент уже точно знал, чем буду заниматься в следующие полтора месяца.

Привет всем, меня зовут Андрей Токарев и я хотел бы поделится опытом участия в Russian AI Cup 2018.

Что это?

Russian AI Cup — ежегодное соревнование по искусственному интеллекту, проводимое с 2012 года. Здесь нужно написать алгоритм который управляет кем-то или чем-то, и эти кто-то или что-то соревнуются между собой. В этом году нужно было управлять роботами играющими в футбол.

В частности я участвовал в Russian AI Cup 2016 (без призового места) и Mini AI Cup 2018 (2-е место).
У меня уже был некоторый опыт выступления в подобных соревнованиях.

Поехали

Первым делом я создал свои классы игрового мира, объектов, взял 2-х и 3-х мерный вектор с прошлых соревнований и залил все это в Гит репозиторий. Можно конечно использовать объекты из языкового пакета, но там нет векторов, их нельзя модифицировать, да и вообще удобней пользоваться своими классами. То чего я не стал переписывать так это класс arena, он меня устраивал так как есть, и изменять его не было надобности.

Симуляция

Вот есть у нас игровой мир, и что с этим можно делать?

Так что пишем списываем симуляцию. А оказывается ничего, пока не умеем симулировать игровой мир, даже не определить залетит ли мяч в пустые ворота. Зато синтаксис его Си подобный, так что копипаст + определение нужных функций, и сима готова на 90%. Код симуляции не входит в состав языкового пакета, он предоставлен на незнакомом мне языке. Пару ошибок мне все же удалось допустить, но все обошлось малой кровью. Там где нужно было править руками, старался делать аккуратно, так как потом ошибки здесь могут дорого обойтись, и ловить их будет непросто.

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

Основы стратегии

И так у нас есть игровой мир и мы умеем симулировать его изменение. И что же дальше?
Тут есть разные подходы. Когда возможных ходов мало и глубина не очень большая, можно брать грубой силой: перебирать все ходы, даже ответные ходы соперника, на них снова свои ходы… т.е. минимакс. Когда ходов много можно их искусственно ограничить, на пример можно брать направления кратные 15-и градусам, прыгать на каждый 10-й тик, и использовать тот же минимакс. Но такой подход как мне кажется подходит, когда результат не слишком чувствителен к мелким изменениям в ходах, здесь же отклонение в один градус направления робота приведет к большим отклонениям после столкновения.

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

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

И так пишем эвристику (в РАИК-овском жаргоне смарт гая или просто смарта)!

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

Далее нам нужна оценочная функция (ОФ).

Здесь goal может быть -1,0,1 в зависимости от того есть ли гол и кому, а tick это тик от начала симуляции на котором произошел гол. Изначальная ОФ выглядела примерно так: (1000 — tick) * goal + ball.z + некоторая функция от относительного положения робота и мяча чтобы он подбегал к мячу даже если не может до него достать. Последнее нужно чтобы робот не откладывал постоянно гол.

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

Такой сценарий повторялся несколько раз для каждого робота и выбирался лучший на основе оценки. Симуляция у меня длилась фиксированное время — 2 секунды, а в конце вызывалась ОФ.

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

Вратарь

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

Итог

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

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

Немного о тестировании

Со временем Граали, которые удваивают силу игры будут встречаться все реже и реже, и нам придется выбирать изменения, которые дают +10-20% прироста по голам. И тут оказывается, что такие малые приросты не так уж и легко выявить. Для досконального результата нужны сотни забитых голов, а при частоте голов раз в минуту это много-много часов игрового времени. По этой причине я почти не тестировал стратегии на сервере, а гонял длинные локальные тесты против предыдущих версий. Но даже локально тестировать любое изменение по пол дня было бы не очень удобно. По этому, я применил небольшую «хитрость» — тестировал урезанные стратегии. Если на пример на сервере я перебирал 50 вариантов за робота, то локально только 10, это позволяло гонять тесты за терпимое время.

Улучшения

Далее я опишу основные улучшения, и их оценку в следующем виде: на сколько процентов новая версия забивает голов больше, чем получает от старой. Т.е. если например новая обыгрывает старую со счетом 120:100 это +20%, если забивает в 2 раза больше то это + 100%.

Если у него не получается, дадим ему больше времени, увеличим количество вариантов вплоть до x10. — Вратарь ваш должен голы отбивать. +15%

Сразу после попадания по мячу пытаемся вернуть его на место и добавляем тот тик, на который он вернулся в оценку с небольшим отрицательным коэффициентом. — Иногда, когда вратарь отбивает мяч, он отправляется в свободный полет и пока он успеет вернуться на место, ему уже забивают гол. +20%

+60% — Дополнительный пинок по мячу перед чужими воротами увеличивает шанс гола, дадим за это бонус в ОФ.

До первого раунда оставалось еще несколько дней, но я решил заранее прощупать нитро. — Эксперимент с нитро! Для начала я научил использовать нитро только нападающего, да и то только в воздухе, а пакеты пока не собирал. Интуитивно мне казалось, что нитро очень сильно повлияет на геймплей, так как на одном баллоне можно подпрыгнуть до потолка или перелететь через все поле. Результат был мягко говоря не очень, более +20% у меня не получилось выжать, а использование нитро на земле вообще не принесло результатов. Нитро использовалось во время полета в случайном теперь уже 3-х мерном направлении. Так что вопрос с нитро был на время отложен в сторону, хотя с этого момента проводить тесты старался с включенным нитро.

Рандом это конечно хорошо, он иногда выдает приемы, до которых сам и не додумаешься, но с другой стороны, когда его слишком много, вероятность того, что все совпадет очень маленькая. — Слишком много рандома! Я решил попробовать перенести момент прыжка на аналитическую основу. А у меня его было слишком много. Теперь вычисляем время (t2) через которое робот окажется на высоте h1, прыгни он сейчас. Поскольку в воздухе горизонтального ускорения не было (забудем о нитро), то можно было легко вычислить момент встречи робота и мяча (t1), и высоту мяча в этот момент (h1). Здесь получается квадратичное уравнение, если оно не имеет решения или t2 < t1, то прыгать рано, в противном случае прыгаем.

новая версия обыгрывала старую в 3 раза по голам, настоящий Грааль! Результат меня немного шокировал, прикрутив правильный прыжок и к нападающему и вратарю, тесты показали + 200%, т.е. Было 17-е января, загрузив стратегию на сервер, она победной серией из 20 игр набрала 200+ рейтинга и на какое-то время возглавила песочницу.

Пока мой вратарь не активировался он стоял как столб. — Учим вратаря играть. Легкая прогулка в стороны: x = ball.x/4 дала небольшой прирост.

Просматривая игры, я заметил, что часто получаю гол после того как вратарь отбивает мяч прямо на соперника и тот на лету забивает мне гол. — Соперника нужно не предсказывать, а предполагать! Нитро конечно же в учет брать не будем. Чтобы бить мяч в обход соперника нужно сначала определять, где он может быть на n-ом тике. А вот с доступной территорией не справился. Скорости робота я еще мог определить аналитически, там вроде получается пересечение двух окружностей. Делим плоскость на н направлений, двигаем робота в каждом из направлений, конечные точки будут вершинами многоугольника, который и определяет досягаемость. Ну и черт с ним, мы же программисты (не по образованию), пусть машина считает за нас.

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

Кроме того этот подход имеет два жирных плюса: удаление вражеских роботов во первых ускоряет симуляцию, а это в свою очередь дает возможность перебирать больше вариантов, а во вторых нам не надо заморачиваться управлением соперника. Результат +40%. Вывод: профит!

В официальном симуляторе есть две строки: — Глупые ошибки, а как же без них.

if abs(ball.position.z) > arena.depth / 2 + ball.radius: goal_scored()

Не знаю кто как, но я оставил функцию abs() так как есть, а зря. Си-шная abs() (не путать с std::abs()) принимает целые значения, а значит десятичные обрезаются. На практике это означает что я фиксировал гол, только когда мяч уже был на целый метр за линией гола. Заменяем abs() на fabs()! Не первый раз меня этот abs() подводит.

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

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

  • Во время прыжка два дополнительных микротика.
  • Когда совмещаем много микротиков то в перемещении правильней использовать среднюю скорость, а не конечную.
  • Бинарным поиском находим тик в котором происходит столкновение, и выполняем два подтика: один до столкновения, другой после. (Столкновение мяча с ровной поверхностью я не учитывал, там расхождение мне казалось незначительным.)
  • Бег по кривой поверхности все еще давал большие расхождения и иногда вратарь из за этого промахивался. По этому, когда мой вратарь находился на кривой поверхности, я использовал 10 микротиков.

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

Что имеем

Благодаря большому количеству значительных улучшений стратегия уверенно росла в рейтинге, а перед вторым раундом едва ли не дошла до исторического рубежа — 5000 рейтинга Эло, уверенно закрепившись на первом месте.

Иногда даже не верится какие комбинации выдает рандом. Спасибо доброму анониму из сообщества за находку.

Последняя неделя

В связи с таким хорошим отрывом я позволил себе не гнаться за мелкими улучшениями, а поискать что-то более глобальное, в особенности что касается игр 3х3. Однако эксперименты направленные на более командную игру, или привить третьему игроку особую роль, или научить во время выходить вратаря, окончились неудачей. Целая неделя была потрачена почти безрезультатно. Не смотря на это за пару дней до финала я все еще лидировал в рейтинге.
И вот подошел последний день перед финалом и я начинаю проигрывать одному, потом другому и даже третьему конкуренту. Если не добавить можно вообще без призового места остаться. Всю неделю ничего не получалось, что я могу сделать в последний день? Настроение было — хоть сдавайся.

Воскрешение

Посмотрев пару проигранных игр я заметил что все скачут как козлы на нитро, пасуют мяч в воздухе, а мои не могут достать. Я попробовал самое простое что может привести к данному поведению — добавил высоту мяча на момент удара с солидным коэффициентом в ОФ. Результат +50%, ничего себе! Вдохновившись результатом, я интенсивно начал крутить параметры (чем пренебрегал по ходу всего соревнования), добавил новые варианты перебора, в конце добавил контроль времени, что позволило по максимуму использовать время без риска для жизни. К концу дня получилось +150-200%, т.е. новая версия почти в три раза по голам обыгрывала предыдущую! Да да, ту самую которая почти неделю перед финалом провисела на первом месте и достигла невиданный ранее в истории чемпионата рейтинг 5000+. На сервере стратегия успешно прошла тестирование за пару часов до финала. После этого я подготовил ее к финальному запуску: отключил assert-ы, добавил проверки деления на ноль, снова залил на сервер и переключил себя в режим ожидания.

Финал, часть первая

Первая часть финала проходила ночью. Следил за результатами, пока не уснул, утром встал рано. Было сыграно 3 волны (в одной волне каждый играет с каждым), я проиграл лишь одну игру против TonyK, а поскольку Антон еще иногда проигрывал другим игрокам, я лидировал с отрывом в 7 очков (за победу дают 2 очка). Довольно серьезный отрыв для 3-х волн, но не достаточно чтобы расслабиться.

Было внесено несколько изменений, но поскольку все тестировалось в спешке, даже не был полностью уверен, что эффект положителен. В последний день естественно ничего серьезного я не предполагал делать, в основном крутил параметры. А вот Антон заметно прибавил и по крайней мере стал играть не хуже меня. В общем прирост был 0-20%.

Делать нечего, пришлось отправить то что есть, и надеяться на удачу и запас очков.

Финал, часть вторая

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

Конечный результат: 352 победы и 2 поражения (оба от Антона), 1-е место с отрывом в 12 очков.

Благодарности и прочая фигня

В целом задание нынешнего года мне очень понравилось, оно было “под меня” (симуляция это мое, и трехмерность меня не отпугивает) и матчи были зрелищными, думаю было интересно наблюдать не только участникам.

Хотелось бы выразить благодарность организаторам за замечательный конкурс.

Также хочу поблагодарить всех участников, особенно Антона Козловского (TonyK) за конкуренцию в финале, Ивана Тямгина (tyamgin) за конкуренцию в песочнице и Алексея Дичковского (Commandos) за то что воздержался от участия и тем самым повысил мои шансы на победу.

Удачи всем в следующем РАИК-е!

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

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

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

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

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