История 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 жизней. Турели, лучники и мечники имеют урон 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 считая, что другие рабочие это препятствия. И если он так ничего не находит, тогда повторяем поиск, только уже считая, что другие рабочие не являются препятствиями. В этом случае, "запертые" среди зданий рабочие все же находили ресурсы и шли к ним напролом, даже если там были другие рабочие, мешающие пройти. Это дало интересный побочный эффект: на тесных картах, если поверхность, с которой можно пристроиться собирать ресурсы оказывалась меньше, чем число рабочих, то рабы как бы прижимались к краям, освобождая пространство под постройку.

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

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

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

Рабочий 1 добывает верхний ресурс, а не правый

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

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

В текущей реализации рабочий пойдет по пути серой пунктирной линии, совершит 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) Надо заботиться о том, чтобы не застроить каких-то рабочих, либо принять как данность, что это может иногда случаться.

Пример хаотичной застройки Commandos-а

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

Причем как видно из скриншота, сетка строится так, чтобы дома были вплотную к базе. Это очень хорошо работает на тесных картах. Хотя может показаться, что это довольно расточительно, т.к. по бокам остается аж 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, но самое радикальное решение было предложеноAlexkarloid-ом.

ЧудоGraalVM

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

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

Финал

С приближением финала, становилось все очевиднее, что чего-то моему боту все же не хватает.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-а, а он, если не ошибаюсь подсмотрел уRecar-а, это выпускать свои войска из барака в 3 потока. Один идет по центру, а другие два по флангам: направо и наверх. Это дает то, что фланговые потоки эффективно обходят врага, не дают его диверсантам прошмыгнуть к нам на базу и попутно атакуют рабочих. В сочетании с прокси бараком это улучшение было особенно убийственным.

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

После финала

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Послесловие

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

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