История 4го места на Russian AI Cup 2020

В этом году поучаствовал в соревновании по написанию игровых ботов Russian AI Cup. И хоть не удалось взять 1е место, как в 2017, но все равно это было увлекательное и невероятно азартное приключение длинной в месяц, полное напряженного кодинга, недосыпания, творческих озарений и интриг в финале. Сразу оговорюсь, что в стратегии не использовался AI в современном понимании, с нейронными сетями и прочим - только алгоритмы и структуры данных. Мыслей накопилось много, поэтому приготовьтесь к длинному чтению..

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

Вообще изначально не планировал участвовать, но когда узнал, какая будет тема, сразу как лампочка в голове загорелась "это же как муравьи"! И в то же время понимал, насколько это будет утомительно, и что придется отложить все планы и посвятить все свободное время. Но интерес и искушение поучаствовать все же пересилило :)

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

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

Игровые механики

Организаторы планировали, что игра будет в космической тематике. Но так уж получилось, что оригинальный визуализатор был совершенно не пригоден для просмотра игр, т.к. не понятно, где какой юнит даже с близкого расстояния. В схематическом же виде все гораздо лучше. Серые клетки — это свободные, тёмно-зелёные — это ресурс, или "лес", через них пройти нельзя, но можно уничтожить. Маленькие квадратики с пиктограммой молотка — это рабочие, они добывают ресурс, атакуя его. Стреляющие маленькие квадратики с изображением лука — это юниты дальнего боя "лучники". Есть еще юниты ближнего боя "мечники", но так уж оказалось, что они мало пригодны для боя из-за того, что при достижении некой критической массы лучники могут их расстреливать без потерь, те даже не успевают подойти. Поэтому в боях 1 на 1 их уже не использовали. Но я забежал немного наперед. В первых 2 турах все игры были на 4 игрока - каждый сам за себя. Выглядело это примерно так:

Еще не упомянул о зданиях. Здание с молотком производит рабочих. Здание с луком — лучников. Здания с домиком — это дома, каждое увеличивает максимальный лимит юнитов на 5, подобно тому, как это есть в разных RTS. Еще можно заметить турели, это такие большие стационарные пушки размером 2 на 2, с большим запасом здоровья и огневой мощью как у одного лучника.

Каждый юнит может ходить в 4 направлениях: вверх, вниз, право, влево. У лучников и рабочих по 10 жизней, у мечников — 50. Турели, лучники и мечники имеют урон 5, рабочий — 1. Дальность стрельбы лучника и турели — 5 клеток. Также для добычи ресурсов рабочий не должен возвращаться с добытым на базу: делает он один удар топором по дереву и на следующий же ход 1 единичка ресурса засчитывается на счет игрока.

При постройке зданий вначале оно появляется в неактивном состоянии с 10ю жизнями и рабочий, путем починки доводит его до активного и полнофункционального состояния. Также рабочий может лечить юнитов.

Что понравилось в этом году

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

По поводу формата игр на 4 игроков

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

• Находясь в нижнем левом углу пошел атаковать того, кто справа, а тебя пришел и вынес тот, кто сверху (моя вечная боль с aropan-ом)

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

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

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

Также усложнялось тестирование в первых 2 турах, т.к. приходилось каждое изменение проверять дважды: на 4 игроках (основном режиме тура), и плюс проверять не ослабился ли бот в 1 на 1.

getAction()

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

Чем раньше в списке - тем больше приоритет.

• инициализация состояния

• отмена предыдущих заказов юнитов

• отступление рабочих от опасности

• обработка задач на строительство

• рекрутинг диверсантов

• строительство лучников

• строительство мечников

• строительство рабочих

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

• заказ зданий

• подтягивание рабочих к строящимся зданиям

• движение рабочих к поврежденным турелям

• атака рабочими соседних врагов

• сбор ресурсов, которые находятся рядом

• подтягивание рабочих к ресурсам

• обработка действий диверсантов

• обработка действий лучников

• обработка действий мечников

• атака турелями

• обработка запросов на освобождение места для движения

Составляющие победы

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

