03 - Sistema di Matchmaking: ELO, Glicko-2 e Queue Management

Il matchmaking è un compromesso tra equità e attesa

Un giocatore che aspetta quaranta secondi per una partita equilibrata è contento; uno che ne aspetta quattro per una partita già decisa al primo minuto non torna. Il matchmaking vive tutto in questa tensione: ogni criterio che stringi (livello simile, ping basso, squadre bilanciate) fa salire il tempo di coda, ogni criterio che allenti lo fa scendere e abbassa la qualità. Non esiste un valore giusto in assoluto, esiste quello che i tuoi giocatori tollerano, e per scoprirlo serve poter misurare.

Questo articolo costruisce i tre pezzi che servono per misurare: un rating che stima il livello (Elo e Glicko-2), una coda che allarga la ricerca col tempo, e un criterio per formare squadre equilibrate. Ogni pezzo ha un listato eseguito: i numeri nelle uscite sono quelli veri del modello, che usa semi fissi e una popolazione di giocatori sintetica. Dopo che il matchmaker ha formato un gruppo, è l'orchestratore dei server a dargli una partita.

Elo: la stima di livello più semplice che funziona

Elo assegna a ogni giocatore un numero. La differenza tra due numeri diventa una probabilità di vittoria: E(A) = 1 / (1 + 10^((RB − RA) / 400)). Con 1500 contro 1200, la differenza di 300 punti dà ad A l'85% di probabilità. Dopo la partita, il rating si sposta di K × (risultato − attesa): chi vince come previsto guadagna poco, chi vince a sorpresa guadagna molto. K è il «coefficiente di sviluppo» e decide quanto il rating è nervoso.

Il listato fa due cose. Prima verifica la formula sui due casi estremi del 1500 contro 1200: la vittoria attesa sposta di cinque punti, quella a sorpresa di ventisette. Poi, per capire cosa fa K, simula 6.000 partite fra 40 giocatori con un livello vero noto (da 1000 a 1975) e misura quanto il rating finale si discosta da quel livello. I risultati delle partite sono estratti dalla stessa formula Elo: è un modello della dinamica di K, non una prova che Elo descriva i giocatori reali.

import random

def expected(ra: float, rb: float) -> float:
    """Probabilita' attesa che A batta B."""
    return 1 / (1 + 10 ** ((rb - ra) / 400))

def update(ra: float, rb: float, score_a: float, k: float = 32):
    ea = expected(ra, rb)
    return round(ra + k * (score_a - ea)), round(rb + k * ((1 - score_a) - (1 - ea)))

print(f"E(1500 vs 1200) = {expected(1500, 1200):.3f}")
print("A (1500) batte B (1200):", update(1500, 1200, 1))
print("B (1200) batte A (1500):", update(1500, 1200, 0))

# Effetto di K: 40 giocatori con livello vero noto, 6000 partite tra coppie casuali.
# Il risultato di ogni partita e' estratto dalla stessa formula (modello, non dati reali).
def run(k: int, seed: int = 1) -> float:
    rng = random.Random(seed)
    true = [1000 + 25 * i for i in range(40)]   # da 1000 a 1975
    rating = [1500.0] * 40
    for _ in range(6000):
        a, b = rng.sample(range(40), 2)
        score = 1.0 if rng.random() < expected(true[a], true[b]) else 0.0
        rating[a], rating[b] = update(rating[a], rating[b], score, k)
    # errore medio sul ranking, centrando i due insiemi (l'Elo e' relativo)
    mt, mr = sum(true) / 40, sum(rating) / 40
    return sum(abs((r - mr) - (t - mt)) for r, t in zip(rating, true)) / 40

for k in (8, 16, 32, 64):
    print(f"K={k:>2}: errore medio sul livello vero dopo 6000 partite = {run(k):.0f} punti")

# Output:
# E(1500 vs 1200) = 0.849
# A (1500) batte B (1200): (1505, 1195)
# B (1200) batte A (1500): (1473, 1227)
# K= 8: errore medio sul livello vero dopo 6000 partite = 75 punti
# K=16: errore medio sul livello vero dopo 6000 partite = 38 punti
# K=32: errore medio sul livello vero dopo 6000 partite = 40 punti
# K=64: errore medio sul livello vero dopo 6000 partite = 60 punti

