Перейти к содержимому

Серебро в Legends of Code and Magic

17/08/2018

Вот эта штука заставила напрячься по настоящему. Во-первых, игра модальная — т.е. сперва идёт драфт и тебе нужен один движок ИИ, а потом начинается собственно матч и тебе нужен другой движок, тем не менее решения принятые первым влияют на решения второго. Во-вторых, игра достаточно случайная. Чтобы это нивелировать (видимо) с каждым соперником проводится по два матча. Я бы проводил вообще до двух побед, как в MtG принято. В третьих, сложность игровых ситуаций иногда просто зашкаливает — столько всего надо учесть и сделать за ход.

Как всегда, начал я с простых эвристик. Для драфта — оценочная формула, сравнивающая эффект карты с её стоимостью и приоритизирующая атаку. Игровой движок — просто «атакуй всеми в противника как можно быстрее», т.е. типичный архетип аггро. С этим добром я умудрился добраться до бронзы. В бронзе такой фигни стало критически не хватать, и я сел пилить симуляцию. Аггро решил оставить, поэтому для экономии ресурсов симуляция включалась только в случаях когда у противника есть Провокаторы — существа, не дающие атаковать оппонента напрямую. Тогда рассчитывался способ с минимальными для меня потерями ликвидировать защитников и самых хрупких атакующих, сохранив при этом максимум своих. Потом симуляции пришлось добавить ограничение по времени, ибо его стало не хватать для просчёта всех вариантов. Потом отсеивание лишних планов атак — например, раз у противника есть Провокаторы, то все планы начинающиеся не с атаки в провокатора просто убирались из пула. Ближе к концу я поступил даже эффективнее — выкидывал все планы, где атаки в провокатора шли после атак в любые другие цели. В итоге планы оставались только те где провокаторов выносили в самом начале.

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

Ещё один серьёзный недостаток моей симуляции — я считал только один порядок атакующих. Т.е. сперва атакует существо m, потом n и так далее, необязательно в том порядке в котором они стоят на поле. Идея как перечислить все варианты планов для одного порядка пришла ко мне в автобусе по дороге на работу, и я радостно её реализовал. Но как перечислить все вероятные варианты для всех порядков? Уже набросанный класс симуляции не позволял так легко передавать и учитывать разные порядки атак, да и по времени симуляции я иногда был впритык. У меня была мысль расширить то как в симуляции хранится план и просто изначально генерить все возможные перестановки атакующих, но там было бы много одинаковых по сути планов, которые просто занимали бы вычислительное время. Если все провокаторы убиты, неважно в каком порядке отстреляются по игроку остальные существа. Но лёгкого способа обрезать такие ветви я так и не придумал.

Но такой симуляции оказалось недостаточно, и пришлось оптимизировать ещё и призыв существ. На поздней игре, где маны много, уже возможно вызывать по 2~3 существа за ход. И какое сочетание существ (из имеющихся в руке) будет оптимальным, это сложный вопрос. Я уже знал что по сути это задача укладки рюкзака (точнее, 0-1 knapsack), но про алгоритм решения только слышал что на больших наборах он очень неоптимален. И да, я помнил что задача эта NP-сложная. Но теперь пришлось закопаться в это поглубже и выяснить для себя, как 0-1 рюкзак решается методами динамического программирования (на псевдокод метода ветвей и границ я только раз взглянул и понял что любой другой способ скорее всего будет проще). В итоге ДП-метод был сделан, немного протестирован и закинут в бота. С этими дополнениями бот рванул в первую сотню бронзовой лиги и плотно там обосновался.

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

С этими добавлениями через полчаса после очередного сабмита я наконец увидел заветное сообщение «Ты лучше босса и через две минуты будешь переведён в серебряную лигу». Это был триумф. Правы были люди из чатика — без симуляции и серьёзных минмаксов из Бронзы не вылезти. В серебре мой бот устаканился примерно на 300 месте из 450. Но там противники — мама не горюй, и в золото выйти, похоже, уже не получится. Но даже серебро в таком сложном соревновании, я считаю, очень значительное достижение.

Реклама

From → Uncategorized

Добавить комментарий

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход /  Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход /  Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход /  Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход /  Изменить )

Connecting to %s

%d такие блоггеры, как: