Как искать путь к победе на Russian AI Cup 2016, но не в том направлении

После не сильно долгих уговоров, меня убедили, что 30 место не так уж и плохо, и написать статью стоит. Я – участник с ником Stef, и занял в песочнице около 30 места.
Картинка нарисованная рядом, имеет глубокий смысл – вместо того чтобы уделить достаточное время и быть призером соревнования, я пошел другим путем — потратил одну треть времени на то, что делать было не обязательно. Если быть точнее, то я занялся алгоритмом поиска пути в пространстве, где нет непробиваемых стен, а есть лишь деревья которые можно или рубить или проходить рядом с ними.
Что из этого получилось, можно посмотреть в видео, а желающих познать все тайны леса прошу под кат.

Вначале немного расскажу о самом соревновании. В этом году правила соревнований базировались на популярном в мире компьютерном жанре MOBA. Основные концепции данного жанра были сохранены — появление крипов на 3 линиях около баз; река с рунами; 5 героев с каждой стороны. Но не смотря на это, полноценной MOBA это не было – мало эффективно переходит с линии на линию, защищать базу по факту тоже, и развитие было всего лишь в виде прокачки скиллов из заданного ограниченного набора. Финал среди топов свелся к тому, что игра проходила по принципу: «кто быстрее снесет базу противника по центральной линии, тот и выиграл», а сносилась она махом, от 4 до 6 волн крипов.
Как человек знакомый с этим жанром не понаслышке, в самом же начале соревнований я заподозрил неладное и высказал предположение, что в финале будет именно такая тактика – все по миду. К сожалению, баланс в лучшую сторону не изменился, а я решил играть в свою игру, а не в ту, что приведет к победе.

Архитектура

В этом году я писал стратегию на C++, который, как я думал, мне более близок. О таком решении пожалел — возможностей из высокоуровневых языков мне не хватило, привык уже к ним. К финалу моя программа включала 141 файл .h или .cpp. Выглядело, это как-то так: леса архитектуры
Из этой картинки можно увидеть основную идею архитектуры:

• Слой общего назначения – В него входят такие папки как: Algorithms, Common, Environment. Расположение классов между этими папками не совсем корректно, особенно между папкой Algorithms и Environment.
• Слой команд – набор классов, реализующий один из трех протоколов: MoveCommand, AttackCommand, CastCommand. Отвечали за логику: куда идти, кого атаковать, что кастовать.
• Слой тактики – В него входят папки Strategy, Tactics, Role:
  • Strategy – сумматор результатов команд и содержит в себе базовый набор для упрощения работы с командами.
  • Role – базовые классы определяющие поведение мага — просто набор цифр.
  • Tactics – Описывает стратегию, и роли для этой стратегии. Под каждый раунд они разные. А на финал их несколько.

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

Время

Перед началом соревнований я установил себе программу для подсчета времени (toggl), и постоянно ей пользовался. Отвечу сразу на один интересующий многих вопрос – много ли времени и сил тратится на олимпиаду? – Да много. Её очень сложно сочетать с работой и семьей, и по факту приходится жертвовать сном ради неё. Студентам в этом плане попроще, но думаю тоже нелегко.
Потраченное время по неделям:

• Первая – 26 часов
• Вторая – 26 часов
• Третья – 27 часов
• Четвертая – 34.5 часов
• Пятая – 38.5 часов
• Шестая (перед финалом) – 10 часов
• После финала – 15 часов

Итого: 177 часов.

Во втором раунде я занял 103 место, несмотря на то, что в песочнице был высоко в рейтинге, и хотел попасть в Финал через песочницу, но так и не смог. Перед финалом я был на 80-90 месте c пониманием, что уже устал и не могу продолжать дальше писать по ночам, по этой причине забросил написание олимпиады на неделю, ну и как следствие, не прошел в финал.

После некоторого отдыха и окончания финала, я потратил еще около 17 часов на правки багов и небольшие улучшения стратегии, что помогло мне подняться с 80-90 мест до 20-30. В этот момент я окончательно осознал, что написание олимпиады ночами было плохой идеей — почти все улучшения кода состояли из правок опечаток, которые в свою очередь появлялись из-за невнимательности, которая сильно страдает ночью.

