Симуляция дуэлей юнитов HoMM III: кто сильнее в честном 1vs1? / Хабр

В Heroes of Might and Magic III у каждого игрока есть свои ответы на вечный вопрос: какой юнит сильнее? Кто-то смотрит на урон, кто-то на способности, кто-то вспоминает личный опыт из партий, где один отряд неожиданно перевернул ход всего боя.

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

А сравнивать юнитов хочется! И не мне одному. Вокруг HoMM3 давно существует отдельный жанр контента: сравнения юнитов, рейтинги, дуэли и попытки ответить, кто сильнее в своём тире. Например, можно встретить ролики, где юниты сражаются друг с другом один на один, или авторские тир-листы юнитов. Для подобного сравнения требуется ручной прогон битвы, а для этого надо создавать кастомную карту, брать героев с одинаковыми статами, использовать ландшафт, который не влияет на скорость юнитов, и т.д. Учитывая, что логика боя не очень сложная, появилась идея: почему бы не использовать симуляцию таких боёв? Так появился этот проект: небольшая модель боя HoMM3, которая позволяет моделировать дуэли юнитов и смотреть, кто чаще побеждает при заданных условиях.

Ограничения

Для первой версии проекта я специально взял только дуэли, так как их намного проще симулировать. Поле представляет собой полосу клеток (одномерное поле), по краям которой стоят сражающиеся юниты. Плюс к этому мы рассматриваем юнитов без учёта героя, что позволяет сравнивать их напрямую, игнорируя первичные и вторичные навыки. Также стоит отметить, что в коде возможны небольшие баги: часть способностей и крайних ситуаций ещё требует проверки. Логика применения некоторых эффектов очень сложна, и часто возникают множественные исключения или условия (тут подробнее можно почитать FizMig и понять, насколько сложными могут быть взаимодействия эффектов и способностей юнитов). Тем не менее основная канва уже работает: юниты ходят, атакуют, отвечают, применяют эффекты, бой завершается победой одной из сторон или ничейным/неопределённым исходом.

В рамках данного анализа я провожу сравнение только улучшенных юнитов из актуального набора городов HoMM3 HotA v1.8.0, так как они обычно обладают более интересными способностями по сравнению со своими неулучшенными вариантами. Ну и данный текст лучше воспринимать больше как фан, нежели как "окончательный научный рейтинг юнитов HoMM3". Это скорее возможная рабочая версия методики сравнения юнитов.

Данные

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

Методика симуляции

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

Для каждого фиксированного тира берём список улучшенных юнитов HotA. Например, для первого тира это набор улучшенных существ: Halberdier, Centaur Captain, Master Gremlin, Familiar, Skeleton Warrior, Infernal Troglodyte, Hobgoblin, Gnoll Marauder, Sprite, Oceanid, Halfling Grenadier и Kobold Foreman. Мы будем проводить по сражений между каждой парой юнитов. Порядок сторон тоже учитывается: A vs B и B vs A считаются отдельными боями (разница небольшая и влияет только при одинаковых скоростях: кто ходит первым), поэтому суммарно между двумя юнитами будет проведено боёв.

Зачем нужно много боёв?

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

одиночные юниты (в каждом стеке ровно юнит);
месячный прирост (в каждом стеке число юнитов, равное месячному приросту в замке);
покупка на 10к (покупаем максимальное возможное число юнитов на золота);

Каждый сценарий симулируем отдельно, так как число юнитов может сильно влиять на исход боя. Если у нас юнитов первого тира, то мы имеем $12 \cdot 11 / 2 = 66$ пар, для которых надо провести сражения. Общее число битв, которое необходимо провести:

$100 \cdot66 \cdot3=19800$

Попробуй запустить столько в самой игре!

В результате для каждого сценария получается матрица (диагональ не учитывается, потому что юнит не дерётся сам с собой):

строки - атакующий юнит;
столбцы - защищающийся юнит;
значение в ячейке - сколько раз атакующий победил в серии боёв против выбранного противника.

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

Результат симуляции битв между одиночными юнитами.

Результат симуляции битв между месячными приростами юнитов.

Результат симуляции битв между юнитами, закупленными на 10 000 золота.

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

Победный score

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

$\text{score}(i) = \text{mean}_j (\text{wins}_{ij} / n)$

Где: $\text{wins}_{ij}$ - число побед юнита над юнитом (из полученной матрицы); n - число повторов боя для одной пары, а $\text{mean}_j$ - среднее по всем противникам этого тира (столбцам), кроме самого себя. Такой скор лежит в диапазоне от до . Значение около означает, что юнит почти всех стабильно побеждает. Значение около означает средний результат. Значение около означает, что юнит почти всем проигрывает.

Но один сценарий, определяющий размер стека, даёт слишком узкий взгляд. Поэтому итоговый рейтинг собирается из всех трёх сценариев.

Сценарий	Вес	Что означает
`unit1`		Один юнит против одного юнита
`growth1m`		Месячный прирост юнитов в стеке
`gold10k`		Сколько юнитов можно купить на золота

Итоговая формула:

$\text{score}_{total} = 0.2 \cdot \text{score}_{unit1} + 0.4 \cdot \text{score}_{growth1m} + 0.4 \cdot \text{score}_{gold10k}$

Почему веса такие?

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

Победный score (по каждому сценарию и общий) для каждого юнита.

Итак, топ-3 юнита с наибольшим скором побед: Halberdier, Sprite, Centaur Captain.

Итоговая таблица лидеров

Аналогичные симуляции и расчёты были проведены для всех тиров юнитов. Финальная таблица победителей приведена ниже.

Для наглядности названия юнитов перекрашены в цвета замков. Видно, что в таблицу лидеров попал хотя бы один юнит из каждого замка, кроме Инферно. Видимо не зря он считается одним из самых слабых замков.

Выводы

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

Ещё один плюс такого подхода - расширяемость. Если данные лежат в базе, то можно относительно легко добавлять других юнитов: например, существ из WoG, VCMI-модов или других наборов контента. После этого их можно прогонять через ту же методику и сравнивать уже не только оригинальные/HotA-существа, но и модовых юнитов.

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

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

Что дальше

Следующие шаги проекта планируются такие:

проверить и доработать все специальные способности юнитов;
улучшить стратегии поведения юнитов;
попробовать reinforcement learning для выбора действий: действий у юнитов немного, они дискретны, поэтому обучение потенциально может быть достаточно быстрым;
расширить базу юнитов на внешние моды, например WoG или VCMI;
в далёком будущем попробовать добавить юнитов из других частей Heroes of Might and Magic (например, 1,2,4,5,...), хотя там уже придётся отдельно думать, как сопоставлять характеристики между разными играми;
перейти от дуэлей 1vs1 к более сложным боям между армиями.