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



Под катом мы сначала обсудим общую практику подбора битв в мультиплеерных играх, а затем поделимся собственным опытом организации матчмейкинга для War Robots.

Какие выбрать критерии?

Так что же определяет хороший матчмейкинг? Конечно, это зависит от платформы и жанровых особенностей игры, но, как правило, разработчики руководствуются следующими критериями:

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

Возможны и другие требования, например:

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

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

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

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

Сокращение числа требований к матчмейкингу ― не единственный способ уменьшить время ожидания. Например, можно реализовать мультиплеер по системе Drop-In-Drop-Out, чтобы пользователи могли присоединиться к игре в любое время и в любое же время из неё выйти. Если это не представляется возможным, при небольшой длительности матчей можно позволить игроку в процессе ожидания поиграть с ботами. Конечно, это не решит проблему ожидания, но хотя бы позволит скоротать время.

Как оценить соответствие выбранным критериям?

Итак, у нас есть определённое количество игроков, которых мы должны распределить по матчам. Как это лучше сделать? Что предпочтительнее: одинаковый уровень навыков или низкий пинг? Как мы можем сбалансировать эти требования с тем, чтобы пати играли друг против друга?

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

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

• Команды с одинаковым уровнем навыков. Это самый очевидный критерий в матчмейкинге. Для каждой игры способ расчёта этого параметра индивидуален. Один из наиболее простых: возьмём средний уровень опыта на команду и сравним его с тем же значением для другой команды. Чем больше окажется разница, тем хуже составлен матч и тем ниже искомый показатель.
• Игроки с одинаковым уровнем навыков. Даже если две команды идеально сбалансированы, но состоят, например, из двух профессионалов и одного новичка, средний показатель по навыкам команд окажется одинаковым, однако хорошего матча всё равно не выйдет. Поэтому введём ещё один параметр не для команды в целом, но для каждого игрока по отдельности, или дисперсию уровня навыков внутри команды.
• Пати. В идеале давно играющая вместе группа должна выступать против другой такой же группы, а не против трёх отдельных игроков. Вычислить это просто: если команда давно играет друг с другом, мы имеем показатель равный 100%. Если команда из трёх человек играет против двух друзей и одного случайного игрока, получим 60%. Если никто из игроков раньше не играл друг с другом, значение окажется равным 0%.
• Пинг противников. Для каждого пользователя мы сверяем пинг со всеми тремя игроками команды противника. Чем выше пинг, тем ниже показатель оценки.
• Вариативность противников. В погоне за удовлетворением более приоритетных требований система матчмейкинга может часто ставить друг против друга одни и те же команды с наивысшими показателями соответствия. Поэтому, чтобы игрокам не наскучило постоянно играть с уже знакомыми лицами, стоит отслеживать, сколько раз они встречаются в матчах.

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

Как учесть неравнозначность критериев?

Итак, для каждого из критериев у нас есть оценка от 0% (очень плохое совпадение) до 100% (наилучшее), но в конечном счёте нам нужно получить всего одно число. Для этого мы будем использовать средневзвешенное значение. Тогда мы сможем задать приоритет важности для каждого критерия.

При подсчёте оценки стоит подумать о том, хотим ли мы получить линейную зависимость параметров. Например, является ли улучшение пинга с 210 мс до 200 мс столь же целесообразным, как с 110 мс до 100 мс? Оба варианта улучшены на 10 мс, но само значение пинга различается в два раза.

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


Пример того, как могут быть составлены команды в соответствии с уровнем навыков. Зелёным и жёлтым показан пинг между игроками

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

Поскольку это число является главенствующим критерием, алгоритм вырабатывает определённые предпочтения. Если обмен двумя игроками увеличивает оценочный параметр одного матча на 5%, но уменьшает его на 10% в другом матче, система не станет этого делать, поскольку в целом результат станет хуже. Однако в некоторых случаях можно этим пренебречь. Так, может оказаться целесообразным улучшение одного показателя с 50% (что очень плохо) до 55% за счет снижения другого с 90% до 80% (что всё ещё довольно неплохо). Достичь этого можно, например, рассчитав квадратный корень из всех показателей оценки до этапа усреднения. Таким образом, улучшение плохих матчей становится относительно более важным, чем хороших.

Как это происходит в War Robots?

Поскольку речь идёт о мобильной игре, где всё должно происходить быстро, главным приоритетом становится низкое время ожидания до попадания в бой. Для этого система матчмейкинга должна быть максимально простой. В настоящий момент матчмейкер War Robots принимает во внимание только рейтинг подбора игроков (MMR) и старается ориентироваться на пати, но, поскольку они в игре мало распространены, этот критерий вторичен: если не получается противопоставить друг другу пати одинаковой силы, система старается скомбинировать между собой несколько пати или не ориентируется на этот критерий вовсе. И если один игрок вышел из боя, на его место возьмут другого, удовлетворяющего критериям, но только в самом начале матча.

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


Упрощённая блок-схема поиска матчей в War Robots

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

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