Sistem de potrivire: ELO, Glicko-2 și Queue Management
Matchmaking și algoritmul silentios care decide dacă un meci va fi distractiv sau frustrant. Un sistem bine conceput reunește jucători de nivel similar într-un timp rezonabil și îi împrăștie egal între echipe. Un sistem prost proiectat creează jocuri dezechilibrate care alungă jucătorii de la joc în câteva zile.
Titluri ca Counter Strike 2, Dota 2, League of Legends e Valorant au sisteme sofisticate de potrivire care combină algoritmi de evaluare (ELO, Glicko-2, TrueSkill) cu gestionarea cozilor, matchmaking bazat pe abilități (SBMM), echilibrarea echipelor și optimizarea latenței. În acest articol vom construi un sistem complet, de la zero matematică până la implementarea producției.
Ce vei învăța
- Algoritmul ELO: calcul, avantaje și limitări
- Glicko-2: abaterea evaluării și volatilitatea pentru o potrivire precisă
- Gestionarea cozii: timp de așteptare, extindere și umplere
- SBMM vs CBMM: abilități vs dezbateri bazate pe conexiune
- Detectare smurfing și protecție împotriva potrivirii
- Implementarea Redis pentru coadă în timp real
Fundamente: Sistemul ELO
Sistemul ELO, inventat de fizicianul Arpad Elo pentru șah în anii 1960, este încă baza
a multor sisteme moderne de rating. Ideea centrală și simplă: după fiecare meci, ratingul
a învingătorului crește, iar cea a învinsului scade cu o sumă proporțională cu „așteptarea”
a rezultatului. Formula pentru victoria așteptată a jucătorului A împotriva lui B este:
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: Evaluare cu incertitudine
Principala limitare a ELO este că tratează toate evaluările ca fiind la fel de sigure. Un jucător care are a jucat 1000 de jocuri cu rating 1500 ar trebui să fie considerat diferit de cel care a jucat doar 5 jocuri cu aceeași evaluare. Glicko-2, dezvoltat de profesorul Mark Glickman de la Universitatea din Boston, introduce doi parametri suplimentari:
- Deviația de evaluare (RD): cât de nesiguri suntem cu privire la ratingul jucătorului. RD mare = multă incertitudine. Implicit 350 pentru jucătorii noi, scade la 50 cu multe jocuri
- Volatilitate (sigma): cât de instabilă este performanța jucătorului. Volatilitate ridicată = performanță imprevizibilă
Glicko-2 este folosit de CS:GO/CS2, Dota 2, Guild Wars 2, Splatoon 2, Lichess și multe alte titluri competitive.
// 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);
}
}Gestionarea cozilor cu Redis
Un algoritm de evaluare sofisticat nu este suficient. Avem nevoie de un sistem de coadă care să gestioneze așteptarea, extindeți progresiv criteriile de potrivire și echilibrați corectitudinea cu timpii de așteptare acceptabili. Redis este alegerea ideală pentru coadă datorită Sorted Sets, care permit căutări după interval rating în 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;
}
}Umplere: reîncărcați jocurile aflate în desfășurare
Când un jucător se deconectează în timpul meciului, completarea caută un înlocuitor din coadă în loc să lase echipa într-un dezavantaj numeric. Necesită o logică separată decât matchmaking standard deoarece trebuie să respecte contextul jocului deja în desfășurare.
// 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: Dezbaterea
Il Matchmaking bazat pe abilități (SBMM) creează jocuri echilibrate, dar poate crește timpii de așteptare. The Matchmaking bazat pe conexiune (CBMM) prioritizează latența, crearea potriviri potențial dezechilibrate, dar cu experiență optimă în rețea. Cele mai multe jocuri modern folosește o abordare hibridă.
| Abordare | Pro | Împotriva | Folosit de |
|---|---|---|---|
| SBMM pur | Jocuri echilibrate, experiență corectă | Așteptări lungi, stres mental | Clasat CS2, Valorant |
| CBMM pur | Latență scăzută, așteptări scurte | Dezechilibre severe, problemă cu ștrumfii | Moduri casual |
| SBMM+CBMM hibrid | Echilibru și latență bun | Complexitate algoritmică | COD, Apex, Fortnite |
| Clasat + Casual | Moduri separate pentru nevoi diferite | Baza jucătorilor împărțită | Overwatch, Rainbow Six |
Detectare smurfing
Lo smurfing (jucători cu experiență pe conturi secundare pentru a juca împotriva începătorilor) și una dintre cele mai insidioase probleme în matchmaking. Evaluarea bazată pe rezultate converge încet: Este nevoie de 50-100 de jocuri pentru ca un ștrumf să-și atingă adevăratul nivel. Între timp, distruge experiența a zeci de jucători fără experiență.
// 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;
}
}Metrici ale sistemului de potrivire
Cum măsori dacă matchmaking-ul tău funcționează bine? Aceștia sunt indicatorii cheie de monitorizat:
| Metric | Formula / Definiție | Țintă ideală |
|---|---|---|
| Scorul de calitate al potrivirii | 1 - |avg_team1 - avg_team2| / avg_global | > 0,85 |
| Timp de așteptare P95 | Percentila 95 de timp în coadă | < 60 de secunde |
| Rata de renunțare anticipată | % jocuri abandonate în primele 20% | < 5% |
| Soldul ratei de câștig | Rata de victorie a echipei distanță de la 50% | < 5 puncte procentuale |
| Latența medie a serverului | Latența medie la serverul de joc | < 60 ms |
| Rata de umplere a cozii | % solicitări care se potrivesc în 2 min | > 95% |
Cele mai bune practici pentru matchmaking
- Potriviri de plasare: Utilizați 5-10 jocuri de început cu factor K ridicat pentru a poziționa rapid jucătorii noi
- RD Decay pentru Idle: Mărește Abaterea Evaluării pentru jucătorii care au fost inactivi mai mult de 2 săptămâni
- Clasamentul ponderat al echipei: Pentru jocurile de echipă, utilizați evaluarea medie ponderată, nu media simplă
- Monitorizați dimensiunea cozii: Dacă coada se golește (puțini jucători online), relaxați criteriile în mod agresiv
- Separat clasat și casual: Modurile cu logici diferite protejează experiența ambelor tipuri de jucători
Concluzii
Un sistem eficient de potrivire necesită înțelegerea matematică a algoritmilor de evaluare, management inteligent al cozilor care echilibrează timpii de așteptare și calitatea și protecția împotriva comportament rău, cum ar fi strumfitul. Glicko-2 reprezintă cel mai bun echilibru de precizie și implementabilitate pentru majoritatea jocurilor competitive moderne.
În următorul articol vom explora sincronizarea stării în timp real: rollback netcode, predicție client și reconciliere server pentru a crea o experiență de joc rulează fără probleme chiar și cu o latență semnificativă a rețelei.
Următorul în seria Game Backend
- Articolul 04: Sincronizarea stării în timp real și retragerea codului net
- Articolul 05: Arhitectura anti-cheat pe partea de server