Продолжая хорошую традицию «раскрытия секретов» победителей ежегодного конкурса Russian AI Cup от Mail.Ru, представляю вниманию всех интересующихся эту статью. Описывать механику игрового мира и прочие правила я не буду, если же вдруг найдутся интересующиеся данной статьей, но не знающие правил, то они смогут найти их на официальной странице чемпионата.
В этом году, в отличие от прошлого, была задача «с физикой», а не пошаговая, что и определило мой повышенный интерес к мероприятию. Вообще, сразу хочу сразу сказать, что под физикой я имею в виду не использование phys2d или еще какого физического движка, а, скорее, определенный набор свойств игрового мира. Первое важное свойство — это непрерывность во времени и пространстве: небольшие смещения объектов или задержка управляющего воздействия также несильно меняют результат. Второе свойство — это достаточная сложность законов движения объектов, так что прямое моделирование мира с абсолютной точностью невозможно (по крайней мере, за разумное время). Невозможность точного моделирования заставляет делать то, что делается в реальной физической науке — определять, какие явления являются наиболее важными в рассматриваемом случае и строить приближенную модель системы. Касательно задачи конкурса, важным при моделировании являлось достаточно точное предсказание свободного движения шайбы и хоккеиста, а также отскока шайбы от бортов (не в районе ворот). Еще полезно было бы иметь предсказание отскока от бортов хоккеиста и шайбы от вратаря. Сразу хочу обратить внимание на слова «достаточно точное» — добиваться абсолютного, побитового совпадения результатов предсказания с тем, что выдает движок игры никакого смысла нет. И те люди, которые этим занимались, бесполезно тратили время. Например, у меня в финале никак не учитывалось изменение ускорения и скорости поворота при падении выносливости в процессе предсказания движения, учитывалось только ее значение на текущий момент.
Еще хочу сказать по поводу случайностей, которых в этом году было заметно больше, чем в прошлых. Случайность добавляет сложности точного предсказания (делает его принципиально невозможным), однако это плохой, «читерский» способ. Настоящая «глубокая» физика позволяет строить все более точные модели (ценой вычислительной сложности или более продвинутых алгоритмов), случайность же не дает этой глубины. Да и на непрерывность процессов она влияет отрицательным образом. С практической точки зрения, дополнительный разброс результатов матчей только усложняет тестирование. Чемпионат этого года будет первым, в которым я, вообще, не занимался подбором оптимальных коэффициентов, ибо даже длинные получасовые матчи не давали четкого понимания силы стратегий. Но, хватит с отступлениями, перехожу к хронологическому описанию хода соревнования.
Бета-тест
Большую часть недели бета-теста я потратил на реверс игровой физики. Причем мне, физику по образованию, гораздо проще получить требуемые формулы с помощью экспериментов, а не декомпиляцией local-runner-а. Все одиночные контакты (удары), кроме столкновения двух хоккеистов (которым я, в принципе, не занимался) и фронтального удара шайбы об вратаря (в котором участвовало чье-то скрытое вращение) я научился предсказывать с точностью float-ов. В устройстве мира хватало странных и хитрых моментов, например устройство штанги (секция длинной 25 единиц с десятикратно уменьшенным отскоком), или выталкивающая стенка для хоккеистов в воротах (причем без обнуления скорости), или положение шайбы, удерживаемой хоккеистом (с компенсацией скорости без учета трения), однако все эти мелочи не имели особого значения для стратегии (да еще менялись в процессе чемпионата), поэтому останавливаться на них не буду.
Вторая важная вещь, которую я успел сделать за бета-тест — это расчет диапазона углов, при которых происходит попадание в ворота. Это предсказание я делал из чисто геометрических соображений, без какого-либо моделирования полета шайбы. В качестве первого угла я брал направление на дальний угол ворот, после считал время полета шайбы по этому направлению. Дальше находил положение вратаря на это время и считал угол, при котором шайба пролетит, касаясь вратаря в этом положении. Потом пересчитывал время полета по новому направлению и повторял процесс несколько раз. Тут стоит сказать, что в это вычисление закрался досадный баг, который приводил к завышенной оценке угла. И хотя я, просматривая игры, неоднократно замечал странные удары и подозревал наличие бага, до финала я его так и не обнаружил. Однако, это не помешало моей стратегии выиграть во втором раунде (это к вопросу о достаточной точности).
Ключевой алгоритм
После окончания бета-теста я завершил эксперименты с физикой и занялся, собственно, стратегией. В отличие от танков, где я, в первую очередь, делал защиту, в этом году я стартовал от атаки. Нормальную защиту, я, в итоге, так и не сделал, она так и осталась «набором костылей», хотя и работала достаточно хорошо. Ключевым для атакующей части стратегии (а затем и для всех остальных ее частей) стал алгоритм выхода на цель под определенным углом, на котором я остановлюсь подробнее.
Рассмотрим сначала метод наибыстрейшего достижения определенной точки (без учета стенок и других хоккеистов) с нулевой начальной скоростью. Ненулевая начальная скорость приводит только к фиксированному смещению области достижимых точек на каждый временной шаг, не меняя саму конфигурацию области. Достаточно хитрые геометрические соображения (сами соображения я приводить не буду ввиду их сложности и отсутствия математической строгости) приводят к следующему набору «оптимальных» траекторий.
- Поворот влево/вправо с ускорением вперед/назад на угол, меньший 90°, затем продолжение движения без поворота не меняя ускорения.
- Поворот влево/вправо с ускорением назад/вперед на угол, меньший 90°, затем реверс ускорения с продолжением поворота в течение следующих 90°, затем продолжение движения с ускорением, но без поворота.
Ввиду отсутствия строгости, реальные оптимальные траектории могут немного отличаться от этих, однако это не принципиально (см. рассуждения выше о достаточной точности). Таким образом, траектории параметризуются флагом типа ускорения на основном участке траектории (вперед/назад) и направления поворота (влево/вправо), а также временем окончания поворота. В случае, если это время больше времени поворота на 90°, то в начале траектории движения присутствует участок с обратным направлением ускорения продолжительностью [время окончания поворота] − [время поворота на 90°].
Аналогичные геометрические рассуждения показывают, что если надо не просто достичь точки, но и выйти под определенным углом, то «оптимальная» траектория при достаточно большом расстоянии до цели выглядит как соединенные своими прямолинейными участками две «оптимальные» траектории для случая простого достижения точки. Т. е. поворот с возможным реверсом в начале, затем движение без поворота, затем конечный поворот с возможным реверсом в конце. Параметрами траектории будут три флага — два направления поворота и тип ускорения в середине, а также две продолжительности поворота (не считая общей продолжительности пути) — в начале и конце. По этим параметрам и необходимо проводить оптимизацию.
Т. к. параметров как минимум два, то простой перебор (как хватало в тех же танках) будет слишком медленным (квадратичная сложность) и надо привлекать более эффективные алгоритмы многомерной оптимизации. Я, как «знаток» генетических алгоритмов, применял именно их, хотя этот класс алгоритмов не особо эффективен и если бы было время, то стоило бы поэкспериментировать с другими, например, с имитацией отжига. Более конкретно, алгоритм был следующий. Для начала, делаем перебор с определенным шагом среди траекторий наибыстрейшего достижения точки (без второго поворота) и на этих траекториях делаем расчет очков (тоже с определенным шагом) за забивание гола пассом и ударом с максимальным замахом. Очки за гол считались как вероятность попасть в нужный диапазон углов с учетом заданного нормального распределения при ударе, умноженная на экспоненциальный коэффициент затухания по времени. Далее, выбираем несколько траекторий с максимальным количеством очков, добавляем «мутировавшие» варианты этих траекторий (при этом появляется ненулевой конечный доворот), повторно оцениваем вероятность забивания, причем уже не с каким-то шагом, а рядом с найденным ранее наилучшим моментом удара, и опять отбираем несколько лучших. Повторяем все это несколько раз со все уменьшающейся силой «мутаций».
Вероятность попасть в ворота без конечного доворота почти всегда близка к 0, однако, нормальное распределение имеет достаточно большие «хвосты», поэтому на первом этапе перебора находились точки удара, а в процессе генетической оптимизации выбирался метод выхода на эти точки. Причем, тут существенную роль сыграл баг с завышением сектора, упомянутый выше, и одновременно с его правкой перед финалом пришлось добавить искусственные «хвосты» в функцию оценки вероятности попадания.
Другой важной характеристикой алгоритма стала растянутая по времени оптимизация, о которой в танках я только думал, а в этом году реализовал с самого начала. Помимо траекторий с перебора в общий пул добавляется и оптимальная траектория с предыдущего шага, с соответствующе скорректированными временами. Это добавляет алгоритму следующее свойство: не страшно, что за текущий шаг найдена не совсем оптимальная траектория, на следующем шагу оптимизация продолжится с того места, на котором закончилась. В итоге, этот алгоритм стал краеугольным камнем всей стратегии, фреймворком, на котором было построено все остальное.
Первая версия
В первую версию стратегии, которая была готова за неделю до первого раунда, помимо основного алгоритма, вошли следующие элементы (в хронологическом порядке).
- Предсказание возможных положений противников, основанное на коде для начального перебора траекторий. Возможные положения противников на каждый шаг, а также примерный центр сектора клюшки заносились в карту по квадратной сетке. По этой карте делались выборки, с достаточно сложной фильтрацией (сильно упрощенной потом), и при оптимизации уже своих траекторий давались штрафы за нахождение рядом с врагами.
- Начальный перебор делался не только для владельца шайбы, но и для других своих хоккеистов. Достигнутые позиции оценивались с учетом времени достижения этой и соседних с ней (по карте) позиций врагом. Несколько позиций с наибольшей оценкой становились возможными целями пасса. При расчете очков удара уже для владельца шайбы перебирались не только удары в сторону ворот, но и в сторону найденных целей. Если в результате оптимизации был выбран вариант с пассом, то получатель начинал двигаться в сторону целевой позиции.
- В случае, если шайба находится в свободном полете, точно просчитываем ее положение в каждый момент времени. Полную оптимизацию выполняем для всех своих хоккеистов, только в функции оценки удара рассматриваем подбор шайбы, либо ее выбивание, если есть угроза воротам. Эта часть кода также дает корректный подбор пассов.
- Помимо подбора и выбивания для свободной шайбы также рассматриваем удар по чужим воротам, абсолютно аналогично случаю владения шайбой. Теперь становятся возможными забивания голов с одного удара, хотя и только при редком стечении обстоятельств.
- В качестве костыля для защиты было использовано следование к точке перед вратарем, если шайба не у врага и к хитро рассчитанной точке между воротами и владельцем шайбы в противном случае. Следование было реализовано в том же цикле начального перебора, причем без учета скорости, поэтому хоккеист постоянно пролетал мимо и, в итоге, болтался туда-сюда рядом с воротами. Этот алгоритм следования назначался для незанятых в других алгоритмах хоккеистов, поэтому обычно был один активный нападающий с шайбой или идущий на перехват свободнолетящей и один защитник у ворот. В случае, если шайба у противника, то оба хоккеиста пытались двигаться в секретную точку.
Первый раунд
Тестирование в системе соревнований с реальными противниками показало, что, во-первых, стратегия слишком медленная и пришлось по-быстрому править параметры алгоритмов, и, во-вторых, алгоритм перехвата врагов с шайбой никуда не годится. В итоге, для второй версии стратегии я сделал так, что в секретную точку едет только один хоккеист, а второй болтается вокруг точки рядом с воротами как обычно. В 3-й версии я вместо следования к секретной точке использовал простой алгоритм по типу QuickStartGuy-я, правда с упреждением, а также добавил проверку опасности перехвата шайбы при пассе или ударе по воротам в функцию оценки удара. Однако, в новый код закрался серьезный баг и пришлось откатиться обратно. В 5-й версии, помимо исправления багов, я провел серьезную переработку кода с целью избавиться от тяжелой тригонометрии внутри циклов.
6-я версия (и ее исправленный вариант — 7-я, с убранным залипанием на замахе) — это новая попытка переосмыслить методы защиты. В условиях, когда существующий алгоритм никуда не годится, а универсальный не придумывается, я реализовал новый костыль, хотя и лучшего качества. Теперь, за врага с шайбой прогонялся мой стандартный алгоритм оптимизации удара, впрочем, без учета влияния оппонентов, и найденная траектория шайбы обрабатывалась немного модифицированным алгоритмом перехвата свободнолетящей шайбы при оптимизации за своих хоккеистов. Приятным бонусом стало то, что стратегия научилась выбивать шайбу сразу во вражеские ворота, алгоритм забивания с лета проявил себя и здесь.
Играющая в первой части первого раунда 8-я версия от 7-й отличалась минимально, однако одно из изменений оказалось решающим. Убрав затухание по времени при расчете вероятности перехвата шайбы врагом я добился того, что мои хоккеисты перестали «тупить» перед воротами противника, ожидая непонятно чего. На вторую часть первого раунда я добавил оценку пассов с отскоком от горизонтальных бортов. Для этого целевая точка отражалась от нужного борта с учетом коэффициента отскока. 8-я и 9-я версии стратегии дали мне 6-е место в первом раунде и, в целом, показали, что я на верном пути.
Второй раунд
В 10-й версии я занимался адаптацией стратегии к изменениям правил во втором раунде и, заодно, финале (правда, без учета изменения выносливости во время предсказания). А вот в 11-й версии добавилось то, что, в конечном счете, и принесло мне победу в конкурсе.
Первое фундаментальное добавление — это забивание голов в одно касание. Причем, реализация всего этого довольно простая, нет никаких многомерных оптимизаций за несколько хоккеистов сразу. Я уже упоминал, что за не владеющих шайбой своих хоккеистов я прогонял первую стадию алгоритма оптимизации траектории — начальный перебор. Теперь я пошел дальше: для «неосновных» хоккеистов я запускаю полную оптимизацию, как будто они являются владельцами шайбы, и для оптимальной траектории помещаю положение шайбы в момент удара в список целей пасса. Пасс в такую голевую позицию ценится так же, как и простой гол (а в будущих версиях — даже больше), поэтому голы в одно касание из редкого стечения обстоятельств стали мейнстримом.
Второе важное улучшение 11-й версии — это алгоритм следования в целевую точку. Теперь в расчет оценки траектории входит не текущее положение, а предельное положение хоккеиста после полной остановки, плюс я добавил учет ориентации и мои защитники перестали встречать шайбу задом. Т. к. во втором раунде хоккеистов стало трое, то, помимо «основного» и защитника, образовался дополнительный игрок, которому я прописал следование в точку чуть выше или ниже середины поля (в зависимости от положения врагов), из которой удобен выход на вражеские ворота.
Финал
В 12-й версии я, по-быстрому, реализовал логику замен для финала: QuickStartGuy-образное следование в область замен на «вне игры» и немного модифицированный алгоритм следования в точку для замен в процессе игры. А дальше я засел реализовывать разные мелкие задумки, которые образовывались у меня в процессе чемпионата. Перечислю их в хронологическом порядке.
- Добавил штраф за перенос шайбы в место, с которого враг может ее выбить прямо мне в ворота.
- Добавил логику игры в овертайме без вратарей: поправил оценку сектора попадания и немного задвинул защитника вглубь ворот. При обновлении кода расчета углов заметил вышеупомянутый баг с завышенным сектором попадания и исправил его.
- Реализовал нормальную обработку состояния замаха: раньше я просто выполнял замах на запомненное количество тиков, теперь провожу полный перебор на выбор оптимального момента прекращения замаха.
- Реализовал учет вероятности перехвата каждым отдельным хоккеистом противника, а не всех скопом, как раньше.
- В процессе выхода на целевую позицию стал стремиться держать ориентацию не на конечное направление, а на конкретную точку. Это решило проблему с долгим скольжением хоккеиста до целевой точки, при котором оставались дыры в защите, а также убрало залипания, когда защитник не мог решить, в какую сторону ему поворачиваться.
- Сделал более точную, чем грубая карта достижимости, оценку секторов перехвата шайбы на первые пару десятков шагов.
- Добавил защиту от голов в одно касание — в случае свободнолетящей шайбы прогоняя алгоритм оптимизации за врага и обновляя предсказанную позицию шайбы. Этот алгоритм добавил негативный побочный эффект — казалось бы, совсем безопасная траектория шайбы причислялась к опасным и мои хоккеисты стали пытаться выбивать шайбу, вместо того, чтобы просто подобрать.
Изменение силы игры от каждого из этих улучшений в отдельности было не заметно, однако все вместе они дали двукратный отрыв по голам 13-й версии от 12-й на длинных матчах. Все эти улучшения в составе стратегии 13-й версии играли в первой части финала, однако я (и не только я) заметил достаточно большое количество голов в свои ворота из-за побочного эффекта. А т. к. моя стратегия шла вровень со своим основным конкурентом, я решил, что даже такое небольшое количество голов может определить победителя. Поэтому в 14-й версии, которая играла во второй части финала, я добавил штраф за попытку выбивать шайбу в свои ворота. То ли это изменение, то ли изменения стратегии конкурента (я больше склоняюсь ко второй версии), позволили моей стратегии уйти в отрыв, а мне стать двукратным победителем чемпионата Russian AI Cup.
Послесловие
Отрыв моей стратегии от соперников в этом году оказался гораздо серьезнее, чем это было в танках. Я уверенно держался на первом месте песочницы до ее закрытия, чего в 2012 мне сделать не удалось. Тогда, в результате случайных колебаний, я даже не попал в призеры песочницы. Правда, дополнительный приз мне все равно не достался, но уже не из-за слабости стратегии, а благодаря новым правилам.
Смотреть бои можно в моем профиле.
Исходный код стратегии доступен здесь.
Моя старая статья за 2012 год (танки).
Автор: DrSmile
