Russian ai cup

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

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

Послесловие

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

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

Данная статья рассмотрит процесс моего участия с тёмной стороны - менеджера проектов. Немного о мотивации, немого о времени и приоритетах. За светлой стороной технических деталей лучше обратится к статьям T1024, Lama, SilentNox.

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

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

О чемпионате

В 2019 году задачей было написать бота для 2d шутера. Вот пример видео от Lama:

Чемпионат проходит в несколько этапов, каждый длинной в одну неделю:

1. Бета тестирование.

2. Первый этап. Перезапуск с незначительными изменениями правил по результатам теста. Боты регулярно сражаются друг с другом в песочнице. В конце недели первый раунд.

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

4. Финальный раунд. Очередное изменение правил - карты становятся сложнее. Без поиска пути на них делать нечего. Бои в песочнице по правилам всех раундов. Финал - 50 победителей второго раунда+10 лучших песочницы. Призовые первые 6 мест.

Какие нужны навыки?

Кажется очевидным, что для победы необходимо:

• Хорошо уметь программировать, чтобы это ни значило.

• Иметь опыт участия в подобных соревнованиях, желательно в RAIC прошлых лет.

• Начать со старта беты - это дополнительная неделя.

Заканчивается первый этап (прошла примерно половина времени) - присоединяется человек, который ни дня не работал программистом и только иногда писал скриптики для автоматизации работы, а в соревновании участвовал только много лет назад в школе на pascal. Ваши ставки на место? Мои ставки до того, как я понял, о чём вообще речь, были: ну я потыкаю, как оно вообще работает, и хватит, а после первого знакомства - "надо войти в топ 250 - во второй раунд и получить футболку, как участник второго раунда". У меня большое самомнение : )

Посмотрим ещё раз на задачу. Нас просят не написать чистый алгоритм - Вася варит n яиц в m кастрюлях. Это задача уровня выше - вот цель, вот правила, вот ограничения. Вам нужно за имеющееся время написать наилучшее решение. Тут можно выделить много подзадач из серии У вас оружие с параметрами p1, у врага c параметрами p2 - найдите оптимальную для вас дистанцию стрельбы. Т.е. помимо решения отдельных маленьких подзадач, нам нужно их самому правильно сформулировать и приоритизировать. А потом выбрать нужный баланс между качеством и трудозатратами с учётом ограниченного времени.

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

Итого для данного чемпионата добавились два важных навыка:

• Гибкость, скорость реакции на изменения мира, готовность изменять стратегию.

• Постановка и выбор наиболее важных задач.

Хм а это точно чемпионат не для тимлидов, аналитиков и менеджеров? Ах, задачи придётся выполнять самому, а не отдавать программистам.

Итак, очевидно, что времени для идеального исполнения мне не хватает. Судя по сложности задачи, предположу, что и большинству участников не хватит тоже, даже несмотря на то, что у них 4 недели, а не 2. Итак мы имеем функцию от времени f(t)->max. Осталось понять что мы будем максимизировать. На первый взгляд, финальное место в рейтинге/крутость бота. И в слагаемых функции будут всякие параметры стратегии. Допустим уклонение от пуль, стрельба, поиск пути. Распределяем время на разработку по этим параметрам - и мы победили : ) Ладно, добавим фундаментальные исследования - изучение платформы, подтягивание знаний ЯП, рефакторинг и оптимизацию. Но люди не машины и в разных условиях одна и та же задача может занять и 2 и 8 часов. Поэтому нам нужно также решить задачу поддержания высокой производительности. Поэтому первую часть чемпионата я буду максимизировать удовольствие от участия, для повышения мотивации продолжать. А место в рейтинге будет всего лишь замечательным искусственным индикатором эффективности, рост рейтинга - быстрая положительная обратная связь.

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

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

Платформа

Вот тут большой респект организаторам.

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

Обычно в самом начале у участников часто мотивация низкая (что это вообще такое, нужно ли оно мне, может время на что-то другое потратить?) и высокий порог входа однозначно отсечёт сомневающихся. Например меня бы точно отсёк. Здесь же на старте сразу даётся:

