Матчмейкинг по-простому: Сигнал и шум

Всем привет! Меня зовут Гриша Дядиченко, и я технический директор и основатель White Label Games. Уже больше десяти лет работаю с компьютерной графикой, AR/VR и компьютерным зрением — в основном заказная разработка, иногда собственные прототипы по выходным.

На этой неделе в телеграм-канале я постил три коротких поста про матчмейкинг: про скрытое число, которое прячется за каждым рейтингом, про формулу ELO и про сигнал с шумом, и про Glicko с TrueSkill как «адаптивный K». И, собственно, давно хотел собрать это всё в один большой материал, где каждая идея — интерактив в браузере, который можно покрутить прямо со страницы.

Searching… — и таймер пополз: 0:14, 0:27, 0:42. Стояли ли вы когда-нибудь перед этим спиннером с мыслью «ну и откуда сервер вообще знает, кого мне дать в пару»? За эти сорок две секунды система из всех, кто сейчас в очереди по всему миру, должна собрать две команды так, чтобы матч получился примерно 50 на 50 — не разнос и не избиение младенцев. Откуда она знает, что вы и незнакомец из другого часового пояса «примерно равны», если вы никогда не играли друг с другом?

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

А сквозная идея простая. Истинный скилл — это скрытый сигнал, который нельзя увидеть напрямую. Один матч — шумная однобитная выборка из него. Рейтинг — это фильтр, который оценивает и сам сигнал, и собственную неуверенность в нём. Вся эволюция ELO → Glicko → TrueSkill — про то, как сделать этот фильтр умнее.

Если интересна тема — добро пожаловать.

// @easy_dev_math

Такие разборы — с кодом и интерактивами — выходят в канале каждую неделю.

1. Сигнал, шум, ожидание и дисперсия — на пальцах

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

Сигнал, шум, среднее, дисперсия — словарь на четыре словаБаза, можно пропустить

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

Скилл игрока — ровно такой же сигнал. Он есть и он реален, но прямого датчика для него не существует — только зашумлённые «замеры» в виде матчей. Хорошая новость: тот же математический аппарат, которым инженеры десятилетиями вытаскивают голос из шипения, работает и для скилла.

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

Математическое ожидание (попросту — среднее) — это центр, к которому стягивается наблюдение, если усреднить его по куче попыток. Шум в одних партиях плюсовой, в других минусовой, и на дистанции он гасит сам себя, а сигнал остаётся. Поэтому среднее многих матчей куда ближе к истине, чем один матч:

\bar{x} = \frac{1}{n}\sum_{i=1}^{n} x_i \;\xrightarrow{\,n\,\to\,\infty\,}\; \mu

Здесь x — наблюдения (исходы матчей), а μ — тот самый сигнал, к которому сходится среднее: чем больше n, тем теснее оно прижимается к μ.

Дисперсия (разброс) — насколько широко наблюдения скачут вокруг среднего. Много шума — большой разброс, точки летают далеко от центра; мало шума — всё кучно. Корень из дисперсии называют стандартным отклонением и обозначают σ: он удобен тем, что меряется в тех же единицах, что и сама величина.

И вот ключевая для всей статьи мысль: разброс — это и есть наша неуверенность. Большой σ (мало данных, нестабильные результаты) — мы плохо знаем скилл игрока. Сужается σ — растёт уверенность. Glicko и TrueSkill дальше будут хранить это σ прямо рядом с оценкой, именно как меру «насколько мы не уверены».

Причём тут распределение Гаусса

Хорошо, наблюдение = сигнал + шум. А какой формы сам шум? Почти всегда — гауссовой, то есть колоколом нормального распределения. И это не совпадение, а следствие центральной предельной теоремы: когда на результат влияет много мелких независимых случайностей (а в матче их полно — реакция, пинг, настроение, действия пятерых тиммейтов), их сумма стягивается к колоколу Гаусса почти независимо от того, как устроены исходные «кубики».

Поэтому перформанс игрока в конкретной партии естественно рисовать колоколом: пик — на истинном скилле, ширина — это шум.

p \;\sim\; \mathcal{N}(\mu,\ \sigma^2)