L'uscita ha la forma di una U: con K=8 il rating insegue troppo lentamente (errore 75 punti dopo 6.000 partite), con K=64 oscilla ad ogni risultato (60), e il minimo sta tra 16 e 32. Questo spiega perché le federazioni non usano un K unico. Il regolamento FIDE (capitolo 8.3.3 della sezione B02) prevede K=40 per chi è nuovo nella lista fino a 30 partite, K=20 finché il rating resta sotto 2400 e K=10 oltre: un rating nuovo deve muoversi in fretta, uno consolidato deve essere stabile. Elo però conosce solo il punteggio: un giocatore con 1500 dopo cinque partite e uno con 1500 dopo mille hanno lo stesso numero, e il sistema li tratta allo stesso modo.

Glicko-2: il rating con la sua incertezza

Glicko-2 di Mark Glickman risponde a quel limite aggiungendo due numeri a ogni giocatore. La rating deviation (RD) dice quanto è incerta la stima: un nuovo utente parte da 1500 con RD 350, e l'RD scende con le partite e risale con l'inattività. La volatilità σ (parte da 0,06) misura quanto il giocatore devia dal proprio livello: chi alterna serate buone e pessime ha σ alta. Il parametro di sistema τ, tra 0,3 e 1,2 secondo il paper, frena i cambi di volatilità.

Il listato implementa l'algoritmo del paper passo per passo, e lo valida sull'esempio che Glickman stesso calcola (giocatore 1500/RD 200 contro tre avversari). Differenze dall'implementazione che si vede spesso in rete: la ricerca del punto di partenza B per il metodo di Illinois cicla sul valore di k finché la funzione cambia segno, invece di fermarsi a k=1, che funziona sull'esempio ma non in generale. Il secondo confronto è la ragione per cui esiste l'RD: la stessa vittoria vale 175 punti per un nuovo e 7 per un veterano. L'ultimo calcolo mostra l'inattività.

import math

SCALE = 173.7178   # fattore di conversione tra la scala di Glicko e quella interna di Glicko-2

def g(phi: float) -> float:
    return 1 / math.sqrt(1 + 3 * phi * phi / math.pi ** 2)

def e(mu: float, mu_j: float, phi_j: float) -> float:
    return 1 / (1 + math.exp(-g(phi_j) * (mu - mu_j)))

def update(rating, rd, sigma, games, tau=0.5):
    """games: elenco di (rating_avversario, rd_avversario, punteggio 1/0.5/0)."""
    mu, phi = (rating - 1500) / SCALE, rd / SCALE
    opp = [((r - 1500) / SCALE, d / SCALE, s) for r, d, s in games]
    v = 1 / sum(g(pj) ** 2 * e(mu, mj, pj) * (1 - e(mu, mj, pj)) for mj, pj, _ in opp)
    delta = v * sum(g(pj) * (s - e(mu, mj, pj)) for mj, pj, s in opp)

    a = math.log(sigma ** 2)
    def f(x):
        ex = math.exp(x)
        return (ex * (delta ** 2 - phi ** 2 - v - ex)) / (2 * (phi ** 2 + v + ex) ** 2) - (x - a) / tau ** 2
    A = a
    if delta ** 2 > phi ** 2 + v:
        B = math.log(delta ** 2 - phi ** 2 - v)
    else:
        k = 1
        while f(a - k * tau) < 0:     # cerca il primo k per cui f cambia segno
            k += 1
        B = a - k * tau
    fA, fB = f(A), f(B)
    while abs(B - A) > 1e-6:           # metodo di Illinois
        C = A + (A - B) * fA / (fB - fA)
        fC = f(C)
        if fC * fB <= 0:
            A, fA = B, fB
        else:
            fA /= 2
        B, fB = C, fC
    new_sigma = math.exp(A / 2)

    phi_star = math.sqrt(phi ** 2 + new_sigma ** 2)
    new_phi = 1 / math.sqrt(1 / phi_star ** 2 + 1 / v)
    new_mu = mu + new_phi ** 2 * (delta / v)
    return new_mu * SCALE + 1500, new_phi * SCALE, new_sigma

# Esempio del paper di Glickman (2012): atteso 1464.06, 151.52, 0.05999
r, rd, s = update(1500, 200, 0.06, [(1400, 30, 1), (1550, 100, 0), (1700, 300, 0)])
print(f"paper di Glickman : rating {r:.2f}, RD {rd:.2f}, sigma {s:.6f}")