Потрачено времени по задачам:

• Поддержка Архитектуры — 28 часов
• Написание Алгоритма Поиска пути — 49 часов
• Написание Алгоритма Уворота — 26 часов
• Остальное — 67 часов

В списке выделено 3 основные задачи, которые отняли больше всего времени: Архитектура, Поиск пути, Увороты. В «остальное» попали такие вещи как: балансировка и подгонка констант, правка багов и алгоритмы которые не отняли много времени.

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

Алгоритмы

За время олимпиады были реализованы следующие алгоритмы:

• Карта влияний — позволяет легко оценить перевес сил по линиям и найти точку где сейчас стоит находится на линии
• Предсказание нахождения врага в невидимой зоне — нужно в первую очередь для более точного просчета карты влияний
• Оценка исхода локальной битвы – нужен для понимания когда нападать, а когда защищаться
• Уклонение от снарядов — один из самых важных алгоритмов
• Поиск оптимальной позиции — второй по важности алгоритм. Оценивает куда лучше идти и поворачиваться в текущий тик. Самое слабое звено моей стратегии
• Поиск пути — позволяет оценить расстояние до точки и найти какие деревья мешаются, чтобы её достичь
• Обход препятствий – нужен чтобы обходить близкие препятствия по кратчайшему пути

Карта влияний

Была сделана после первого раунда. Изначально создавалась в первую очередь для принятия тактических решений в финале.
По факту основное её предназначение — это определение линии фронта, точки, где сейчас происходит сражение.
Помимо этого карта влияний важна при оценке исхода локальной битвы, и оценки на какой линии лучше стоять.
Выглядит она как-то так:

Если посмотреть внимательно, то можно увидеть что основное влияние оказывают крипы. Маги оказываются маленькое влияние в силу их непостоянства, а башни слабые, и не способны дать отпор в случае нападения. В принципе слабость башен и является одной из самых больших причин другого баланса в игре, нежели в MOBA.
Строилась она достаточно легко:
Проходим по всем юнитам, зданиям, магам на карте, и заполняем сетки вокруг. Всего есть две сетки: дружественная и вражеская, обе сетки размером 80x80 и на всю карту.

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

На самом деле изначально алгоритм действовал по другому принципу, и выдавал точки где первый раз встречается «желтая» зона со стороны противника. Но участник под ником core2duo изменил мое мнение о том, где должна находится линия фронта – его стратегия в финале нападала на верхнюю вышку, обходя по лесу и не заходя на линию, тем самым крипы проходили мимо его магов не обращая на них внимания.

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

Предсказание нахождения врага в невидимой зоне

Существует три предсказания: нахождение вражеских крипов, нахождение магов, вышки. Первое предсказание достаточно точное, но и не используется напрямую. Оно нужно только для оценки силы линии, так как без этого алгоритм почти всегда бы считал, что наши линии выигрывают.
Для предсказания вражеских крипов используется достаточно простой алгоритм — раз в 750 тиков, время появления крипов, из точки появления пускаются 4 крипа всегда в одной и той же группировке, и с одной и той же скоростью. Как только они доходят до зоны, где есть видимость, то они исчезают.
С магами другая история — они мало влияют на карту влияний, но при этом иногда было бы неплохо иметь возможность догнать вражеского мага, который убежал за край экрана. Поэтому все вражеские маги после первого их появления в зоне видимости сохраняются в локальном мире, и если они исчезли из зоны видимости, то идет эмуляция их отхода к базе. То есть стратегия всегда считает — если мага больше не видно, значит, он бежит к базе.

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

Оценка исхода локальной битвы