• Базовая работающая стратегия. Хватай пушку, беги к врагу и стреляй. На разных ЯП.

• Визуализатор (local runner), который позволяет сыграть самому мышкой и клавиатурой против бота или же запустить своего бота против стартовой стратегии/другой версии своего бота. И показывает собственно сам бой.

• Простые правила первого раунда. Один юнит и простая карта.

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

Это дает возможность за 10 минут добавить к базовой стратегии, допустим, сбор аптечек и сразу же увидеть результат - моментальная положительная обратная связь. Причём по нескольким каналам восприятия: и сам сбор аптечек, и звук сбора и возросший шанс на победу - чаще побеждает бот. Что в свою очередь даёт мозгу информацию А это не так и сложно. Если за 10 минут мы уже столького добились, то давай попробуем вложить больше времени, прикинь какой тогда эффект будет?.

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

Да нас сама платформа подталкивает работать в потоке! Осталось только помочь ей!

Немного теории о потоке и модели Фогга в моём кратком изложении.

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

• Сложность >> Навыка - тревога

• Сложность << Навыка - скука.

• Сложность ~ Навыку - потоковое состояние - максимальная концентрация на задаче, чувство потери времени, озарения и т.п. Но ресурсозатратно для организма.

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

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

В теории Фогга говорится что для совершения действия необходимо:

1. чтобы мотивация была выше, чем затраты усилий на за задачу;

2. толчкок/тригер/напоминание для совершения действия.

Можно создавать события повышающие мотивацию, снижающие (субъективную) сложность и просто напоминания.

Для завершения теоретической базы хочется добавить ещё:

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

• Фундаментальная ошибка атрибуции. Чтобы здраво оценивать свои достижения и достижения других и своевременно реагировать.

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

Программист VS менеджер

Так получилось, что в качестве аватарки я использовал логотип моего проекта по развитию soft skills, поэтому лично для меня этот чемпионат ещё превратился в проверку гипотезы могу ли я за счёт soft skills компенсировать недостаток hard skills.

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

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

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

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

Общий подход менеджера - не надо решать задачу идеально, надо решать по наилучшему соотношения польза/время.

История участия

Начало. Тут какое-то соревнование идёт? Выглядит симпатично, давай глянем. Погружение низкое. Навык и мотивация тоже. Задача: решить участвовать или нет.

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

Открываю пример кода стартовой стратегии на Python И половину не понимаю. Программист: Тут пипец сложно, это не мой уровень только разбираться во всём будем неделю. А и так уже 2 недели соревнования прошло. Пошли отсюда.. Менеджер: Давай глянем другие примеры, общая логика-то понятна.

К счастью пример на C# оказался написан попроще, а там уже в Python стало понятно. Но что делать? После игры со стартовой стратегией кажется, что она и так уже играет идеально. Быстрый анализ выдал - подбирай аптечки и уворачивайся от пуль. Программист, конечно же захотел всё это реализовать, а в идеале увязать в единую логику, только неясно как. Менеджер: давай вначале аптечки сделаем. Аптечки делались копированием кода подбора оружия и заменой пары значений. 10 минут, запускаем - оно работает! Моего уровня достаточно для написания RAIC!

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

Время уворачиваться от пуль.

Метод назывался try_to_be_neo

П: хочет писать идеальный код уворота от всех пуль.

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

П: но там же может быть стена, или я не могу сейчас прыгать или ещё что.

М: просто игнорируй это.

П: это же часто будет не срабатывать!

М: пусть это будет срабатывать в 50% случаев. Для простоты будем считать, что в среднем нужно попасть по врагу 4 раза, вероятность попасть 20%, скорострельность одинаковая. Тогда у врага шанс попасть в нас 10%, а у нас в него 20%. Это даст нам около 84% побед, при куда меньших затратах времени. Наша же задача побеждать не всегда, а чаще, чем оппонент. А оставшиеся 16% потребуют для реализации куда больше времени, чем этот алгоритм, но дадут куда меньше пользы на данном этапе.

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

