System dobierania graczy: ELO, Glicko-2 i zarządzanie kolejkami
Dobieranie graczy i cichy algorytm, który decyduje, czy mecz będzie zabawny, czy frustrujący. Dobrze zaprojektowany system łączy graczy na podobnym poziomie w rozsądnym czasie i rozdziela ich równo pomiędzy zespołami. Źle zaprojektowany system tworzy niezrównoważone gry, które odstraszają graczy z meczu za kilka dni.
Tytuły takie jak Counter Strike 2, Dota 2, Liga Legend e Waleczny mają wyrafinowane systemy dobierania graczy, które łączą algorytmy oceniania (ELO, Glicko-2, TrueSkill) z zarządzaniem kolejkami, dobieraniem graczy na podstawie umiejętności (SBMM), równoważeniem drużyn i optymalizacja opóźnień. W tym artykule zbudujemy kompletny system od podstaw matematyki do wdrożenia produkcyjnego.
Czego się nauczysz
- Algorytm ELO: obliczenia, zalety i ograniczenia
- Glicko-2: odchylenie i zmienność ocen w celu dokładnego dobierania graczy
- Zarządzanie kolejkami: czas oczekiwania, rozbudowa i zapełnienie
- SBMM kontra CBMM: debata oparta na umiejętnościach i połączeniach
- Wykrywanie smurfingu i ochrona przed dobieraniem partnerów
- Implementacja Redis do kolejkowania w czasie rzeczywistym
Podstawy: System ELO
System ELO, wynaleziony przez fizyka Arpada Elo na potrzeby szachów w latach 60. XX wieku, nadal stanowi podstawę
wielu nowoczesnych systemów ocen. Główny i prosty pomysł: po każdym meczu ocena
zwycięzcy wzrasta, a przegranego maleje o kwotę proporcjonalną do „oczekiwań”
wyniku. Wzór na oczekiwane zwycięstwo gracza A nad B jest następujący:
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: Ocena z niepewnością
Głównym ograniczeniem ELO jest to, że traktuje wszystkie oceny jako jednakowo pewne. Gracz, który ma rozegrał 1000 gier z rankingiem 1500, należy traktować inaczej niż grę, w którą grał tylko 5 gier z tą samą oceną. Glicko-2, opracowany przez profesora Marka Glickmana Uniwersytetu Bostońskiego wprowadza dwa dodatkowe parametry:
- Odchylenie znamionowe (RD): jak niepewni jesteśmy co do oceny gracza. Wysokie RD = dużo niepewności. Domyślne 350 dla nowych graczy, w wielu grach spada do 50
- Zmienność (sigma): jak niestabilna jest wydajność gracza. Wysoka zmienność = nieprzewidywalna wydajność
Glicko-2 jest używany w CS:GO/CS2, Dota 2, Guild Wars 2, Splatoon 2, Lichess i wielu innych konkurencyjnych tytułach.
// 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);
}
}Zarządzanie kolejkami za pomocą Redis
Wyrafinowany algorytm oceniania nie wystarczy. Potrzebujemy systemu kolejkowego, który zarządza oczekiwaniem, stopniowo poszerzaj kryteria dopasowywania i równoważ uczciwość akceptowalnym czasem oczekiwania. Redis to idealny wybór do kolejkowania dzięki Sorted Sets, które umożliwiają wyszukiwanie według zakresu ocena w 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;
}
}Uzupełnianie: uzupełnianie trwających gier
Gdy gracz rozłączy się w trakcie meczu, funkcja Backfill szuka następcy z kolejki zamiast pozostawiać zespół w niekorzystnej sytuacji liczebnej. Wymaga innej logiki niż dobieranie graczy standardem, ponieważ musi uwzględniać kontekst już trwającej gry.
// 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 kontra CBMM: debata
Il Dobieranie graczy oparte na umiejętnościach (SBMM) tworzy zrównoważone gry, ale może wydłużyć czas czekania. The Dobieranie graczy oparte na połączeniu (CBMM) nadaj priorytet opóźnieniom, tworzeniu potencjalnie niezrównoważone mecze, ale z optymalnym doświadczeniem sieciowym. Większość gier modern wykorzystuje podejście hybrydowe.
| Zbliżać się | Zawodowiec | Przeciwko | Używany przez |
|---|---|---|---|
| Czysty SBMM | Zrównoważone gry, uczciwe doświadczenie | Długie oczekiwanie, stres psychiczny | Rankingowe CS2, Valorant |
| Czyste CBMM | Niskie opóźnienia, krótkie oczekiwania | Poważne braki równowagi, problem ze smerfem | Tryby swobodne |
| Hybrydowy SBMM + CBMM | Dobra równowaga i opóźnienie | Złożoność algorytmiczna | COD, Apex, Fortnite |
| Rankingowe + Swobodne | Oddzielne tryby dla różnych potrzeb | Baza graczy podzielona | Overwatch, Rainbow Six |
Wykrywanie smurfingu
Lo smerfowanie (doświadczeni gracze na kontach dodatkowych do gry przeciwko początkującym) i jeden z najbardziej podstępnych problemów w dobieraniu graczy. Ocena oparta na wynikach powoli się zbliża: Aby Smurf osiągnął swój prawdziwy poziom, potrzeba 50–100 gier. Tymczasem niszczy doświadczenie kilkudziesięciu niedoświadczonych graczy.
// 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;
}
}Wskaźniki systemu dobierania graczy
Jak zmierzyć, czy Twoje kojarzenie działa dobrze? Oto kluczowe wskaźniki, które należy monitorować:
| Metryczny | Formuła / definicja | Idealny cel |
|---|---|---|
| Dopasuj Wynik Jakości | 1 - |avg_team1 - avg_team2| / średni_globalny | > 0,85 |
| Czas oczekiwania P95 | 95. percentyl czasu w kolejce | < 60 sekund |
| Wskaźnik wczesnego kończenia pracy | % porzuconych gier w pierwszych 20% | < 5% |
| Saldo współczynnika wygranych | Odległość współczynnika zwycięstw drużyny od 50% | < 5 punktów procentowych |
| Średnie opóźnienie serwera | Średnie opóźnienie na serwerze gry | < 60 ms |
| Współczynnik wypełnienia kolejki | % żądań pasujących w ciągu 2 minut | > 95% |
Najlepsze praktyki w zakresie kojarzeń
- Mecze o miejsce: Użyj 5-10 gier początkowych z wysokim współczynnikiem K, aby szybko pozycjonować nowych graczy
- Zanik RD w stanie bezczynności: Zwiększa odchylenie oceny u graczy, którzy byli nieaktywni przez ponad 2 tygodnie
- Ważona ranga drużyny: W przypadku gier zespołowych użyj średniej ważonej oceny, a nie zwykłej średniej
- Monitoruj rozmiar kolejki: Jeśli kolejka się opróżni (kilku graczy online), agresywnie złagodź kryteria
- Oddzielne rankingowe i zwykłe: Tryby o różnej logice chronią doświadczenie obu typów graczy
Wnioski
Skuteczny system kojarzeń wymaga matematycznego zrozumienia algorytmów oceniania, inteligentne zarządzanie kolejkami, które równoważy czas oczekiwania i jakość oraz zabezpieczenia przed złe zachowanie, takie jak smerfowanie. Glicko-2 reprezentuje najlepszą równowagę dokładności i możliwość wdrożenia w większości nowoczesnych gier rywalizacyjnych.
W następnym artykule omówimy synchronizacja stanu w czasie rzeczywistym: przywracanie kodu sieciowego, przewidywanie klientów i uzgadnianie serwerów w celu zapewnienia wrażeń w grach działa płynnie nawet przy znacznych opóźnieniach sieci.
Następny w serii Game Backend
- Artykuł 04: Synchronizacja stanu w czasie rzeczywistym i przywracanie kodu sieciowego
- Artykuł 05: Architektura zapobiegająca oszustwom po stronie serwera