Путь К Серебряной Медали Russian Ai Cup 2012

Расскажу о своем участии в Кубке России по AI. Я участник с ником Хохол , занявший в финале второе место.

У меня уже был некоторый опыт написания бота для управления танком.

Дело в том, что я участвую в ACM ICPC уже пять лет. Четвертьфиналы нашего региона проходят в стенах Саратовского государственного университета, который, напомню, является одним из организаторов Кубка России по ИИ.

В четвертьфинале каждый раз проводится неофициальное игровое соревнование Code Game Challenge. Суть все та же — написать бота, который всех порвет. И хотя боты оказываются либо волшебниками в шляпе и с посохом, либо гоночными машинами, либо судами на воздушной подушке — мы всегда называли их танками.

Поскольку я пять раз участвовал в CGC, поначалу конкурс не вызвал у меня особого энтузиазма.

Но познакомившись с правилами поближе, я решил, что конкурс мне все равно интересен.

Выделялись следующие моменты:

Сложность игрового мира в CGC была выше, чем обычно.
Гусеницы танка управляются отдельно.
Башня перемещается отдельно от корпуса.
Объекты в мире имеют прямоугольную, а не круглую форму.
А самое крутое — это управление сразу несколькими танками.
Все это обещало значительную глубину игры, разнообразие тактик и возможность сделать что-то невероятно крутое.
Продолжительность — месяц (в отличие от всего четырех часов, которые отводятся на написание бота в CGC).
За это время стратегии должны сильно развиться.
Даже если вы сами не участвуете, наблюдать за прогрессом участников будет крайне интересно.
Понятно, что участников будет много.
Интерес к спорту очень велик.
Хорошие призы, где бы мы были без них?

Начав разбираться в системе более детально, я заметил, что организаторы постарались сделать низкий порог входа.

Для просмотра боев на сервере вам не нужно ничего, кроме браузера.