• Добыча ресурсов

• Строительство

• Производство юнитов

• Боевая система

• Стрельба

И на более поздних стадиях пришло понимание важности еще таких факторов как:

• Безопасность рабочих

• Пространство

Каждый из факторов — это отдельная тема с множеством нюансов. Рассмотрим их по порядку.

Добыча ресурсов

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

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

Тут рабочий 1 доезжает раньше и занимает место. А второму не останется ничего как искать куда пристроится в другом месте. В итоге второй рабочий совершает кучу ненужных движений.

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

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

С этим вариантом тоже не все так гладко.

Тут, если считать расстояние всегда по прямой, ближайшей будет клетка за домом, и чтобы его обойти надо не 5, а 11 ходов! Тогда как был более близкий ресурс в 6 шагах. И тут мы приходим к тому факту, что встроенного поиска пути нам уже недостаточно. С ним мы не знаем, сколько по факту времени займет путь, а также нет уверенности, как именно будет ходить движок, т.к. в общем случае можно проложить множество разных наикратчайших путей к одной точке.

Для поиска пути есть 2 основных алгоритма: поиск в глубину и поиск в ширину.

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

Поиск в ширину (или BFS) хорош в случаях, когда у нас есть один или множество начальных клеток и одна или множество целевых. Кстати, целевых может вообще не быть, а просто происходить завершение поиска по некоторому условию. В этом поиске, если простыми словами, мы как бы начинаем обход слоями, или волнами, вначале проходим всех клетки на расстоянии 1, потом на расстоянии 2 и т.д. Это гораздо более тяжелый поиск, потому что за раз обходим большое количество клеток, в худшем случае - все поле. Надо стараться запускать его как можно реже. Дойдя до некой целевой клетки, можно по цепочке отследить начало, если в каждой ноде поиска хранить ссылку на предыдущую ноду.

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

Как было у меня?

В общем, я тут немного ударился в теорию, а на самом деле изначально сделал совсем примитивно, а именно: все сущности, в том числе и рабочие сортировались по близости к врагу. Потом от каждого рабочего запускалось BFS чтобы найти ближайший ресурс. И потом вызывалась функция performMove, общая для всех юнитов, которая ищет путь по DFS и ходит в соседнюю клетку. Это даже не спасало от проблемы, описанной в самом начале, когда 2 рабочих едут к одному ресурсу. Но тогда я заметил еще один явный недостаток. Поиск не учитывал, что, если путь заблокирован другим рабочим, что через время он может освободится.

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

Исправил это следующим образом. В начале, для рабочего делался поиск ресурса с помощью BFS считая, что другие рабочие — это препятствия. И если он так ничего не находит, тогда повторяем поиск, только уже считая, что другие рабочие не являются препятствиями. В этом случае, "запертые" среди зданий рабочие все же находили ресурсы и шли к ним напролом, даже если там были другие рабочие, мешающие пройти. Это дало интересный побочный эффект: на тесных картах, если поверхность, с которой можно пристроиться собирать ресурсы оказывалась меньше, чем число рабочих, то рабы как бы прижимались к краям, освобождая пространство под постройку.

Потом по мере добычи периметр сбора ресурсов расширяется, и прижавшиеся рабочие быстро находят себе место.

Кстати, еще интересный вопрос: какой ресурс лучше собираеть, если на выбор есть несколько соседних? Пробовал много разных вариантов, но самым лучшим оказалось собирать ресурс, который уже больше всего добыт (возможно другими рабочими).

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

Следующее, что я заметил, это такую типичную ситуацию