Читается так: перформанс p — гауссиана с центром μ (сигнал, наша оценка скилла) и шириной σ² (шум, он же неуверенность). Запомните пару μ и σ: ELO работает по сути только с μ, Glicko добавляет σ под именем RD, а TrueSkill хранит весь колокол целиком. Вся статья дальше — про то, как аккуратно оценить μ и посчитать σ по шумным матчам.

2. Что должен делать матчмейкер

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

С точки зрения геймдизайна близкие 50 на 50 — это не каприз ради красивых чисел, а главный рычаг удовольствия. Интересно там, где исход не предрешён: если одна сторона побеждает с вероятностью 90%, это уже не матч, а формальность — скучно и фавориту, и обречённому. Это и есть состояние потока: вызов должен совпадать с вашим уровнем, иначе слишком легко наводит скуку, а слишком сложно бьёт по нервам, и в обоих случаях игру хочется закрыть. Добавьте сюда восприятие справедливости — поражение в равной игре проглатывается легко («ещё бы чуть-чуть»), а в заведомо проигранной превращается в тильт и повод бросить ранкед. Поэтому ровный матч — это в конечном счёте про удержание: захотите ли вы нажать «ещё разок».

Пункты «оценить» и «предсказать» — это одно и то же, вид сбоку. Если есть модель, переводящая скиллы в вероятность победы, то оценка скилла и предсказание исхода — две стороны одной монеты. Вся математика дальше живёт именно здесь.

Тут возникает вопрос джуна: зачем огород из формул, есть же винрейт? Да? Конечно же нет.

Винрейт не отвечает на главный вопрос — какова вероятность вот этого конкретного матча. 60% у того, кто фармил ботов, и 60% у того, кто рубится в топ-100, — это два разных числа, склеенных в одно. Винрейт игнорирует силу соперника: победа над чемпионом и над новичком весят одинаково. И винрейт не несёт неуверенности: 3 победы из 5 — это 60%, и 600 из 1000 — тоже 60%, но во втором случае мы знаем про игрока в разы больше.

Зафиксируем словарь, он понадобится дальше:

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

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

3. ELO: одно число и логистическая кривая

И сразу обязательный факт, на котором спотыкаются буквально все: ELO — это не аббревиатура. Это фамилия. Арпад Эло (Arpad Elo) — венгерско-американский профессор физики и сильный шахматист-любитель.

Эло придумал систему для Шахматной федерации США (USCF), которая приняла её в 1960 году; FIDE подхватила в 1970-м. До Эло в USCF работала система Харкнесса — Эло её заменил. Метод подробно изложен в его книге «The Rating of Chessplayers, Past and Present» (1978).

Перформанс как случайная величина

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

Рейтинг A1500

Рейтинг B1500

K20

P(A) 50.0%P(B) 50.0%Δ победа +10.0Δ ничья +0.0Δ пораж. -10.0

Вероятность победы — формулойОсторожно! Математика!

E_A = \frac{1}{1 + 10^{(R_B - R_A)/400}}

Здесь E_A — ожидаемый счёт игрока A (попросту его вероятность победы), R_A и R_B — рейтинги соперников. Чем сильнее соперник, тем больше показатель степени и тем ближе E_A к нулю.

Почему «400 очков = ×10 шансов»

Рейтинг меряет силу не «в попугаях», а в шансах. Шансы — это «сколько раз к скольким»: 1 к 1 — это ровно 50 на 50, а 10 к 1 — «выиграю десять раз, проиграю один», то есть около 91%.

И вся соль Elo в одном правиле: каждые 400 очков разницы умножают ваши шансы на 10. Пройдём по шагам, отталкиваясь от равных:

Разница 0 — никто не сильнее, шансы 1 к 1 → 50%.
+400 — один шаг ×10, шансы 10 к 1 → выигрываете 10 раз из 11 → ~91%.
+800 — два шага: ×10, потом ещё ×10 = ×100, шансы 100 к 1 → ~99%.
+200 — полшага. Тут легко ляпнуть «×5», но половина множительного шага — это ×√10 ≈ ×3.16, шансы примерно 3 к 1 → ~76%.

Теперь главное наблюдение. По рейтингу мы складываем (+400, +400), а шансы при этом умножаются (×10, ×10). Сложение на одной шкале превращается в умножение на другой — а инструмент, который как раз переводит «умножать» в «складывать», и называется логарифмом. Вот и весь секрет, почему в формальной записи формулы вылезает логарифм: разность рейтингов — это просто «на сколько ×10-шагов по шансам вы друг от друга отстаёте».

