CodeWizards — Russian AI Cup 2016, техническая часть

Изначально решил взять в качестве основной технологии потенциальные поля (potential fields). Впоследствие оказалось, что большинство участников из топа (если не все) поступили так же, только использовали их все по-разному. Это, грубо говоря, карта опасности. Карта разбивается на клетки, для каждой считается коэффициент опасности. Объекты, представляющие опасность, излучают поля, затухающие по мере удаления. Точно так же, объекты интереса, снижают поле опасности и являются аттракторами. Для attenuation-а использовалась простая линейная интерполяция. Пробовал в некоторых случаях другие функции интерполяции, но они не давали большого преимущества и при этом прилично увеличивали нагрузку на проц за счёт вычисления квадратных корней и прочих экспонент. Также в некоторых местах использовались условные функции, которые, к примеру, линейно увеличивали опасность в определенном радиусе, но при этом оставляли "кольцо" сниженной опасности, которое являлось оптимальной зоной для выстрела.

Долго мучился с градиентным спуском. А точнее, local minima avoidance. Так и не нашёл нормального варианта, который хорошо бы отрабатывал во всех случаях. Всегда находилось исключение, где всё ломалось. Пробовал интегрировать по полю опасности, как завещал Mr.Smile, но мне это тоже показалось нецелесообразным, т.к. в игре не было инерции и направление движения менялось мгновенно. В итоге плюнул и начал просто выбирать точку с наименьшей опасностью в заданном радиусе, а затем пытаться проложить к ней пусть с наименьшим суммарным cost-ом по узлам графа.

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

Для макроконтроля был свой класс под названием Emperor, который, по моей задумке, должен был имитировать игрока за компьютером, который дает задания. Класс генерировал Order-ы, которые представляли собой точки на поле с заданной силой притяжения и радиусом. Вейпоинтов, как таковых, у меня не было. Вместо них были чистые потенциальные поля, заставляющие двигаться к order-ам. В целом, макроменеджмент у меня был очень костыльный и написанный левой ногой, потому что я в большей степени делал упор на боёвку и его реализовать нормально просто не успевал.
Да, кроме того, путь к order-ам прокладывался не напрямик, ибо я прокладывал путь только в радиусе расчета ПП (он у меня на разных этапах равнялся 400-450 юнитов), так что часто получалось так, что ПП заканчивается в лесу, а когда добираюсь до точки назначения, оказывается, что это — тупик. Поэтому для ордеров я сделал простенький BFS c полусотней нод и считал attenuation не по эвклидову расстоянию, а по суммарной длине пути от игрока до ордера, если двигаться по дорожкам. А через лес я ходил только если финальная точка пути лежит вне леса. Т.е. если я прохожу его насквозь. Также были костыли, чтобы избежать завтыкивания между двумя ордерами, где притяжения уравниваются (а-ля точки Лагранжа).

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

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

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

Первой (и одной из двух основных) функцией микроконтроля был додж. Уклонение от пуль. Каждый тик я смотрел, не летят ли в меня пули (ну точнее, заклинания, но у меня в коде они назывались bullets). До этого у меня тоже была функция уклонения, но более примитивная. Итак, я проводил симуляцию по 8 направлениям движения (вперед/назад/левый и правый стрейфы и 4 диагонали). для каждого направления добавлял три turn-а (движение без поворота, полный поворот влево, полный поворот вправо). Это проводилось по отношению к каждой летящей в меня пуле и в итоге выбиралась та цепочка действий, которая позволяла уклониться от наибольшего числа пуль (в случае, если в меня летит сразу больше одной). Работало это достаточно хорошо и до конца уже почти не менялось. Причем, если я видел, что увернуться не могу, то я даже не пытался и сразу шел в контратаку, навстречу пуле.

