Балан в WoT blitz

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

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

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

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

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

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

Требования

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

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

Список требований к балансировщику

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

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

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

Начало боя

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

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

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

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

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

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

• Выбирает случайные параметры боя (случайный уровень боя (от 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 модели.

Заключение

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