В текущей реализации рабочий пойдет по пути серой пунктирной линии, совершит 2 хода и на 3ий начнет добычу. Тогда как более оптимально было бы стать на место рабочего сверху, а тот который сверху должен подвинуться направо. Да, механика игры позволяла совершить такие одновременные ходы. В этом случае на следующем ходе недополучим 1 единицу ресурса из-за движения рабочего сверху, но уже на второй ход будем добывать 2, таким образом эта 1 единица ресурса возвращается. Вроде прямого выигрыша нет, но тем не менее, по тестам это давало преимущество. Возможно из-за того, что задача дойти до ресурса решалась быстрее, и рабочие меньше времени бегали по полю, путаясь друг у друга под ногами. Реализация была довольно примитивна: для каждого рабочего перед движением проверяем, есть ли у него ресурс в шаговой доступности, где стоит другой рабочий. Если есть, то создаем "запрос" этому втором рабочему подвинуться. Причем, второй рабочий может подвинуться только на клетку, рядом с которой будет ресурс, иначе не удастся выиграть единицу ресурса и весь профит теряется. Если в этой клетке есть еще и 3ий рабочий, то запрос посылается так же и ему, и так по цепочке, пока у крайнего рабочего не будет свободной клетки рядом с ресурсом, на которую тот может пойти.

Но появились сложности..

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

Как сравнивать разные стратегии добычи ресурсов?

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

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

Потом я обратил внимание на игры Commandos-а, который в итоге занял 1е место. У него подход со сдвигами тоже работал, но как-то намного более интенсивно, и не только в экономике, а и в постройке тоже. Призадумался, и мне показалось, что знаю, как он реализовал (хотя, как оказалось не так), и что надо все сделать по-другому.

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

В примере выше, начинаем обход с целевых свободных клеток возле ресурсов, помеченных красным прямоугольником (0 шаг), на 1 шаге волна распространяется от них, проходит сквозь уже добывающих рабов, но пока не двигает их. А когда доходит до свободных рабов, то подтягивает их к себе, с 4 на 3, и с 5 на 4.

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

Когда волна от A доходит до рабочего 1, и успешно подтягивает его - она останавливается. И если по завершении BFS есть рабочие, до которых не дотянулись + есть свободные клетки, к которым еще никто не двигался, то запускаем BFS повторно, от оставшихся свободных клеток (B и C), и уже проходим сквозь рабочих возле ресурсов, а также сквозь походившего рабочего 1, пока не дойдем до рабочего 2.

Далее происходит:

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

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

Строительство домов

Тут есть два разных подхода, каждый из который имеет свои преимущества и недостатки.

Строительство по сетке — это подстройка домов в заранее предопределенных позициях. Преимущества: 1) Экономия пространства 2) Не нужно думать о возможности блокирования юнитов, когда застройкой часть юнитов случайно отрезаются от остальной части карты

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

Хаотичная застройка. Ну тут все наоборот, в качестве преимущества получаем возможность построить дом там, где сейчас стоят больше всего рабочих, а значит закончат они его максимально быстро и без лишних движений. А недостатки: 1) Позиции домов могут получиться очень разреженными, что требует много места 2) Надо заботиться о том, чтобы не застроить каких-то рабочих, либо принять как данность, что это может иногда случаться.

Лично я выбрал путь строительства по сетке:

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

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

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

Тут следует учесть то, что если рабочих мало, то дом будет строиться долго, и можно упереться в лимит. А если рабочих сильно много, то хотя дом и построится быстро, они будут отвлекаться от добычи ресурсов и будет нанесен урон экономике. Для себя я вывел оптимальное соотношение, что дом строят не более 4 рабочих причем не более 1 домов за раз, при популяции до 15, 2 домов при популяции от 15 до 50 и 3 домов - если более 50 . Также начинаем строить заранее, чтобы минимизировать моменты, когда лимит на максимуме и не можем больше строить юнитов.

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

Также я разделял понятия сколько рабочих едут изначально на постройку дома и сколько могут присоединиться позже, чтобы помочь достроить. Вполне реальна ситуация, что в округе нет достаточно рабочих чтобы начать строить, остальные слишком далеко, и начнем строить допустим одним или двумя. Но те, что вдалеке могут случайно подъехать и будут также привлечены к строительству. Почему случайно? Практика показала, что не стоит специально вести рабочих слишком издалека для постройки домов, т.к. лучше рабочий вместо этого будет добывать ресурсы. Так что на помощь в достраивании у меня могут приезжать рабочие с радиуса 15, но не более.

Некоторые участники еще перед подводом рабочего считали, какой вклад он успеет внести в строительство, ведь может оказаться, что рабочий подъедет, но практически никак не сократит время постройки, либо сократит очень незначительно. Это интересная идея, но у меня не дошли руки до её реализации.

Расступись!

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

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

Как подводить рабочих к домам для строительства?

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

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

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

Где строить барак?

Это очень интересный вопрос. Изначально при оценке позиций для барака я старался строить его как можно ближе к углу базы. Почему? Не спрашивайте.. Так подсказывала интуиция. Но потом я случайно заметил стойкую корреляцию, что чем ближе барак к центру, тем больше вероятность победы. Буквально ближе на 5 клеток, и уже новая версия выигрывает, грубо говоря в 55% процентах случаев, на 10 клеток - в 60% и т.д. Поэтому метрика для строительства была переписана так чтобы поощрять более близкие к центру позиции. Это все выродилось в совершенно наглую чизовую стратегию, но об этом расскажу позже)

Приехали строить, а денег нет

Довольно частая ситуация, которая возникала на ранних этапах, что создавалась задача на постройку, когда ресурсы были, но, когда рабочие подъезжали к месту строительства - они куда-то тратились на другие нужды, и теперь денег нет.. Чтобы такого не происходило, когда создана задача на строительство я поначалу запрещал строительство чего-либо еще. Но это грубое костыльное решение, ведь могло оказаться, что денег скопится намного больше, чем нужно. 

Поэтому где-то к концу я придумал механизм резервирования денег на счету. Выглядит это так. Допустим на счету есть 300, и хотим построить барак. Создаем задачу на строительство и резервируем 500 на барак. Далее, когда пытаемся узнать сколько есть свободных денег, то передаем параметром в функцию тип сущности, которую хотим построить. Если допустим это барак - то будет выдано 300, но если это другой тип, например дом, то будет выдано -200 (300 - 500). А значит денег на дом нет. Потом, пока рабочие едут чтобы заложить барак, денег может стать допустим 560. Если теперь спросим сколько денег есть на дом, то будет выдано 60 (560 - 500). А значит дом ценой 50 уже можем без проблем построить и еще останутся деньги на барак. Подобная система резервирования средств сделала строительство более прогнозируемым. Я пытался её применять и для строительства юнитов, но там заметного улучшения добиться не удалось. 

Производство юнитов

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

Экспериментальным путем было установлено, что оптимальное кол-во в среднем для разных карт это около 60. Поэтому бот у меня вначале старался довести рабочих до максимума, а потом плавно достраивал лучников. Хотя минимально 10 лучников должно было быть при любом количестве рабочих.

Тут еще накладывает эффект особая механика, что каждый следующий живой юнит одного типа стоит на 1 единицу дороже. Так, если допустим базовая цена рабочего 10, то при живых 10 рабочих, 11-й будет стоить уже 20. Поэтому достроить 10 рабочих когда у тебя их 60, это совсем не то же самое, что построить 10, когда их у тебя 50. Первый вариант на 100 ресурсов дороже.

Но даже при таком раскладе, все-таки имеет смысл, когда вокруг много мест добычи, достраивать рабочих, чтобы превзойти противника по экономике. Они успевают окупиться. Я в этом убедился, когда была запущена песочница с возможностью запуска игр 1на1. Бот упорно проигрывал тем, кто строил 70-80 рабочих, против моих 60ти.

Нужно ли больше рабочих?

Стало понятно, что нужна некая гибкая стратегия подстройки рабочих и я пришел к такой метрике, которую практически не менял до конца. Строим минимально 40 рабочих. Далее, считаем, сколько уникальных свободных клеток рядом с ресурсами есть в радиусе 3 клеток от моих рабочих, добывающих ресурсы. Вычитаем из этого числа количество рабочих, которые не находятся рядом с ресурсами (т.е. они потенциально займут найденные свободные позиции). Далее вычитаем еще магическую константу 2 и вуаля! Если число получилось положительное — значит стром еще рабочих. 

FreePositionsInRange3 - FreeWorkers - 2 > 0

