Matchmakingsysteem: ELO, Glicko-2 en wachtrijbeheer
Matchmaking en het stille algoritme dat beslist of een match leuk of frustrerend wordt. Een goed ontworpen systeem brengt spelers van hetzelfde niveau binnen een redelijke tijd bij elkaar en spreidt ze gelijk tussen de teams. Een slecht ontworpen systeem zorgt voor onevenwichtige games die spelers wegjagen van het spel over een paar dagen.
Titels zoals Tegenaanval 2, Dota 2, Liga van Legenden e Valorant ze hebben geavanceerde matchmaking-systemen die beoordelingsalgoritmen combineren (ELO, Glicko-2, TrueSkill) met wachtrijbeheer, op vaardigheden gebaseerde matchmaking (SBMM), teambalancering en latentie-optimalisatie. In dit artikel zullen we een compleet systeem vanaf de grond opbouwen wiskunde tot productie-implementatie.
Wat je gaat leren
- ELO-algoritme: berekening, voordelen en beperkingen
- Glicko-2: ratingafwijking en volatiliteit voor nauwkeurige matchmaking
- Wachtrijbeheer: wachttijd, uitbreiding en aanvulling
- SBMM versus CBMM: debat over vaardigheden versus verbindingen
- Smurfdetectie en matchmaking-bescherming
- Redis-implementatie voor realtime wachtrijen
Basisprincipes: het ELO-systeem
Het ELO-systeem, uitgevonden door natuurkundige Arpad Elo voor schaken in de jaren zestig, vormt nog steeds de basis
van veel moderne beoordelingssystemen. Het centrale en eenvoudige idee: na elke wedstrijd de beoordeling
van de winnaar neemt toe en die van de verliezer neemt af met een bedrag dat evenredig is aan de "verwachting"
van het resultaat. De formule voor de verwachte overwinning van speler A tegen B is:
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: Beoordeling met onzekerheid
De belangrijkste beperking van ELO is dat alle beoordelingen als even zeker worden beschouwd. Een speler die dat heeft 1000 spellen gespeeld met een rating van 1500 moeten anders worden beschouwd dan iemand die heeft gespeeld slechts 5 games met dezelfde rating. Glicko-2, ontwikkeld door professor Mark Glickman van Boston University, introduceert twee extra parameters:
- Beoordelingsafwijking (RD): hoe onzeker we zijn over de rating van de speler. Hoge RD = veel onzekerheid. Standaard 350 voor nieuwe spelers, zakt bij veel games richting 50
- Volatiliteit (sigma): hoe onstabiel de prestaties van de speler zijn. Hoge volatiliteit = onvoorspelbare prestaties
Glicko-2 wordt gebruikt door CS:GO/CS2, Dota 2, Guild Wars 2, Splatoon 2, Lichess en vele andere competitieve titels.
// 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);
}
}Wachtrijbeheer met Redis
Een geavanceerd beoordelingsalgoritme is niet voldoende. We hebben een wachtrijsysteem nodig dat het wachten beheert, breid de matchingcriteria geleidelijk uit en breng eerlijkheid in evenwicht met aanvaardbare wachttijden. Redis is de ideale keuze voor wachtrijen dankzij Sorted Sets, waarmee gezocht kan worden op bereik beoordeling in 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;
}
}Aanvulling: lopende games aanvullen
Wanneer een speler tijdens de wedstrijd de verbinding verbreekt, zoekt backfill naar een vervanger uit de wachtrij in plaats van het team in een numeriek nadeel achter te laten. Vereist aparte logica dan matchmaking standaard omdat het de context van het spel dat al aan de gang is, moet respecteren.
// 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 versus CBMM: het debat
Il Op vaardigheden gebaseerde matchmaking (SBMM) creëert evenwichtige spellen, maar kan de tijden verlengen van wachten. De Op verbindingen gebaseerde matchmaking (CBMM) geef prioriteit aan latentie, creëren potentieel onevenwichtige matches maar met een optimale netwerkervaring. De meeste spellen modern hanteert een hybride aanpak.
| Benadering | Pro | Tegen | Gebruikt door |
|---|---|---|---|
| Puur SBMM | Evenwichtige spellen, eerlijke ervaring | Lange wachttijden, mentale stress | CS2 gerangschikt, Valorant |
| Puur CBMM | Lage latentie, korte wachttijden | Ernstige onevenwichtigheden, smurfprobleem | Casual modi |
| Hybride SBMM+CBMM | Goede balans en latentie | Algoritmische complexiteit | COD, Apex, Fortnite |
| Gerangschikt + Casual | Afzonderlijke modi voor verschillende behoeften | Spelersbasis verdeeld | Overwatch, Rainbow Six |
Smurfen detectie
Lo smurfen (ervaren spelers op secundaire accounts om tegen beginners te spelen) en een van de meest verraderlijke problemen bij matchmaking. Op resultaten gebaseerde beoordelingen convergeren langzaam: Het duurt 50-100 spellen voordat een smurf zijn ware niveau bereikt. Ondertussen vernietigt het de ervaring van tientallen onervaren spelers.
// 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;
}
}Matchmaking-systeemstatistieken
Hoe meet je of jouw matchmaking goed werkt? Dit zijn de belangrijkste indicatoren om te monitoren:
| Metrisch | Formule / definitie | Ideaal doelwit |
|---|---|---|
| Match kwaliteitsscore | 1 - |avg_team1 - gem_team2| /gem_global | > 0,85 |
| Wachttijd P95 | 95e percentiel van de tijd in de wachtrij | < 60 seconden |
| Tarief vroegtijdig stoppen | % verlaten games in de eerste 20% | < 5% |
| Winsttariefsaldo | Teamwinstpercentage afstand vanaf 50% | < 5 procentpunten |
| Gem. serverlatentie | Gemiddelde latentie naar de gameserver | < 60 ms |
| Vulpercentage wachtrij | % verzoeken dat binnen 2 minuten overeenkomt | > 95% |
Beste praktijken voor matchmaking
- Plaatsingsovereenkomsten: Gebruik 5-10 startspellen met een hoge K-factor om snel nieuwe spelers te positioneren
- RD-verval voor inactief: Verhoogt de beoordelingsafwijking voor spelers die langer dan 2 weken inactief zijn
- Gewogen teamrang: Gebruik voor teamspellen de gewogen gemiddelde beoordeling, niet het eenvoudige gemiddelde
- Controleer de wachtrijgrootte: Als de wachtrij leeg raakt (weinig spelers online), versoepel dan de criteria agressief
- Apart gerangschikt en casual: Modi met verschillende logica beschermen de ervaring van beide soorten spelers
Conclusies
Een effectief matchmakingsysteem vereist wiskundig inzicht in beoordelingsalgoritmen, intelligent wachtrijbeheer dat wachttijden en kwaliteit in evenwicht brengt, en bescherming biedt tegen slecht gedrag zoals smurfen. Glicko-2 vertegenwoordigt de beste balans tussen nauwkeurigheid en implementeerbaarheid voor de meeste moderne competitieve games.
In het volgende artikel zullen we de realtime statussynchronisatie: terugdraai netcode, clientvoorspelling en serverafstemming om een game-ervaring te creëren verloopt soepel, zelfs met een aanzienlijke netwerklatentie.
Volgende in de Game Backend-serie
- Artikel 04: Realtime statussynchronisatie en netcode-rollback
- Artikel 05: Anti-Cheat-architectuur aan de serverzijde