Приветствую!
Напишу о том, как мне довелось поучаствовать и победить в ежегодном чемпионате по программированию искусственного интеллекта Russian AI Cup 2013 (codetroopers). Выступал я там под ником slash и занял первое место как в финале, так и в песочнице на момент подведения в ней итогов.
Сначала пара слов о самом чемпионате для тех, кто не в курсе, что это такое.
Сам чемпионат организуется компанией Mail.Ru Group и проводится в онлайн режиме, то есть участвовать в нем можно не слезая с любимого компьютерного кресла или дивана. Он является открытым, то есть любой желающий может зарегистрироваться на сайте и начать сражаться за призовые места. Проводится уже во второй раз, прошлый турнир проходил в 2012 году, и мы надеемся, что и дальше ребята из mail.ru продолжат в том же духе. Более подробную информацию о чемпионате можно почитать на сайте чемпионата russianaicup.ru, а также в блоге компании Mail.ru Group.
А теперь о том, что будет в этом рассказе, а чего не будет. Наверное, подробной инструкции о том, как дойти до финала и победить в нем, здесь не будет. Согласитесь, это было бы не так интересно, если бы такая инструкция была. Технических подробностей про то, как реализовать ту или иную функцию, какие использовать инструменты, как писать программу — этого тоже не будет. Будет здесь скорее мое лично впечатление о чемпионате, скажем так, осадок, который после него остался. Плюс некоторые идеи, часть из которых мне показались интересными.
Хотя технических деталей описывать в своем рассказе я и не планирую, но с удовольствием отвечу на таковые вопросы, если они у кого-нибудь возникнут. Также для более детального анализа можно посмотреть сам код стратегии: drive.google.com/file/d/0B5pWCOQbKqEuekZNRWNkQUpNbnc/edit?usp=sharing. Он, конечно, написан не идеально, формат разработки все-таки наложил свои ограничения, и глобальные переменные используются, и все в одном файле, но думаю, что вполне читабельно.
Сразу скажу, что ничего сверхъестественного в своей стратегии я не делал. Большинство идей, которые я в итоге реализовал, так или иначе возникали и у других участников, многие уже описаны на форуме чемпионата. Возможно, у меня получилось совместить лучшие из них так, чтобы они заработали максимально эффективно.
Сначала немного предисловия.
Начну, пожалуй, с прошлого года, когда я в первый раз принял участие в подобном мероприятии.
На самом деле, желание написать стратегию, которая сама бы играла против живого человека или против другой стратегии, появлялось у меня, когда я был еще студентом и сам игрался в разные игрушки, но тогда не хватало опыта в программировании, каких-то других технический знаний и самое главное — какой-то конкретной цели, которая бы заставила начать этим заниматься. А так как специально такого рода соревнований я не искал, это желание так и оставалось чем-то вроде мечты до тех пор, пока на нашем университетском форуме (привет ребятам с forumlocal.ru) я не наткнулся на обсуждение прошлогоднего чемпионата.
Надо сказать, обсуждение там было достаточно активное, и тогда в это дело вовлеклось много народу, но мне немного не повезло, так как я заметил эту тему и начал вникать в нее уже перед самым началом первого раунда, понятное дело, пока разбирался с localrunner'ом, пока почитал документацию, пока что-то написал, первый раунд уже прошел и я в него не попал. Пытаться залезть во второй раунд по добору тоже показалось сложной задачей, мне тогда еще было сложно оценить уровень остальных стратегий и шансы оказаться в 50ке, поэтому я остановился на том, что просто довел до конца свою первую идею — а именно, смотря на чужие танки составлять карту выгодности позиций и потом по градиенту ехать в точку максимума. Ну плюс еще пару фишек типа сбивания патронов, которые в меня попадают, стрельбы на опережение и согласованности поворота пушки и корпуса. Дальше я все это залил на сервер и ждал, где моя стратегия осядет.
В итоге закончила соревнования она где-то в районе 2-3й сотни. Меня этот результат вполне удовлетворил, так как показал, что путем не таких больших затрат можно было бы пройти во второй раунд, если бы я начал чуть пораньше, ну а там хотя бы футболку дадут, и стимул играть дальше будет. Ну, подумал я, главное в следующем году начало не провафлить.
В этом году вспомнил про чемпионат где-то в октябре, полистал немного интернет, ничего с ходу не нашел и решил, что наверное как-нибудь да узнаю про начало, опять же на форуме может кто отметится. В итоге пришло оповещение на почту 9 ноября. Правда в тот момент был в целом занят, поэтому сначала проигнорировал его, вспомнил только через 2 дня, когда работа немного отпустила. Заглянул на сайт, ага — все уже началось, но до раундов вроде успеваю. Скачал пакет, все запустилось, времени на настройку ушло минимум — с прошлого года ничего не изменилось, а я еще не успел все забыть.
Теперь коротко о задаче, которую предлагалось решать участникам Russian AI Cup 2013 (скопировано с сайта чемпионата).
У игрока в распоряжении находится отряд из нескольких (от 3 до 5 в зависимости от этапа соревнования) бойцов (юнитов), обладающих разными характеристиками и способностями. Наборы юнитов являются одинаковыми для каждого из игроков. Юниты получают право ходить по очереди. Ход следующего юнита начинается только после завершения хода предыдущего. Ход каждого бойца состоит из одного или нескольких действий, которые боец совершает до тех пор, пока у него достаточно очков действия или он не завершит ход принудительно.
Поле игры представляет собой прямоугольник, разделённый на квадратные клетки. Количество клеток 30 × 20. В начале боя юниты игроков расположены симметрично каждые в своей четверти карты. Юнит занимает ровно одну клетку. Два юнита не могут одновременно находиться в одной клетке.
Очки игрок получает за урон нанесенный бойцам другого игрока (по 1 очку за единицу урона), за уничтожение вражеского бойца (25 очков) и т. д.
Количество набранных игроками баллов — фактор, который определяет победителя (или занятое место). Чем больше очков — тем выше место.
Более подробное описание игрового мира можно прочитать на сайте чемпионата в разделе «Правила».
Идею будем использовать ту же самую, что в прошлом году — просчитывать выгодность каждой позиции и идти в самую выгодную. Она зарекомендовала себя еще с прошлого года, да и вряд ли тут что-то принципиально другое можно придумать. Плюс ко всему еще время совсем дискретное и карта маленькая — значит вполне пойдет полный перебор.
Всего принципиально разных, или можно еще сказать мажорных, версий у меня было две. Первая сыграла в первом раунде, прошла во второй, а уже перед вторым была выпущена вторая версия.
Начну с первой. Так сказать, пишем то, что первое приходит в голову. Стратегий тут на самом деле 2, одна локальная, которая будет определять конкретную позицию, куда пойдет наш солдат, а вторая — глобальная, которая определяет общее направление движения всей команды и ее поведение.
Цель глобальной стратегии — найти врага, убить врага, а потом перегруппироваться и подлечиться, если надо, дальше идти на следующего врага. Естественным образом возникает 3 режима действия, в которых локальная стратегия будет действовать по-разному:
1. Разведка — режим, в котором команда находится, пока не увидит врага.
2. Битва — как только враг обнаружен, начинаем с ним биться до тех пор, пока не убьем всех солдат, либо пока он не отступит, либо пока мы не отступим.
3. После битвы — режим включается после режима битвы, если нет врагов в поле зрения. Еще после 2-3 полных итераций, если врага все еще нет, считаем, что либо он закончился, либо убежал (либо мы убежали). Т.о. снова нужно искать врага, и мы переходим в режим разведки.
Также возникло понятие глобальной цели — в моем случае это была просто клетка на карте, где по моим прикидкам находится ближайший ко мне враг. Туда всегда будет стремиться моя команда. Исключением стали начальные цели на некоторых картах, а именно на тех, где команда разделена на две группы — там пришлось вручную выставлять цель в начальный момент, чтобы они объединились, а уже потом шли на врага. Еще уже после первой половины финала выставил вручную первую цель на карте fefer, иначе команда лезла в трубу смерти и часто попадала там в засаду.
Теперь локальная стратегия.
Итак, солдат смотрит на все позиции (клетка + стойка), до которых может дойти за свой полный ход, для каждой считает несколько параметров:
1. Безопасность. Грубая формула выглядит так: изначальное число жизней нашего бойца минус максимальный урон, который ему могут набить в этой позиции.
2. Очки, которые он сможет там набить, т.е. возможные выстрелы или броски гранаты из этой клетки, плюс для медика лечение тоже считаем очками, так как это его основная профессия. Если вражеский солдат умирает в результате нашего выстрела, кроме очков увеличиваем еще и безопасность позиции. Если в этой клетке бонус — это либо тоже очки, если находимся в режиме битвы, либо безопасность, если находимся в другом режиме.
3. Приоритет. Если мы стреляем в кого-нибудь из этой клетки, то приоритет говорит, насколько выгодно там стрелять именно в этого бойца. Так, например, наиболее приоритетными для выстрела являются медик, командир, снайпер на всех картах, кроме лабиринта (в лабиринте он наоборот имеет наименьший приоритет для выстрела). Если же мы просто идем в эту клетку, то приоритет — это близость к глобальной цели. Чем ближе — тем выше приоритет. Близость здесь измеряется в шагах.
Сначала для сравнения двух позиций я пытался просто сравнивать суммы этих параметров с некоторыми коэффициентами, но быстро понял, что этого недостаточно, так, для безопасности есть некоторые критические точки, например 0, при переходе которой позиция становится существенно хуже. Даже если мы набьем там чуть больше очков, но безопасность будет чуть ниже нуля, то солдат умрет, и потеряем мы от этого существенно больше. Если же наоборот, мы выбьем из чужого солдата все его жизни, это лучше, чем если мы выбьем чуть больше из другого солдата, но он останется жив.
В итоге возникла сложная функция сравнения двух позиций по всем имеющимся параметрам. В первой версии там было около 5 случаев, во второй — около 10. Вот некоторые из них:
Если безопасность позиции больше 50, и превосходство в очках больше 50, то выбираем эту позицию не раздумывая.
Если безопасность позиции больше 50, проигрыш по безопасности не больше 30, а превосходство в очках хотя бы 20 — тоже выбираем эту позицию.
Плюс в каких-то случаях игнорируем некоторые параметры, например, если сравниваем позицию, из которой будем стрелять, с позицией, куда просто идем, то приоритет игнорируется. Если безопасность позиций близка к 0, то игнорируем приоритет глобальной цели. Куда уж там, нас убить могут, а мы тут еще о чем-то глобальном размышляем.
Хотелось еще регулировать общее поведение своих бойцов в плане агрессивности. Для этого определил несколько вариантов поведения, которые на самом деле просто влияли на баланс между очками, приоритетом и безопасностью при сравнении позиций путем изменения коэффициентов.
1. Обычное поведение — попытка максимально сбалансировать очки и безопасность, находимся в таком поведении, если число бойцов противника такое же, как у нас.
2. Агрессивное поведение — делаем больший упор на очки и приоритет, меньший на безопасность. Поведение активируется, если у врага осталось меньше солдат, чем у меня, либо если я давно не видел врага, нужно его искать более агрессивно.
3. Раш — добиваем врага, если у него совсем мало солдат, или если мы долго находимся в режиме разведки, и при этом отстаем по очкам. Нужно быстро бежать кого-нибудь искать.
4. Защитное поведение — стараемся действовать аккуратно, акцент на безопасность. Включается, когда мы не знаем порядок хода с врагом, или когда у него небольшое преимущество в численности.
5. Бегство — тупо сваливаем с поля боя, если враг имеет сильное численное превосходство.
После такого способа ранжирования и небольшого шаманства с коэффициентами стратегия стала довольно неплохо сначала двигаться к глобальной цели, а потом стрелять по врагам.
Однако, были некоторые проблемы.
Первая — солдаты могли идти в обход какого-нибудь препятствия с разных сторон. Чтобы такой ситуации не возникало, я добавил штрафы в безопасность каждой клетки. Штрафы были 4х типов: штраф за минимальное расстояние по манхэттену до союзника, штраф за максимальное расстояние по манхэттену до союзника, штраф за минимальное расстояние в шагах до союзника и штраф за максимальное расстояние в шагах до союзника. Понятно, что если первое расстояние большое — значит солдат совсем отделился от остальных, за это ему был большой штраф. Если первое маленькое, а второе большое, значит он отделился, но не один, а с кем-то еще. Это, конечно, не так плохо, но все равно влепим ему штраф, чтобы был стимул соединиться с остальными. Расстояние в шагах тоже необходимо учитывать, так как солдат может находиться близко, но за стенкой. С другой стороны, близко за стенкой, и далеко по шагам — это лучше, чем чуть ближе по шагам, но дальше по манхэттену, потому штрафы за расстояние по манхэттену выкидывать не стоит. Поблажки даются только лидеру, который должен бежать вперед, тем самым увеличивая расстояние до остальной группы, остальные должны его сокращать. В качестве лидера выбираю скаута, если же скаут совсем в поганом положении или умер — лидером становится тот, кто ближе к цели.
Вторая проблема — находясь в режиме разведки солдаты не видели врагов, поэтому безопасность считалась некоторым эвристическим образом, зачастую переоценивалась, что приводило к тому, что они в погоне за высоким приоритетом клетки выбегали к врагу, а увидев его уже не успевали спрятаться назад. Пришлось искусственно занижать коэффициент приоритета, если до конца хода бойца осталось всего 1-2 шага.
Третья проблема — иногда возникала ситуация, когда в начале хода рядом с солдатом лежал бонус, но он его не брал, так как он оценивал позицию в целом и считал, что лучше он убежит ближе к глобальной цели и получит за это больше очков за приоритет, чем возьмет бонус рядом, ведь что будет после того, как он возьмет бонус, он уже не просчитывал. То же самое со стрельбой — можно один раз стрельнуть, а потом спрятаться, а солдат вместо этого сразу убегает за стенку, потому что посчитал, что стрелять из той клетки опасно.
Появилось довольно простое естественное решение — нормировать очки по числу затраченных действий, тогда он легко увидит, что тут можно взять бонус всего за 2 очка действия, а туда надо идти аж 10 или 12 очков, или стрельнуть за 4 очка действий вместо того, чтобы убегать за 8 очков действий.
Однако с этой нормировкой я довольно много намучился, например, получалось выгоднее всего стоять на месте, так как на это вообще не тратятся очки действия, или возникали неправильные решения по поводу того, лучше стрельнуть, или бросить гранату и т. д., навставлял в эту нормировку кучу костылей и уже сам стал в них путаться, в итоге с трудом заставил все как-то сносно работать к первому раунду с мыслью о том, что подход неверный, и в следующей версии нужно делать просчет полного хода солдата целиком.
Последний штрих — научиться определять, кто ходит раньше, враг или я. Уже в первой версии я понял, что эта информация очень важна, например, при выборе цели для выстрела больший приоритет у меня имели враги, которые ходят раньше, при этом нужно было определять, сходил этот солдат уже или еще нет, ходит их медик раньше моего, или наоборот.
Для начала реализовал самые простые способы определения порядка ходов:
1. Если врага только что не было в этой позиции и вот мы его увидели — значит он ходит раньше/позже в зависимости от типа бойца. Или солдат остался в той же позиции, но у него изменились очки действия, пропала граната или что-нибудь в таком духе.
2. Если мы видели в прошлый ход, но тут он исчез, то с большой вероятностью он куда-то ушел. Тут возможен второй вариант — его убили, так что второй способ является менее достоверным, но тоже можно его использовать.
В первой версии я реализовал только эти два варианта, потом появился еще один.
Итак, первая релизная версия готова, уверенно мочит smartов, заливаю на сервер, вижу, что после всех описанных исправлений держится неплохо (к тому моменту она уже доползла до 30ки), во второй раунд пройдет.
Пилить первую версию смысла вроде бы уже не было, потому что знал, что буду переделывать основную логику, поэтому решил сделать небольшой перерыв и поднакопить идеи.
Вообще, как мне показалось, у меня гораздо лучше получалось придумывать новые идеи, если я в это время ничего не писал, мысли не тратились на то, чтобы решить, как именно тут переместить бойца именно туда, как правильно выбрать стойку и т.д. Можно было спокойно рассуждать глобально и оценивать, какой подход стоит реализации, а какой нет. За эти пару дней перед первым раундом я окончательно осознал, что запиливать стратегию под какие-то конкретные шаблоны и места на картах мне будет влом, нужно делать что-то универсальное. Вообще при разработке я получаю гораздо больше удовольствия, если моя программа или система делает все сама в автоматизированном режиме, чем если необходимо ей задавать какие-то входные параметры, указывать что-то, вручную выставлять какие-то подсказки и т.д. Тут наверное играет роль природная лень в хорошем своем проявлении — типа лучше я сейчас чуть побольше подумаю, зато потом мне ничего не придется делать, все сделают за меня.
В целом в течение этого месяца у меня сложился примерно такой способ разработки — утром за завтраком любуюсь боями своих солдатиков, радуюсь за их достижения, но также отмечаю для себя некоторые моменты, где можно было бы поступить иначе. Потом, пока еду на работу или с работы или еще куда — есть время обдумать все эти моменты и осознать, почему бой пошел не так. Важно сначала попытаться найти именно глобальную причину, а не списывать сразу все на неверный коэффициент, подправив который можно запортить остальные 10 боев. Осознав, что есть недоработки на глобальном уровне, как правило, придумывал сразу и какие-то варианты решения, которые уже вечером воплощались в жизнь. Бывало, конечно, что и до вечера не удавалось дотерпеть, чуть свободная минутка на работе выдалась — быстрей-быстрей кодить, пока тепленькое.
Итак, основные изменения, которые появились во 2й версии.
Во-первых, перебор теперь происходит не по всем клеткам, до которых может дойти солдат, а по парам клеток, а точнее парам позиций (клетка + стойка), одна из позиций — это позиция действия, т. е. в которой солдат что-то делает, а вторая — финальная позиция, где он заканчивает свой ход. В позиции действия совершенно не обязательно он должен в кого-то стрелять или кого-то лечить, он может просто до туда дойти и получить за это очки. Например, если там лежит бонус.
Так как перебор существенно расширяется, моя стратегия начинает вылазить за рамки отведенного времени — на первом этапе спасает просто кэширование вычисленных параметров позиций, хотя дальше к этой проблеме придется вернуться еще не раз.
Теперь сравнивать нужно пары позиций, я назвал их целями. У каждой цели остаются прежние параметры, а именно
1. Безопасность финальной позиции
2. Очки в позиции действия
3. Приоритет финальной позиции в смысле глобальной цели + приоритет действия в позиции действия, если действие имеет место.
Плюс добавляется еще один параметр:
4. Очки, которые я планирую получить в следующие ходы. Сюда добавляем, например, очки за то, что солдат разведал клетку, которая раньше была в тумане. Очки, которые получит боец-союзник, если я ему подсвечу предполагаемого врага. Очки, которые я смогу получить на следующий ход из этой финальной позиции.
С помощью этих же «очков на следующих ходах» удобно оказалось оценивать стрельбу по врагам, которых могут добить союзники. Так, например, если я посчитал, что могу стрельнуть по солдату на 20 очков, а потом ходит мой снайпер, причем солдат за это время никуда не уйдет, и его никто не вылечит, то я записываю себе 20 очков, а также 80+25 очков, полученных на следующих ходах. И это получается выгоднее, чем стрельнуть по другой цели пусть на 40 очков, но которая успеет уйти перед ходом снайпера.
Причем на первый взгляд сложный маневр типа подсветить одним солдатом врага, ранить его, а потом добить снайпером, пока он еще никуда не ушел, получается автоматически, ничего даже специально подкручивать не надо. При этом враг нас может даже не заметить.
Тут удалось выбить вражеского снайпера, но только за счет того, что мой ход был раньше его хода, в обратном случае он бы точно так же застрелил моего снайпера. Кажется, что ходить первым немного выгоднее, но с другой стороны, тот, кто ходит последний, имеет больше шансов таким же макаром завалить разведчика, так как видит его уже после того, как тот сходил.
Далее, вычисляя возможные повреждения своего или чужого бойца, которые он может нанести по заданной позиции, я начинаю учитывать возможные передвижения бойца перед собственно действием. Раньше считал только повреждения, наносимые с места.
Добавляю еще вариант распознавания порядка хода игроков:
3. Анализирую очки полученные игроками и проверяю типы бойцов, которые могли их нанести. Действует практически безотказно, плюс имеется возможность определить порядок игрока, ни разу с ним не встретившись — очень большой плюс. Странно, что не добавил его сразу.
Тем не менее, абсолютно надежным методом является только 1й, поэтому пока он не сработает, считаю что порядок определен почти наверняка, но все-таки есть очень маленькая вероятность, что определен неверно, поэтому совсем критические решения на основе него принимать не стоит.
Стратегия начинает красиво воевать, слаженно выбирая самую незащищенную цель и вышибая вражеских солдат двухходовыми схемами, но все ломается, когда большая часть вражеских солдат оказывается в тени, а при приближении ко 2му раунду почти все топы только так и играют, что зачастую у них удается подглядеть только одного-двух солдат.
Разумеется, для этого случая у меня уже накопился целый вагон эвристик типа если рядом с солдатом есть свободная клетка, которую я не вижу, возможно там стоит его союзник, и в этом случае я, например, умножаю его повреждения на какой-то повышающий коэффициент, чтобы учесть также повреждения от его союзника. Или наоборот, при расчете выгодности броска гранаты искусственно повышаю очки за бросок, если рядом с солдатом есть свободная теневая клетка в расчете на то, что там стоит еще один солдат. Но чем дальше, чем сложнее становится синхронизировать все эти эвристики, чтобы они друг другу не противоречили, если бойцов становится 5, а видно только одного, то иногда получается, что эвристика слишком сильно переоценивает, или наоборот недооценивает ситуацию, в общем, мне это все начинает нравиться все меньше и меньше.
В конце концов приходит решение отказаться от всех эвристик и искусственных подкручиваний очков в пользу четкой математической модели, для которой все можно будет однозначно подсчитать, и ставка, таким образом делается на точность этой модели.
Теперь каждый вражеский боец становится размазанным по всему игровому полю в соответствии с некоторым распределением вероятностей. То есть мы считаем, что в каждой клетке стоит каждый боец, но, возможно, с вероятностью, отличной от 1. Тогда все функции подсчета повреждений, нанесенных мне вражеским бойцом, и повреждений, нанесенных мной вражескому бойцу, не меняются, лишь результат умножается на вероятность того, что этот боец действительно стоит в этой клетке. То же самое автоматически получается и при вычислении вероятности того, что враг увидит моего бойца в свой ход. По сути, вместо того, чтобы решать задачу с неполной информацией мы решаем несколько раз задачу с полной информацией, но каждый раз для своего исхода в вероятностном пространстве, а потом просто считаем мат.ожидание.
Остается только правильно вычислить вероятности всех этих бойцов для каждой клетки. И чем точнее будут вычислены вероятности, тем более точной информацией будут обладать мои бойцы, тем лучше они выберут свою цель. Вот как раз это и стало моей основной задачей вплоть до самого финала чемпионата.
Однако тут же возникли и некоторые технические трудности. До этого у нас было не более 3 врагов, у каждого не более 4 солдат, даже если все 12 одновременно появятся в поле зрения, обсчитать их вполне хватило бы времени. Тут же у нас возникают целые полчища вражеских солдат, до 12 человек в каждой клетке, а если считать разные стойки, то все 36, понятное дело, что посчитать для каждого из них урон в обе стороны — никаких 2 секунд не хватит. Приходится чем-то жертвовать. Но с другой стороны и понятно чем — самыми маловероятными солдатами. Так, в финальной версии у меня не обсчитывались солдаты с вероятностью меньше 0.001, а те, у которых вероятность была меньше 0.01, считались в огрубленном варианте.
Итак, вернемся к подсчету наших вероятностей. Делаем их в 2 этапа.
Первый этап — отсекаем те клетки и позиции, в которых солдаты не могут находиться чисто физически, например те, которые мы сейчас видим, или до которых солдат не успел бы добежать с момента, когда мы его последний раз видели, даже если бы прыгал семимильными шагами, или те, которые мы видели совсем недавно, и солдат с тех пор еще не ходил.
Второй этап — на оставшихся клетках строим распределение вероятностей в соответствии с информацией о игроке и солдате, которая у нас есть. Если мы знаем примерное положение игрока (от командира, или недавно видели кого-то из его солдат), то строим что-то наподобие нормального распределения с центром в этой клетке. Если прошло не так много времени с момента, как мы видели солдат игрока, пытаемся экстраполировать их движение, основываясь на средней скорости игрока. Этот же метод используем в начале сражения, считая, что все бегут друг другу навстречу со скоростью примерно 4-5 клетки. При этом считаем, что чем дальше солдат отклоняется от средней скорости игрока, тем он менее вероятен. Если же прошло много времени и про игрока ничего не известно, предполагаем плохой случай и считаем, что враг где-то совсем рядом, т.е. высокую вероятность получают солдаты, находящиеся на расстоянии менее 1.5 максимального обзора.
Несмотря на все попытки построить распределение максимально точно, иногда получается переоценка или недооценка вероятностей каких-то солдат, и это приводит к тому, что повреждения по какой-то позиции переоцениваются и солдаты боятся куда-либо идти, например считая, что сейчас из всех углов выбегут камикадзе и начнут в них пулять. Пришлось отсекать варианты, когда вражеский солдат без особых причин выбегает на максимум своих очков и делает 1 выстрел — таким образом он себя сильно подставляет, что считаем маловероятным. Либо наоборот, наш солдат считает, что рядом никого нет и выбегает на открытое пространство, где его благополучно расстреливают. В этом случае пришлось более серьезно относиться к позициям, которые простреливаются из многих клеток, и даже если вероятность врагов в них мала, бежать туда с большей осторожностью.
Наверное где-то в этот момент случился 2й раунд, после которого я в первый раз дополз до 1 строчки песочницы и даже некоторое время там продержался.
Далее, вообще говоря, никаких существенных изменений в стратегии не было, а все, что были, можно отнести к разряду «точно не хуже, чем было». Но тем не менее, некоторые из них я тут перечислю.
Научился определять все возможные клетки, откуда мог стрелять в меня вражеский солдат, и куда он мог спрятаться, если я его не вижу сейчас. Это давало более точное множество возможных клеток в первом этапе вычисления вероятностей.
Начал хранить историю карт видимостей всех солдат на 3 итерации назад. С помощью них определял клетки как менее вероятные, если я их видел не так давно.
Оптимизировал работу командира по вызову самолета — теперь приоритет этого действия рос по мере того, как росло время, прошедшее с последней встречи с врагом.
Начал обрабатывать выстрелы в темноту, т.е. анализировать полученные очки, попал/не попал, даже пытался предсказать, что тот солдат, в которого я стрелял, был убит в результате моего выстрела. В результате огреб веселый баг, который проявился вот в этом бою: russianaicup.ru/game/view/519509. Тут в меня стреляет вражеский штурмовик, я считаю для него наиболее вероятные клетки и стреляю в одну из них (снайпером на 10м ходу). По очкам получается, что попал (а на самом деле попал в медика), заключаю, что штурмовик действительно там, но когда открываю эту клетку, штурмовика там нет, а по ходам он все еще должен там стоять — следовательно, помечаю его как умершего. Все это накладывается на еще один баг в логике, которая по идее должна была обратно пометить его как живого, когда я его снова увидел. В результате получаем зомби-штурмовика, на которого мои солдаты бегут, потому что при вычислении глобальной цели штурмовик виден, но не стреляют, потому что при выборе цели он помечен как мертвый и игнорируется.
В результате оставил минимальный анализ, чтобы не стрелять второй раз в тень, если один раз туда уже промахнулся, и наоборот, стрелять еще раз, если в кого-то там попал.
Подточил определение вероятности бойцов, которых видел недавно основываясь на наблюдениях за другими стратегиями. Так, заметил, что если ранить медика и убежать куда-нибудь в тень, то медик думает что он в безопасности и начинает лечиться не сходя с места. Тогда, если он ранен больше, чем может вылечить за ход, с большой вероятностью он будет в той же клетке. Это же верно и для остальных солдат, многие еще раз выбирают ту же самую клетку на следующий ход. Сам же в своей стратегии ввел штраф в безопасность тем, кто остается на том же месте, что был в начале хода.
Заметил, что иногда мои бойцы уничтожив одного-двух вражеских солдат радостно бегут добивать остальных (в силу изменившегося поведения на агрессивное), и попадают под пули остальных засевших в засаде врагов. Это было важно для боев с 4 игроками, там нужно было быстро добивать первого врага и бежать ко второму. Если остался всего один враг, и очков у меня больше, чем максимум из остальных, сделал своих бойцов более сдержанными. Хоть это и привело к тому, что в некоторых боях они стали позорно отползать и кемперить в засаде, за что прошу прощения всех противников, которых удалось выиграть столь гнусным образом, но в зато число бессмысленных рашей сократилось.
Наказал своим бойцам не лезть вперед скаута путем введения штрафов в безопасность, если солдат находится ближе к цели, чем скаут.
Добавил учет бонусов, поднятых при переходе к позиции действия при выборе самого действия и отхода.
Наконец-то доделал фишку, чтобы бойцы не мешали друг другу при перемещении на большие расстояния, особенно эта проблема доставала в лабиринте, когда какой-нибудь балбес последним своим шагом вставал в проход и запирал всех остальных. Достаточно было просто сравнить количество шагов до глобальной цели каждого союзника с учетом вновь выставленного бойца и без нее. Разницу, как обычно, записываем в штраф очков приоритета. Тем самым вроде бы совсем мы это и не запрещаем, но очков солдат получает меньше, если встал в плохую позицию.
Чего я так и не сделал в своей стратегии, но на мой взгляд, тоже неплохие идеи.
Организация работы с бонусами. Правильно было бы распределять бонусы между солдатами по принципу «кому нужнее». У меня единственное, что было сделано — паек отдается снайперу, если нет других пайков в зоне досягаемости. Можно было бы добавить еще несколько правил типа отдавать паек тому, у кого уже есть граната и наоборот. Аптечку оставлять медику и т.д. Можно строить карту бонусов (они же расположены симметрично) и специально идти за бонусами, которые с большой вероятностью еще никто не взял, если бой затянулся или пошел неудачно для нас, чтобы переломить ход игры в свою пользу за счет новых бонусов.
Расчет количества оставшихся в живых солдат по очкам (не реализовал в силу того, что когда дошел до этой идеи, второй раунд уже прошел и я переключился на дуэли, а там это никакого смысла не имеет). По изменениям в очках можно быстро установить порядок хода игроков, потом следить, если изменение очков не подходит под возможный урон текущего типа солдата — значит кто-то был убит. Так, можно отследить, сколько человек убил каждый из игроков. После того, как мы расправимся с первым врагом (рассматриваем только такой случай, остальные нам не интересны :)), смотрим, кто из остальных игроков остался в живых (например с помощью командира), если мы убили не всех солдат своего первого врага, вычитаем это число из числа убитых кого-нибудь из оставшихся так, чтобы сумма сошлась, по оставшемуся числу или двум определяем сколько солдат осталось у каждого игрока. Метод в целом, конечно не абсолютно достоверный и начинает работать не очень хорошо, если у нас кого-то убивают, и между нашими солдатами ходит несколько чужих солдат, но в целом должна получиться неплохая оценка.
Некоторые забавные баги, которые возникали в моей стратегии.
Один с штурмовиком-зомби уже описал чуть выше. Еще один похожий баг был, когда только появился снайпер, и я неправильно рассчитывал его видимость без учета штрафа видимости в положении снайпера лежа. По моим расчетам снайпер должен быть там, и клетка открыта, а в списке видимых бойцов его нет — значит он умер. Вот вам и снайпер-зомби.
Еще один баг случался, когда у меня оставался один боец. Казалось бы, один боец, считай уже проигрыш, можно дальше не смотреть, но вот этот бой поставил меня в тупик и заставил покопаться в коде: russianaicup.ru/game/view/514859. Совершенно очевидно, что оставшийся в живых медик легко должен завалить снайпера, но почему-то вместо этого ныкается в угол. Оказалось, что всегда, когда у меня остается один боец, минимальное расстояние до остальных бойцов оказывается равным 100500 (некоторое начальное значение, которое должно перезаписываться первым же союзником). В итоге боец получает огромный штраф за минимальное расстояние и в судорогах пытается спрятаться из клетки с безопасностью -100500 в клетку с безопасностью -100499 и никакие очки его в этот момент не интересуют.
Я уж не говорю про плюсы вместо минусов, когда вместо штрафа за большое расстояние до союзников солдаты получали за это бонус и радостно разбегались в разные стороны. Такие ляпы обнаруживались еще в локал раннере и до сервера не дошли.
Про время, отжираемое моей стратегией.
На форуме уже где-то заметили, что она получилась одной из самых прожорливых, на грани фола, так сказать. Разумеется, в первую очередь это обусловлено достаточно глубоким перебором, но цели выжать максимум отведенного времени у меня не стояло. Понятное дело, было несколько моментов, когда она начинала превышать лимит, после чего я запускал профилировщик и вставлял какой-нибудь кэш или сокращал излишне широкий перебор. После чего заливал на сервер, проводил несколько боев и убедившись, что все пролазит по времени, забывал до следующего затыка. О том, что у меня стратегия до сих пор иногда падает по времени я узнал уже ко второй половине финала, когда нашел на сайте ссылку «Бои с упавшей стратегией». Сейчас глянул профилировщик, действительно там было пара совершенно ужасных мест с точки зрения скорости. Так с ходу удалось раза в 2 увеличить скорость на одном из боев, который падал по времени без каких-либо изменений в логике. К тому же есть всегда потенциал для ускорения путем повышения порога для точного обсчета солдатов, т. е. если поднять порог грубой оценки с вероятности 0.01 до 0.02, можно еще ускорить.
Про время и ресурсы, затраченные мной на стратегию.
В целом времени затрачено достаточно много. Писать приходилось в основном по вечерам, но иногда и на работе сколько времени удавалось отхватить. В последнюю пятницу перед финалом вообще почти весь день посвятил стратегии, благо рабочий график позволял. Тут еще сыграл тот факт, что я понимал, что в субботу у меня на нее времени не будет, а если и будет, то совсем мало, поэтому старался максимально вылизать все в пятницу. Так в общем-то и произошло. В пятницу вечером посмотрел первую волну финала, слегка прифигел от своей стратегии, и лег спать с мыслью «блин, а неплохое начало, ладно, если до утра в тройке продержится, то авось до конца воскресенья из 6ки и не вытеснят», на завтра подъем в 7:45 и тяжелый длинный день.
Жена по началу смеялась, мол играется в войнушку, потом, когда дополз в песочнице до тройки лидеров, стало проще отмазываться, мол вот, на призы иду, ну а в финале уже всей семьей болели за моих солдатиков.
Всю разработку вел в visual studio, тестирование минимальное с помощью Localrunnerа и сразу на сервер, за ночь как правило что-то набегало и можно было уже оценить новую версию. Пару раз заливал совсем ужасные баги, в результате чего существенно скатывался в рейтинге, приходилось откатывать до предыдущей версии.
На следующий чемпионат планы освоить какой-нибудь новый язык программирования в таком игровом режиме. На призы уже, конечно, вряд ли можно будет рассчитывать в этом случае, но зато хоть польза какая-то будет.
Вот наверное и все, кто дочитал до конца — молодец.
Всем удачи в боях!
Автор: yshutkin