При уменьшении магической константы бот будет строить больше рабочих. Этим можно и регулировать. В финале я её сделал равной 1. 

Чем хороша такая метрика? Она хорошо работает на тесных картах, где периметр, с которого можно добывать довольно мал. Бот не будет перестраивать рабов, которые в итоге будут стоять и тупить без возможности занять место для добычи. И вместо этого построить армию, которая будет гораздо более полезна на этом этапе. А когда периметр добычи расширится, и появятся места куда встать, тогда уже бот адаптивно подстроит еще рабочих. 

Пример выше: свободных позиций отмеченных желтым: 32, свободных рабочих, отмеченных красным: 19 

32 - 19 - 2 = 11 > 0 , значит нужно строить еще рабочих. Кстати, тут видно одну особенность такой метрики - рабочие в отдалении, вокруг которых нет других рабочих вносят большой вклад по свободным клетки и при наличии таких рабочих бот скорее всего будет идти в макро. Считать ли это дефектом или фичей я не знаю.. 

Когда строить лучников? 

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

Вообще же в бою экономически целесообразно держать лимит лучников как можно меньше и размениваться хотя бы 1 в 1. Тогда Если допустим у нашего бота лимит лучников 40, а у противника 60 но он не может продавить и идет размен - то каждый наш новый лучник будет стоить 35 + 40 = 75, а каждый лучник противника 35 + 60 = 95, и мы даже размениваясь 1 в 1 будем выигрывать по экономике. Но это в теории. А на практике же, когда у бота превосходство по лимиту, то есть неплохой шанс просто продавить, атаковать рабов, снести бараки и т.д. Так это работает для всех, кроме бота Commandos-а :) Он как-то умудрился строить лучников пачками по 40. И пока расходуется одна пачка, копятся деньги на следующую. По каким-то хитрым условиям у него это поведение также отключается и переводится в строительство лучников на все деньги. 

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

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

Боевая система 

Боевая система - это то как именно бот использует войска, чтобы нанести наибольший урон противнику. Её можно разделить на 4 составляющие: выбор цели, перемещение к цели, боевое микро и стрельба. 

Выбор цели 

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

Тут наиболее простое и прямолинейное решение, это идти к самому ближнему вражескому юниту. Что плохого в таком подходе? Пример: на базу проник 1 лучник противника. И мы значит всем войском, произведенным с казармы, начинаем за ним гонятся, т.к. он ближе всех остальных врагов. А в это время, на передней линии войск не хватает, и противник продавливает, захватывая территорию. 

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

Перемещение к цели 

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

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

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

Ближе к концу я модифицировал свой DFS таким образом, чтобы считать лес не препятствием, а проходимой клеткой, но имеющей штраф 6 (столько ходов надо чтобы уничтожить единицу леса). Таким образом ноды со штрафом разворачивались позже, и вначале поиск пытается найти путь по свободным клеткам, и только если не получилось - идет через лес. С этой модификацией лучник уже пытается уничтожить мешающий ему лес сразу, а не ждет, пока окажется заблокированным со всех сторон. 

Считать ли непроходимыми клетками своих лучников? Я считал, но при условии ограниченности радиуса поиска и когда лучник стремится подойти как можно ближе к цели. А значит, если лучники ходят, начиная от ближайших к цели, то получаются вполне организованные колонны - все идут строем один за другим: 

Числами показан порядок перемещения.

Толстая фаланга

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

Красным отмечены пассивные бойцы. Очень хотелось, чтобы вместо того, чтобы подпирать стенку, они старались оббегать её по флангам. И, если будет мешать лес, то чтобы активно этот лес расстреливали. Решилось это комплексом изменений.  

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

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

Третье: когда находим путь к противнику с помощью DFS, то смотрим его конечную точку, если эта точка находится аккурат за спиной 2 моих других лучников, которые мешают пройти к цели - то отменяем поход к этой цели и включаем поиск BFS, который стремится найти ближайшего врага, в обход моих лучников. Это делает практически невозможным ситуацию, когда один лучник упирается в спины других. Ну и во время такого движения деревья не считаем препятствиями, просто даем небольшой штраф за перемещение по ним. Если деревья будут мешать пройти - сразу расстреляем их. 