//использование дедлайна для стимуляции- приём известный всем студентам.

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

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

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

М: пф, запретим юниту брать базуку, пусть берёт всё остальное.

//5 минут, +1 доп условие и резкий буст к победам.

Это дало: резкое усиление мотивации. Показало, что не всё так сложно и как минимум в первую половину участников мы уже легко попадаем. Нужно участвовать!

Стратегия и правда легко прошла после открытия песочницы в понедельник с 1000+места в топ 300. Несколько напоминает MVP.

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

К сожалению для меня задача усложнилась, теперь в бою часто участвуют уже 2 юнита с одной стороны. Все-то научились одним управлять в первую неделю, а теперь время командной работы. А я ещё с одним не разобрался. Посмотрев на игры, я выделил следующие зоны развития: Стрельба, уворот, контроль поля, командная работа, доп фичи. 0% реализации в любой зоне, кроме доп фич, даёт резкое падение эффективности, при этом до 20-30% доводится довольно быстро, и даёт сильный взлёт. Т.е. 20% стрельба и 20% уворот выгоднее, чем 90% уворот и 0% стрельба (почти невозможно победить не стреляя).

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

Командной работы тут ни у кого нормальной нет и выигрыш по оценкам она пока даёт небольшой. Быстро пилю свои 10% (не стреляй в спину своему) и возвращаюсь к другим доработкам.

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

Во вторник занимаю двухсотые места в рейтинге. В среду вхожу в топ 100 - шанс не попасть во второй раунд мизерный. Задача выполнена.

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

Теперь задача во втором раунде войти в топ 50, чтобы попасть в финал. Всё в базовом виде реализовано, общая логика работы понятна. Мотивация высокая и не требуется постоянное подкрепление. Можно теперь потратить время на фундаментальные исследования и вложения в будущее - переписать код понятнее, сделать сложные расчёты. Где-то здесь были переходы к более универсальным моделям, понятной структуре. Здесь же я допустил ошибку и начал писать симуляцию на 60 тиков (ходов) вперёд перебором. Каждый ход есть 9 вариантов действия юнита. На первый ход 9 вариантов, на второй 81 и т.д. Представляете порядок 9^60 (и это только для одного юнита, а в идеале считать все перемещения всех четырёх)? Это очень много - не рассчитывается за адекватное время. Ну а мои программист и менеджер проглядели этот момент. Программист только теоретически знает о сложности алгоритмов, а менеджеру кажется логичным подход когда компьютер считает(работает), а человек думает. Знакомые настоящие программисты когда я им потом рассказывал этот момент громко ржали : )

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

Утро пятницы, код стал упорядоченнее, некоторые функции уже выглядят не как мешок ifов и магических циферок

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

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

Конец первой части второго раунда. Моё место около 14. Есть 24 часа на правки. День отдыха дал о себе знать. Это было почти 24 часа программирования запоем. Пригодились мои фундаментальные исследования геометрии пуль, деталей прицеливания, разброса и т.п. Симуляция многих моментов, была сильно улучшены за счёт перехода на новую более тщательную и быструю модель мира. Остаётся 4 часа до запуска. Мозг уже заканчивается. В поисках, что бы ещё быстро и не сложно улучшить, перечитываю документацию. О! Есть мины. Я ими ещё не пользуюсь, т.е. они реализованы на 0%. Значит, возможно в них можно немного вложить и получить заметный рост. А есть проблема. Мой рейтинг побед около 90%. Стартовая стратегия работает по принципу: беги и прилипай вплотную к сопернику. Из-за особенностей карт держать дистанцию удаётся недолго, а вплотную уже неважно, насколько точно целиться и как уворачиваться. И мой условный шанс победы над стратегией, которая идет на сокращение дистанции, около 80%. Вроде хорошо, но это меньше моего текущего рейтинга побед. Простых стратегий довольно много. По правилам игры трюк поставить себе мину под ноги и взорваться вместе с врагом выгоден по очкам. Это кажется проще всего и надёжнее для защиты от любителей подойти вплотную. Пара строчек, пара ifов, мол если случайно всё совпало и есть мины, и враг уже рядом, и союзника рядом нет, то взрывайся нафиг, не испытывай судьбу. Конечно, программисту это было чуть скучнее и он рвался реализовывать хитрое чередование союзников по перезарядке оружия.

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

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