# Stessa vittoria contro un avversario 1500/RD 50, per un nuovo giocatore e per un veterano
for nome, rd0 in (("nuovo (RD 350)", 350), ("veterano (RD 50)", 50)):
    r, rd, s = update(1500, rd0, 0.06, [(1500, 50, 1)])
    print(f"{nome:<18}: dopo una vittoria rating {r:.0f} (+{r - 1500:.0f}), RD {rd:.0f}")

# Inattivita': senza partite l'RD sale di sqrt(phi^2 + sigma^2) per periodo, con tetto 350
phi = 50 / SCALE
for periodo in range(1, 101):
    phi = min(math.sqrt(phi ** 2 + 0.06 ** 2), 350 / SCALE)
    if periodo in (1, 10, 50, 100):
        print(f"dopo {periodo:>3} periodi senza giocare: RD {phi * SCALE:.1f}")

# Output:
# paper di Glickman : rating 1464.05, RD 151.52, sigma 0.059996
# nuovo (RD 350)    : dopo una vittoria rating 1675 (+175), RD 248
# veterano (RD 50)  : dopo una vittoria rating 1507 (+7), RD 51
# dopo   1 periodi senza giocare: RD 51.1
# dopo  10 periodi senza giocare: RD 59.9
# dopo  50 periodi senza giocare: RD 89.1
# dopo 100 periodi senza giocare: RD 115.6

Il primo risultato coincide con il paper: 1464,05 contro 1464,06 (la differenza viene dagli arrotondamenti intermedi della tabella del paper) e una volatilità di 0,059996, che il paper scrive 0,05999. Dalle ultime righe si legge la scelta di progetto: un RD alto fa cambiare il rating molto per poche partite (il nuovo giocatore che vince contro un 1500 salta a 1675), ed è proprio ciò che serve contro i principianti che sono in realtà esperti. Dopo cento periodi di inattività l'RD di un veterano è risalito da 50 a 116: il sistema è meno sicuro di dove sia, e tornerà a muoversi in fretta. Glickman scrive che il metodo dà il meglio con una media di almeno 10-15 partite per giocatore in un «periodo di valutazione»; aggiornare dopo ogni singola partita è una scelta di prodotto, non quella del paper, e vale la pena misurarla sui tuoi dati. Lichess, per esempio, dichiara di usare Glicko-2.

La coda: una finestra che si allarga con l'attesa

Un rating da solo non forma partite. Serve una coda che, dato un giocatore in attesa, cerchi chi ha un livello vicino. Il punto delicato è «vicino»: una finestra stretta dà partite eque ma lascia giocatori ai margini della distribuzione (i più forti e i più deboli) fermi in coda. La soluzione standard è una finestra che cresce con il tempo trascorso. Un ordinamento per rating rende la ricerca di una finestra rapida: la lista ordinata in memoria del listato fa lo stesso lavoro di un sorted set di Redis, e il comando equivalente (Redis 6.2 o successivo) è sotto.

# Schema da adattare: richiede Redis 6.2 o successivo (ZRANGE ... BYSCORE)
ZADD mm:ranked 1534 player:42                      # score = rating, membro = id
HSET mm:ranked:meta:42 joinedAt 1699800000 region eu
ZRANGE mm:ranked 1434 1634 BYSCORE LIMIT 0 20     # candidati entro +-100 punti
ZREM mm:ranked player:42                           # restituisce 1 solo a chi lo toglie davvero

Il rating sta nello score, il giocatore è il membro. La nota sull'ultima riga conta: due worker che cercano partite in parallelo possono vedere lo stesso candidato, ma ZREM restituisce 1 a uno solo, e chi riceve 0 deve rinunciare e riprovare. Per questo il dettaglio del giocatore va in una struttura a parte e non serializzato dentro il membro: sostituire un membro JSON significa scansionarlo tutto per ritrovarlo. Il comando ZRANGE ha complessità O(log N + M), dove M è il numero di elementi restituiti (documentazione Redis).

Il listato seguente simula 10 minuti di coda 1 contro 1, con un giocatore ogni due secondi in media e livelli estratti da una normale (media 1500, deviazione 300). Provo quattro politiche: una finestra fissa di ±25, due che si allargano di 5 e 25 punti al secondo, e una fissa e larga di ±200. In fondo, lo stesso file risolve un secondo problema: dividere dieci giocatori in due squadre da cinque.