Все это привело к реально эффектному и стремительному обходу по флангам - то что нужно! 

Боевое микро 

Когда лучники оказываются на расстоянии 7 и 6 клеток к противнику и ближе то внезапно становится необходимо очень ответственно подходить к каждому ходу, т.к. от этих ходов будут зависеть какими будут возникающие бои, выгодными или не очень.. Бой — это когда лучники уже могут стрелять, т.е. 5 клеток к противнику и ближе. 

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

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

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

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

Тут перебирать очень не хотелось, поэтому придумал довольно простую систему: 

• для каждого своего лучника изначально находим кто в радиусе 6 и 7, и сохраняем в отдельные списки, это пригодится потом 

• для каждого вражеского лучника - также, по отношению ко мне 

• сортируем всех своих лучников по степени вовлеченности в бой, а это: по кол-ву лучников в радиусе стрельбы, потом в радиусе 6 и потом в радиусе 7 

• начинаем итерации от самых вовлечённых. для каждого: 

• если у него есть цели в радиусе стрельбы - стреляем, если нет 

• если у него есть цели в радиусе 6, то находим из них самую вовлеченную в бой цель, по тому же принципу как сортировал своих, это пригодится потом 

• смотрим, сколько у этой цели есть наших лучников в радиусе 6, и опрашиваем их, собираются ли они атаковать 

• смотрим, сколько у этой цели есть защитников, т.е. лучников стоящих в радиусе 6 + тех что на подходе, т.е. в радиусе 7 

• если наших больше - атакуем 

• зеркально проверяем по тому же принципу, не смогут ли атаковать нас. Если смогут - отступаем 

• если силы примерно равны - никому не выгодно наступать или отступать, то стоим и ждем подкрепление 

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

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

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

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

Групповые операции 

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

Например, такая ситуация: 3 против 4 лучников противника. Нужно отступить. Если лучники ходят по очереди, и допустим первым будет ходить лучник под номером 2, то он может ненароком своим отходом закрыть путь для лучника 1. Это человеку понятно, что единственно правильным ходом будет отступить вниз, но бота надо еще этому обучить.

Для этого, когда лучники ходят, они еще не ходят по-настоящему. Они только обозначают свое желание сделать что-то. В данном случае все 3 лучника скажут, что они хотят отступать. А потом, после того как все лучники на расстоянии 6 от врагов будут обработаны, срабатывает так называемый групповой отход. Всех лучников, которые хотят отступать делим на группы так, чтобы минимальное расстояние до ближайшего лучника из группы было не больше, чем 2. Далее смотрим, если группа не слишком большая, скажем до 10, то запускаем перебор всех возможных комбинаций ходов отступления. Этого хватает, чтобы в большинстве ситуаций отступления были скоординированными, чтобы одни юниты не путались под ногами у других. 

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

"Я отступаю, подвиньтесь пожалуйста" 

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

Координация через MicroAction 

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

enum class MicroAction {
    NONE,
    STAND_STILL,
    NOT_ATTACK,
    ATTACK,
    GO_CLOSER,
    GO_TANGENTIALLY,
    FALL_BACK,
    GO_TO_HEAL
}

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

Стрельба 

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

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

Как разбивать лучников на группы, участвующие в стрельбе? Ну это довольно просто. Берем произвольного своего лучника, смотрим если есть враги в радиусе стрельбы 5 - добавляем их в текущую группу в качестве противников. Потом смотрим всех добавленных противников, находим всех наших в радиусе 5, и добавляем в текущую группу в качестве союзников. Потом для добавленных повторяем то же самое, и так далее. И, когда некого будет добавить, тогда группа будет готова. 

Как же стрелять оптимальным образом внутри такой группы? Симуляцией, как же еще! Вначале считаем сколько есть вариантов комбинаций стрельбы. Если их до 2 миллионов, что соответствует боям с примерно 10-11 нашими лучниками, значит нормально, можно перебирать. В симуляции за каждого убитого даем 10 очков, за раненого 1 очко. 

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