А почему вообще шансы, а не проценты напрямую? Потому что разрывы в скилле ощущаются множителями. Прыжок от новичка к крепкому любителю по ощущению такой же, как от любителя к мастеру — каждая ступенька это противник «на порядок» сложнее. Множительная шкала это ловит, и заодно никогда не упирается в 100%: всегда можно быть ещё на 400 сильнее.

Само число 400 взято с потолка — это просто выбор единицы, как Цельсий против Фаренгейта. Эло мог взять любое; 400 удобно тем, что рейтинги попадают в привычные сотни-тысячи.

Та же мысль одной строкойОсторожно! Математика!

\log_{10}\frac{E_A}{1-E_A} = \frac{R_A - R_B}{400}

Слева — логарифм шансов на победу A, справа — разность рейтингов, делённая на 400. Та же логистическая модель, просто записанная через логарифм: разность рейтингов линейно задаёт, на сколько ×10-шагов вы оторвались по шансам.

Отсюда же и нелинейность: первые 200 очков форы дают +26 процентных пунктов, а вторые 200 — всего +15. Чем выше задрался фаворит, тем дороже ему каждый следующий процент.

Формула не из ниоткуда — у неё большая семья: модель Брэдли–Терри (1952) (та же логика парных сравнений за восемь лет до USCF), softmax на два класса и распределение Больцмана из статфизики. Эло был физиком. Совпадение? Не думаю.

Обновление: предсказал → пронаблюдал → поправил

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

Правило обновления — формулойОсторожно! Математика!

R_A' = R_A + K\,(S_A - E_A)

Здесь R — старый рейтинг, R′ — новый, S — что вышло по факту (1 — победа, 0.5 — ничья, 0 — поражение), E — что мы предсказывали (тот самый ожидаемый счёт из сигмоиды), K — размер шага.

Вся соль — в скобке. S − E — это «удивление»: насколько реальность разошлась с прогнозом. Разберём на числах: пусть вам как фавориту давали 76%, то есть E = 0.76.

Выиграли (S = 1): удивление 1 − 0.76 = +0.24. Прибавка маленькая (K·0.24) — от вас этого и ждали.
Проиграли (S = 0): удивление 0 − 0.76 = −0.76. Просадка втрое больше: проиграть тому, кого должен был обыграть, — это новость.

Ожидаемая победа приносит копейки, а неожиданное поражение бьёт ощутимо. И в обратную сторону так же: обыграли заведомо сильного (у вас маленькое E, скажем 0.1) — удивление +0.9, рейтинг подскакивает. Система платит ровно за ту информацию, которой не ждала.

И ещё: сколько очков прибавилось вам, столько убыло у соперника — его «удивление» зеркально вашему. Очки не берутся из воздуха, Elo замкнут и в сумме нулевой.

А почему он вообще сходится к правде? Если ваш рейтинг занижен, вы в среднем выигрываете чаще, чем предсказано, S − E держится в плюсе — и рейтинг ползёт вверх. Ровно до точки, где прогноз E совпадёт с вашей реальной долей побед: там «удивления» в среднем гасят друг друга, и рейтинг замирает. Самонастройка.

Обновление Elo целиком (Python)Осторожно! Код!

def expected(r_a, r_b):                 # логистическая сигмоида разности
    return 1 / (1 + 10 ** ((r_b - r_a) / 400))

def update(r_a, r_b, score_a, k=20):    # score_a ∈ {1, 0.5, 0}
    e_a = expected(r_a, r_b)
    surprise = score_a - e_a            # S − E: сигнал и шум в одном числе
    return r_a + k * surprise           # предсказал → пронаблюдал → поправил

K — это learning rate, и в нём весь компромисс

S − E — это сигнал плюс шум в одном числе. Часть удивления — настоящая новость о скилле, часть — везение партии; в моменте фильтр их не различает. Всё, что он может, — решить, насколько доверять одному наблюдению. За это доверие отвечает K — по сути learning rate.

