Russian AI Cup - сражение алгоритмов. Часть 2

Аккаунты автора: GitHub

Время чтения: около 8 минут

Хеллоу, ворлд!

Началась новая рабочая неделя. Понедельник прошёл успешно? Думаю, да, а значит время отдохнуть и почитать вторую часть истории про участие в Russian AI Cup 2016. В прошлом выпуске на канале Джун уронил прод, я рассказал вам об этом чемпионате, некоторых нюансах и привёл историческую сводку. Сегодня пришло время поговорить о том, какие же алгоритмы позволили мне подняться до 777 места из 1500 и какие уроки я для себя вынес.

CodeWizards

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

Wizards (визарды, волшебники) - ключевые персонажи этой игры. В игре есть 2 базы: левая нижняя и правая верхняя. Карта симметричная и исполняющая машина считает, что вы всегда появляетесь на нижней, что сильно упрощает разработку. Волшебники могут прокачивать свои уровни, бросать замедляющие или поджигающие шары, бить палкой, покачивать защиту или быстро бегать. Карта разделена дорогами и лесами. Каждые N тиков игры на вас бегут свежеиспеченные миньоны с вражеской базы. Периодически респаунятся бонусы, которые дают временное улучшение + очки. Ваша задача получить как можно больше очков на момент конца раунда или уничтожения вражеской базы. Ссылка на мой профиль, в котором можно посмотреть игры, будет в конце.

Разработка алгоритма

Множество идей, еще больше подходов к реализации, я решил окунуться в это неизведанное море и получил массу удовольствия от новой информации, тогда я не знал про существование "потенциальных полей" , которыми пользовались победители (ссылка будет ниже), а шёл с желанием применить какие-то свои знания полученные в институте.

Разработчикам изначально дается стратегия "по умолчанию", ничего особенного, просто бегаем, стреляем и при низком HP убегаем. "Как же сделать лучше?" - подумал я и первая мысль, которая пришла мне в голову - это разбить карту на граф. Сделать так, чтобы волшебник бегал по заранее определенным, кратчайшим путям до необходимой точки. Долго думать я не стал и принялся за реализацию. Идея была хороша, до того момента, пока я не увидел противников, которые бегают по лесу, сокращают пути и вообще тащат очки ото всюду. Но что-то менять тогда было уже поздно и я решил улучшать это решение из последних сил. Так сказать, загнать себя в локальный экстремум по самое "не балуйся".

Я покрыл основную часть карты графом, сделал множество вариантов и визард стал немного лучше бегать. Каждый раз алгоритм рассчитывал расстояния до ближайшего бонуса по графу и т.к. время респауна бонуса заранее известно, я мог рассчитать сколько времени мне понадобится, чтобы достичь его. "Дейкстра!" - вскрикнул я и отправился искать примеры реализации :) К слову, использование готовых библиотек в чемпионате запрещено. Также я решил оставить кусочек поведения из алгоритма по умолчанию и мой волшебник бегал как ошпаренный влево и вправо, чтобы в него лишний раз не попали.

Обход препятствий

Перемещаясь по этому маленькому миру ты понимаешь, что каждое дерево, каждый союзник, каждая мелочь - враг твоего отступления или вылазки за бонусом. Это потребовало от меня описать смещения влево или вправо если мой юнит вот вот упрётся во что-то и т.к. я выделил только определенные маршруты для движения, то вероятность попасть в неприятную ситуацию "Мама, я застрял в локации" сводилась к минимуму. Однако, вероятность была и мне пришлось заставить моего волшебника уничтожать ни в чем неповинные деревья, стоявшие у него на пути. Тогда это казалось мне хорошим решением. С тех пор, я не уничтожил больше ни одного дерева.

Зонирование

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

В расчете на то, что мой юнит иногда погибал, а сдавать базу не очень-то хотелось, я ввел зоны. По зонам я определял как много в них противников в отношении к союзникам и от этого выбирал место куда я отправлюсь после респауна. В дальнейшем я применял зоны для определения угрозы моему юниту, если в двух ближайших зонах количество противников "сильно" превышало союзников (читай "коэффициент вражеской активности был больше критического показателя"), то мой юнит начинал отступать. Много раз это меня спасало.

Потенциальная смерть

Каждый тик мой волшебник оценивал на сколько возможно погибнуть от рук противника с учетом регенерации хп, перезарядки противника и прочей активности, если я не начну отступать со следующего тика. Это была одна из самых полезных и при этом бажных особенностей моего алгоритма. Терпения понять где я ошибся и почему центральная база меня периодически добивала мне так и не хватило, в итоге я просто ужесточил требования к "сохранению жизни" и большинстве случаев я спасался.

Стой! Кому говорю!

Эта часть алгоритма, пожалуй, самая весёлая. Я оценивал смогу ли я добить вражеского волшебника и в случае, если да, то я пытался его догнать и закончить начатое. Было очень весело наблюдать эти увлекательные погони, которые иногда останавливались "здравым смыслом" в виде вышеописанных алгоритмов.

Отладка

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

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

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

Заключение

Естественно, с такими простыми вещами было мало шансов занять место в топе, но удовольствие, это... вы не представляете. Те запойные кодом вечера я вспоминаю до сих пор, как я искал лучшие варианты решения, как отлаживал алгоритмы, как дебажил своего волшебника. Желаю каждому испытать такое! Тут я и закончу, спасибо что читали эту незатейливую историю. До встреч в игре!

Ссылки

Победители Russian AI Cup рассказывают о своих стратегиях здесь

Мой профиль из 2016 года здесь

Исходный код описанного алгоритма на Java здесь