Алгоритм подбора игроков в “Awesomenauts”

На тему «правильного» матчмейкинга сломано немало копий. Ниже — перевод опубликованного на гамасутре рассказа разработчика Awesomenauts о том, как мм устроен в его игре. 

Подбор игроков — это сложная тема со множеством подводных камней, но в основе лежит один-единственный вопрос: кто должен играть с кем? Через несколько лет после выпуска “Awesomenauts” мы полностью переделали наши алгоритмы подбора (АП), выпустив нововведения в обновлении “Галактрон”, и сегодня я бы хотел рассказать вам, как Галактрон выбирает, с кем вы будете играть. Вопрос простой, а вот ответ на него довольно сложный.

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

Если на все эти вопросы вы ответили “Да, давайте учтем все это!”, то у вас должно быть много игроков! Я уже писал о том, сколько игроков нужно для такой схемы, и короткий ответ — десятки тысяч одновременно играющих людей все время. Это нереалистично (разве что для реально хитовых игр), так что придется обойтись меньшим количеством игроков и сделать все, что возможно, с вашим подбором.

В “Awesomenauts” мы решили позволить алгоритму подбора собирать множество игроков и затем раз в пару минут разбивать их всех по командам. Таким образом, у АП есть столько игроков, сколько возможно, и он может собрать из них лучшие комбинации.

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

Обеспечение качества подбора

Итак, вот у нас сто с лишним игроков, и их всех нужно рассортировать, так как же нам решить, кого с кем? Например, какой вариант выбрать: расставить игроков по равным навыкам или по низкому пингу? А если разница незначительна, если навыки примерно равны, а пинг немного получше? Где нам провести границу? И как совместить это с желанием позволить готовым командам играть друг против друга? И так далее, и так далее.

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

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

• Команды с одинаковыми навыками. Это самый очевидный фактор в подборе: обе команды должны быть одинаково хороши. Превратить это требование в цифры легко: мы просто возьмем средний уровень навыков по команде и посмотрим на разницу. Чем она больше, тем ниже наша оценка.  Обратите внимание, что для этого в вашей игре должна быть система оценивания навыков, например, ELO или Trueskill. Также это значит, что новых игроков будет сложно правильно расставить, потому что мы не знаем, насколько они хороши, пока они хоть немного не поиграют.
• Игроки с одинаковыми навыками. Даже если две команды идеально совпали, это еще не означает идеальный подбор. Например, если в обеих командах есть по два классных игрока и по одному новичку, средний навык команд одинаков, но матч будет неинтересным. Поэтому нам нужно использовать отдельную оценку, которая не будет принимать во внимание команду и будет смотреть только на разницу в навыках всех игроков. В матче на шесть пользователей есть пятнадцать сочетаний игроков, и мы просто возьмем их среднее значение. Чем больше разница, тем ниже оценка.
• Готовые команды. В идеале, группа из трех друзей должна играть с такой же группой друзей, а не против трех отдельных игроков, которые друг друга не знают. Поставить оценку такой ситуации просто: если обе команды в одинаковом положении, то у нас 100%. Если есть небольшая разница, к примеру, команда из трех игроков против команды из двоих и игрока-одиночки, то у нас 60%. Если разница большая — команда из трех против троих игроков-одиночек — то это 0%.
• Пинг с врагами. Для каждого игрока мы проверяем пинг со всеми тремя игроками вражеской команды. Чем выше пинг, тем ниже оценка. Таким образом, есть девять комбинаций игроков, и мы просто выводим среднее из этих девяти оценок, чтобы получить общую оценку за пинг для этого матча.
• Вариативность противников. Этот неочевидный критерий мы добавили вскоре после запуска Галактрона. Поскольку наш АП ищет связанных друг с другом игроков с одинаковыми навыками, он часто ставит одних и тех же пользователей друг против друга. Мы ожидали, что это будет происходить достаточно редко, чтобы играть было веселее, когда это произойдет, но на практике наши игроки слишком часто сталкивались с одними и теми же противниками. Чтобы избежать этого, мы давали подбору более низкую оценку, если игроки уже играли вместе в прошлом матче. Если они играли друг против друга, но теперь попали в одну команду, и наоборот, мы давали более высокую оценку, чем если они встречались в одинаковой ситуации (противники ранее, противники сейчас, и союзники ранее, союзники сейчас). Из-за этого АП в некотором роде начал менять команды местами, если, вопреки этому правилу, он делал подборку с теми же игроками. Это правило наименее значимое, потому что другие более важны, но оно все же весьма улучшило ситуацию, и жалоб от игроков стало меньше.
• Два возможных сервера. Поскольку “Awesomenauts” — система “peer-to-peer”, в каждом матче необходим игрок, который сможет связаться со всеми, чтобы стать сервером. В идеале, должен быть второй такой игрок, чтобы, если первый игрок-сервер выйдет из матча, могла произойти передача полномочий и игра продолжалась для всех. Это правило нужно только для игр “peer-to-peer”, в играх с выделенным серверами или relay серверами^[1]Если я правильно понял, это что-то по типу фотон клауда, когда сервер просто броадкастит на все клиенты в … Continue reading это правило не имеет значения.

