История 4го места на Russian AI Cup 202017.01.2021 22:47

В этом году поучаствовал в соревновании по написанию игровых ботов 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 таким образом, чтобы считать лес не 

© Habrahabr.ru