Была среда, шло обычное скучное совещание на работе.
Дизайнер почесывал ухо, а тестировщик смотрел в телефон.
За окном завелась машина, а мне пришло письмо на телефон - понеслось Кубок России по искусственному интеллекту 2018 .
Никто вокруг ничего не подозревал, и в тот момент я уже точно знал, что буду делать в ближайшие полтора месяца.
Привет всем, меня зовут Андрей Токарев и мне бы хотелось поделиться своим опытом участия в Кубок России по искусственному интеллекту 2018 .
Что это?
Russian AI Cup — ежегодное соревнование по искусственному интеллекту, проводимое с 2012 года.Здесь нужно написать алгоритм, который управляет кем-то или чем-то, и этот кто-то или что-то конкурирует друг с другом.
В этом году нам пришлось управлять роботами, играющими в футбол.
У меня уже был некоторый опыт участия в подобных соревнованиях.
В частности, я участвовал в Russian AI Cup 2016 (без призового места) и Mini AI Cup 2018 (2 место).
Идти
Первым делом я создал свои классы игрового мира, объекты, взял 2- и 3-мерный вектор с прошлых соревнований и залил все это в репозиторий Git. Можно, конечно, использовать объекты из языкового пакета, но векторов там нет, их нельзя модифицировать, да и вообще удобнее использовать свои классы.Что я не переписывал, так это класс арены, он меня устраивал такой, какой был, и менять его не было необходимости.
Моделирование
У нас есть игровой мир, и что мы можем с ним сделать? Но оказывается, ничего страшного, пока мы не умеем моделировать игровой мир, мы даже не можем определить, полетит ли мяч в пустые ворота.Вот и пишем и списываем симуляцию.
Код моделирования не входит в языковой пакет, он предоставляется на незнакомом мне языке.
Но его синтаксис похож на C, поэтому копипаст + определение нужных функций, и сим готов на 90%.
Там, где нужно было редактировать руками, я старался делать это аккуратно, так как последующие ошибки здесь могут дорого стоить, да и отловить их будет непросто.
Пару ошибок мне все же удалось сделать, но все обошлось немного дорого.
Сразу стало понятно, что если использовать честную симуляцию (100 микротиков) то этого ни на что не хватит, гораздо выгоднее просчитать 100 вариантов с одним микротиком, чем один вариант со 100 микротиком.
Я все же оставил 2 микротика, чтобы расхождение не было слишком большим.
Основы стратегии
Итак, у нас есть игровой мир и мы можем смоделировать его изменение.Ну и что дальше? Здесь есть разные подходы.
Когда возможных ходов мало и глубина не очень велика, можно взять перебором: пройти все ходы, даже контрходы противника, а затем снова использовать на них свои ходы.
т. е.
минимакс.
Когда есть ходов много, их можно искусственно ограничить, например, можно брать направления, кратные 15 градусам, прыгать на каждом 10-м тике и использовать тот же минимакс.
Но этот подход, мне кажется, подходит, когда результат не слишком чувствителен к небольшим изменениям ходов; здесь отклонение на один градус в сторону робота приведет к большим отклонениям после столкновения.
Другая крайность — когда мы делаем ходы без грубой силы, используя некую эвристику.
Такой подход, возможно, и жизнеспособен, но создать сильного футболиста исключительно эвристичными методами очень сложно.
А вот комбинация двух методов выглядит многообещающе: сначала можно двигаться в случайном направлении, а затем закончить игру эвристикой, способной подбежать к мячу и подпрыгнуть в нужный момент. Ту же эвристику можно использовать и для прогнозирования ходов вашего оппонента.
Ранее я использовал нечто подобное на соревнованиях, и этот метод показал себя хорошо.
И вот пишем эвристику (на жаргоне RAIC, умник или просто умник)! Так как хотелось увидеть результат как можно быстрее, то умник писался на скорую руку и оказался довольно глупым (даже стыдно код приводить).
Я просто вычислил время, через которое робот сможет догнать мяч, исходя из текущей скорости мяча и максимальной скорости робота, и добежал до точки, где мяч находился бы в это время (столкновения были не учитывается).
Он не умел прыгать и даже не считался с высотой мяча; он мог легко пробежать под мячом, а если мяч уходил слишком быстро, он обычно бежал в противоположном направлении.
Так как умный прыгать не умел, то сначала я заставил его прыгать на фиксированное расстояние от мяча, а чуть позже выбор момента для прыжка лег на плечи великого рандома! Большим недостатком оказалось отсутствие рационального выбора прыжка, но об этом позже.
Но в целом чистый умник выглядел неплохо, а иногда даже забивал голы, правда тоже в свои ворота.
Далее нам понадобится функция оценки (EF).
Исходное ОФ выглядело примерно так: (1000 — тик) * цель + мяч.
z + некоторая функция взаимного положения робота и мяча, чтобы он подбежал к мячу, даже если не смог до него дотянуться.
Здесь цель может быть -1,0,1 в зависимости от того, есть ли цель и для кого, а тик — это тик от начала симуляции, при котором цель возникла.
Последнее необходимо для того, чтобы робот постоянно не откладывал достижение цели.
Теперь заставляем робота бежать в случайном направлении случайное количество тактов, затем передаем управление смарту, который подводит его к мячу, в случайный момент он подпрыгивает и бьет по мячу, промахиваясь.
Причем бежать лучше не к центру мяча, а со случайным сдвигом на небольшое расстояние, чтобы робот мог ударить под углом.
Моя симуляция длилась фиксированное время — 2 секунды, и в конце вызывался ОФ.
Этот сценарий повторялся несколько раз для каждого робота и на основе оценки выбирался лучший.
Пока что у этой стратегии есть серьёзный недостаток: у неё нет памяти — на каждом тике всё рассчитывается с нуля, а значит стратегия может видеть цель на одном тике, но не находить её на следующем.
Это не так, нам нужно это исправить — сохраняем лучший найденный вариант для каждого робота и повторно используем его в следующем тике.
Также теперь роботы в курсе дел друг друга, если, например, первый собирается отбить мяч, то второй не бежит за мячом, а пытается получить пас.
Вратарь
Нам нужен вратарь.Мой вратарь главным образом отличался от нападающего тем, что активировался при приближении мяча к воротам на некоторое расстояние, в противном случае он просто возвращался в исходную точку.
Нижняя граница
Теперь у нас есть хорошая базовая стратегия, которая может делать все, что вам нужно, и которую можно развивать в будущем.Возможно, все описанное выше кажется простым и логичным, но, честно говоря, в начале конкурса не было такой четкой картины стратегии, которая появилась ближе к концу, и на ее реализацию ушло две недели, а это уже 1 /3 конкурса.
Немного о тестировании
Со временем Граали, удваивающие силу игры, будут становиться всё реже и нам придётся выбирать изменения, дающие +10-20% прирост целей.И тогда оказывается, что такие небольшие увеличения не так-то просто обнаружить.
Для основательного результата нужны сотни забитых голов, а с частотой голов один раз в минуту это многие-многие часы игрового времени.
По этой причине я практически не тестировал стратегии на сервере, а проводил длительные локальные тесты на предыдущих версиях.
Но даже локально тестировать какое-либо изменение полдня было бы не очень удобно.
Поэтому я применил небольшую «хитрость» — протестировал урезанные стратегии.
Если, например, на сервере я перебирал по 50 вариантов на одного робота, то локально только 10, это позволяло мне запускать тесты за терпимое время.
Улучшения
Далее я опишу основные улучшения, и их оценку в следующем виде: на сколько процентов новая версия забивает больше голов, чем получает от старой.Те.
если, например, новый обыграет старого со счетом 120:100, это +20%, если наберет в 2 раза больше, то это +100%.
— Ваш вратарь должен отбивать голы.
Если у него это не получится, мы дадим ему больше времени и увеличим количество вариантов до х10. +15% — Иногда, когда вратарь бьет по мячу, он уходит в свободный полет и к тому моменту, когда ему удается вернуться на свое место, в его ворота уже забивают гол.
Сразу после удара по мячу стараемся вернуть его на место и добавить галочку, при которой он вернулся, к счету с небольшим отрицательным коэффициентом.
+20% — Дополнительный удар по мячу перед чужими воротами увеличивает шанс гола, за это дадим бонус в ОФ.
+60% —Ээкспериментируйте с нитро! До первого тура оставалось еще несколько дней, но я решил заранее протестировать нитро.
Интуитивно мне казалось, что нитро сильно повлияет на игровой процесс, так как на одном танке можно допрыгнуть до потолка или перелететь через все поле.
Для начала я научил использовать нитро только нападающего, и то только в воздухе, а пакеты пока не собирал.
Нитро использовалось во время полета в случайном, теперь трехмерном направлении.
Результат был мягко говоря не очень, больше +20% мне выжать не удалось, а использование нитро на земле вообще не принесло никаких результатов.
Так что вопрос с нитро был на время отложен, хотя с этого момента я старался проводить тесты с включенным нитро.
- Слишком много случайности! Случайность - это, конечно, хорошо, она иногда выдает приемы, о которых самостоятельно даже не додумаешься, но с другой стороны, когда ее слишком много, вероятность того, что все совпадет, очень мала.
И у меня этого было слишком много.
Я решил попробовать перевести момент прыжка на аналитическую основу.
Поскольку в воздухе не было горизонтального ускорения (забудем про нитро), то нетрудно было вычислить момент встречи робота и мяча (t1), и высоту мяча в этот момент (h1).
Теперь рассчитаем время (t2), через которое робот достигнет высоты h1, если прыгнет сейчас.
Здесь мы получаем квадратное уравнение; если оно не имеет решения или t2 < t1, then it’s too early to jump, otherwise we jump. Результат меня немного шокировал, прикрутив правильный прыжок и нападающему, и вратарю, тесты показали +200%, т. е.
новая версия обыграла старую в 3 раза по голам, настоящий Грааль! Это было 17 января, загрузив стратегию на сервер, она набрала рейтинг 200+ при победной серии в 20 игр и какое-то время лидировала в песочнице.
— Мы учим вратаря играть.
Пока мой вратарь не активизировался, он стоял как столб.
Легкая прогулка в стороны: x = ball.x/4 дала небольшой прирост. — Соперника надо не предугадывать, а угадывать! Смотря игры, я заметил, что часто забиваю гол после того, как вратарь отбивает мяч прямо в соперника, и он с ходу забивает мне гол.
Чтобы отбить мяч вокруг противника, вы должны сначала определить, где он может находиться на n-м такте.
Нитро, конечно, не будем учитывать.
Скорость робота я еще смог определить аналитически, вроде бы это пересечение двух окружностей.
Но справиться с доступной территорией мне не удалось.
Ну и черт с ним, мы программисты (не по образованию), пусть машина делает за нас математику.
Делим плоскость на n направлений, перемещаем робота в каждом направлении, конечными точками будут вершины многоугольника, определяющего радиус действия.
Как это использовать? Я добавил галочку, при которой соперник сможет впервые коснуться мяча, с хорошим коэффициентом в ОФ.
Поскольку теперь противником считался не конкретный сценарий действий, а определенное облако досягаемости, я удалял вражеских роботов, как только они соприкасались с землей.
Результат +40%.
Кроме того, у такого подхода есть два больших преимущества: удаление вражеских роботов, во-первых, ускоряет симуляцию, а это в свою очередь дает возможность перебрать больше вариантов, во-вторых, нам не придется заморачиваться с контролем противника.
Вывод: прибыль! - Глупые ошибки, но что бы мы без них делали? В официальном симуляторе есть две строчки:
Теги: #Алгоритмы #искусственный интеллект #спортивное программирование #russian ai cup #соревнования роботов #russian ai cup 2018if abs(ball.position.z) > arena.depth / 2 + ball.radius:
-
Nosql И Антивакцинизм
19 Oct, 24 -
Цена Ошибки И Ее Последствия В Google
19 Oct, 24 -
Сафари В Windows
19 Oct, 24 -
Язык Программирования Петух
19 Oct, 24