Но не хватает одного важного фактора: пинг с сокомандниками. Почему он не учитывается? Потому что с каждым добавленным нами фактором другие становились чуть менее важными. В “Awesomenauts” плохое соединение с сокомандниками — не очень большая проблема, потому что вам не нужно уклоняться от их пуль. Плохое же соединение с противником куда хуже, потому что уклоняться становится сложнее, если пинг высокий. Игнорируя пинг с сокомандниками, мы делаем пинг с соперниками намного важнее.

Когда высчитываете оценку, нужно подумать, стоит ли делать ее линейной. Например, настолько ли значительно улучшение пинга от 210 миллисекунд до 200, как улучшение от 110 до 100? В обоих примерах пинг улучшается на десять миллисекунд, но второй намного относительно больше. В “Awesomenauts” мы изменили наши формулы оценки, чтобы сопоставлялась воспринимаемая, а не абсолютная разница.

Еще стоит подумать о том, чтобы ограничить охват оценок. Например, в “Awesomenauts” у самых топовых игроков показатель навыков – более 20,000 очков, но только у 0,3% процентов игроков больше 18,000 очков. Другими словами: у топов большая разница в навыках, но она бесполезна для АП, потому что таких игроков слишком мало, чтобы принимать их во внимание. Так что перед тем, как высчитывать оценку за навыки, мы ограничим их до охвата, с которым можно работать. Таким образом, алгоритм подбора будет считать совпадение двух игроков с 18,000 очков таким же, как и совпадение игрока с 18,000 очков и игрока с 20,000 очков. В идеале не стоит ничего ограничивать, но, поскольку нам нужно сохранить баланс всех разных целей подбора, ограничение некоторых моментов сделает другие охваты и аспекты более важными.

Сочетание оценок

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

Интересно, что некоторые из этих оценок сказываются на подборе намного сильнее, чем иные. Сложно получить 0% за навыки, потому что для этого нужно трое очень сильных игрока и трое начинающих, что случается очень редко. В то же время, получить 0% за готовые команды намного легче, потому что все, что для этого нужно — готовая команда из троих игроков, играющая против троих новичков. Такого рода колебания нужно принимать во внимание, когда мы взвешиваем все “за” и “против”: поскольку готовые команды так сильно сказываются на подборе, их важность нужно понизить, чтобы они не загораживали собой более сглаживаемые оценки, такие, как навыки и пинг.

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

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

Определение подбора с лучшей оценкой

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

Я подумал, что это на самом деле может задача теории графов, поэтому попытался найти алгоритмы вершинных графов, которые могли бы мне пригодиться, но задача оказалось столь специфичной, что я ничего не нашел. Даже консультация с хардкорным ученым, экспертом по алгоритмам, ничего не дала, поэтому я решил полагаться на старые добрые оценки наугад и просто принять, что реального наилучшего варианта подбора можно и не найти. Возможно, это вообще NP-полная задача, но на деле я не пытался проверить и доказать. Может, какому-нибудь студенту-информатику поиск лучшего алгоритма покажется интересной темой для курсовой.

В итоге я использовал такой подход: сначала создал более-менее приемлемый подбор, использовав простое правило. Я попробовал несколько правил, например, просто отсортировав всех игроков по уровню навыков и потом расставив их согласно этой сортировке. Таким образом, шесть лучших игроков попали в один матч, потом шесть следующих за ними…  Это довольно просто устроить, и именно так получились лучшие оценки за подбор. Но, поскольку все остальные оценки этот метод игнорирует, с пингом и готовыми командами получилось совсем плохо.