До появления этого алгоритма, моя стратегия всегда играла от защиты, единственный случай когда маг мог напасть — в случаи смещения линии фронта сильно в сторону вражеской базы. Или вражеский маг сам пришел, чтобы его убили.
Появление этого алгоритма явно дало преимущество среди не топ стратегий — топ стратегии почти не совершают ошибки и редко можно сказать, что если нападешь, то точно выиграешь, а вот более слабые стратегии рано или поздно совершат ошибку и в этот момент предсказатель исхода битвы скажет — все можно нападать.
Хотя основное преимущество он дал в нападении, создавался он в первую очередь ради того чтобы не совершать ошибки при дисбалансе на линии или, по-другому, если вражеских магов больше чем своих. В этом случае лучше стоять слегка подальше от врагов, так как если допустить хотя бы одну ошибку, то велики шансы, что твоего мага убьют.
Способ расчета исхода локальной битвы до невозможности простой, но, несмотря на это достаточно эффективен.
Вначале определимся с входными параметрами — на входе мы имеем своего мага и точку, куда мы хотим напасть. Существует также более продвинутый вариант — на вход подается свой маг + вражеский, в таком случае вызывается два раза функция оценки шанса на победу — один раз для своего и один раз для вражеского мага. Такой подход помогает более точно оценить шансы на победу, нежели через точку, так как в случае равенства сил он выдаст число более близкое к нулю, а в случае большого различия наоборот усилит эту разницу еще сильнее.

Основная же функция расчета выглядит так:

1. Если в текущий тик по мне могут нанести урона больше чем у мага хп, при условии, что все одновременно в него выстрелят, то возвращаем отрицательный шанс на победу
2. Прибавляем сумму опасности дружественных магов которые находятся приблизительно на том же расстоянии до контрольной точки или ближе чем мой маг.
3. Отнимаем сумму опасности вражеских магов, которые находятся между своим магом и контрольной точкой.
4. Прибавляем перевес сил в круге заданного радиуса и в центре между положением мага и контрольной точкой.
5. Нормализуем получившиеся значения и вуаля — шанс победы есть.

Шанс на победу 100%, если силы союзников больше на полтора мага первого уровня, чем вражеские силы.
Поэтому в играх без уровня я не часто нападаю, так как для атаки шанс на победу должен быть более 50%, что не так часто случается, при условии, что крипы составляют около 20% силы одного мага, и хп магов зачастую равны.

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

Уклонение от снарядов

Самый эффективный алгоритм из всех существующих, и при этом почти самый простой.
Изначально для уклонения была написана функция эмуляции движения в заданном направлении. То есть стратегия оценивает, сколько снаряду еще максимум лететь тиков и эмулирует, движение мага в некотором направлении, с учетом, что он поворачивается на каждом тике к нему. Если снаряд попал в мага, значит, данное направление ошибочное и надо посмотреть в другом направлении. Если во всех направлениях попадает снаряд, значит уклониться невозможно.
Изначально стратегия считала в 3 направления, или в 6 если рассматривать движения передом и задом за разные направления. Но через некоторое время понял, что такие уклонения не дают времени для атаки или отступления и стал вначале считать куда лучше идти, а потом прогонять уклонение для 60 направлений, дабы найти то которое наилучшим образом совпадает с направлением движения.

Тут слабым местом, я считаю тот факт, что при увороте я всегда двигаюсь и поворачиваюсь в одном направлении. В теории этот алгоритм можно улучшить и находить не самое лучшее отклонение движения, но при этом минимальное отклонение по углу. Такой подход увеличил бы шансы на победу в схватке, так как чтобы выстрелить в противника надо совершить поворот на меньший угол, чем при текущем алгоритме. Это могло бы сэкономить 2-3 тика, что очень существенно при условии, что маг может стрелять раз в 60 тиков, а снаряд летит до мага около 12 тиков.

Но я не описал одного нюанса — при уклонении стоит учитывать еще препятствия вокруг: деревья, крипов, магов, здания. Для этих целей, прежде чем считать направление движения, ищутся все пересечения в этом направлении, и выбирается самое наиближайшее к нам. То есть в итоге получается не вектор, в котором двигаться, а отрезок. Так как часть объектов каждый тик смещаются, но у них нет инерции, то чтобы лишний раз не обрезать себе возможность уворота, радиус объекта каждый «тик» уменьшается на скорость объекта. Для магов это их максимальная скорость, а для крипов зависит от их направления движения. Так, если крип двигался в нашем направлении, то его радиус наоборот увеличится, а не уменьшится. «тик» я взял в кавычки, так как там нет симуляции движения, за место этого там формула, которая высчитывает тик основываясь на расстояния до пересечения с объектом.