Поставим эксперимент. Два равных игрока, E = 0.5 у каждого. Каждый матч — монетка 50/50, чистый шум: скилл не меняется. Но рейтинг прыгает на ±K/2 за партию. Покрутите K — и смотрите, как зелёная линия (наблюдение) дрожит вокруг ровной линии истинного скилла (сигнал):

K32

шаг за партию ±16истинный скилл постоянныйбольшой K — отзывчиво, но шумно

Большой K — отзывчиво, но шумно; малый — гладко, но инертно. FIDE решает это вручную грубой лесенкой: K=40 новичкам, K=20 основной массе, K=10 тем, кто за 2400 (FIDE Handbook B.02). Адаптация ручная — машина сама не понимает, про кого знает мало.

Дырки ELO

Каждая дырка — это, по сути, техзадание на следующую систему:

K фиксированный. Доверие к одному матчу задано заранее (в лучшем случае — ручной лесенкой 40/20/10). Машина сама не понимает, про кого знает мало, а про кого уже всё ясно.
Нет меры уверенности. Рейтинг 1500 после трёх партий и после трёхсот — одно и то же число, хотя во втором случае мы знаем об игроке несравнимо больше. Эту уверенность Elo просто негде хранить.
Только 1v1. Команды Эло не предусматривал — шахматы парные. Как раскидать один общий результат на пятерых игроков, формула не знает.
Не учитывает простой. Не играли год — скилл наверняка поплыл, а рейтинг стоит памятником. Свежесть данных система не отслеживает.

Первые две закроет Glicko (через RD), третью — TrueSkill, а четвёртую — «протухание» RD в том же Glicko.

4. Glicko: добавляем неуверенность

Систему Glicko придумал статистик Марк Гликман (его работы и калькуляторы — на glicko.net). Идея, которой не хватало ELO: хранить второе число — RD (rating deviation), отклонение рейтинга. По смыслу это стандартное отклонение оценки: насколько мы в ней не уверены. У новичка RD большой, у ветерана с сотнями партий — маленький.

RD — это адаптивный K

Ключ ко всему разделу: RD — это адаптивный K. Шаг обновления масштабируется неуверенностью. Большой RD → крупные шаги (мало знаем — не жалко); маленький → осторожные шажки. Glicko сам понимает, кому доверять резкие изменения, а кому нет.

Как неуверенность входит в формулуОсторожно! Математика!

Технически вводится $q = \ln 10 / 400 \approx 0.0058$ и функция, прижимающая влияние «мутных» соперников:

g(RD) = \frac{1}{\sqrt{1 + 3q^2 RD^2/\pi^2}}, \qquad E = \frac{1}{1 + 10^{-g(RD_j)(r - r_j)/400}}

Чем больше RD соперника, тем меньше g(RD) и тем слабее его результат двигает ваш рейтинг: матч против «мутного» игрока несёт мало информации.

Уверенность копится и протухает

RD падает с числом партий (каждая добавляет информации) и растёт за простой — старые данные протухают. Дефолт потолка у Гликмана — $RD_0 = 350$ . Покрутите: матчи сужают полосу r ± RD, простой раздувает её обратно к потолку.

Сыграно0

Простой, нед.0

RD0 350c (модель) 48полоса = r ± RD

Как RD растёт за простой — формулойОсторожно! Математика!

RD \leftarrow \min\!\left(\sqrt{RD^2 + c^2 t},\; RD_0\right)

t — время простоя, c — скорость «протухания», RD₀ = 350 — потолок неуверенности, выше которого RD не поднимается.

Период обновления Glicko целиком (Python)Осторожно! Код!

import math
q = math.log(10) / 400

def g(rd):                                # чем мутнее соперник, тем меньше доверия
    return 1 / math.sqrt(1 + 3 * (q * rd / math.pi) ** 2)

def expected(r, r_j, rd_j):
    return 1 / (1 + 10 ** (-g(rd_j) * (r - r_j) / 400))

def update(r, rd, games):                 # games = [(r_j, rd_j, s_j), ...]
    inv_d2 = 0.0
    delta  = 0.0
    for r_j, rd_j, s_j in games:
        e = expected(r, r_j, rd_j)
        inv_d2 += (q * g(rd_j)) ** 2 * e * (1 - e)
        delta  += g(rd_j) * (s_j - e)
    rd_new = 1 / math.sqrt(1 / rd**2 + inv_d2)   # точность складывается → RD сжимается
    r_new  = r + q * rd_new**2 * delta           # шаг ∝ RD² — это и есть адаптивный K
    return r_new, rd_new