После скачивания языковой пакет сразу работает (по крайней мере в моем случае - C#, Windows).

Низкий порог входа положительно скажется на количестве участников.

И чем больше участников, тем веселее.

Раунд 1 Напомню, соревнования начались в полночь.

Для знакомства с системой я отправил какого-то мусора, крутящегося на месте и пытающегося стрелять по врагам.

По каким-то причинам оно попадало примерно в нуле случаев (оказывается, чтобы определить, стрелять ли, я использовал self.GetAngleTo, а надо было использовать self.GetTurretAngleTo).

Однако я убедился, что бот движется, а не падает, и лег спать.

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

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

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

Этого, с моим объединенным рейтингом, хватило для победы практически во всех системных боях.

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

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

Я начал двигаться.

Я научился подъезжать к бонусам задом наперед, если ближе.

Это резко увеличило выживаемость.

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

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

Танк упорно танцевал вокруг бонусов, но забирать их стеснялся.

Он забил и оставил движение на усмотрение быстрого статгая.

К тому времени возникла проблема более важная, чем кривое движение.

Стало модно ездить по углам и стрелять в тех, кто в центре.

Я долго не хотел присоединяться к этой основной волне, бродил по центру и быстро умер.

В конце концов мне пришлось смириться и пойти на поводу у моды – в угол.

Следующая проблема заключалась в том, что танк часто застревал носом на краю карты.

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

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

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

Я решил, что мне тоже нужно помочь повернуть орудие с гусеницами.

Если скорости поворота орудия не хватает для поворота в сторону цели за оставшееся время перезарядки, разворачиваемся в сторону цели всем телом.

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

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

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

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

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

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

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

Мой танк был на первом месте.

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

Тогда я понял, что пути назад нет. Если бы я был на первом месте, мне нужно было бы вывести свои танки в финал.

Приближался первый тур.

Я решил снова начать совершенствовать свои движения.

Слишком часто по алгоритму faststartgay я проезжал мимо накопительного бонуса.

Еще раз прохожу зависимость сил на путях от угла.

Пропорционально углу - я уже пробовал, получается ерунда.

Пропорционально квадрату угла - та же фигня.

Что еще мне следует попробовать? Пропорционально ли оно кубу? Ну ок, поехали.

Внезапно я обнаруживаю, что это выглядит довольно хорошо.

Издалека танк мчится в сторону бонуса по довольно красивой линии.

Только если бонус близко и танк от него отвернут, он плохо двигается.

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

Мимо бонусов я уже не прошел.

Верхи уже умели более-менее нормально уворачиваться.

В этом отношении я безнадежно отстал.

Место в песочнице уменьшилось.

Я пытался реализовать уклонение, используя какую-то странную эвристику, но ничего хорошего не получилось.

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

К началу перерыва я был где-то на 25-м месте.

Это, конечно, проход в следующий раунд, но быть явно отстающим как-то неприятно.

Было ясно, что мне не хватает знаний местной физики, чтобы реализовать нормальное уклонение.

Я знал, по какому закону меняется скорость снарядов, но не знал законов движения танков.

Поэтому нам нужно их выяснить.

Здесь я воспользовался помощью анонимный .

Я проводил простые эксперименты – движение вперед по прямой, движение назад – и на каждом такте находил характеристики танка.

И анонимный Используя эти характеристики, он выяснил законы движения.

Я решил, что для начала мне будет достаточно уклоняться с полным газом вперед/назад. Разобравшись с этими законами, я был готов написать простой обходной путь.

Я реализовал это так: я представлял, что мой танк движется по прямой равномерно, проверял, попадет ли в меня пуля в ближайшие 100 тактов, и если да, то проверял, попадет ли она в меня, если я включу газ вперед/ назад прямо сейчас.

Это уклонение уже работало хорошо.

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

Эти меры позволили мне подняться на 8-е место к концу первого тура.

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

При этом никаких помех при уклонении не было.

Ожидаемое поведение — либо уклониться, либо вообще не пытаться уклониться.

Очевидно, ошибка.

Веду бой в Репитере, отлаживаю.

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

Но почему? Он въехал в грязь или поскользнулся? Высылаю журнал движения танка анонимный - так и так, проверь, не тупой ли я.

Подтверждает, что ускорение здесь слишком маленькое.

— Ваш танк случайно не подбили? - Ну, боеспособность экипажа была всего вполовину, а какая разница? — А движение танка зависит от боеспособности экипажа.

- Что? Зависит ли движение от экипажа? Откуда ты вообще это взял? «Правила гласят…» Открываю правила и читаю: «По мере снижения здоровья экипажа снижается эффективность управления танком: он начинает медленнее двигаться, вращать башню, а также увеличивается время перезарядки орудия».

Почему-то, перечитывая правила несколько раз, я так и не заметил этой фразы.

И во время боев я ни разу не заметил, чтобы подбитые танки как-то тормозили.

РТФМ, товарищи.

И все же, в чем дело? «Экипаж крутит педали, чтобы гусеницы продолжали двигатьсяЭ» Он поворачивает башенку руками? Он вручную перезаряжает снаряды? Кажется, наступил 21 век.

Хорошо, что снаряды с рук не кидают, иначе бы прямо под гусеницы с низким ХП попали бы.

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

Пришло время еще раз улучшить движение.

Заметил, что танк часто начинает странно шевелить носом при движении в сторону бонуса, если этому движению предшествовал резкий поворот. Из-за этого скорость передвижения сильно снизилась.

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

Затем снова принудительно поворачиваемся к бонусу, на этот раз в обратную сторону, и все повторяется снова.

Потом я начал гасить угловую скорость, если меня теперь направили в сторону бонуса.

Колебания прекратились, скорость движения к бонусам увеличилась.

Как я ни думал, как ни экспериментировал, я так и не понял, как оптимально расположить два танка.

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

Ну а в случае со спавном на стороне все в целом получается хорошо, потому что противники, спавнящиеся на другой стороне, убивают друг друга.

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

В конце концов он как-то стал втискивать два танка в угол, но ничего особенно хорошего из этого не вышло.

То есть теперь я знаю, что ничего хорошего не произошло.

А потом я был в пятёрке в песочнице, и думал, что всё в шоколаде.

Наступил второй тур, и по итогам первой половины я оказался на 75-м месте.

В финал прошли 50 человек.

Итак, перерыв.

Что-то срочно нужно улучшить.

Вершки явно лучше меня уклонялись.

Я мог увернуться, только ускоряясь назад или вперед. Этого было недостаточно.

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

Я готовился к новому этапу реверс-инжиниринга, который отнимет у меня много времени.

Но здесь Нуб дал мне ссылку на обсуждение конкурса на gamedev.ru - многостраничную тему, начавшуюся одновременно с конкурсом.

Люди там давно разобрались во всей физике мира путем экспериментов или декомпиляции местного раннера.

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

И я, скрепя сердце, использовал эти готовые данные для написания точного предсказателя движения.

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

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

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

Эффективность уклонения резко возросла.

Устали скучать по хорошо ускользающим врагам.

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

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

Реализовано это.

Я стал лучше бить, я был доволен.

Но через некоторое время я заметил, что почему-то стал умирать быстрее.

Какая ерунда? Я улучшил свою стрельбу, почему это ухудшило мою живучесть? Сравнив несколько боев до и после улучшения, я понял, в чем дело.

Оказывается, рассылая пули, я часто сбивал летящие в меня пули, от которых не мог увернуться.

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

Теперь, редко стреляя, я часто попадал под пули.

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

Научили танков не брать бонус, который больше нужен их товарищу по команде.

До этого приоритет всегда отдавался тем, у кого TeammateIndex = 0, что, конечно, нонсенс.

Я начал не подбирать бонус, соответствующий полному ХП, а стоять рядом, на случай получения урона.

И поднимите, если рядом есть враг.

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

И вот пришло время второй половины раунда.

Насколько я помню, первые 8 часов тестирования я шатался где-то на 65-м месте, без каких-либо видимых шансов на повышение.

Я был готов распрощаться с конкурентами и продолжить жить нормальной жизнью, но головокружительная серия побед в последние часы подняла меня на 48-е место.

Жаль, что некоторые сильные игроки, которых я помню, не прошли в финал, например MrDindows И twrlx .

Финал Итак, я дошел до финала, и это серьезное дело.

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

Даже несмотря на проигрыш второго тура.

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

Вернемся к идее точной стрельбы.

Я отказался от него, потому что он плохо сбивал опасные пули.

Но что мне мешает проверить, опасна ли эта пуля и смогу ли я ее сбить? Ничего не мешает, непонятно, почему сразу не пришло в голову.

Я это реализовал и стал снимать намного лучше.

Теперь вы могли полностью сосредоточиться на дуэлях.

В этот момент каждый из трёх моих танков считал себя частью двухтанковой команды.

Они странно бродили в поисках бонусов и смешно суетились в углу, пытаясь туда вписаться, не понимая, что их трое, а не двое.

Пришлось создать отдельную стратегию с тремя танками.

Но что даст эта стратегия? Я вновь обратился к опыту нынешних высших руководителей.

Я обнаружил, что тактика «занять стену и стоять у нее, уворачиваясь» очень модна.

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

Итак, решено – расположим баки равномерно вдоль вертикальной стенки.

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

Но эффективно ловить попадания можно было только в лоб.

Пришлось поставить вертикально.

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

Но на самом деле предстояло еще много работы.

Настал последний день перед финалом.

Стало ясно, что недавно улучшенная система стрельбы больше не работает. Я стрелял только тогда, когда был уверен в попадании.

До того, как я перешел на дальнюю стратегию, этот тип стрельбы работал хорошо.

Но теперь враг почти всегда был далеко.

Оказывается, я почти никогда не был уверен в попадании и почти никогда не стрелял.

При этом спамящие в меня выстрелы противника издалека хоть иногда попадают в меня.

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

Я закончил со стрельбой.

Далее оказалось, что важность уклонения резко возросла.

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

Одно случайное попадание в вас не изменило погоды – вы могли забрать бонус, восстановиться и уничтожить обидчика.

В дуэли HP можно восстановить, но очки, полученные противником за удар, отнять нельзя.

Как его уничтожить, если он сидит далеко.

Было очевидно, что нынешние топы снова уклоняются лучше меня.

В чем проблема? Проанализировав бои, я это выяснил.

Расскажу немного подробнее, как я изворачивался за это время.

У меня был список из 121 возможной пары усилий.

Была булева функция, которая определяла, попадет ли в меня пуля, если я приложу заданную пару сил в течение следующих 100 тактов.

Получается, что пуля, летящая от меня на расстоянии 1 пиксель, мне не угрожала.

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

Единственное, что было слышно на протяжении всей вечеринки, — это характерный звенящий звук рикошета моих танков.

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

Как верхушки увернулись? Их рикошеты были редки.

Они старались держаться подальше от пули, с запасом на дистанцию.

Как я могу добиться того же? Может просто считать свой танк на 10 пикселей больше во всех направлениях? Да, в этом случае танк действительно старается уйти от пули хотя бы на 10 метров.

Но представьте, что в нас летит пуля, и мы можем от нее увернуться, оставаясь в лучшем случае на расстоянии 5 от нее.

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

Я нашел следующее решение: перестать считать опасность пули булевой величиной и считать ее реальной.

Пусть minDist — минимальное расстояние от танка, до которого пройдет пуля.

Тогда будем считать, что его опасность равна max(0,20-minDist).

Задача решена.

Теперь танк держится подальше от любой пули, летящей на расстоянии не менее 20 пикселей.

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

Теперь я практически стабильно обыгрываю всех, кроме самых топовых - Миланин , Мистер Улыбка , СДиЛ , Ромка .

Два часа до начала первой половины финала.

Снова и снова я смотрю бои, в которых проигрываю СДиЛ , ищу вещи, которые можно быстро улучшить.

Я обнаружил, что большинство попаданий я получаю от нескольких пуль, летящих в меня.

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

Вам нужно уклоняться от нескольких снарядов одновременно.

Могу ли я успеть за два часа? У меня будет время написать.

Как насчет тестирования? Для этого вам необходимо отправить стратегию на сервер.

А если после этого выложит (это произошло до начала раунда), версия окажется глючной, и я не успею ее переслать? Давайте рискнем.

Через некоторое время код готов.

Тестирую в локальном раннере.

Багов не видно, не понятно, работает ли то, что нужно - умники не очень дружно стреляют. Отправляю на сервер, создаю бои с пятью топами и на время отхожу от компьютера.

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

Я творю снова, я побеждаю всех, кроме Мистер Улыбка .

Я смотрю бои, и он отлично уклоняется.

Что ж, танки готовы к старту финала.

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

Посмотрев некоторое время, он пошел спать довольный.

Утром я оказался на втором, Мистер Улыбка во-первых.

Действительно, его винрейт выше, и он постоянно меня убивает. Кажется, здесь мы ничего не можем сделать; мы постараемся сохранить второй.

Перерыв начался, пора совершенствовать стратегию.

Я боялся, что после Мистер Улыбка многие начнут использовать стратегии дальнего боя.

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

Но пока ничего подобного, похоже, не произошло.

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

А пока ищем очевидные недостатки в существующей стратегии.

Посмотрев несколько объединенных боев, я заметил в нескольких случаях очень странное вращение моих танков - не в ту сторону, в которую мне хотелось бы в данный момент. Репитер, отладка.

Я захожу в несколько вложенных вызовов функций и в одном из них вижу следующий код:

   

 if (toy > 0)
     TurnTo(self.X, self.Y+1);
 else
     TurnTo(self.X, self.Y+1);

Хм, неплохо для стратегии, находящейся на втором месте.

Конечно, else должно содержать "-1".

Я исправляю.

Я продолжаю смотреть слитые в сеть бои.

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

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

Но вместо этого он делает какое-то странное движение телом, уворачивается от одного, а второму попадает в корму.

Репитер, отладка.

Через некоторое время я понимаю, что происходит. Я рассматривал опасность от двух снарядов как сумму их индивидуальных опасностей.

Что, напомню, равно max(0,20-minDist).

Но тогда оказывается, что пара пуль с дистанциями (19,1) представляет такую же опасность, как и пара с дистанциями (10,10).

Очевидно, что первая пара все же гораздо опаснее.

Это означает, что мы будем рассматривать общую опасность как максимум отдельных опасностей, а не сумму.

Больше в тот день почти ничего не изменилось.

Я решил лечь спать пораньше, проснуться утром и проверить, не написали ли мне за ночь мои оппоненты чего-нибудь противоречащего мне.

Я вижу сообщение утром Мегабайт на gamedev.ru, где он говорит, что обманул меня, Мистер Улыбка И Ромка - Сейчас он нас сразу бросит. Хм, интересно, давайте проверим.

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

Его танки совершенно нагло приближаются к моим и методично расстреливают их одного за другим.

Проверил еще несколько плееров - радикальных изменений вроде нет. Только Ромка Я нашел кое-что интересное.

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

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

Однако это дополнение сводилось лишь к повышению приоритета бонусов (особенно премиум-снарядов), когда нас атакуют. Более того, я считал, что меня атакуют, если на моей половине поля было хотя бы два танка противника.

Мегабайт У меня все еще текла.

Мне казалось, что это произошло из-за того, что я слишком поздно среагировал на его порыв.

Нам пришлось добавить следующий код в функцию, определяющую, подверглись ли мы атаке:

if(enemies[0].

PlayerName == "Megabyte") return true;

После этого взлома увеличилась скорость реакции и улучшился процент побед. Вторая половина тестирования не преподнесла никаких сюрпризов.

Была только интрига, кто займет 6 место (последний приз) - Ромка или коммандос.

Все еще Ромка сохранил свое место.

Эпилог На самом деле, я немного разочарован собственной стратегией в дуэлях.

Бои выглядят немного скучно.

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

Путь к серебряной медали Russian AI Cup 2012

Начало эпической битвы

Ситуация накаляется

Нервы напряжены до предела

Дружба победила В любом случае Мистер Улыбка — его броски в дуэлях просто замечательны.