Диверсанты 

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

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

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

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

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

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

Строительство турелей 

Что сказать, долгое время я их игнорировал. Т.к. хотя они и дешевые время на постройку одной турели довольно большое. В играх 1 на 1 они казались абсолютно неиграбельными. Постановка нескольких турелей уже давала ощутимое проседание по ресурсам, и противник успевал продавливать. Но вот в играх с 4мя игроками они очень выручали. Я экспериментировал с разными стратегиями их постановки, но остановился на такой:  

• Ставим турель если приближаются враги, но еще не очень близко (иначе успеют снести) и в радиусе нет моих войск 

• Приоритет получают позиции близкие к моим рабочим и близкие к ресурсам 

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

Борьба за производительность 

По поводу ограничений: на всю игру, которая состоит из максимум 1000 тиков было разрешено использовать не более 40 секунд времени процесса, и максимум 1 секунду на тик. Довольно быстро я начал упираться в общий лимит. Причем мне это казалось странно, т.к. уже не один год работаю с джавой, и знаю, что она должна уступать C++ не более чем в 1.5 - 2 раза, но блин, факт на лицо, соперники на плюсах намного быстрее. Хотя конечно я не знаю, какие они используют алгоритмы... 

Но в принципе, любые проблемы получалось решить с помощью профилирования. В основном это были какие-то повторяющиеся тяжелые вычисления, которые можно было закешировать. Но, основная причина — это BFS. К слову в, финальной версии суммарно BFS в разных местах отжирал где-то 3/4 всего времени. Так что с этим поиском надо поосторожнее, запускать его как можно реже и по возможности максимально ограничивать глубину. 

Медленная JVM 

Насколько я помню первым бить тревогу по поводу подозрительно медленной джавы и необъяснимых таймаутов на сервере начал Андрей Рыбалка (Lama). Через какое-то время помню он сконтактировал с Commandos-ом и они вместе попытались разобраться в чем причина. Оказалось дело было в jit компиляторе. В принципе - это логично. Бот - это относительно короткоживущий процесс, а JVM рассчитывает на то, чтобы процесс жил подольше и потихоньку оптимизировался. Да, джава не настолько медленнее чем C++, но уже после всех jit-овых оптимизаций, которые тоже жрут процессорное время. Был вариант запускать джаву на сервере с некоторыми флагами, чтобы как-то тюнить jit, но самое радикальное решение было предложено Alex karloid-ом. 

Чудо Graal VM 

Решение состояло в том, чтобы при помощи Graal VM скомпилировать jar-ник бота в exe, со всеми выполненными оптимизациями во время статической компиляции. Alex не поленился и написал даже стартовый пакет для того, чтобы можно было собрать этот исполняемый файл докером. Правда это хорошо работает под линуксом и маком, но не под виндой. Ведь исполняемый файл собирался бы внутри докера, а значит под линукс. А мне нужен был виндовый exe, так что проще было воспользоваться утилитой native-image, которая входит в поставку Graal VM. Только для работы под windows еще требуется поставить дополнительные библиотеки от вижуал студии и с этим возникли определенные проблемы.. Большое спасибо Андрею Ламе, что помог разобраться и Алексу за то, что пропушил всю эту тему. Без компиляции в exe было бы совсем грустно. А так стало раза в 1.5 быстрее, причем еще видно, что процессор стал не так сильно нагружаться и греться. 

Кстати, уже после финала, обновил процессор с ryzen 1700x до ryzen 5800x, что дало еще двухкратное (!) ускорение прогона тестовых игр. Эх! Чего же я не сделал этого раньше.. :) 

Финал 

