Systém dohazování: ELO, Glicko-2 a Queue Management
Matchmaking a tichý algoritmus, který rozhoduje, zda bude zápas zábavný nebo frustrující. Dobře navržený systém svede dohromady hráče podobné úrovně v rozumném čase a rozprostře je rovnoměrně mezi týmy. Špatně navržený systém vytváří nevyvážené hry, které hráče odhání ze hry za pár dní.
Tituly jako Counter Strike 2, Dota 2, League of Legends e Udatný mají sofistikované systémy dohazování, které kombinují hodnotící algoritmy (ELO, Glicko-2, TrueSkill) se správou fronty, dohazováním podle dovedností (SBMM), vyvažováním týmu a optimalizace latence. V tomto článku vytvoříme kompletní systém od základů matematiky až po realizaci výroby.
Co se naučíte
- Algoritmus ELO: výpočet, výhody a omezení
- Glicko-2: odchylka v hodnocení a volatilita pro přesné dohazování
- Správa fronty: čekací doba, expanze a zálohování
- SBMM vs CBMM: debata o dovednostech vs připojení
- Detekce smurfingu a ochrana proti dohazování
- Implementace Redis pro řazení do front v reálném čase
Základy: Systém ELO
Systém ELO, který vynalezl fyzik Arpad Elo pro šachy v 60. letech, je stále základem
mnoha moderních ratingových systémů. Ústřední a jednoduchá myšlenka: po každém zápase hodnocení
počet vítězů se zvyšuje a počet poražených se snižuje o částku úměrnou „očekávání“
výsledku. Vzorec pro očekávané vítězství hráče A proti B je:
E(A) = 1 / (1 + 10^((RB - RA)/400))
// Implementazione ELO in TypeScript
class ELOSystem {
private readonly K: number; // K-factor: velocità di cambiamento del rating
constructor(kFactor: number = 32) {
this.K = kFactor;
}
// Probabilità attesa di vittoria del giocatore A
expectedScore(ratingA: number, ratingB: number): number {
return 1 / (1 + Math.pow(10, (ratingB - ratingA) / 400));
}
// Aggiorna i rating dopo una partita 1v1
updateRatings(
ratingA: number,
ratingB: number,
actualScoreA: number // 1 = vittoria A, 0 = vittoria B, 0.5 = pareggio
): { newRatingA: number; newRatingB: number } {
const expectedA = this.expectedScore(ratingA, ratingB);
const expectedB = 1 - expectedA;
const actualScoreB = 1 - actualScoreA;
const newRatingA = Math.round(ratingA + this.K * (actualScoreA - expectedA));
const newRatingB = Math.round(ratingB + this.K * (actualScoreB - expectedB));
return { newRatingA, newRatingB };
}
// K-factor dinamico basato sul numero di partite giocate
dynamicKFactor(gamesPlayed: number, currentRating: number): number {
if (gamesPlayed < 30) return 40; // Nuovo giocatore: cambia velocemente
if (currentRating > 2400) return 16; // Elite: cambia lentamente
return 32; // Standard
}
}
// Esempio di utilizzo
const elo = new ELOSystem();
// Rating 1500 vs Rating 1200: A e favorito (prob. 85%)
const result = elo.updateRatings(1500, 1200, 1); // A vince
// A guadagna pochi punti (atteso), B perde pochi punti
console.log(result); // { newRatingA: 1505, newRatingB: 1195 }
// Sorpresa: B batte A
const surprise = elo.updateRatings(1500, 1200, 0); // B vince
// A perde molti punti (sorpresa!), B guadagna molti punti
console.log(surprise); // { newRatingA: 1473, newRatingB: 1227 }Glicko-2: Hodnocení s nejistotou
Hlavním omezením ELO je to, že považuje všechny ratingy za stejně jisté. Hráč, který má 1 000 odehraných her s hodnocením 1 500 by se mělo posuzovat jinak než ten, který hrál pouze 5 her se stejným hodnocením. Glicko-2, vyvinuté profesorem Markem Glickmanem z Bostonské univerzity, zavádí dva další parametry:
- Odchylka hodnocení (RD): jak nejistí jsme ohledně hodnocení hráče. Vysoká RD = velká nejistota. Výchozí 350 pro nové hráče, u mnoha her klesá na 50
- Volatilita (sigma): jak nestabilní je výkon hráče. Vysoká volatilita = nepředvídatelný výkon
Glicko-2 používají CS:GO/CS2, Dota 2, Guild Wars 2, Splatoon 2, Lichess a mnoho dalších soutěžních titulů.
// Struttura dati Glicko-2
interface Glicko2Player {
rating: number; // Rating visibile (default: 1500)
rd: number; // Rating Deviation (default: 350 per nuovo giocatore)
volatility: number; // Volatilita sigma (default: 0.06)
lastActive: Date; // Per il decay del RD per inattivita
}
class Glicko2System {
private readonly TAU = 0.5; // Costante di sistema (0.3-1.2, riduce volatilita)
// Converti sulla scala interna di Glicko-2
toInternal(player: Glicko2Player): { mu: number; phi: number; sigma: number } {
return {
mu: (player.rating - 1500) / 173.7178,
phi: player.rd / 173.7178,
sigma: player.volatility
};
}
fromInternal(mu: number, phi: number, sigma: number): Glicko2Player {
return {
rating: Math.round(mu * 173.7178 + 1500),
rd: Math.round(phi * 173.7178),
volatility: sigma,
lastActive: new Date()
};
}
private g(phi: number): number {
return 1 / Math.sqrt(1 + (3 * phi * phi) / (Math.PI * Math.PI));
}
private E(mu: number, muJ: number, phiJ: number): number {
return 1 / (1 + Math.exp(-this.g(phiJ) * (mu - muJ)));
}
// Aggiorna il rating dopo un set di partite
update(player: Glicko2Player, results: Array<{ opponent: Glicko2Player; score: number }>): Glicko2Player {
const p = this.toInternal(player);
// Step 3: Calcola varianza stimata v
let vInverse = 0;
for (const { opponent } of results) {
const o = this.toInternal(opponent);
const gPhi = this.g(o.phi);
const eVal = this.E(p.mu, o.mu, o.phi);
vInverse += gPhi * gPhi * eVal * (1 - eVal);
}
const v = 1 / vInverse;
// Step 4: Calcola improvement delta
let delta = 0;
for (const { opponent, score } of results) {
const o = this.toInternal(opponent);
delta += this.g(o.phi) * (score - this.E(p.mu, o.mu, o.phi));
}
delta = v * delta;
// Step 5: Nuova volatilita (algoritmo Illinois iterativo)
const newSigma = this.updateVolatility(p, v, delta);
// Step 6: Nuova phi* (pre-rating RD)
const phiStar = Math.sqrt(p.phi * p.phi + newSigma * newSigma);
// Step 7: Aggiorna phi e mu
const newPhi = 1 / Math.sqrt(1 / (phiStar * phiStar) + 1 / v);
const newMu = p.mu + newPhi * newPhi * (delta / v);
return this.fromInternal(newMu, newPhi, newSigma);
}
// Decay RD per giocatori inattivi (simula incertezza crescente)
decayForInactivity(player: Glicko2Player): Glicko2Player {
const p = this.toInternal(player);
const newPhi = Math.min(
Math.sqrt(p.phi * p.phi + p.sigma * p.sigma),
350 / 173.7178 // Massimo RD
);
return this.fromInternal(p.mu, newPhi, p.sigma);
}
private updateVolatility(
p: { mu: number; phi: number; sigma: number },
v: number,
delta: number
): number {
const a = Math.log(p.sigma * p.sigma);
const eps = 0.000001;
const f = (x: number) => {
const ex = Math.exp(x);
const phiSq = p.phi * p.phi;
return (
(ex * (delta * delta - phiSq - v - ex)) /
(2 * Math.pow(phiSq + v + ex, 2)) -
(x - a) / (this.TAU * this.TAU)
);
};
let A = a;
let B = delta * delta > p.phi * p.phi + v
? Math.log(delta * delta - p.phi * p.phi - v)
: a - this.TAU;
let fA = f(A);
let fB = f(B);
while (Math.abs(B - A) > eps) {
const C = A + (A - B) * fA / (fB - fA);
const fC = f(C);
if (fC * fB < 0) { A = B; fA = fB; }
else { fA /= 2; }
B = C; fB = fC;
}
return Math.exp(A / 2);
}
}Správa front s Redis
Sofistikovaný hodnotící algoritmus nestačí. Potřebujeme systém front, který zvládá čekání, postupně rozšiřujte odpovídající kritéria a vyvažujte spravedlnost s přijatelnou čekací dobou. Redis je ideální volbou pro řazení do fronty díky Sorted Sets, které umožňují vyhledávání podle rozsahu hodnocení v O (log N + M).
// Sistema di matchmaking con Redis Sorted Set
import Redis from 'ioredis';
interface QueueEntry {
playerId: string;
rating: number;
rd: number;
regionLatencies: Record<string, number>;
joinedAt: number;
mode: string;
}
class MatchmakingQueue {
private redis: Redis;
private readonly MAX_WAIT_MS = 120_000;
constructor() {
this.redis = new Redis(process.env.REDIS_URL!);
}
async enqueue(entry: QueueEntry): Promise<void> {
const key = `mm:queue:${entry.mode}`;
await this.redis.zadd(key, entry.rating, JSON.stringify(entry));
}
async dequeue(playerId: string, mode: string): Promise<void> {
const key = `mm:queue:${mode}`;
const members = await this.redis.zrange(key, 0, -1);
for (const member of members) {
const e: QueueEntry = JSON.parse(member);
if (e.playerId === playerId) {
await this.redis.zrem(key, member);
return;
}
}
}
async findMatch(
candidate: QueueEntry,
teamSize: number = 5
): Promise<{ team1: string[]; team2: string[]; region: string } | null> {
const waitMs = Date.now() - candidate.joinedAt;
// Range di rating dinamico: si espande con l'attesa
// Radice quadrata per crescita sub-lineare (espansione graduale)
const waitRatio = Math.min(waitMs / this.MAX_WAIT_MS, 1);
const expansion = Math.sqrt(waitRatio);
const baseRange = 150;
const rdBonus = candidate.rd * 0.5; // RD alto = giocatore incerto = range più ampio
const waitBonus = expansion * 200; // Più attendi, più si allarga
const range = baseRange + rdBonus + waitBonus;
// Cerca candidati nel range di rating
const key = `mm:queue:${candidate.mode}`;
const rawCandidates = await this.redis.zrangebyscore(
key,
candidate.rating - range,
candidate.rating + range
);
const candidates = rawCandidates
.map(r => JSON.parse(r) as QueueEntry)
.filter(c => c.playerId !== candidate.playerId);
const needed = teamSize * 2 - 1; // Per un 5v5, servono 9 altri
if (candidates.length < needed) return null;
// Seleziona i migliori per qualità e latenza
const selected = this.selectOptimalGroup(candidate, candidates, needed);
const all = [candidate, ...selected];
return this.formBalancedTeams(all, teamSize);
}
private selectOptimalGroup(
anchor: QueueEntry,
pool: QueueEntry[],
count: number
): QueueEntry[] {
// Score composito: skill similarity + latenza bassa
const scored = pool.map(p => {
const skillDiff = Math.abs(p.rating - anchor.rating);
const sharedRegions = Object.keys(p.regionLatencies).filter(
r => anchor.regionLatencies[r] !== undefined
);
const avgSharedLatency = sharedRegions.length > 0
? sharedRegions.reduce((s, r) => s + p.regionLatencies[r], 0) / sharedRegions.length
: 999;
// Score basso = candidato migliore
const score = skillDiff * 0.7 + avgSharedLatency * 0.3;
return { player: p, score };
});
return scored
.sort((a, b) => a.score - b.score)
.slice(0, count)
.map(s => s.player);
}
private formBalancedTeams(
players: QueueEntry[],
teamSize: number
): { team1: string[]; team2: string[]; region: string } {
// Ordina per rating decrescente, poi distribuisci alternando
const sorted = [...players].sort((a, b) => b.rating - a.rating);
const team1: QueueEntry[] = [];
const team2: QueueEntry[] = [];
let sum1 = 0, sum2 = 0;
for (const p of sorted) {
if (team1.length < teamSize && (sum1 <= sum2 || team2.length === teamSize)) {
team1.push(p); sum1 += p.rating;
} else {
team2.push(p); sum2 += p.rating;
}
}
const region = this.findBestRegion(players);
return {
team1: team1.map(p => p.playerId),
team2: team2.map(p => p.playerId),
region
};
}
private findBestRegion(players: QueueEntry[]): string {
const regions = Object.keys(players[0].regionLatencies);
let best = regions[0];
let bestAvg = Infinity;
for (const r of regions) {
const avg = players.reduce(
(s, p) => s + (p.regionLatencies[r] ?? 999), 0
) / players.length;
if (avg < bestAvg) { bestAvg = avg; best = r; }
}
return best;
}
}Backfill: Doplňte probíhající hry
Když se hráč během zápasu odpojí, backfill hledá náhradu z fronty místo toho, aby nechal tým v početní nevýhodě. Vyžaduje samostatnou logiku než matchmaking standardní, protože musí respektovat kontext již probíhající hry.
// Backfill service - ricerca sostituti per partite in corso
interface BackfillRequest {
sessionId: string;
slotsNeeded: number;
currentPlayers: QueueEntry[];
elapsedMs: number; // Quanto e durata la partita gia
}
class BackfillService {
async findSubstitutes(
request: BackfillRequest,
queue: MatchmakingQueue
): Promise<string[]> {
// Calcola rating medio della partita in corso
const avgRating = request.currentPlayers.reduce(
(s, p) => s + p.rating, 0
) / request.currentPlayers.length;
// Range più ampio per backfill (tolleranza maggiore)
const range = 300;
const key = 'mm:queue:ranked';
const redis = new Redis(process.env.REDIS_URL!);
const raw = await redis.zrangebyscore(key, avgRating - range, avgRating + range);
const candidates = raw
.map(r => JSON.parse(r) as QueueEntry)
.sort((a, b) => Math.abs(a.rating - avgRating) - Math.abs(b.rating - avgRating))
.slice(0, request.slotsNeeded);
// Notifica ai candidati - hanno 15 secondi per accettare
await this.notifyAndWaitForAcceptance(
candidates.map(c => c.playerId),
request.sessionId,
15_000
);
return candidates.map(c => c.playerId);
}
private async notifyAndWaitForAcceptance(
playerIds: string[],
sessionId: string,
timeoutMs: number
): Promise<string[]> {
// Invia notifica push a ogni giocatore candidato
const notifications = playerIds.map(id =>
this.pushService.notify(id, {
type: 'BACKFILL_INVITE',
sessionId,
timeout: timeoutMs,
message: 'Una partita in corso ha bisogno di un giocatore. Vuoi unirti?'
})
);
await Promise.all(notifications);
// Attendi conferma entro il timeout
return new Promise((resolve) => {
const accepted: string[] = [];
const timer = setTimeout(() => resolve(accepted), timeoutMs);
this.acceptanceBus.on('backfill-accept', (playerId: string) => {
if (playerIds.includes(playerId)) {
accepted.push(playerId);
if (accepted.length === playerIds.length) {
clearTimeout(timer);
resolve(accepted);
}
}
});
});
}
}SBMM vs CBMM: Debata
Il Dohazování založené na dovednostech (SBMM) vytváří vyvážené hry, ale může prodloužit časy čekání. The Matchmaking na základě připojení (CBMM) upřednostňovat latenci, vytvářet potenciálně nevyvážené zápasy, ale s optimálním síťovým zážitkem. Většina her moderní používá hybridní přístup.
| Přístup | Pro | Proti | Použito uživatelem |
|---|---|---|---|
| Čistý SBMM | Vyvážené hry, férový zážitek | Dlouhé čekání, psychický stres | CS2 Ranked, Valorant |
| Čistý CBMM | Nízká latence, krátké čekání | Závažná nerovnováha, problém se šmouly | Příležitostné režimy |
| Hybridní SBMM+CBMM | Dobrá rovnováha a latence | Algoritmická složitost | COD, Apex, Fortnite |
| Hodnoceno + příležitostné | Oddělené režimy pro různé potřeby | Hráčská základna rozdělena | Overwatch, Rainbow Six |
Detekce smurfingu
Lo smurfování (zkušení hráči na sekundárních účtech, aby mohli hrát proti začátečníkům) a jeden z nejzákeřnějších problémů v matchmakingu. Hodnocení založené na výsledcích se pomalu sbližuje: Šmoula potřebuje 50-100 her, než dosáhne své skutečné úrovně. Mezitím ničí zkušenosti desítek nezkušených hráčů.
// Rilevamento smurf tramite analisi comportamentale
interface PlayerBehaviorProfile {
winRate: number;
avgKDA: number; // Kill-Death-Assist ratio
headShotPercent?: number; // FPS-specific
reactionTimeMs?: number;
accuracyPercent?: number;
mvpRate: number; // % partite come MVP
gamesPlayed: number;
rankProgression: number[]; // Storico rating ultimi 20 match
}
class SmurfDetectionService {
isLikelySmurf(profile: PlayerBehaviorProfile): { likely: boolean; confidence: number } {
let suspicionScore = 0;
let maxScore = 0;
// Check 1: Account nuovo con statistiche da veterano
if (profile.gamesPlayed < 25) {
maxScore += 30;
if (profile.winRate > 0.70) suspicionScore += 20;
if (profile.mvpRate > 0.40) suspicionScore += 10;
}
// Check 2: Performance outlier rispetto al rating assegnato
maxScore += 25;
if (profile.avgKDA > 3.5) suspicionScore += 15;
if (profile.headShotPercent && profile.headShotPercent > 60) suspicionScore += 10;
// Check 3: Curva di apprendimento assente
// Un vero principiante migliora gradualmente; uno smurf e subito al massimo
maxScore += 20;
if (profile.rankProgression.length >= 5) {
const variance = this.calculateVariance(profile.rankProgression);
const meanRank = profile.rankProgression.reduce((s, r) => s + r, 0) / profile.rankProgression.length;
const coeffVar = Math.sqrt(variance) / meanRank;
// Bassa varianza nei primi match = giocatore che non sta "imparando" = smurf
if (coeffVar < 0.05 && profile.gamesPlayed < 20) suspicionScore += 20;
}
const confidence = suspicionScore / maxScore;
return { likely: confidence > 0.6, confidence };
}
// Applica boost al K-factor per correggere velocemente il rating
getRatingBoostMultiplier(smurfConfidence: number, gamesPlayed: number): number {
if (smurfConfidence > 0.8) return 4.0; // Alto sospetto: sale velocissimo
if (smurfConfidence > 0.6) return 2.5; // Medio sospetto
if (gamesPlayed < 10) return 2.0; // Placement fase normale
return 1.0;
}
private calculateVariance(values: number[]): number {
const mean = values.reduce((s, v) => s + v, 0) / values.length;
return values.reduce((s, v) => s + Math.pow(v - mean, 2), 0) / values.length;
}
}Metriky systému dohazování
Jak měříte, zda vaše dohazování funguje dobře? Toto jsou klíčové ukazatele, které je třeba sledovat:
| Metrický | Vzorec / Definice | Ideální cíl |
|---|---|---|
| Porovnejte skóre kvality | 1 - |avg_team1 - avg_team2| / avg_global | > 0,85 |
| Čekací doba P95 | 95. percentil času ve frontě | < 60 sekund |
| Míra předčasného ukončení | % opuštěných her v prvních 20 % | < 5 % |
| Zůstatek výhry | Vzdálenost týmových výher od 50 % | < 5 procentních bodů |
| Prům. latence serveru | Průměrná latence na herní server | < 60 ms |
| Míra naplnění fronty | % požadavků, které se shodují do 2 minut | > 95 % |
Nejlepší postupy pro dohazování
- Zápasy o umístění: Použijte 5-10 počátečních her s vysokým K-faktorem k rychlému umístění nových hráčů
- RD Decay for Idle: Zvyšuje odchylku hodnocení u hráčů, kteří byli neaktivní déle než 2 týdny
- Vážené pořadí týmu: U týmových her používejte vážený průměr hodnocení, nikoli prostý průměr
- Sledujte velikost fronty: Pokud se fronta vyprázdní (málo hráčů online), agresivně uvolněte kritéria
- Samostatně hodnocené a neformální: Režimy s různou logikou chrání zážitek obou typů hráčů
Závěry
Efektivní systém dohazování vyžaduje matematické porozumění ratingovým algoritmům, inteligentní správa front, která vyvažuje čekací doby a kvalitu a chrání před špatné chování, jako je smurfování. Glicko-2 představuje nejlepší rovnováhu přesnosti a implementovatelnost pro většinu moderních soutěžních her.
V příštím článku prozkoumáme synchronizace stavu v reálném čase: rollback netcode, predikce klienta a sladění serveru pro vytvoření herního zážitku běží hladce i při značné latenci sítě.
Další v sérii Game Backend
- Článek 04: Synchronizace stavu v reálném čase a vrácení zpětného kódu Netcode
- Článek 05: Server-Side Anti-Cheat Architecture