- PVSM.RU - https://www.pvsm.ru -
WoT Blitz — это мобильный танковый шутер, в котором игроки сражаются в формате 7 на 7.
Матчмейкер, или балансировщик это механизм, который на основе очереди игроков, желающих попасть в бой, формирует состав команд.
У танков есть следующие важные для матчмейкинга параметры:
Самая простая реализация матчмейкера — закидывание игроков в команды случайным образом. Но в данном случае у игроков на низких уровнях не будет никаких шансов нанести хоть какой-то урон, и играть станет неинтересно.
Список требований к балансировщику был сформирован на основе фидбека от игрового сообщества и периодически обновляется по сей день.
На момент написания статьи для обычных боёв список состоял из следующих пунктов:
Разработать матчмейкер, особенно с учётом такого количества ограничений, — очень интересная задача. И подходов к её решению может быть довольно много.
Изначально в мобильных танках использовался балансировщик, доставшийся ему от большого брата — танков десктопных. В целом он работал довольно хорошо, но у него было несколько проблем: во-первых, он не давал чётких гарантий по удовлетворению поставленных требований; во-вторых, добавить новые требования было довольно сложно.
Начало боя
Поэтому был написан другой балансировщик, который работал по следующему алгоритму:
Получившийся балансировщик работал быстрее прошлой версии в 5-10 раз и изначально собирал команды, которые соответствовали всем имеющимся на тот момент требованиям. Новые правила добавлялись путём написания дополнительных проходов перебалансировки.
В начале всё работало хорошо. Но со временем, чем больше правил добавлялось, тем сложнее было написать перебалансировку. Новые перебалансировки должны были в результате своей работы не поломать работу предыдущих. Стало понятно, что это путь в никуда.
Баг в матчмейкере — собралась команда 9 на 9
В конечном варианте мы остановились на балансировщике, который работает по следующему алгоритму. Все игроки, которые нажимают кнопку «В бой», попадают в общую очередь. Балансировщик в бесконечном цикле делает следующее:
Для формирования команд из списка подходящих игроков используется метод имитации отжига. Подробнее про сам метод можно почитать тут [1].
Поиск глобального максимума методом имитации отжига
В контексте применения к формированию команд алгоритм следующий:
Основное преимущество данного подхода: для добавления новых требований достаточно модифицировать оценочную функцию. Нет необходимости писать код, который будет описывать, как именно получить то, что мы хотим. Достаточно добавить правило, которое смотрит на сформированную команду и говорит, хорошо ли она сбалансирована или нет.
Хороший пример добавления таких правил — рейтинговые бои. В рейтинговых боях в матчмейкере появилось сразу несколько новых правил:
Пример профиля игрока из бриллиантовой лиги
Первое правило реализовано путём модификации оценочной функции: был добавлен штраф за превышение максимально допустимой разницы в рейтинге. Второе правило реализовано путём изменения функции, которая вытаскивает подходящих игроков из очереди.
Недостаток данного подхода — медленная скорость работы. По сравнению с предыдущим вариантом, текущий стал работать приблизительно в 10 раз медленней, даже несмотря на ряд оптимизаций. Кстати, про оптимизации. Большая часть сервера (кроме сети и физики) для игры написана на Python. Балансировщик был переписан на C++ и распараллелен на много потоков. Из Python в плюсовый код прилетает запрос на формирования команды. Далее каждый из потоков независимо стартует метод отжига. Как только какой-то поток находит решение, остальные потоки останавливают процесс поиска, и найденное решение возвращается в Python.
Время ожидания и размер очереди на RU сервере (5 секунд в обычных боях и 10 в рейтинговых)
По мере роста онлайна росла и нагрузка на балансировщик. Этой осенью, когда онлайн на RU сервере добрался до 120 тысяч (во время ивента Mad Games), балансировщик перестал справляться. В качестве временной меры мы отключили часть правил, это позволило уменьшить нагрузку. Чтобы избежать подобных проблем в будущем мы сделали матчмейкер распределённым.
Лучшие игроки в бриллиантовой лиге, 21 апреля 2019
Во многих ММО играх, кроме случайных боёв, существуют также и рейтинговые / ранговые / etc. Основная идея данного режима: противники ищутся не случайные, а подходящие по скилу. Если ты скиловый игрок, ты будешь играть с такими-же скиловыми игроками, и наоборот, если ты не умеешь играть, ты будешь попадаться против таких же новичков.
В начале сезона игрок проходит серию калибровочных боёв по результатам которых определяется его стартовая позиция. Затем, в зависимости от дальнейшей успешности игры, игрок либо поднимается, либо опускается в рейтинге. Рейтинговая система в Блице создавалась, в первую очередь, для правильной балансировки. Она заточена на скилл игроков и практически не зависит от количества сыгранных игр.
Для реализации рейтинговых боёв понадобилось решить сразу две задачи. Во-первых, нужно было выбрать рейтинговую систему (по какому принципу начислять игрокам рейтинг). Во-вторых, нужно было доработать балансировщик, чтобы он собирал бои с учётом ограничений по рейтингу.
Основное требование к рейтинговой системе — возможность максимально точно определить уровень игрока. Чтобы оценить, насколько точно работает та или иная рейтинговая система, был создан симулятор, на вход которому подавали историю боёв и выбранную рейтинговую систему, а на выходе получали точность работы системы.
Точность считалась следующим образом:
Наиболее популярные системы расчёта рейтинга: winrate, Elo [2], Glicko [3], TrueSkill [4]. Winrate — обычный процент побед. Elo — система подсчёта рейтинга, изначально созданная для игр с участием двух человек (шахматы, etc). В этой системе игроку за победу / поражение даётся / отнимается некоторое количество очков в зависимости от рейтинга противника. Glicko в целом похожа на Elo, но кроме этого учитывает, сколько времени игрок был не активен. TrueSkill — запатентованная рейтинговая система от Microsoft, в которой у каждого игрока есть два параметра: рейтинг и уверенность системы в этом рейтинге.
Во время разработки первой версии рейтинговых боёв мы рассматривали winrate и Elo (несколько вариантов, адаптированных к командной игре), а также простую систему Score (в которой игрокам всегда давалось фиксированное количество очков рейтинга за победу и отнималось за поражение).
Наилучшие результаты показала система Elo, в которой Ra — рейтинг игрока, а Rb — разница между суммарным рейтингом команды противника и суммарным рейтингом команды игрока за исключением самого игрока.
Основные трудности, с которыми мы столкнулись после запуска:
Первую проблему полностью решить не удалось из-за того, что скиловых игроков слишком мало, им приходится долго ждать, пока начнётся бой, и очень часто видеть в своих командах игроков послабее. Для смягчения эффекта мы сделали доступными рейтинговые бои только в прайм-тайм (то есть в то время, когда на серверах играет максимальное количество людей).
Вторую проблему мы решили, введя замедляющий коэффициент (то есть чем дальше игрок от среднего рейтинга, тем сложнее ему подниматься или опускаться ниже).
Также мы пробовали различными способами улучшить качество рейтинговой системы. В первых версиях для изменения рейтинга мы использовали только информацию о победе / поражении. Но у нас командная игра, и не всегда хорошие действия одного конкретного игрока приводят к победе всю команду. То есть даже в случае, если игрок хорошо играл, а команда проиграла, этот игрок получал такой же минус к рейтингу, как и все остальные игроки. Чтобы это предотвратить, мы стали пробовать учитывать индивидуальные действия игрока в бою.
Для этих целей мы пробовали применить машинное обучение: собрали различные факторы и пытались обучить модель предсказывать победу / поражение команды по действиям игрока в бою, чтобы потом использовать эту модель для определения коэффициента бонуса к рейтингу (то есть если команда проиграла, но поведение игрока было похоже на поведение игроков-победителей, давать таким игрокам дополнительный бонус).
Игрок из победившей команды который сыграл хорошо получил +40 к рейтингу. А который плохо всего +10
Мы смогли построить хорошую модель, которая показывала результаты существенно лучше текущей, но возникла одна сложность (которая довольно часто всё портит в задачах машинного обучения). Модель была хорошая, но у неё иногда бывали ошибки, которые хорошо заметны людям. Периодически возникали ситуации, когда игрок, который с точки зрения человека показал хорошие результаты — с точки зрения модели получал низкий бонус, и наоборот.
В итоге мы отказались от ML-модели и взяли более простую ручную формулу. Эта формула учитывает только боевой опыт без учёта бонусов за победу, x2 и прочих. Она даёт весьма достойный результат, хоть он и слегка ниже, чем у ML модели.
Мы продолжаем развивать и улучшать балансировщик. Мы практически победили негативные впечатления от несбалансированности по классам. Основные проблемы, на которые обращают внимание наши игроки, — это несбалансированность по скилу, турбосливы и афк игроки. Это серьёзный вызов, мы продолжаем работу над балансировщиком в этих направлениях.
Если у вас есть какие-то вопросы / предложения по балансировщику в WoT Blitz, отписывайтесь в комментариях (или на нашем форуме [5]).
Автор: bak
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/324849
Ссылки в тексте:
[1] тут: https://habr.com/ru/post/209610/
[2] Elo: https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B9%D1%82%D0%B8%D0%BD%D0%B3_%D0%AD%D0%BB%D0%BE
[3] Glicko: https://en.wikipedia.org/wiki/Glicko_rating_system
[4] TrueSkill: https://en.wikipedia.org/wiki/TrueSkill
[5] форуме: http://forum.wotblitz.ru/
[6] Источник: https://habr.com/ru/post/458866/?utm_campaign=458866&utm_source=habrahabr&utm_medium=rss
Нажмите здесь для печати.