Как устроен балансировщик команд в World of Tanks Blitz

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

У танков есть следующие важные для матчмейкинга параметры:

• Уровень. В зависимости от уровня, у танков меняются различные характеристики (например, скорость, бронепробитие). На 1-ом уровне — самые слабые танки, на 10-ом — самые сильные.
  
• Тип. В WoT Blitz существует 4 типа танков: лёгкий, средний, тяжёлый и ПТ-САУ (противотанковые самоходные артиллерийские установки)
  

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

Требования

Список требований к балансировщику был сформирован на основе фидбека от игрового сообщества и периодически обновляется по сей день.

На момент написания статьи для обычных боёв список состоял из следующих пунктов:


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

Балансировщик формирующий пары игроков

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


Начало боя

Поэтому был написан другой балансировщик, который работал по следующему алгоритму:

• Разбиваем игроков на группы по уровню и типу техники;
• Из получившихся игроков формируем пары;
• Раскидываем пары по разным командам: берём каждую пару, первого игрока кидаем в первую команду, второго — во вторую;
• В полученных командах делаем финальный ребаланс: для удовлетворения большинства требований заменяем часть игроков из одной команды игроками из другой команды.

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

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


Баг в матчмейкере — собралась команда 9 на 9

Балансировщик на основе имитации отжига

В конечном варианте мы остановились на балансировщике, который работает по следующему алгоритму. Все игроки, которые нажимают кнопку «В бой», попадают в общую очередь. Балансировщик в бесконечном цикле делает следующее:

• Выбирает случайные параметры боя (случайный уровень боя (от 1 до 10), случайный режим, случайную карту);
  
• Находит в очереди всех игроков, которые подходят по выбранным выше критериям (зашли в бой на танке подходящего уровня, имеют включённым выбранный режим, имеют загруженную выбранную карту);
  
• Пытается сформировать команды, удовлетворяющие всем перечисленным выше требованиям (описание ниже);
  
• Если удалось сформировать команду, выкидывает этих игроков из очереди ожидания и стартует бой.
  

Для формирования команд из списка подходящих игроков используется метод имитации отжига. Подробнее про сам метод можно почитать тут.


Поиск глобального максимума методом имитации отжига

В контексте применения к формированию команд алгоритм следующий:

• Стартует с двух пустых команд;
  
• На каждой итерации случайным образом изменяет состояние команд. Для этого делает одну из следующих операций:
  
  
  • Добавляет случайного игрока из списка подходящих игроков в первую или вторую команду (команду тоже берём случайную);
    
  • Удаляет случайного игрока из случайной команды;
    
  • Заменяет случайного игрока из списка подходящих на одного из существующих в первой или второй команде;
    
  • Меняет случайного игрока из первой команды на случайного игрока из второй команды.
    
  
  
• Получает оценку получившегося состояния. Для этого вызывает оценочную функцию. Функция проходит по списку требований и за нарушение каждого из пунктов увеличивает штраф. Чем сильнее нарушен пункт, тем выше штраф. Например, штраф за команду размером 2x2 будет выше, чем штраф за команду размером 6x6;
  
• В зависимости от изменения значения оценочной функции и текущей температуры, определяем вероятность перехода в новое состояние;
  
• Продолжаем процесс, пока либо температура не достигнет заданной минимальной, либо значение оценочной функции не достигнет нуля (в этом случае все требования удовлетворены и можно запускать бой).
  

Основное преимущество данного подхода: для добавления новых требований достаточно модифицировать оценочную функцию. Нет необходимости писать код, который будет описывать, как именно получить то, что мы хотим. Достаточно добавить правило, которое смотрит на сформированную команду и говорит, хорошо ли она сбалансирована или нет.

Хороший пример добавления таких правил — рейтинговые бои. В рейтинговых боях в матчмейкере появилось сразу несколько новых правил:

