Расскажу о своем участии в Russian AI Cup. Я — участник с ником Hohol, занявший второе место в финале.
У меня уже имелся некоторый опыт в написании бота для управления танком. Дело в том, что я вот уже пять лет участвую в ACM ICPC. Четвертьфинал нашего региона проходит в стенах Саратовского Государственного Университета, который, напомню, является одним из организоторов Russian AI Cup. На четвертьфинале каждый раз проводится неофициальный игровой конкурс Code Game Challenge. Суть все та же — напишите бота, который всех порвет. И хотя боты оказываются то волшебниками в шляпе и с посохом, то гоночными автомобилями, то суднами на воздушной подушке — мы всегда звали их танчиками.
Так как я участвовал в CGC аж пять раз, конкурс особого энтузиазма у меня поначалу не вызвал.
Но познакомившись с правилами поближе, решил, что конкурс мне все же интересен. Привлекали следующие пункты:
- Большая чем обычно была в CGC сложность игрового мира. Гусеницы танка управляются по-отдельности. Башня движется отдельно от корпуса. Объекты мира прямоугольные, а не круглые. И самое крутое — управление несколькими танками сразу. Все это обещало значительную глубину игры, разнообразие тактик, возможность сделать что-то нереально классное.
- Продолжительность — месяц (в отличие от всего лишь четырех часов, которые даются на написание бота в CGC). За это время стратегии должны очень сильно развиться. Даже если не участвовать самому, наблюдать за прогрессом участников будет крайне интересно.
- Ясно, что участников будет очень много. Спортивный интерес очень велик.
- Приятные призы, куда же без них.
Начав подробнее разбираться с системой, заметил, что организаторы постарались сделать порог вхождения низким. Для просмотра боев на сервере не нужно вообще ничего кроме браузера. Языковой пакет после скачивания сразу просто работает (по крайней мере в моем случае — C#, Windows).
Низкий порог вхождения положительно скажется на количестве участников. А чем больше участников, тем веселее.
Раунд 1
Напомню, конкурс начался в полночь. Я для ознакомления с системой отправил какой-то трешак, крутящийся на месте и пытающийся стрелять по врагам. Почему-то попадал он примерно в нуле случаев (оказывается, для определения, нужно ли стрелять, я использовал self.GetAngleTo, а нужно было self.GetTurretAngleTo). Впрочем, я убедился, что бот шевелится, не падает, и лег спать. За ночь мой рейтинг был слит в минус бесконечность.
На следующий день я заменил этот трешак на чуть допиленного квикстартгая (QuickStartGuy — бот с простейшей стратегией, код которого был выложен на сайте). Он уже выбирал бонусы по соотношению полезность/расстояние и стрелял во врагов с упреждением, считая что они движутся равномерно прямолинейно. Этого с моим слитым рейтингом хватало, чтобы выигрывать почти все системные бои. Но тут я столкнулся с проблемой, которая впоследствие много обсуждалась среди участников: первые несколько сражений рейтинг изменяется сильно, а последующие — слабо. Соответственно, на трешовую стратегию пришлись все резкие скачки рейтинга, а далее, несмотря на победы, рейтинг рос очень-очень медленно.
Занялся движением. Научился подъезжать к бонусам задом, если так ближе. Это резко повысило выживаемость. Пытался улучшить траекторию, чтобы ездить не по ломаным, как квикстартгай, а по красивым кривым. Пробовал делать усилие на гусеницу пропорционально углу, пропорционально квадрату угла, пропорционально всяким функциям от угла и расстояния — ничего хорошего не получалось. Танк упорно водил хороводы вокруг бонусов, а подбирать стеснялся. Забил и оставил движение квикстатгайским.
К тому времени возникла проблема более важная, чем кривое движение. Появилась мода разъезжаться по углам и расстреливать тех кто в центре. Я долго не хотел вливаться в эту мейнстримовскую волну, бродил по центру и быстро умирал. В конце концов пришлось смириться и пойти на поводу у моды — в угол.
Следующая проблема — танк часто застревал, вписавшись носом в край карты. Пришлось проифать это — если мы уже много тиков стоим на месте, и при этом не находимся в теплом уютном углу, кажется мы застряли, давайте-ка отъедем к центру карты.
Заметил, что пушка моего танка слишком уж часто простаивает из-за того, что не успевает повернуться к врагу. Вот вроде почти повернулась, уже готова стрелять, но тут мы подобрали бонус, поворачиваемся к следующему, пушка отклоняется от врага, и стрелять опять некуда. Решил, что нужно помогать повороту пушки еще и гусеницами. Если скорости поворота пушки недостаточно для поворота к цели за оставшееся время перезаряда, повернемся к цели всем корпусом. Теперь пушка никогда не простаивала, количество очков, набираемых за партию, заметно возросло. Также это забавно исказило траекторию движения — теперь все повороты стали чуть более плавными, чтобы пушка всегда была нацелена на врага. Казалось, что танк стал лучше ездить, хотя вроде бы изменение относилось к совсем другой части стратегии.
Вроде бы описание почти всех фич на тот момент уместилось в пару абзацев, но этого уже было достаточно, чтобы подняться где-то до 10 места. Да, после слива рейтинг рос очень медленно, но верно. На несколько дней я уехал домой в деревню, где не было интернета, и про танки подзабыл. Когда вспомнил, решил заглянуть с телефона — посмотреть, насколько танк за эти дни слился, и как сейчас выглядит топ. Мой танк был на первом месте. Это кривое, ездящее как квикстартгай создание, каким-то чудом добралось до верхней строчки рейтинга. Тогда я понял, что назад пути нет. Если я побывал на первом месте, нужно выводить свои танки в финал.
Близился первый раунд.
Я решил вновь заняться улучшением движения. Слишком уж часто по квикстартгаевскому алгоритму ехал мимо спасительного бонуса. Вновь перебираю зависимости усилий на гусеницы от угла. Пропорционально углу — уже пробовал, чушь получается. Пропорционально квадрату угла — та же фигня. Что бы еще попробовать? Пропорционально кубу что ли? Ну ок, давайте. Внезапно выясняю, что это выглядит совсем неплохо. Издалека танк по довольно красивой линии устремляется к бонусу. Лишь если бонус близко, и танк повернут не к нему, плохо двигается. Ну что ж, если бонус близко, будем двигаться как умеем — как квикстартгай. Больше мимо бонусов не ездил.
Топы уже умели более или менее нормально уворачиваться. Я в этом плане безнадежно отставал. Место в песочнице понизилось. Попытался реализовать уворот, используя некие странные эвристики, но ничего хорошего не получалось. В результате пришлось все попытки откатить, и входить в первую половину раунда, отставая от топов на столетие в техническом плане.
К началу перерыва я был где-то на 25 месте. Это, конечно, проход в следующий раунд, но быть очевидно отсталым как-то неприятно. Было ясно, что для реализации нормального уклонения мне не хватало знаний о местной физике. Я знал, по какому закону происходило изменение скорости снарядов, но вот законов движения танка не знал. Значит, нужно их выяснить. Тут я воспользовался помощью anonymous. Я ставил простые опыты — движение по прямой вперед, движение назад — и находил характеристики танка в каждый тик. И anonymous по этим характеристикам выяснял законы движения. Я решил, что для начала мне вполне хватит уворотов с использованием полного газа назад/вперед. После выяснения этих законов я готов был к написанию простейшего уклонения.
Реализовал я его так: представлял, что мой танк движется прямолинейно равномерно, проверял, ударит ли в меня пуля в ближайшие 100 тиков, и если да, проверял, а ударит ли, если я прямо сейчас включу газ вперед/назад.
Такое уклонение работало уже неплохо. Для пущего эффекта, находясь в углу, я поворачивался боком к врагу, который сейчас целился в меня.
Эти меры позволили мне подняться уже до 8 места к концу первого раунда. Пришло время боев 2на2на2.
Раунд 2
Просматривая сражения из первого раунда, заметил несколько случаев, когда танк пытался уклоняться, но пуля несмотря на это его настигала. При этом никаких помех при уклонении не было. Ожидаемое поведение — либо уклониться, либо не пытаться уклоняться вообще. Очевидно, бага. Прогоняю бой в Repeater, дебажу. Выясняю, что ускорение танка при движении было сильно меньше предполагаемого. Но почему? В грязь он заехал чтоли, буксует? Отправляю лог движения танка anonymous — так и так, проверь, не туплю ли я. Подтверждает, что ускорение тут слишком маленькое. «А у тебя танк при этом случайно не подбит был? — Ну, хп экипажа на половине было, а какая разница? — А движение танка от хп экипажа как раз зависит. — Что? Движение зависит от экипажа? Откуда ты вообще такое такое взял? — В правилах написано...»
Открываю правила, читаю:
«С уменьшением здоровья экипажа эффективность управления танком падает: он начинает медленнее двигаться, поворачивать башню, увеличивается также время перезарядки орудия.»
Почему-то, перечитывая правила несколько раз, я ни разу не заметил этой фразы. И в боях ни разу не обратил внимания, что подбитые танки приторможенные какие-то. RTFM, товарищи.
И все-таки, что за дела? Экипаж педали крутит, чтобы гусеницы двигались? Башню руками поворачивает? Снаряды вручную перезаряжает? 21 век на дворе вроде бы. Хорошо хоть снаряды руками не бросают, а то падали бы прямо под свои гусеницы при низком хп.
В общем, выяснив зависимость мощности движка от хп экипажа, я исправил уклонение.
Пришло время еще раз улучшить движение. Заметил, что танк часто начинает странно покачивать носом при движении к бонусу, если этому движению предшествовал резкий поворот. Из-за этого сильно снижалась скорость движения. Это происходило вот почему: мы только что оказались лицом к бонусу и сейчас газуем вперед, но перед этим мы к нему поворачивались с большой угловой скоростью, и угловая скорость по инерции поворачивает нас от бонуса, причем довольно сильно. Тогда мы вновь с силой поворачиваемся к бонусу, на этот раз в обратную сторону, и все повторяется снова. Тогда я начал гасить угловую скорость, если сейчас направлен к бонусу. Колебания прекратились, скорость движения к бонусам повысилась.
Как ни размышлял, как ни экспериментировал, но я так и не понял, как оптимально располагать два танка. Если мы спавнимся сбоку, то вроде бы вдоль вертикальной стенки хорошо получается. Ну да в случае спавна сбоку вообще все хорошо получается, ибо поспавнившиеся с другой стороны противники убивают друг друга. А вот если выпал спавн между врагами, или хотя бы на вертикальной линии с врагом — не понимаю что делать. В конце концов стал неким образом забиваться двумя танками в угол, но ничего особо хорошего из этого не получилось.
То есть это сейчас я знаю, что ничего хорошего не получилось. А тогда я в песочнице был в первой пятерке, и думал что все в шоколаде. Подошел второй раунд, и по результатам первой его половины я был на 75 месте. В финал же проходило 50.
Итак, перерыв. Нужно срочно что-то улучшать.
Топы явно уворачивались лучше меня. Я умел уворачиваться только газуя назад или вперед. Этого было недостаточно. Но чтобы правильно уворачиваться с поворотом, нужно знать физику мира гораздо более подробно. Я приготовился к новому этапу реверс инжиниринга, который занял бы у меня кучу времени. Но тут Noob дал мне ссылку на обсуждение конкурса на gamedev.ru — многостраничную тему, начавшуюся одновременно с конкурсом. Люди там уже давно выяснили всю физику мира опытами либо декомпиляцией локал раннера. Понятно, что если эти данные были выложены в открытом доступе, многие уже, возможно, пользовались ими. И я, скрепя сердце, воспользовался этими готовыми данными для написания точного предсказателя движения.
Отныне, зная текущее состояние танка, и какие усилия будут приложены к гусеницам, я мог точно определить его состояние через несколько тиков. Теперь я перебирал не два возможных способа уворота от снаряда, а 121 — по 11 различных усилий на левую и правую гусеницу. Также было добавлено уклонение рикошетом — для этого просто нужно было определять, под каким углом пуля ударит в броню. Эффективность уворота резко возросла.
Надоело промазывать по хорошо уклоняющимся врагам. Часто было понятно: если выстрелить сейчас, враг легко увернется; однако через несколько тиков он оказывался в таком положении, из которого увернуться уже не сможет. Может, попробовать стрелять только если враг точно не может увернуться? Благо у нас есть идеальный предсказывальщик его положения при различных выбранных путях отступления. Реализовал это. Попадать стал лучше, был доволен. Но через некоторое время заметил, что почему-то стал бысрее умирать. Что за чушь? Я же улучшил стрельбу, почему это ухудшило мою выживаемость? Сравнив несколько боев до и после улучшения, понял в чем дело. Оказывается, спамя пулями, я часто сбивал летящие в меня пули, от которых я не мог увернуться. Это происходило с самых первых версий, я никогда не задумывался об этом и попросту не замечал, что такое происходит. А оказалось, что таким образом сбивается очень много опасных снарядов. Теперь, редко стреляя, я часто попадал под пули. Обескураженный, я выпилил фичу для обычных снарядов, оставив лишь для премиумных — уж для них она была совершенно уместной.
Научил танки не брать бонус, который нужнее тиммейту. До этого приоритет был всегда у имеющего TeammateIndex = 0, что, конечно, чушь.
Начал не подбирать бонус, соответствующее которому хп полное, а стоять рядом с ним, на случай если получу урон. И подбирать, если поблизости враг. Довольно часто получалось таким образом утаскивать ненужный мне бонус прямо из под носа врага, которому он был нужен.
И вот, подошло время второй половины раунда. Насколько помню, первые 8 часов тестирования я пошатывался где-то в районе 65 места, без каких-то видимых шансов на повышение. Я готов был уже распрощаться с конкурсом и продолжить жить нормальной жизнью, но головокружительная череда побед в последние часы подняла меня на 48 место.
Жаль, что не прошли в финал некоторые запомнившиеся мне сильные игроки, такие как MrDindows и twrlx.
Финал
Итак, я прошел в финал, а это уже серьезный бизнес. Хоть я и отшучивался перед друзьями, что не гарантирую убийство хотя бы одного вражеского танка в финале, на самом деле я сразу был настроен на попадание в призовые места. Даже несмотря на слив второго раунда. Теперь я был ученый — знал, что нельзя доверять песочнице, и нужно опираться лишь на статистику по дуэлям.
Возвращаемся к идее точной стрельбы. Я отказался от нее, так как с ней плохо сбивал опасные пули. Но что мешает мне проверить, является ли эта пуля опасной, и собью ли я ее выстрелом? Ничто не мешает, непонятно почему сразу в голову не пришло. Реализовал, стрелять стал намного лучше.
Теперь можно было полностью сосредоточиться на дуэлях. На данный момент каждый из трех моих танков считал себя частью команды из двух танков. Они странно блуждали в поисках бонусов и смешно копошились в углу, пытаясь разместиться там, не понимая, что их трое, а не двое. Пришлось таки создавать отдельную трехтанковую стратегию. Но чем будет заниматься эта стратегия? Вновь обратился к опыту текущих топов. Выяснил, что очень модной является тактика «занять стену и стоять у нее, уворачиваясь». Как бы скучно это ни выглядело, эта стратегия, видимо, была оптимальнейшей по отношению сложности реализации к эффективности.
Итак, решено — танки равномерно расставляем вдоль вертикальной стены. Поначалу я попробовал ориентировать их лицом к середине карты — возможно, получится эффективно уворачиваться рикошетом. Но получилось лишь эффективно ловить попадания в лоб. Пришлось располагать вертикально. Уже на этом этапе получилась версия, практически неотличимая от финальной невооруженным взглядом. Но на самом деле работы предстояло еще много.
Наступил последний день перед финалом.
Стало понятно, что недавно улучшенная система стрельбы больше не работает. Стрелял я только когда был уверен в попадании. До того как я перешел к стратегии дальнего боя, такая стрельба работала хорошо. Но теперь враг почти всегда был далеко. Получается, в попадании я не был уверен почти никогда, и не стрелял почти никогда. В то же время враг, издалека спамящий выстрелами в меня, хоть иногда, но попадал. Пришлось пойти на компромисс — если враг близко, стрелять только если уверен в попадании, иначе спамить. Со стрельбой на этом закончил.
Далее, оказалось, что резко возросла важность уворотов. Другие типы боев почти всегда заканчивались уничтожением всех соперников, у оставшегося очков обычно было больше, и он побеждал. Одно случайное попадание в тебя погоды не делало — можно было подобрать бонус, восстановиться, и уничтожить обидчика. В дуэли же хп восстановить можно, но очки, которые противник получил за попадание, отобрать не получится. Как и уничтожить его, если он сидит далеко.
Было очевидно, что текущие топы опять уворачиваются лучше меня. В чем же проблема? Проанализировав бои, я выяснил это.
Расскажу чуть подробнее, как я уворачивался в это время. У меня имелся список из 121 возможных пар усилий. Была булева функция, определяющая, попадет ли в меня пуля, если я буду ближайшие 100 тиков применять данную пару усилий. Получается, что пуля, пролетающая от меня на расстоянии в 1 пиксель, мне не угрожала. В результате почти все пули касались танка, но рикошетили. Только и слышно было всю партию характерное дзыньканье рикошета от моих танков.
Проблема была в том, что при любой случайности — стена помешала повернуться, тиммейт толкнул, танк сам выстрелил — движение танка немного отклонялось от рассчитанного, и вместо рикошета происходило четкое попадание.
Как же уворачивались топы? Рикошеты у них были редки. Они старались держаться от пули подальше, с запасом расстояния. Как мне добиться того же? Может, просто считать свой танк на 10 пикселей больше по всем направлениям? Да, в таком случае танк действительно старается быть от пули хотя бы на расстоянии 10. Но представим, что в нас летит пуля, и мы можем увернуться от нее, оставшись в лучшем случае на расстоянии 5 от нее. Танк, думающий что он на 10 пикселей больше, посчитает, что увернуться от нее шансов нет. И со спокойной душой позволит ей попасть в себя.
Я нашел следующий выход: прекратить считать опасность пули булевской величиной и считать ее вещественной. Пусть minDist — минимальное расстояние от танка, на котором побывает пуля. Тогда будем считать, что ее опасность равна max(0,20-minDist). Проблема решена. Теперь танк держится подальше от любой пули, пролетающей на расстоянии хотя бы 20 пикселей.
Тестовые бои показали, что новая система уворота действительно работает значительно лучше. Теперь я практически стабильно обыгрывал всех, кроме самых топов — Milanin, Mr.Smile, SDiL, Romka.
Два часа до начала первой половины финала. Раз за разом просматриваю бои, в которых я сливаю SDiL, в поисках вещей, которые можно быстро улучшить. Выясняю, что большинство попаданий по мне происходит, когда в меня летят несколько пуль. Танк уворачивается только от ближайшей, и ловит попадания последующих. Нужно писать уворот от нескольких снарядов одновременно. Успею за два часа? Написать успею. А потестить? Для этого надо отправить стратегию на сервак. А вдруг он после этого залагает (бывало уже перед началом раунда), версия окажется багнутой, и не успею переотправить? Рискнем.
Через некоторое время код готов. Тестирую в локал раннере. Багов не видно, работает ли то что нужно, непонятно — смартгаи не особо дружно стреляют. Отправляю на сервак, создаю бои с пятью топами, отлучаюсь на некоторое время от компа. Возвращаюсь, обновляю страничку, и дух перехватывает, когда вижу, что все пять боев выиграны. Создаю еще раз, обыгрываю всех кроме Mr.Smile. Смотрю бои — уворачивается отлично. Что ж, к началу финала танки готовы.
С началом тестирования сразу оказался на первом месте. Понаблюдав некоторое время, довольный лег спать. Утром обнаружил себя на втором, Mr.Smile на первом. Действительно, винрейт у него выше, и меня убивает стабильно. Кажется, тут уже ничего не сделать, постараемся удержать второе.
Начался перерыв, пора улучшать стратегию. Я опасался, что вслед за Mr.Smile многие начнут рашить стратегии дальнего боя. Это означало бы необходимость внесения серьезных изменений в случае высокой эффективности таких рашей. Но пока ничего подобного вроде не происходило. Решил подождать изменений в тактиках противников, чтобы было ясно, на что реагировать. А пока поискать явные недостатки в существующей стратегии.
Просмотрев несколько слитых боев, заметил в нескольких случаев очень странное верчение своих танков — не в ту сторону, в которую хотелось бы в данный момент. Repeater, debug. Захожу в несколько вложенных вызовов функций, и вижу в одной из них такой код:
if (toy > 0)
TurnTo(self.X, self.Y+1);
else
TurnTo(self.X, self.Y+1);
Хм, неплохо для стратегии, находящейся на втором месте. Разумеется, в else должно быть "-1". Исправляю.
Продолжаю просмотр слитых боев.
Обнаруживаю бой, в котором в мой танк летят две пули, примерно параллельно, одна летит в нижнюю часть моего танка, другая в верхнюю. Ожидаемое поведение — танк немного поворачивается и позволяет пулям пролететь по разные стороны от себя. Но вместо этого он делает какое-то странное телодвижение, уклоняется от одной, и получает в корму вторую. Repeater, debug. Спустя некоторое время понимаю в чем дело. Я считал опасность от двух снарядов как сумму их опасностей по отдельности. Которая, напомню, равна max(0,20-minDist). Но тогда получается, что пара пуль с расстояниями (19,1) имеет ту же опасность, что и пара с расстояниями (10,10). Очевидно, первая пара все же куда опаснее. Значит, будем считать итоговую опасность как максимум отдельных опасностей, а не сумму.
Больше в тот день почти ничего не менял. Решил лечь спать пораньше, проснуться утром и проверить, не написали ли противники за ночь чего-нибудь контрящего меня.
Утром вижу сообщение Megabyte на gamedev.ru, в котором он говорит, что проифал меня, Mr.Smile и Romka — теперь он будет сразу рашить нас. Хм, интересно, проверим. Создаю пять боев с ним, и с отвисшей челюстью наблюдаю, как он выносит меня во всех боях. Его танки совершенно внаглую подходят вплотную к моим, и методично по-очереди расстреливают их. Проверил несколько других игроков — радикальных изменений вроде нет. Лишь у Romka я нашел кое-что интересное. Если начальное расположение танков таково, что один из игроков находится прямо над бункером, другой под бункером, Romka горизонтальной цепочкой едет в ту же сторону, что и я, занимает один из моих углов раньше меня, расстреливает танк, который едет в этот угол, после чего расправляется с остальными.
В общем, пришлось в срочном порядке допиливать тактику ближнего боя. Впрочем это допиливание свелось всего лишь к увеличению приоритета бонусов (особенно премиумных снарядов), когда мы находимся под атакой. Причем я считал, что я под атакой, если на моей половине поля есть хотя бы два вражеских танка. Megabyte я все еще сливал. Как мне показалось, из-за того, что слишком поздно реагировал на его раш. Пришлось добавить в функцию, определяющую, под атакой ли мы, следующий код:
if(enemies[0].PlayerName == "Megabyte")
return true;После такого хака скорость реагирования повысилась, и винрейт улучшился.
Вторая половина тестирования никаких сюрпризов не преподнесла. Была лишь интрига, кто же займет 6 место (последнее призовое) — Romka или Commandos. Все-таки Romka удержал место за собой.
Эпилог
На самом деле, немножко разочарован собственной стратегией в дуэлях. Скучновато бои выглядят.
Типичный бой с такой же как и моя дальнобойной стратегией от valex:
Начало эпичной битвы
Обстановка накаляется
Нервы напряжены до предела
Победила дружба
То ли дело Mr.Smile — его раши в дуэлях просто прекрасны. Убийство практически любого оппонента быстрее чем за половину отведенного времени — это нечто.
Напомню интересующимся, что песочница на сайте продолжит работать еще несколько месяцев. Все, кто сетовал, что слишком поздно узнал о конкурсе, могут поиграться с танками, никуда особо не торопясь.
Спасибо организаторам за прекрасный конкурс. Надеемся увидеть продолжение через год.
Автор: glashenko