import bisect
import itertools
import random

class Queue:
    """Equivalente in memoria di un sorted set: lista ordinata per (rating, id)."""
    def __init__(self):
        self._keys: list[tuple[float, int]] = []
        self.joined: dict[int, int] = {}

    def add(self, pid: int, rating: float, now: int):
        bisect.insort(self._keys, (rating, pid)); self.joined[pid] = now

    def remove(self, pid: int, rating: float):
        self._keys.remove((rating, pid)); del self.joined[pid]

    def in_range(self, lo: float, hi: float):          # come ZRANGE ... BYSCORE
        a = bisect.bisect_left(self._keys, (lo, -1))
        b = bisect.bisect_right(self._keys, (hi, 10 ** 9))
        return self._keys[a:b]

def simulate(base: float, growth: float, seed: int = 3, seconds: int = 600):
    rng = random.Random(seed)
    q, pid = Queue(), 0
    waits, gaps = [], []
    ratings: dict[int, float] = {}
    for now in range(seconds):
        if rng.random() < 0.5:                             # un giocatore ogni 2 s in media
            pid += 1; ratings[pid] = rng.gauss(1500, 300); q.add(pid, ratings[pid], now)
        for p in sorted(q.joined, key=lambda x: q.joined[x]):   # il piu' vecchio per primo
            if p not in q.joined:
                continue
            r = ratings[p]
            window = base + growth * (now - q.joined[p])        # finestra che si allarga con l'attesa
            others = [(rr, i) for rr, i in q.in_range(r - window, r + window) if i != p]
            if others:
                rr, i = min(others, key=lambda x: abs(x[0] - r))
                waits += [now - q.joined[p], now - q.joined[i]]; gaps.append(abs(rr - r))
                q.remove(p, r); q.remove(i, rr)
    return len(gaps), sum(waits) / len(waits), sum(gaps) / len(gaps), len(q.joined)

print("finestra iniziale + crescita al secondo -> partite, attesa media, scarto medio di rating, ancora in coda")
for base, growth in ((25, 0), (25, 5), (25, 25), (200, 0)):
    n, w, gp, left = simulate(base, growth)
    print(f"+-{base:>3} + {growth:>2}/s: {n:>3} partite, attesa {w:5.1f} s, scarto {gp:5.1f}, in coda {left:>2}")

# Bilanciare 10 giocatori in 5v5: greedy contro la ricerca esaustiva di tutte le 126 divisioni
rng = random.Random(11)
def greedy(players):
    t1, t2 = [], []
    for p in sorted(players, reverse=True):
        if len(t1) < 5 and (sum(t1) <= sum(t2) or len(t2) == 5): t1.append(p)
        else: t2.append(p)
    return abs(sum(t1) - sum(t2))
def best(players):
    return min(abs(2 * sum(c) - sum(players)) for c in itertools.combinations(players, 5))
gg = bb = 0
for _ in range(200):
    pl = [round(rng.gauss(1500, 300)) for _ in range(10)]
    gg += greedy(pl); bb += best(pl)
print(f"scarto medio fra le somme dei team su 200 lobby: greedy {gg / 200:.1f}, esaustivo {bb / 200:.1f}")

# Output:
# finestra iniziale + crescita al secondo -> partite, attesa media, scarto medio di rating, ancora in coda
# +- 25 +  0/s: 145 partite, attesa  24.0 s, scarto  13.5, in coda 20
# +- 25 +  5/s: 153 partite, attesa   7.5 s, scarto  61.5, in coda  4
# +- 25 + 25/s: 154 partite, attesa   3.7 s, scarto 123.0, in coda  2
# +-200 +  0/s: 154 partite, attesa   4.1 s, scarto  95.7, in coda  2
# scarto medio fra le somme dei team su 200 lobby: greedy 138.2, esaustivo 12.2

La prima parte dell'uscita è il compromesso del paragrafo iniziale, in numeri. La finestra fissa stretta dà lo scarto di rating minimo (13,5 punti) ma 24 secondi di attesa media e venti persone ancora in coda. La finestra fissa larga toglie quasi l'attesa (4,1 s) al costo di uno scarto sette volte maggiore (95,7). La finestra che cresce di 5 punti al secondo sta in mezzo: 7,5 s e 61,5. Tutto dipende da cosa vuole il tuo gioco, e per questo la politica è un parametro da tarare sui dati reali, non una costante nel codice. Ho scelto numeri tondi per il modello; i tuoi dipenderanno dalla densità dei giocatori in coda.

