Публикация Школы траблшутеров

Теория очередей в подборе игроков

Время чтения: 11 мин 25 сек
22 ноября 2026 Просмотров: 11

Сбор матча на четверых занимает в среднем 1,5 секунды на игрока, если в общую очередь поступает один одиночный игрок в секунду. Если разделить тот же поток на четыре равные очереди, среднее вырастет до шести секунд. Олег Брагинский и Антон Бессарабов разбирают, как оценить цену новых режимов и отличить дефицит соперников от технической задержки.

Теория очередей в подборе игроков

Рис. 1. Матч начинается, когда в очереди набирается совместимая четвёрка.

Сначала собрать людей, затем запустить матч

В теории очередей запросы поступают в систему, ждут и выходят. Для подбора игроков запрос – заявка на матч. Её подаёт как одиночный участник, так и готовая группа друзей. Начнём с модели, где каждый запрос представляет одного игрока.

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

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

Первый участник ждёт три следующих прихода, второй – два, третий – один, четвёртый начинает сразу. Среднее по участникам равно (3 + 2 + 1 + 0) / 4 = 1,5 секунды. Длительность боя в расчёт сборки состава не входит. Для состава из k игроков и потока λ заявок в секунду среднее ожидание равно (k − 1) / (2λ).

image html

Рис. 2. Один общий поток собирает четвёрку быстрее четырёх отдельных очередей.

Почему новые режимы удлиняют поиск

Распределим заявки случайно и независимо между равнопопулярными режимами. При двух очередях средний интервал между приходами в каждую составит две секунды, при четырёх – четыре. Общий поток и требования к размеру матча оставим прежними.

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

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

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

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

image html

Рис. 3. Разделение потока между режимами удлиняет поиск.

Закон Литтла

В 1961 году Джон Литтл доказал связь между средним числом заявок в системе, интенсивностью поступления и средним временем пребывания [1]. Для применения нужны согласованные долгосрочные средние. По одному спокойному отрезку журнала устойчивость очереди установить нельзя.

В стационарном режиме с конечными средними число ожидающих равно произведению потока вошедших заявок на среднее время в очереди. Если интенсивность посчитана для всех вошедших, время пребывания тоже измеряем для всех, включая отмены.

Допустим, в очередь поступают четыре одиночных игрока в секунду. При ожидании в среднем десять секунд одновременно ждут сорок человек, при двадцати – восемьдесят. Если среднее вырастет до сорока секунд, число ожидающих достигнет ста шестидесяти.

Закон Литтла помогает сверить измерения. Границу очереди проводим одинаково: если заявка выходит при отмене, время до отмены входит в расчёт наряду со временем до успешного подбора. Отдельно выясняем, где именно возникла задержка.

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

image html

Рис. 4. При том же притоке время ожидания определяет размер очереди.

Редкая роль ограничивает весь состав

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

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

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

Сюй, Юй и У изучали подбор для матчей «два на два»: выбор сторон, диапазоны навыка и заявки без жёсткого предпочтения [2].

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

image html

Рис. 5. Свыше тридцати заявок поддержки в минуту темп ограничивают остальные роли.

Расширять поиск по понятным правилам

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

В PlayFab правила участвуют в фильтрации и ранжировании кандидатов, а допустимые границы могут расширяться по мере ожидания [3]. Приемлемый разброс навыка команда определяет по результатам матчей в своей игре.

В Amazon FlexMatch по умолчанию учитывается возраст самой новой заявки в неполном составе [4]. При добавлении участника отсчёт может начаться заново. Сверьте момент фактического расширения поиска с тем, который обещает интерфейс.

Объясняйте компромисс прямо в интерфейсе. Например, предложите расширить регион поиска при прежнем пределе сетевой задержки. Игроку важно заранее знать, какое условие меняется и какая граница остаётся обязательной.

Как измерять время поиска

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

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

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

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

image html

Рис. 6. Отмена и найденный состав завершают поиск, вход в игру фиксируют отдельно.

Как проверить новые правила

Быстрый поиск может повысить число сыгранных матчей. Связь с выручкой требует наблюдений. Пример гипотезы: объединение двух малопопулярных ночных режимов сократит отмены без выхода за допустимый разброс навыка.

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

Распределяйте настройки между достаточно независимыми регионами или временными блоками. При чередовании учитывайте часы пик и заявки, переходящие из одного блока в другой. Эффекты переноса разбирают Бойинов, Симчи-Леви и Чжао [5].

До запуска полезно проиграть новые правила на журнале приходов и отмен, сохраняя группы друзей целиком. Так выявляются невозможные составы и узкие места. Запись прошлого не показывает, как новое ожидание повлияет на терпение игроков.

Окончательное решение требует проверки на живом продукте и наблюдения за редкими категориями. Проверьте и сценарий снижения потока: настройка, удобная вечером, может оказаться непригодной ночью.

Что запомнить?

  • Время сборки совместимого состава и длительность боя описывают разные процессы
  • В учебной модели четыре равные независимые очереди увеличивают среднее ожидание вчетверо
  • Закон Литтла связывает поток, время и число ожидающих при согласованных границах измерения
  • Пропускную способность ограничивает дефицит нужных ролей даже при большом онлайне
  • Среднее ожидание оценивают вместе с долгими поисками, отменами и качеством состоявшихся матчей

Заключение

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

Порядок работы

  1. Опишите заявку, обязательный состав и момент окончания ожидания. Отдельно выделите подключение к серверу
  2. Измерьте поток по совместимым категориям и сохраните время до отмены наравне со временем до успешного подбора
  3. Рассчитайте цену разделения очередей и ограничения по ролям, явно записав допущения модели
  4. Настройте постепенное расширение условий и проверьте, какая заявка управляет таймером
  5. Проведите эксперимент с учётом общего пула. Проверьте качество матчей, отмены и редкие категории

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

Где искать причину задержки

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

image html

Рис. 7. Журнал заявок помогает отличить дефицит игроков от задержки при входе.

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

Источники и дальнейшее чтение

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

[1] Little J. D. C. A Proof for the Queuing Formula: L = λW. Operations Research, 1961.

[2] Xu M., Yu Y., Wu C. Rule Designs for Optimal Online Game Matchmaking, 2019.

[3] Microsoft. How matchmaking works. PlayFab.

[4] AWS. Allow requirements to relax over time. Amazon GameLift Servers.

[5] Bojinov I., Simchi-Levi D., Zhao J. Design and Analysis of Switchback Experiments. Management Science, 2022.