Тут мне с мотивацией помогает уже достигнутое высокое место в раунде, обсуждения в чатике соревнования про CProfile и Cython (снижение сложности), и несколько друзей, которые свято уверены, что я просто очень умный и могу занять призовое место (немного повышение мотивации, немного повышение субъективного навыка).

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

Пару слов про поиск пути. С первого же дня в чатике было много обсуждений про поиск пути, ругались страшными (для меня на тот момент) словами дейкстра и астар. Складывалось впечатление, что это что-то очень сложное и его надо начинать делать сильно заранее до последней недели. Мой программист пару раз тоже кричал, что раз это сложная задача, к которой вообще неясно что делать, то надо взяться за неё пораньше. Менеджер неизменно отвечал: Пока отложим её. Пока забудь про неё. Я контролирую процесс. Потому что субъективно это была задача сложнее чем навык и вызывала тревогу. К тому же было бы сложно получить явный результат, т.к. игр на сложных картах не проводилось. Итак, у меня 12 место в раунде. Большинство игроков из топового диапазона без особых проблем справляются с этой задачей. Вряд ли она кардинально сложнее всего, что я уже решил. Место и сравнение с другими сильно повысило субъективную оценку моих навыков и снизило сложность задачи. Она как раз оказалась в секторе потока. И вот именно тогда я взялся за поиск пути.

Оказалось, задача и правда куда проще, чем я думал. 2 часа - нагуглить и понять основные алгоритмы. И остаток дня - разработать и реализовать поиск пути для своей стратегии. И ещё 1,5 дня - написать навигатор, который сможет без особых багов водить по этому маршруту ботика. Из смешных моментов - мне помогло знакомство с навигаторами в смартфонах - часто бывает, что точка полученных GPS координат в одном месте, а стрелочка вашего положения в другом. Вот и мой навигатор действовал так же при сходе с маршрута. Если отклонение небольшое и незапланированное, то ещё пару мгновений будем считать, что это ошибка позиционирования и на самом деле юнит идёт по маршруту.

В итоге мой довольно простой поиск пути отлично работал.

А профилирование заставило меня долго ругаться. Я как раз в процессе рефакторинга переписал почти всё на предложенные организаторами типы данных, взятые из базовой модели. ООП, единообразие, наше всё. Огромный выигрыш в быстродействии я получил, переписав ещё раз все координаты на примитивный tuple.

Минимум к финалу - готов. Что дальше? Сейчас в песочнице проводятся бои по правилам обоих раундов и финала. Т.к. нас интересует только финал, то остальные игры сознательно игнорируем как не показательные. Так же не смотрим больше на рейтинг в песочнице, чтобы не делать универсального бота. Решение только под финал написать проще, чем универсальное. На картах финала больше аптечек и мин, и это играет роль: во-первых, мои ущербные мины начали приносить чуть больше пользы, во-вторых, в районе моего рейтинга образовалось много людей, которые побеждали за счёт стратегии добежать до соперника и взорваться с ним. В целом такая хорошо реализованная стратегия давала место что-то вроде 15-20 в общем зачёте. Я нашёл только один хороший вариант борьбы с ними: если они прибежали - взорваться первым. А если не прибежали, то расстреливать, т.к. стрельба и уворот у меня лучше реализованы. Потратив пару часов на анализ, пришлось увеличить приоритет действиям по сбору минимального комплекта мин, чаще держаться земли (в воздухе нельзя поставить мину, а пока я в прыжке, враг подбегал и взрывался со мной) - в целом повысить вероятность создания благоприятных условий для использования мины. Если не можешь сейчас взорвать мины, значит ты беззащитен против близкого врага. Это дало достаточную защиту и я радостно почти забыл про мины, оставив сам подрыв кривой проверкой после всех тщательно рассчитанных действий мол а не выгодно ли взорваться ли нам сейчас? Почему я не реализовывал стратегию подбегаем к врагу для подрыва? Я ошибся в предсказании действий других топов. Из-за простоты моей проверки я думал, что все её или лучшую воткнут как мастхэв и мины станут практически не применяемым оружием. Все юниты будут просто держаться друг от друга вне зоны действия мин, т.к. как только подойдёшь ближе, то тебя взорвут. Поэтому я радостно занялся более интересными частями алгоритма про командную работу и стрельбу. Как оказалось я ошибся и мины очень неплохо себя показали. А вот не надо подходить к мои юнитам - они от этого нервничают.

