Eşleştirme Sistemi: ELO, Glicko-2 ve Kuyruk Yönetimi
Eşleştirme ve bir karşılaşmanın eğlenceli mi yoksa sinir bozucu mu olacağına karar veren sessiz algoritma. İyi tasarlanmış bir sistem, benzer seviyedeki oyuncuları makul bir sürede bir araya getirir ve dağıtır takımlar arasında eşit. Kötü tasarlanmış bir sistem, oyuncuları uzaklaştıran dengesiz oyunlar yaratır birkaç gün içinde oyundan
Gibi başlıklar Counter Strike 2, Dota2, efsaneler Ligi e Valorant derecelendirme algoritmalarını birleştiren gelişmiş eşleştirme sistemlerine sahipler (ELO, Glicko-2, TrueSkill) kuyruk yönetimi, beceriye dayalı eşleştirme (SBMM), takım dengeleme ile ve gecikme optimizasyonu. Bu yazıda sıfırdan komple bir sistem kuracağız matematikten üretim uygulamasına.
Ne Öğreneceksiniz
- ELO algoritması: hesaplama, avantajlar ve sınırlamalar
- Glicko-2: doğru eşleştirme için derecelendirme sapması ve oynaklık
- Kuyruk yönetimi: bekleme süresi, genişletme ve doldurma
- SBMM ve CBMM: beceri ve bağlantı temelli tartışma
- Şirin tespiti ve çöpçatanlık koruması
- Gerçek zamanlı sıraya alma için Redis uygulaması
Temeller: ELO Sistemi
1960'lı yıllarda fizikçi Arpad Elo tarafından satranç için icat edilen ELO sistemi hala temeldir.
birçok modern derecelendirme sisteminden biridir. Temel ve basit fikir: Her maçtan sonra reyting
"Beklenti"yle orantılı olarak kazananın oranı artarken kaybedeninki azalır
sonuçtan. A oyuncusunun B'ye karşı beklenen zaferinin formülü:
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: Belirsizlikle Derecelendirme
ELO'nun temel sınırlaması, tüm derecelendirmeleri eşit derecede kesin olarak ele almasıdır. Olan bir oyuncu 1500 reytingli 1000 oyun oynamış olandan farklı olarak değerlendirilmelidir aynı derecelendirmeye sahip yalnızca 5 oyun. Glicko-2Profesör Mark Glickman tarafından geliştirilmiştir. Boston Üniversitesi'nden iki ek parametre daha sunuyor:
- Derecelendirme Sapması (RD): Oyuncunun reytingi konusunda ne kadar kararsızız. Yüksek RD = çok fazla belirsizlik. Yeni oyuncular için varsayılan 350, birçok oyunda 50'ye düşüyor
- Volatilite (sigma): oyuncunun performansının ne kadar dengesiz olduğu. Yüksek oynaklık = öngörülemeyen performans
Glicko-2, CS:GO/CS2, Dota 2, Guild Wars 2, Splatoon 2, Lichess ve diğer birçok rekabetçi oyun tarafından kullanılmaktadır.
// 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);
}
}Redis ile Kuyruk Yönetimi
Gelişmiş bir derecelendirme algoritması yeterli değildir. Beklemeyi yöneten bir kuyruk sistemine ihtiyacımız var. Eşleştirme kriterlerini aşamalı olarak genişletin ve adaleti kabul edilebilir bekleme süreleriyle dengeleyin. Redis, aralığa göre aramaya olanak tanıyan Sıralanmış Kümeler sayesinde sıraya koymak için ideal seçimdir O(log N + M) cinsinden derecelendirme.
// 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;
}
}Dolgu: Devam eden oyunları yeniden doldurun
Bir oyuncunun maç sırasında bağlantısı kesildiğinde, dolgu kuyruktan yeni bir oyuncu arar Takımı sayısal olarak dezavantajlı durumda bırakmak yerine. Eşleştirmeden ayrı bir mantık gerektirir standart çünkü halihazırda devam eden oyunun bağlamına saygı gösterilmesi gerekiyor.
// 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 ve CBMM: Tartışma
Il Beceriye Dayalı Eşleştirme (SBMM) dengeli oyunlar yaratır ancak süreleri artırabilir beklemekten. Bağlantı Tabanlı Eşleştirme (CBMM) gecikmeye öncelik verin, potansiyel olarak dengesiz eşleşmeler ancak optimum ağ deneyimi ile. Çoğu oyun modern, hibrit bir yaklaşım kullanıyor.
| Yaklaşmak | Profesyonel | Aykırı | Kullanan |
|---|---|---|---|
| Saf SBMM | Dengeli oyunlar, adil deneyim | Uzun beklemeler, zihinsel stres | CS2 Dereceli, Valorant |
| Saf CBMM | Düşük gecikme süresi, kısa bekleme süreleri | Şiddetli dengesizlikler, şirin sorunu | Gündelik modlar |
| Hibrit SBMM+CBMM | İyi denge ve gecikme | Algoritmik karmaşıklık | COD, Apex, Fortnite |
| Dereceli + Sıradan | Farklı ihtiyaçlar için ayrı modlar | Oyuncu tabanı bölündü | Overwatch, Gökkuşağı Altı |
Şirin tespiti
Lo şirin (ikincil hesaplardaki deneyimli oyuncular yeni başlayanlara karşı oynayabilir) ve çöpçatanlığın en sinsi sorunlarından biri. Sonuca dayalı derecelendirme yavaş yavaş birbirine yaklaşıyor: Bir şirinin gerçek seviyesine ulaşması için 50-100 oyun gerekiyor. Bu arada yok eder onlarca deneyimsiz oyuncunun deneyimi.
// 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;
}
}Eşleştirme Sistemi Metrikleri
Eşleştirmenizin iyi çalışıp çalışmadığını nasıl ölçersiniz? İzlenmesi gereken temel göstergeler şunlardır:
| Metrik | Formül / Tanım | İdeal Hedef |
|---|---|---|
| Eşleşme Kalite Puanı | 1 - |avg_team1 - avg_team2| / avg_global | > 0,85 |
| Bekleme Süresi P95 | Kuyrukta geçirilen sürenin 95'inci yüzdelik dilimi | < 60 saniye |
| Erken Bırakma Oranı | İlk %20'deki terkedilen oyunların yüzdesi | < %5 |
| Kazanma Oranı Dengesi | Takımın kazanma oranı %50'ye çıktı | < yüzde 5 puan |
| Ortalama Sunucu Gecikmesi | Oyun sunucusuna ortalama gecikme | < 60ms |
| Kuyruk Doldurma Oranı | 2 dakika içinde eşleşen isteklerin yüzdesi | > %95 |
Çöpçatanlık için En İyi Uygulamalar
- Yerleştirme eşleşmeleri: Yeni oyuncuları hızla konumlandırmak için yüksek K faktörlü 5-10 başlangıç oyunu kullanın
- Boşta Durumda RD Bozulması: 2 haftadan uzun süredir aktif olmayan oyuncular için Derecelendirme Sapmasını artırır
- Ağırlıklı takım sıralaması: Takım oyunları için basit ortalamayı değil ağırlıklı ortalamayı kullanın
- Kuyruk boyutunu izleyin: Sıra boşalırsa (çevrimiçi oyuncu sayısı azsa), kriterleri agresif bir şekilde gevşetin
- Ayrı dereceli ve sıradan: Farklı mantıklara sahip modlar, her iki oyuncu türünün deneyimini korur
Sonuçlar
Etkili bir eşleştirme sistemi, derecelendirme algoritmalarının matematiksel olarak anlaşılmasını gerektirir. bekleme sürelerini ve kaliteyi dengeleyen akıllı kuyruk yönetimi ve Şirinleme gibi kötü davranışlar. Glicko-2 en iyi doğruluk dengesini temsil eder ve çoğu modern rekabetçi oyun için uygulanabilirlik.
Bir sonraki yazımızda bunları inceleyeceğiz gerçek zamanlı durum senkronizasyonu: Bir oyun deneyimi oluşturmak için ağ kodunu geri alma, müşteri tahmini ve sunucu mutabakatı Önemli ağ gecikmelerinde bile sorunsuz çalışır.
Oyun Arka Uç Serisinin Sonraki Bölümü
- Madde 04: Gerçek Zamanlı Durum Senkronizasyonu ve Netcode Geri Alma
- Madde 05: Sunucu Tarafı Hile Önleme Mimarisi