Была среда, шло обычное скучное заседание на работе. Дизайнер чесал за ухом, а тестировщик уткнулся в телефон. За окном завелся автомобиль, и мне пришло письмо на телефон — стартовал 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%. Там где нужно было править руками, старался делать аккуратно, так как потом ошибки здесь могут дорого обойтись, и ловить их будет непросто. Пару ошибок мне все же удалось допустить, но все обошлось малой кровью.
Сразу стало понятно что если использовать честную симуляцию (100 микро тиков) то этого мало на что хватит, гораздо выгодней просчитать 100 вариантов с одним микротиком чем один вариант с 100 микротиков. Я все же оставил 2 микротика чтобы расхождение было не слишком большим.
Основы стратегии
И так у нас есть игровой мир и мы умеем симулировать его изменение. И что же дальше?
Тут есть разные подходы. Когда возможных ходов мало и глубина не очень большая, можно брать грубой силой: перебирать все ходы, даже ответные ходы соперника, на них снова свои ходы… т.е. минимакс. Когда ходов много можно их искусственно ограничить, на пример можно брать направления кратные 15-и градусам, прыгать на каждый 10-й тик, и использовать тот же минимакс. Но такой подход как мне кажется подходит, когда результат не слишком чувствителен к мелким изменениям в ходах, здесь же отклонение в один градус направления робота приведет к большим отклонениям после столкновения.
Другая крайность, когда делаем ходы без перебора, некоторой эвристикой. Этот подход может быть жизнеспособным, но создать сильного футболиста чисто эвристикой очень сложно.
А вот совмещение двух методов выглядит перспективным: можно сначала двигаться в случайном направлении, а потом доигрывать эвристикой которая умеет подбегать к мячу и прыгать в нужный момент. Ту же эвристику по совместительству можно использовать и для предсказания ходов соперника. Ранее я уже использовал нечто подобное на соревновании и данный метод более менее не плохо себя проявил.
И так пишем эвристику (в РАИК-овском жаргоне смарт гая или просто смарта)!
Поскольку как можно быстрее хотелось увидеть результат, смартгай был написан на скорую руку и получился достаточно тупым (даже код приводить стыдно). Я просто вычислял время, через которое робот сможет догнать мяч исходя из текущей скорости мяча и максимальной скорости робота, и бежал в точку, где окажется мяч в это время (коллизии не учитывались). Он не умел прыгать и даже не учитывал высоты мяча, мог спокойно пробежать под мячом, а если мяч отдалялся слишком быстро, то вообще бежал в противоположную сторону. Поскольку прыгать смарт не умел, то сначала я заставлял его прыгать на фиксированном расстоянии от мяча, а чуть позже выбор момента прыжка лег на плечи великого рандома! Отсутствие рационального выбора прыжка оказалось большим недостатком, но об этом позже. Но в целом чистый смарт выглядел не плохо, и иногда даже забивал голы, хотя и в свои ворота тоже.
Далее нам нужна оценочная функция (ОФ).
Изначальная ОФ выглядела примерно так: (1000 — tick) * goal + ball.z + некоторая функция от относительного положения робота и мяча чтобы он подбегал к мячу даже если не может до него достать. Здесь goal может быть -1,0,1 в зависимости от того есть ли гол и кому, а tick это тик от начала симуляции на котором произошел гол. Последнее нужно чтобы робот не откладывал постоянно гол.
Теперь заставляем робота бежать в случайном направлении случайное количество тиков, потом передаем управление смарту, который ведет его к мячу, в случайный момент он прыгает и бьет по мячу промахивается. Причем бежать лучше не к центру мяча, а со случайным сдвигом на не большое расстояние, чтобы робот мог бить под углом.
Симуляция у меня длилась фиксированное время — 2 секунды, а в конце вызывалась ОФ. Такой сценарий повторялся несколько раз для каждого робота и выбирался лучший на основе оценки.
Пока у данной стратегии есть серьезный недостаток: у нее нету памяти — на каждом тике все вычисляется с нуля, это значит стратегия может на одном тике увидеть гол, а на следующем не найти его. Это не дело, нужно исправить — сохраняем лучший найденный вариант для каждого робота и переиспользуем в следующем тике. Так же теперь роботы в курсе дел друг друга, если например первый собирается отбить мяч, то второй бежит не за мячом, а старается принять пас.
Вратарь
Нам нужен вратарь. Вратарь у меня в основном отличался от нападающего тем что активировался когда мяч приближался на некоторое расстояние к воротам, в противном случае просто возвращался на свою базовую точку.
Итог
Теперь мы имеем не плохую базовую стратегию, которая умеет все самое необходимое и на которую в дальнейшем можно строится.
Возможно все описанное выше кажется простым и логичным, но если честно в начале соревнования не было такой четкой картины стратегии которая появилась ближе к концу, и на реализацию данного ушло две недели, а это уже 1/3 соревнования.
Немного о тестировании
Со временем Граали, которые удваивают силу игры будут встречаться все реже и реже, и нам придется выбирать изменения, которые дают +10-20% прироста по голам. И тут оказывается, что такие малые приросты не так уж и легко выявить. Для досконального результата нужны сотни забитых голов, а при частоте голов раз в минуту это много-много часов игрового времени. По этой причине я почти не тестировал стратегии на сервере, а гонял длинные локальные тесты против предыдущих версий. Но даже локально тестировать любое изменение по пол дня было бы не очень удобно. По этому, я применил небольшую «хитрость» — тестировал урезанные стратегии. Если на пример на сервере я перебирал 50 вариантов за робота, то локально только 10, это позволяло гонять тесты за терпимое время.
Улучшения
Далее я опишу основные улучшения, и их оценку в следующем виде: на сколько процентов новая версия забивает голов больше, чем получает от старой. Т.е. если например новая обыгрывает старую со счетом 120:100 это +20%, если забивает в 2 раза больше то это + 100%.
— Вратарь ваш должен голы отбивать. Если у него не получается, дадим ему больше времени, увеличим количество вариантов вплоть до x10. +15%
— Иногда, когда вратарь отбивает мяч, он отправляется в свободный полет и пока он успеет вернуться на место, ему уже забивают гол. Сразу после попадания по мячу пытаемся вернуть его на место и добавляем тот тик, на который он вернулся в оценку с небольшим отрицательным коэффициентом. +20%
— Дополнительный пинок по мячу перед чужими воротами увеличивает шанс гола, дадим за это бонус в ОФ. +60%
— Эксперимент с нитро! До первого раунда оставалось еще несколько дней, но я решил заранее прощупать нитро. Интуитивно мне казалось, что нитро очень сильно повлияет на геймплей, так как на одном баллоне можно подпрыгнуть до потолка или перелететь через все поле. Для начала я научил использовать нитро только нападающего, да и то только в воздухе, а пакеты пока не собирал. Нитро использовалось во время полета в случайном теперь уже 3-х мерном направлении. Результат был мягко говоря не очень, более +20% у меня не получилось выжать, а использование нитро на земле вообще не принесло результатов. Так что вопрос с нитро был на время отложен в сторону, хотя с этого момента проводить тесты старался с включенным нитро.
— Слишком много рандома! Рандом это конечно хорошо, он иногда выдает приемы, до которых сам и не додумаешься, но с другой стороны, когда его слишком много, вероятность того, что все совпадет очень маленькая. А у меня его было слишком много. Я решил попробовать перенести момент прыжка на аналитическую основу. Поскольку в воздухе горизонтального ускорения не было (забудем о нитро), то можно было легко вычислить момент встречи робота и мяча (t1), и высоту мяча в этот момент (h1). Теперь вычисляем время (t2) через которое робот окажется на высоте h1, прыгни он сейчас. Здесь получается квадратичное уравнение, если оно не имеет решения или t2 < t1, то прыгать рано, в противном случае прыгаем.
Результат меня немного шокировал, прикрутив правильный прыжок и к нападающему и вратарю, тесты показали + 200%, т.е. новая версия обыгрывала старую в 3 раза по голам, настоящий Грааль! Было 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) за то что воздержался от участия и тем самым повысил мои шансы на победу.
Удачи всем в следующем РАИК-е!
Автор: T1024