Второй основной функцией была функция атаки. каждый игровой тик, в случае, если мой cooldown был равен нулю (я перезаряжен), либо был меньше, чем у противника, я проводил симуляцию предположения "а что будет, если я прямо сейчас пойду в атаку, выстрелю при первой возможности и постараюсь уйти от ответного выстрела?". При этом я исходил из предположения, что противник будет стоять на месте и только будет поворачиваться ко мне и стрелять в ответ. При этом, цепочку action-ов я нигде не сохранял и каждый тик пересчитывал заново, поэтому это достаточно хорошо работало, несмотря на то, что противник на самом деле не стоял на месте.
Суть была в том, чтобы атаковать в тех ситуациях, когда подобная симуляция говорила о том, что у меня есть шанс выстрелить и при этом не получить пулю в ответ. Т.к. это строилось на предположении, что противник не будет двигаться, что не являлось правдой, то по факту, часто он стрелял. Но всё же не всегда, т.к. его часто атаковали ещё и крипы, кроме меня. А я в любом случае шёл в атаку только будучи не сильно битым, так что меня устраивало, если он всё же ответит мне и мы разменяемся.
Одним из побочных следствий, к которым я стремился, было то, что если в меня выстрелили и попали, то скорее всего, я выстрелю и попаду в ответ. Кроме того, я переписал функцию выбора траектории для выстрела: я перебирал 21 угол в вокруг врага, для каждого угла ставил себя на вражеское место и пытался "уклониться". В итоге выбирал тот угол, где уклониться не выходило. Причем, стрелял только в том случае, если враг точно не сможет уклониться. Вернее, относительно точно, ибо симуляция уклонения всё же была довольно грубой, так что бывали случаи, когда всё же промахивался, но редко.
Вот эти две функции дали мне резкий рост рейтинга во второй половине второго раунда (ребята из чата помнят, как я считал "недополученную прибыль" по сравнению с тем, если бы реализовал это днём ранее, и сокрушался об упущенном 30-м месте во 2-м раунде)

Кроме того, со временем микроконтроль оброс ещё кучей функций — для ближнего боя, для того, чтобы убегать от орка таким образом, чтобы он меня не доставал, для подбора бонусов ровно в момент их появления, для того, чтобы оказываться в радиусе получения очков (очки за каждого убитого врага начислялись всем союзникам, кто оказался в определенном радиусе и эта функция стремилась попасть внутрь этого радиуса в случае, если кто-то из моих союзников бъет врага и он при смерти), для уклонения от башен в том случае, если их целью мог быть я, для побега от врага по оптимальной траектории (из моей позиции строились три вектора — строго назад по отношению к средней вражеских магов, а также под 0.6 * Π и -0.6 * Π). Из них выбиралась одна, в которой менее "тесно" и к которой мне поворачиваться быстрее всего, а врагу — дольше всего.
Ну и ещё несколько других функций.
Кроме того, здесь же пришлось реализовать простую функцию обхода препятствий без графа, ибо на момент микроконтроля у меня ещё не было никакой сетки, а считать ПП только ради поиска пути было дорого. Я запилил простенький homemade алгоритм — берём отрезок от мага к цели (AB) и проверяем на коллизии (если расстояние от центра какого-либо объекта до отрезка меньше чем сумма радиусов этого объекта и мага, я считаю, что столкновение происходит). Если оно произошло, делю отрезок пополам, строю перпендикуляр к этой точке и на перпендикуляре нахожу нахожу две точки, в которой коллизии уже нет (C и D — точки слева и справа от объекта). затем склеиваю отрезки AC-CB и AD-DB в, смотрю, какой из них короче, и рекурсивно вызываю эту же функцию по отношению к каждому отрезку.
Так повторяю до тех пор, пока не будет найден путь, либо пока не будет достигнут лимит глубины рекурсии.
Очевидно, что это никак не алгоритм поиска пути, а только лишь алгоритм обхода препятствий. Но работал вполне сносно. Причём, я сохранял послений найденный путь, и если в следующем тике был найден путь короче предыдущего, я заменял его. Так что обычно получалось так, что первый путь был очень грубым, но по мере движения по нему, он всё уточнялся и в итоге получался близким к оптимальному.

Вкратце, полный workflow выглядел примерно так:

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

В общем, как-то так оно всё работало. Напоследок, традиционное видео из моего визуализатора (слева — официальная визуализация для разработки, справа — то, что рисую я сам, вместе с debug информацией и т.д.). Фрагмент боя 2х2 моей последней версии с предыдущей (разница в силе не очень велика, поэтому особого преимущества одной из сторон на видео нет):

Ну и ссылка на мой профиль на сайте. Если кому-то интересно, там можно посмотреть игры.