La seconda parte è una lezione sulle squadre. Il bilanciamento «goloso» (ordina per rating e dai ogni giocatore alla squadra con la somma più bassa) sembra ragionevole, ma su 200 lobby casuali lascia una differenza media di 138 punti tra le somme dei due team. Provare tutte le 126 divisioni possibili di dieci giocatori in 5 e 5 costa poche operazioni, e abbassa la differenza media a 12. Con lobby così piccole la ricerca esaustiva non ha motivo di essere evitata.

SBMM o CBMM: quale dei due vincoli cedi

Il skill-based matchmaking (SBMM) privilegia l'equilibrio di livello; il connection-based matchmaking (CBMM) privilegia la vicinanza di rete. Il dibattito pubblico ne fa due fazioni, ma a livello di codice sono due pesi nella stessa funzione di punteggio del candidato.

La tabella non si legge in colonna ma in riga: ogni scelta compra qualcosa e lo paga altrove. Quella che conviene dipende dalla densità della popolazione. Con migliaia di persone in coda anche un SBMM stretto trova subito un avversario; con poche decine, un SBMM puro lascia i giocatori fermi e conviene allargare la finestra o separare le modalità. Quando la popolazione è scarsa, la rinuncia più sicura è quella sul livello e non sulla rete: una partita sbilanciata si finisce, una partita con un ping ingestibile no.

Smurf, backfill e metriche

Uno smurf è un giocatore forte su un account nuovo. Glicko-2 lo tratta già meglio di Elo: l'account nuovo ha RD 350, quindi le prime vittorie lo spostano di molti punti (è il +175 dell'uscita), e il suo rating si adegua al livello vero molto più in fretta. Quello che manca è un rilevatore dei casi limite, e le soglie di un rilevatore (win rate, precisione di tiro, curva di apprendimento) non si importano da un articolo: si ricavano dai dati dei tuoi giocatori e si validano contro i casi noti. Chi pubblica una soglia fissa regala ai bari il confine da non superare.

Il backfill è il caso opposto: una partita in corso ha perso un giocatore e ne cerca un sostituto in coda. Ha regole diverse dalla ricerca normale, perché la finestra deve guardare al livello medio di chi sta già giocando, e la persona che entra non ha visto l'inizio. Se usi GameLift, il callback onUpdateGameSession è proprio il canale su cui il servizio comunica il backfill di FlexMatch al server di gioco. Quanto alla qualità del sistema, queste sono le cinque grandezze che leggerei per prime.

• Percentile 95 dell'attesa in coda: la coda lunga conta più della media.
• Scarto di rating tra le due squadre, per partita: la qualità effettiva dei match.
• Uscite nella prima parte della partita: chi se ne va subito sta dicendo che era sbilanciata.
• Distanza dal 50% del tasso di vittoria per fascia di livello: la prova che il rating è calibrato.
• Latenza media verso il server assegnato.

Le cinque voci misurano due cose diverse: la seconda, la terza e la quarta dicono quanto sono eque le partite, la prima e l'ultima il prezzo che paghi in tempo e in rete. Non ti do soglie perché non ne esistono di universali: il valore di partenza è quello di oggi, e la domanda utile è se un cambio di politica li sposta nella direzione che volevi. Un confronto tra due politiche, con gli stessi dati per una settimana, vale più di qualunque target.

Che cosa sai fare adesso

Sai calcolare un aggiornamento Elo e spiegare perché K ha un valore ottimo, non un valore massimo. Sai implementare Glicko-2 e verificarlo sull'esempio del paper, e sai dire quando conviene all'Elo la sua semplicità. Sai progettare una coda con finestra variabile, misurarne il compromesso tra attesa e scarto, e non lasciare il bilanciamento delle squadre a un algoritmo goloso quando bastano poche operazioni per trovare la divisione ottima. Il passo successivo è far sentire il gioco fluido nonostante la rete: la sincronizzazione dello stato in tempo reale. Per un matchmaker pronto all'uso, c'è Open Match.