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

image

Под катом мы сначала обсудим общую практику подбора битв в мультиплеерных играх, а затем поделимся собственным опытом организации матчмейкинга для 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 ведётся постоянно. Возможно, в будущем удастся скомбинировать старый и новый подход к поиску матчей, но не стоит забывать, что любое повышение качества матчмейкинга ведёт к увеличению времени ожидания. Поэтому разработка такого решения будет целесообразна только в том случае, если оно не существенно повлияет на быстродействие системы.

Комментарии (15)


  1. DrunkBear
    19.11.2019 15:10
    +3

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


    1. iMaddox
      19.11.2019 16:01

      В CoD такая проблема наблюдается часто, да. Но тот же упомянутый Starcraft 2 поначалу дает разыграться с ИИ-оппонентом, который после нескольких матчей подстроит оптимальную сложность и соперников в соответствии с навыком игрока.


      1. DrunkBear
        19.11.2019 16:29

        В SC2 — да, но там вариативность — три расы.
        Выигрываешь цепочку побед — летишь на лигу вверх, проигрываешь — пожалуйте вниз (доползал в платину в своё время)
        А во всех играх, где есть много разных машин/самолётов / классов уже труднее балансировать: вот хороший снайпер, но он решил сыграть штурмовиком — как его балансить? Выкинуть поиграть против ботов сначала? Дать средневзвешенный рейтинг — а вдруг он станет маленьким злом для противника, зная карты и имея опыт? Балансить по текущему рейтингу — так у него нет нужного стиля игры и привычки, скорее, будут мешать.
        В Halo не играл, но, судя по wiki, там есть предбанник, где лидеры команд собирают команды, половина работы балансера делается вручную.
        Ну и любой мм ничего не сделает с психологией: пришёл человек сорвать злость, играет агрессивно и совершает ошибки, ну или напился коньяка и обнаружил, что с каждым новым снифтером команда играет всё хуже и хуже /irony
        PS у меня в разгар игры может прибежать к монитору 6 килограмм маленькой ( 2 лет нет, около метра в длину с хвостом) задумчивой мэйнкошки, которую заинтересовали вспышки на экране — этого точно не учтёт ни один балансер.


        1. omgwhatswrong Автор
          19.11.2019 16:57

          вот хороший снайпер, но он решил сыграть штурмовиком — как его балансить?

          Именно поэтому по-хорошему стоит учитывать рейтинг не только средневзвешенный, но по каждому классу. Однако учет всех условий, которые только можно прописать в матчмейкере, значительно увеличит время составления матча. Не каждый игрок согласится ждать своей очереди по 5-7 минут.

          Ну и любой мм ничего не сделает с психологией

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


          1. DrunkBear
            19.11.2019 17:14

            Средневзвешеный рейтинг тоже должен откуда-то появиться: если человеку нравится играть снайпером, он 2000 боёв отыграл снайпером и решил узнать, а что там у других классов — будет проблема.
            Если человек периодически ведёт себя агрессивно — он влетит на штрафы за токсичность, редко кто может играть агрессивно и молча.
            А вообще, психология в играх действительно заслуживает отдельной публикации, а то и серии: часто видел, когда в ситуациях «ну трудно не выиграть» проигрывали и наоборот, и практически всегда был ответ «психология» — слишком расслабились или наоборот, впали в уныние на старте и ничего не смогли сделать.


            1. omgwhatswrong Автор
              19.11.2019 18:08

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


              1. DrunkBear
                19.11.2019 18:17

                Хорошая идея, но, на мой взгляд, даже у идеального алгоритма будут проблемы, если игроки воспримут его в штыки, как пример — широкоизвестный в узких кругах «патент кислого», который мало кто читал, ещё меньше поняли о чём он, но большинство уверены, что именно этот коварный патент мешает становиться суперзвёздами с идеальной статистикой.
                Простые вопросы «почему он другим не мешает» и «в курсе ли вы, что самый идеальный алгоритм подбора выровняет статистику побед/поражений каждого до 50/50, ибо будут встречаться абсолютно равные команды» вызывает только всплеск фекнегатива.


                1. omgwhatswrong Автор
                  20.11.2019 10:13

                  Да, именно из-за неоднозначности пока сильно в это не углублялись, но, возможно, еще подумаем, как можно развить тему в будущем.


          1. olegchir
            24.11.2019 21:25

            Я часто играю в Overwatch и страдаю из-за несовершенства матчмейкера.


            Хотел бы иметь галку "точный подбор", заранее зная что встряну на 5 минут дополнительного ожидания, но зато матч точно будет нормальный


      1. vrnvorona
        19.11.2019 18:04

        Старик это 1v1 игра. Достаточно обычного ELO, для командных игр все очень неоднозначно.


        1. iMaddox
          19.11.2019 18:11

          2v2, 3v3 и 4v4 тоже есть. Тем более, у каждой расы есть командиры с собственным набором юнитов и особенностями. Понятное дело, что матч в сетевом шутере собирает побольше игроков, но имхо у SC2 добротный матчмейкинг.


          1. vrnvorona
            19.11.2019 19:43

            С каких пор в ладдер ранкеде старика есть командиры? Дефолтные расы всегда. По крайней мере последние лет 5. Да и их коопы это не так серьезно и не так важно, ELO-like работает неплохо просто не так идеально как для дуэлей.


  1. omgwhatswrong Автор
    19.11.2019 15:41

    Матчмейкинг действительно является сложным для исполнения — об этом и идет речь в статье. Что касается удовлетворенностью работой, то те же StarCraft и Halo хвалят в том числе.


    1. garrydvaraza
      27.11.2019 18:44

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


      1. omgwhatswrong Автор
        02.12.2019 13:38

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

        подход реализованный в стимовском мм

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

        А что до алгоритмов и программирования — тянет уже на тему следующей статьи.