С приближением финала, становилось все очевиднее, что чего-то моему боту все же не хватает. Commandos и Recar были явно лучше. Также подтягивались и другие топы, которые уже дышали в спину, а то и обходили. Поэтому созрел коварный план.. Помните я говорил, что чем ближе строить барак к противнику, тем сильнее повышаются шансы на победу? А что, если строить барак, эмм, в центре карты. Вот так нагло и пораньше прийти и построить, даже в ущерб экономике? За два дня до финала, начал реализовывать эту чизовую стратегию, известную еще со старкрафта как "прокси барак". Когда полностью отладил и протестировал на разных картах - ужаснулся. Это была бомба.. Абсолютно никаких шансов у моей прошлой версии если у чизовой получилось поставить барак в центре. 

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

Я долго думал, когда лучше залить эту чизовую версию, и решил за 25 минут до окончания приема новых версий перед финалом.. Тогда уже точно никто не успеет ничего сделать. На принятие версии нужно минут 10. Заливаю значит, 15 минут до конца "Отказ тестирования", версия не принята. "О нет! Такого никогда еще не было! Что-то сломалось на сайте." Заливаю еще 2 раза подряд (в чате подсказали, что так можно), у второй попытке снова "Отказ тестирования", 5 минут до конца.. И только 3я попытка прошла успешно. "Фуууух!.." 

И вот начинается финал, и этот чиз начинает всех топов раз за разом разбивать! План полностью оправдался. Правда, эта стратегия оказалась все же не такой стабильной. На некоторых картах проигрывала и намного более слабым ботам. Тем не менее, она мне дала закончить на 3ем месте очень близко к первым двум, и неплохим отрывом от 4го. 

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

Раш фотонками 

Кстати, пришлось подготовится к еще одному неприятному чизу, который приготовил участник Romka в первой части финала. А именно ранняя застройка противника турелями. Или, как это называется в старкрафте - зафотонивание, или фотон раш :) 

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

Сказано - сделано, ввел глобальный булевский флаг turretRushMode, и если он true, то после тика 100 посылаем группу рабочих в угол соперника. Если они видят безопасное здание, то ставят возле него турель.  

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

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

Во второй части финала еще 2 игрока включили раш бараком, так что эта стратегия там иногда помогала. Но чаще нет, т.к. мои рабочие слишком медленно подъезжали в центр, и не успевали достроить турель или даже заметить вражеский барак. 

3 потока 

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

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

После финала 

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

Подтягивание лучников на защиту базы. 

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

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

Менее пугливые рабочие 

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

Другая стратегия постановки турелей 

Ранее мне казалось, что в играх 1 на 1 турели особо не эффективны, а Commandos их строит уже якобы, когда выигрывает, и мог бы выиграть без них. Я ошибался.. Многие игры проигрываются только потому, что пару вражеских диверсантов просачиваются на базу, по одному из боковых проходов. Если бы в этом проходе уже стояла турель, то исход был бы другим.. Но как узнать, как именно будут бежать вражеские диверсанты? Ведь если поставить турель не в том месте - то это пустая трата ресурсов. И когда их строить? Решение оказалось довольно оригинальным. Поскольку карта является зеркальной для обоих игроков я начал предсказывать позицию вражеских диверсантов, как отзеркаленную позицию своих. Таким образом, если мои диверсанты подбегают к противнику, то тут же мои рабочие начинают строить защитную турель против гипотетических диверсантов противника, которые бегут по тому же маршруту ко мне. Причем строят только если враг еще не слишком близко, чтобы успеть достроить. 

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

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

Мечники в играх на 4 игрока без тумана 

По ходу соревнования я много экспериментировал чтобы сделать мечников более полезными. И считаю, что мне это удалось, но для игр 1 на 1. Проблема только в одном: строить барак для них — это слишком дорого. Но вот в играх с 4 игроками без тумана барак уже есть.. В чем же заключалась моя стратегия для мечников? 

• Строить их не больше 10 - иначе они становятся слишком дорогими.  

• Если 1 на 1 с лучником - мечник нападет. 

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

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

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

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

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

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

Послесловие

Еще раз спасибо организаторам за этот конкурс, это было незабываемо!

И конечно спасибо игрокам. То что мы на месяц выпадаем из жизни и с интересом и азартом работаем над одной задачей, пусть и каждый сам по себе - в этом есть что-то магическое :)

Автор: GoodGreenTea

Источник