И вот у нас по шесть игроков в подборе, но мы еще не решили, кто в красной команде, а кто – в синей. Наш следующий шаг — решить, как именно мы их разделим по командам, и вот тут уже можно использовать брутфорс: просто перепробуем все возможные комбинации и выберем лучшую. Здесь мы примем во внимание все шесть оценок, не только навыки. Число комбинаций не очень велико, особенно поскольку порядок игроков в каждой команде не имеет значения. Именно потому, что мы попробуем каждую комбинацию, мы будем уверены, что игроки распределились по командам лучшим возможным способом.

Отличное начало. Следующий шаг — найти улучшения: мы посмотрим, можно ли поменять игроков местами так, чтобы общая оценка улучшилась. Будем менять по одному за раз. И снова можно использовать брутфорс: просто перепробуем все варианты и выберем лучший. Есть много возможных замен, и, кроме этого, нам придется пересчитывать разделение по двум командам каждый раз, так что потребуется много вычислительной мощи. Но современные компьютеры очень мощные, так что при некоторой оптимизации мы сможем посчитать по несколько сотен замен за секунду.

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

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

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

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

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

Минусы

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

Например, если мы посмотрим на раунд подбора в 20:00 по восточноевропейскому времени, то подавляющее большинство игроков будет из Европы, а остаток распределится по остальному миру. Это значит, что в раунде подбора команд ста игрокам будет всего несколько человек из Австралии или Южной Африки. В плане пинга у этих игроков будет плохой матч, потому что в том раунде просто не хватит игроков из их региона.

Для решения этой проблемы потребуется еще больше игроков в раунде: думаю, около трехста хватит идеально. Тем не менее, это означает, что либо игроки будут невероятно долго ждать, либо вам нужна гигантская база игроков. Нам бы хотелось иметь такую же большую базу, как у Лиги Легенд, но, к сожалению, это нереалистично, если только игра — не бьющий все рекорды хит. В результате мы выбрали нечто среднее: мы ждем, пока не наберется сто игроков, что может занять минут пять или даже больше, а потом просто выполняем подбор, принимая, что у некоторых результат может быть не настолько хорошим, как хотелось бы. Если же игроков недостаточно, в какой-то момент мы все равно выполняем подбор, чтобы время ожидания не превышало максимум.

Создавая Галактрон, мы почти не нашли информации о том, как именно крупные мультиплеерные игры справляются с подбором игроков, но из речи дизайнера “Heroes of the Storm” (которую я, к сожалению, уже не могу найти на YouTube) стало ясно, что в какой-то момент в игре существовала такая система: подбор начинался, как только его можно было провести достаточно качественно. В нашем случае это бы означало, что, как только появляются шесть игроков с примерно равными навыками и хорошим пингом друг с другом, то подбор начинается сразу же. Если он слишком долго не происходит, то требования постепенно снижаются. В какой-то момент игрок, который слишком долго ждет, становится основным приоритетом и просто получает пятерых наиболее подходящих игроков, которых смог найти АП, даже если качество подбора ниже, чем хотелось бы.

Преимущество такого подхода — гибкость: в регионах с большим количеством игроков подбор происходит намного быстрее, а в местах, где игроков мало, – наоборот. Такого рода гибкость также хороша для сильных игроков: они могут подождать подольше, но играть только против таких же сильных. Наш собственный алгоритм так не умеет, поскольку игроки со всего мира расставляются по матчам одновременно в определенные моменты.

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

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

К сожалению, невозможно вживую прямо сравнить АП “Awesomenauts” и “Heroes of the Storm”, потому что у “Heroes of the Storm” намного больше игроков. Любой алгоритм подбора будет работать лучше с большим количеством игроков, так что, подозреваю, качество подбора в крупной игре типа “Heroes of the Storm” в любом случае лучше, чем в “Awesomenauts”.

Вывод

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

Просто помните, что, чем больше правил вы добавляете, тем менее значимыми становятся другие, и каждое правило, которое кажется вам важным, делает менее важными другие. Главное — найти баланс и сдерживать себя. А еще вам, возможно, потребуется отполировать правила, когда алгоритм выйдет в лайв, как мы сделали с Галактроном в “Awesomenauts”, позже добавив правило вариативности противников.

В моем блоге разработчика www.joostvandongen.com вы найдете еще больше статей по разработке “Awesomenauts”, “Swords & Soldiers”, “Cello Fortress” и “Proun”, а еще мою музыку и другие вещи, над которыми я работаю.

Перевод — Ирина Михеева.