Поиск оптимальной позиции

Если считать пользу алгоритма как – ‘преимущество данное алгоритмом’/’количество строк кода’, то это самый ненужный алгоритм. Но, к сожалению, без него маг бы не смог двигаться. Все команды находящиеся в папке move и defense + парочка из attack отвечают за подсчет движения. Точнее каждая команда возвращает вектор, куда надо двигаться, приоритет движения в этом направлении и такую же пару для поворота. Часто поворот и движение совпадают, но не всегда. Сами команды — это некоторые сложные функции, которые по некоторым критериям считают эти вектора. Всего существует 9 команд движения:

• Преследовать вражеского мага
• Бежать атаковать в ближний бой
• Держатся на расстоянии от башни
• Держатся на расстоянии от крипа
• Уворачиваться от снаряда
• Держатся на расстоянии от вражеского мага
• Подбежать, чтобы получить опыт
• Бежать к бонусу
• Бежать к линии фронта

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

После подсчета всех таких векторов, стратегия находит среди них обязательный с максимальный приоритетом. Если такого нет, то находит среди всех вектор с максимальным приоритетом и усредняет его. Обязательными считаются два вида векторов — уворот от снаряда и уход от башни. Под усреднением понимается сумма векторов, которые отклонены от максимального не более чем на 45 градусов и с учетом их приоритета. Сделано это для большей точности, куда отходить, если рядом с магом много почти одинаковых векторов — например, рядом два вражеских крипа. При этом для обязательных векторов такое делать не желательно – они просчитаны так, что если им не следовать, то можно получить урон.

Поиск пути

Первая версия поиска пути была достаточно простой, и была написана до раунда 1 – по заданным точкам, которых было около 50, был создан статический граф, в котором находился наикратчайший путь до точки. Так как конечная точка и точка где находится маг, были не на самом пути, то из этих точек строился перпендикуляр к наиближайшим заданным ребрам графа.
Самый большой минус, который я видел у такого подхода – это был далеко не наикратчайший путь и чтобы оценить время за которое можно дойти до точки, была написана простенькая эвристика которая давала некий приближенный коэффициент – насколько теоретически наикратчайший путь отличается от подсчитанного.

Поэтому к раунду 2 был написан более сложный, но и более точный поиск пути. Помимо лучшей оценки длины пути, он еще позволял оценить путь с учетом рубки деревьев, что в ряде случаев позволяет сэкономить время. Алгоритм представляет из себя объединение Ли и Дейкстры и принцип его работы можно описать так:

Создаем сетку размером 125x125 с ценами на карте. Там где никого нет – цена 1, по краям карты цена бесконечная. После к цене прибавляется цена за проход по дереву, которая зависит от радиуса дерева — в центре дерева она максимальная, а к краям понижается. Для крипов и башен устанавливаются почти бесконечный цены. Также карта влияний для вражеской стороны тоже отказывает небольшое влияние на цены в поиске пути – нужно это чтобы не лезть в центр сражения, а обходить его.

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

1. Создается карта весов – все веса бесконечные, и создается стек точек переходов
2. Для текущей точки устанавливаем нулевой вес, и она заносится как точка перехода
3. В цикле, пока есть точки перехода:
   1. Достаем первую точку перехода
   2. Просматриваем всех соседей (4 соседние клетки), и считаем предварительные веса в этих клетках – текущий вес клетки + цена у соседа
   3. Если получившийся вес меньше текущего веса в клетке, то меняем вес, и добавляем клетку в стек точек перехода
   4. Переходим к следующей итерации