10 минут до старта финала, уже всё отправлено. Формально правки для себя запрещены, чтобы хуже не сделать. И тут вижу, что в одном месте вроде не учитывается какой-то момент. Сейчас улучшу! - Но мы же не успеем оттестировать! - Да тут просто! Изменяю. Отсылаю. Код принят. И тут я смотрю на код ещё раз я ошибся, и эти правки сломали проверку мин и иногда боты взрывались сами просто так :) Гонг - старт финала, на 12 часов новые стратегии не принимаются. Конечно, я исправил тут же обратно и отослал, но всю первую часть финала содрогался от периодического самоубийства своих ботов. Хорошо хоть не частого.

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

Из смешного про работу с мотивацией.

Перед вторым раундом я сильно улучшил алгоритм стрельбы. Учёт вероятности попадания, изменения разброса, наилучшая точка противника для усложнения уворота. И всё такое. Звучит очень всё хорошо. Тесты не показали выигрыша, а скорее небольшое падение процента попаданий. Программист отказался принимать такие результаты тестов - ещё пару раз проверил - должно быть сильно лучше. Менеджер, прикинув запас прочности стратегии и временя поиск проблемы, помечая в блокнотике: хорошо, хорошо, давай оставим. Тесты в 5-10 запусков с текущим рандомом и правда не показательны.

Приближается финал.

М: Слушай, я помню там были неоднозначны тесты новой системы прицеливания. Давай попробуем протестировать с более простой.

П: Давай.

Тестирую - лучше с простой.

Оба: ну и фиг с ней, отключаем.

Потому что прошло время и П уже это не так ценно. Для него сейчас гордость - поиск пути.

Итого:

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

• Очевидно, что работать в потоке эффективнее, но надо не забывать отдыхать.

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

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

• Гибкость. Готовность изменяться и принимать мир как он есть, а не как его хочется видеть. Приоритетные оружия у меня менялись раз 6, в зависимости от текущего уровня стратегий врагов и крутости моей стратегии. Если долго отрицать реальность и бухтеть на её несправедливость, то можно не успеть адаптироваться, как у многих случилось с минами.

• Думает человек, работает компьютер. Во всяком случае я пока не могу заставить компьютер думать лучше меня, но он куда лучше работает. Зачастую час анализа заменяет 12 часов программирования - можно упростить задачу или вообще её не решать. Я был очень удивлён, когда в чате сказал, что если противник падает, то мы можем довольно точно предсказать его следующие позиции по высоте (очевидно ниже, т.к. прыгнуть или зависнуть невозможно), а мне сказали, что это толстая помощь другим. При том что ссылки на алгоритмы и прочее не являлись толстой помощью.

Благодарности

• Mail.ru Group за интересный чемпионат в таком формате.

• Alexander N за волшебную фразу cProfile же, стандартный для питона, не самый удобный кстати, упоминание Cython и моральную поддержку по возможности Python выйти в топ против уверенности основной части сообщества, что у Python без шансов.

• Сообществу за тёплую атмосферу дружеского соперничества в чатике.

• Всем участникам за интересные вызовы.

• Друзьям, что в меня верили и поддерживали.

• Lama, за видео.

Сейчас начался RAIC этого года! Если вы сомневаетесь, то присоединяйтесь - топовые места ждут вас.