Точности (1/RD²) складываются — это буквально байесовское обновление гауссианы. Glicko-2 добавляет третье число — волатильность σ — и ловит «штормящих» игроков. Кто использует в проде: Lichess (Glicko-2, открытый код — можно залезть и посмотреть), Chess.com, Rocket League. Чего Glicko по-прежнему не умеет — команды. За этим идём к финальному боссу.

5. TrueSkill: убеждения, команды и factor graph

TrueSkill разработали в Microsoft Research — Хербрих, Минка и Грэпел, статья на NIPS 2006. Подход откровенно и заточен под командный матчмейкинг Xbox Live.

Скилл как гауссово убеждение

Скилл игрока — это не число, а целое распределение, гауссиана $\mathcal{N}(\mu, \sigma^2)$ : μ — оценка, σ — неуверенность (та же роль, что у RD). Дефолты MS: $\mu_0 = 25$ , $\sigma_0 = 25/3 \approx 8.33$ . Числа подобраны красиво: игроку показывают консервативную оценку $\mu - 3\sigma$ , и у новичка она равна нулю — вверх ползёт по мере того, как σ сжимается. Матч — байесовское наблюдение: смещается (μ) и сужается (σ).

μ — оценка, σ — неуверенностьпосле матча σ сжимается, у кого σ больше — тот сдвинется сильнее

Factor graph на одном примере 2v2

Как TrueSkill раздаёт плюсы и минусы по команде? Через factor graph и передачу сообщений. Кружки — переменные, квадраты — факторы; узлы шлют друг другу гауссовы сводки (среднее + точность), пока картина не сойдётся. Команда A обыграла команду B:

Сверху вниз — что мы ожидали. Берём, что знали про скилл каждого (это приоры). В конкретной партии человек играет чуть выше или ниже своего уровня — этот случайный разброс и есть «+β», шум дня; добавляем его к скиллу и получаем перформанс, то есть насколько круто игрок выступил именно сейчас. Складываем перформансы внутри команды → получаем силу команды. Вычитаем одну из другой: d — это «на сколько команда A впереди команды B». Пока это только прогноз: до результата d размазан — может, A впереди, а может, и позади.

Фактор исхода — что случилось на самом деле. Теперь подаём реальный результат. A победила — значит на самом деле она набрала больше, то есть d оказалась положительной. Фактор отрезает все варианты, где A была бы позади, и оставляет только «A впереди» (формально — d больше крошечного ничейного зазора ε). Вот это отрезание лишнего и есть новая информация, которую принёс матч.

И здесь рождается «удивление». Если фаворит победил, как и ждали, — отрезать почти нечего, убеждения едва шевельнутся. А если случился апсет (слабый обыграл сильного) — отрезается огромный кусок «ожидаемого», и колокола дёргаются сильно.

Снизу вверх — раздаём поправку. Эта поправка едет обратно: от d — к двум командам, оттуда — к перформансу каждого игрока, а от него — к его скиллу. Колокол каждого чуть смещается и сужается. Делится поправка пропорционально неуверенности: у кого σ больше, тот сдвигается сильнее — про него знали меньше, значит, из матча узнали больше.

Замкнутая форма для 1v1 (Python)Осторожно! Код!

Для команд — та же идея, прогнанная через граф выше; для пары игроков обновление сворачивается в замкнутую форму:

from scipy.stats import norm                 # φ = norm.pdf, Φ = norm.cdf
from math import sqrt

def update_1v1(mu_w, s_w, mu_l, s_l, beta):   # w — победитель, l — проигравший
    c = sqrt(2 * beta**2 + s_w**2 + s_l**2)
    t = (mu_w - mu_l) / c
    v = norm.pdf(t) / norm.cdf(t)             # «удивление»: велико при апсете
    w = v * (v + t)
    mu_w += s_w**2 / c * v                     # сдвиг μ ∝ собственной дисперсии σ²
    mu_l -= s_l**2 / c * v
    s_w  *= sqrt(1 - s_w**2 / c**2 * w)        # σ всегда сжимается
    s_l  *= sqrt(1 - s_l**2 / c**2 * w)
    return (mu_w, s_w), (mu_l, s_l)