Если проанализировать данный алгоритм, то такая реализация алгоритма Ли, без учета цены перехода, имеет оценку O(N*M), то есть каждую клетку алгоритм обошел ровно один раз. Можно еще добавить множитель `*4` так как идет проверка соседних клеток. Из-за наличия весов каждую клетку алгоритм может посетить по несколько раз, но это не критично. Правда одно ограничение которого нету у Ли добавляется – надо обязательно обойти всю карту. Но для нас это не критично, так как в дальнейшем по этой карте можно быстро найти путь до любой точки, которых в среднем за тик порядка 5, а в экстремальных ситуациях может доходить до 10 и более.
Чтобы еще сильнее уменьшить время построения, данная карта пересчитывается раз в 30 тиков. Если маг за это время меняет клетку в которой он сейчас находится, то отрабатывает быстрая подмена веса. Подмену веса коротко можно описать так — в новой клетке вес делаем нулевой, в старой устанавливаем значение слегка меньше единицы. Значение слегка меньше единицы зависит от того, сколько раз мы сменили клетку за последние 30 тиков. Это нужно, чтобы в дальнейшем, при поиске пути, алгоритм всегда мог попасть в текущую точку, которая с нулевым весом.

Сам поиск пути по карте весов не представляет ничего сложного: Из некоторой точки строим путь так, чтобы всегда выбирать наименьшую цену из соседних клеток. Правда тут уже соседей 8, а не 4 и для диагональных соседей цена перехода завышается на sqrt(2).

Рубка леса

После того как путь построен, можно запросить информацию о том, какие деревья нужно срубить. Любой путь представляется в виде набора коротких отрезков, которые были построены по сетке. Эти отрезки я буду называть сегменты. Для получения информации о том, какие деревья мешаются, применяется следующий алгоритм:

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

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

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

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

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

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

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

Первое что бросается в глаза при просмотре видео, то это постоянно дергающиеся фиолетовые линии. Сами линии в алгоритме не использовались, но такое отображение оказалось наиболее эффективным, чтобы понимать, где какая группа объектов. Чтобы понять, что такое группа объектов, можно посмотреть на 40 секунду видео – там маг уходит в лес и проходит между двумя группами. Если давать определение то, группы объектов – это не пересекающиеся подмножества всего множества объектов на карте, такие что между любыми двумя объектами из разных подмножеств может пройти маг, ну или расстояние между двумя объектами больше чем диаметр мага + радиус первого объекта + радиус второго объекта.

Первая часть алгоритма занимается построением этих групп. Делается это так:
Вначале имеем множество объектов и пустое множество групп. Берем объект из множества объектов и проверяем – если он попадает в одну группу, то есть находится близко к одному из объектов группы, то добавляем его туда. Если он попадает более чем в одну группу, то объединяем все такие группы и добавляем в новую большую группу новый объект.

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

1. Вначале бросаем луч в точку, куда хотим прийти.
2. Находим пересечение с группой, объектом из группы, который ближе всего к нам.
3. Проходим по всем объектам выбранной группы и для каждого считаем обе внутренние касательные.
4. Находим касательные, которые будут давать максимальный угол отклонения от текущего луча – их будет две (одна влево другая вправо).
5. Далее по магической логике (см. ниже), выбираем одну из двух.
6. Точка касания с учетом радиуса мага, будет нашей новой точкой, куда надо двигаться.
7. После чего снова бросаем луч, но в новую точку, предварительно удалив ту группу, с которой мы уже пересекались.

Чтобы понять причину существования «магической логики», давайте рассмотрим картинку:

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

Как заключение

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

Для тех, кто захочет писать олимпиаду в следующем году, а количество людей из года в год явно растет, советую спать по ночам… Лучше потрать два часа на код, но он будет хороший нежели написать ночью и потом в течение недели искать баги в коде. Для себя я сделал именно такой вывод, когда просматривал свой код в «трезвом» состоянии. Собственно сам код можно посмотреть тут: github.com/ivlevAstef/CodeCupAI2016MOBA. Там много комментариев на русском, которые могут помочь разобраться в коде. Правда для понимания архитектуры придется потратить время.

Хочу также отметить участника с ником firano (Лобанов Леонид) за непосильную помощь с написанием этой статьи.
И большое спасибо Роману Удовиченко (Romka) за организацию чата в телеграмме и всем активным участникам этого чата. Без вас написание олимпиады было бы намного скучнее, хоть и продуктивнее.

Автор: ivlevAstef

Источник