• Команды должны быть сбалансированы по рейтингу (разница в суммарном рейтинге игроков между командами не должна превышать заданного значения);
  
• Разница в рейтинге между игроками должна быть минимальна (игроки из бронзовой лиги не должны попадать в бои с игроками из бриллиантовой).
  

Пример профиля игрока из бриллиантовой лиги

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

Недостаток данного подхода — медленная скорость работы. По сравнению с предыдущим вариантом, текущий стал работать приблизительно в 10 раз медленней, даже несмотря на ряд оптимизаций. Кстати, про оптимизации. Большая часть сервера (кроме сети и физики) для игры написана на Python. Балансировщик был переписан на C++ и распараллелен на много потоков. Из Python в плюсовый код прилетает запрос на формирования команды. Далее каждый из потоков независимо стартует метод отжига. Как только какой-то поток находит решение, остальные потоки останавливают процесс поиска, и найденное решение возвращается в Python.


Время ожидания и размер очереди на RU сервере (5 секунд в обычных боях и 10 в рейтинговых)

По мере роста онлайна росла и нагрузка на балансировщик. Этой осенью, когда онлайн на RU сервере добрался до 120 тысяч (во время ивента Mad Games), балансировщик перестал справляться. В качестве временной меры мы отключили часть правил, это позволило уменьшить нагрузку. Чтобы избежать подобных проблем в будущем мы сделали матчмейкер распределённым.

Рейтинговая система

Лучшие игроки в бриллиантовой лиге, 21 апреля 2019

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

В начале сезона игрок проходит серию калибровочных боёв по результатам которых определяется его стартовая позиция. Затем, в зависимости от дальнейшей успешности игры, игрок либо поднимается, либо опускается в рейтинге. Рейтинговая система в Блице создавалась, в первую очередь, для правильной балансировки. Она заточена на скилл игроков и практически не зависит от количества сыгранных игр.

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

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

Точность считалась следующим образом:

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

Наиболее популярные системы расчёта рейтинга: winrate, Elo, Glicko, TrueSkill. Winrate — обычный процент побед. Elo — система подсчёта рейтинга, изначально созданная для игр с участием двух человек (шахматы, etc). В этой системе игроку за победу / поражение даётся / отнимается некоторое количество очков в зависимости от рейтинга противника. Glicko в целом похожа на Elo, но кроме этого учитывает, сколько времени игрок был не активен. TrueSkill — запатентованная рейтинговая система от Microsoft, в которой у каждого игрока есть два параметра: рейтинг и уверенность системы в этом рейтинге.

Во время разработки первой версии рейтинговых боёв мы рассматривали winrate и Elo (несколько вариантов, адаптированных к командной игре), а также простую систему Score (в которой игрокам всегда давалось фиксированное количество очков рейтинга за победу и отнималось за поражение).



Наилучшие результаты показала система Elo, в которой Ra — рейтинг игрока, а Rb — разница между суммарным рейтингом команды противника и суммарным рейтингом команды игрока за исключением самого игрока.

Основные трудности, с которыми мы столкнулись после запуска:

• слишком большой разброс в рейтинге между игроками;
  
• плохо предсказуемая скорость, с которой игроки набирают рейтинг (достигают лиги).
  

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

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

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

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


Игрок из победившей команды который сыграл хорошо получил +40 к рейтингу. А который плохо всего +10

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

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

Заключение

• Балансировщик на основе метода имитации отжига позволил нам перейти от описания решения (как именно собирать команду) к описанию требований (какие условия не должны нарушаться);
  
• В командных рейтинговых боях хорошо себя показала модифицированная система Эло, учитывающая индивидуальные действий игрока в бою;
  
• Не всегда стоит применять сложные методы машинного обучения (особенно, когда важна интерпретируемость и понятность результата человеком).
  

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

Если у вас есть какие-то вопросы / предложения по балансировщику в WoT Blitz, отписывайтесь в комментариях (или на нашем форуме).