Команды: перформанс команды = сумма перформансов игроков, кредит и вина делятся по дисперсиям. Ничьи — через «ничейный зазор» ε. В 2018-м Минка и соавторы выпустили TrueSkill 2: индивидуальная статистика (киллы/ассисты как доп-сигналы), частичное участие, опора на опыт игрока. Оригинал дебютировал на Halo 2 на Xbox Live (первое массовое внедрение); TrueSkill 2 — на Halo 5 и Gears of War 4.

6. Где математика заканчивается

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

Смурфы и буст. для фильтра — «новичок с большим σ», и фильтр отрабатывает идеально: за десяток матчей догоняет реальный скилл и выпинывает смурфа наверх. Беда в том, что эти матчи он провёл, проезжаясь катком по настоящим новичкам. Задача тут не математическая — решается телефоном, гейтами на ранкед, детектом аномальных винстриков, а не тюнингом K.

Очередь против качества. Идеальный баланс требует идеального соперника, которого может не быть в очереди прямо сейчас. Это ползунок: уже допуск — ровнее матч, но дольше ждать; шире — мгновенно, но с разбросом по скиллу.

Допуск ±τ120

разброс по скиллу ≈ ±60доля пула в окне 37%ожидание ≈ 11 сигрушечная модель механизма, не реальные серверные цифры

О том, что такой компромисс существует и как его крутят, открыто писали в дев-блогах Riot, Valve и Blizzard.

Психология. Игроки помнят редкие плохие матчи. Десять ровных каток забываются, один разнос с тиммейтом-вредителем идёт в твиттер с подписью «matchmaking is broken». Часть претензий — про восприятие дисперсии, а не про математику фильтра. Ваша память — тоже шумный канал.

7. Одна мысль на пятьдесят лет

Пройдите взглядом от 1960-х до 2018-го — это одна и та же мысль, которую полвека делают всё аккуратнее: оцени скрытый сигнал по шумным однобитным наблюдениям, фильтруй шум и — главное — знай свою неуверенность.

ELO сделал первый шаг: сигмоида разности и фиксированный K. Glicko заметил, что доверие должно быть адаптивным, и завёл RD. TrueSkill довёл скилл до полноценного убеждения N(μ, σ) и научился раздавать его по командам, взвешивая поправки на уверенность. Каждая система — заплатка на конкретную дыру предыдущей.

Что брать под свою игру:

1v1 с длинной историей (шахматы, файтинг-ладдер) — ELO. Простая, прозрачная, проверенная полувеком.
Нужна быстрая калибровка — Glicko-2 (и код Lichess открыт, подсмотреть есть где).
Команды (шутеры, MOBA) — TrueSkill или его идеи.

И держите в голове неудобную часть про пределы: смурфы, холодный старт, ползунок «очередь ↔ качество» и человеческая память живут за гранью математики. Самый хитрый фильтр их не закрывает — это работа поведенческих и продуктовых систем. Рейтинг необходим, но он не весь матчмейкинг.

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

Референсы

Arpad Elo, «The Rating of Chessplayers, Past and Present» (1978) — первоисточник по ELO от автора системы.
FIDE Handbook, раздел B.02 — действующие правила и K-факторы (40/20/10).
Bradley, Terry (1952) — модель парных сравнений, математический предок формулы ELO.
Mark Glickman, glicko.net — статьи по Glicko и пошаговый пример «Example of the Glicko-2 system».
Lichess — открытый исходный код реализации Glicko-2 в боевом проде.
Herbrich, Minka, Graepel, «TrueSkill: A Bayesian Skill Rating System» (NIPS 2006) — factor graph и message passing.
Minka, Cleven, Zaykov, «TrueSkill 2» (Microsoft Research, 2018) — индивидуальная статистика, частичное участие.
Jeff Moser, «Computing Your Skill» — доходчивый разбор TrueSkill с выводом функций v и w.
Дев-блоги Riot Games, Valve, Blizzard — про компромисс «очередь ↔ качество».

// @easy_dev_math

Такие разборы — с кодом и интерактивами — выходят в канале каждую неделю.