매치메이킹 시스템: ELO, Glicko-2 및 대기열 관리
매치메이킹과 매치가 재미있을지 아니면 실망스러울지를 결정하는 자동 알고리즘입니다. 잘 설계된 시스템은 비슷한 수준의 플레이어를 합리적인 시간에 모아서 분산시킵니다. 팀 간에도 똑같이. 잘못 설계된 시스템은 플레이어를 멀어지게 하는 불균형한 게임을 만듭니다. 며칠 안에 게임에서.
다음과 같은 제목 카운터 스트라이크 2, 도타 2, 리그 오브 레전드 e 용감한 등급 알고리즘을 결합한 정교한 매치메이킹 시스템을 보유하고 있습니다. (ELO, Glicko-2, TrueSkill) 대기열 관리, 스킬 기반 매치메이킹(SBMM), 팀 밸런싱 기능 포함 대기 시간 최적화. 이 기사에서 우리는 처음부터 완전한 시스템을 구축할 것입니다. 수학부터 생산 구현까지.
무엇을 배울 것인가
- ELO 알고리즘: 계산, 장점 및 제한 사항
- Glicko-2: 정확한 매치메이킹을 위한 등급 편차 및 변동성
- 대기열 관리: 대기 시간, 확장 및 채우기
- SBMM 대 CBMM: 기술 대 연결 기반 논쟁
- 스머핑 탐지 및 매치메이킹 보호
- 실시간 대기열을 위한 Redis 구현
기초: ELO 시스템
1960년대 물리학자 Arpad Elo가 체스를 위해 발명한 ELO 시스템은 여전히 기본입니다.
많은 현대 등급 시스템 중 하나입니다. 핵심적이고 간단한 아이디어: 각 경기가 끝난 후 등급이 매겨집니다.
승자의 승률은 증가하고 패자의 승률은 "기대"에 비례하여 감소합니다.
결과의. B에 대한 A의 예상 승리 공식은 다음과 같습니다.
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: 불확실한 평가
ELO의 주요 한계는 모든 등급을 동일하게 확실하게 취급한다는 것입니다. 가지고 있는 선수 평점 1500으로 1000게임을 플레이한 사람과 플레이한 사람은 다르게 간주되어야 합니다. 같은 등급의 게임은 5개뿐입니다. 글리코-2, Mark Glickman 교수가 개발 Boston University의 두 가지 추가 매개변수를 소개합니다.
- 등급 편차(RD): 우리가 플레이어의 평가에 대해 얼마나 불확실한지. 높은 RD = 불확실성이 높습니다. 신규 플레이어의 경우 기본 350, 게임이 많아지면 50으로 낮아집니다.
- 변동성(시그마): 플레이어의 성능이 얼마나 불안정한지. 높은 변동성 = 예측할 수 없는 성능
Glicko-2는 CS:GO/CS2, Dota 2, Guild Wars 2, Splatoon 2, Lichess 및 기타 여러 경쟁 타이틀에서 사용됩니다.
// 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를 통한 대기열 관리
정교한 평가 알고리즘만으로는 충분하지 않습니다. 대기를 관리하는 대기열 시스템이 필요합니다. 일치 기준을 점진적으로 확장하고 허용 가능한 대기 시간과 공정성의 균형을 유지합니다. Redis는 범위별로 검색할 수 있는 Sorted Set 덕분에 대기열에 이상적인 선택입니다. 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 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 대 CBMM: 논쟁
Il 기술 기반 매치메이킹(SBMM) 균형 잡힌 게임을 만들지만 시간이 늘어날 수 있음 기다림의. 그만큼 연결 기반 매치메이킹(CBMM) 대기 시간 우선 순위 지정, 생성 잠재적으로 불균형한 일치가 가능하지만 네트워크 환경은 최적입니다. 대부분의 게임 현대에서는 하이브리드 접근 방식을 사용합니다.
| 접근하다 | 찬성 | 에 맞서 | 사용처 |
|---|---|---|---|
| 순수 SBMM | 균형 잡힌 게임, 공정한 경험 | 오랜 기다림, 정신적 스트레스 | CS2 랭크, 용감한 |
| 순수 CBMM | 낮은 대기 시간, 짧은 대기 시간 | 심각한 불균형, 스머프 문제 | 캐주얼 모드 |
| 하이브리드 SBMM+CBMM | 좋은 균형과 대기 시간 | 알고리즘의 복잡성 | COD, 에이펙스, 포트나이트 |
| 랭크 + 캐주얼 | 다양한 요구에 맞는 별도의 모드 | 플레이어 기반 분할 | 오버워치, 레인보우 식스 |
스머핑 감지
Lo 스머핑 (보조 계정의 숙련된 플레이어가 초보자와 대결할 수 있음) 중매에서 가장 교활한 문제 중 하나입니다. 결과 기반 평가는 천천히 수렴됩니다. 스머프가 진정한 수준에 도달하려면 50~100번의 게임이 필요합니다. 그 사이에 파괴된다 경험이 부족한 수십 명의 플레이어의 경험.
// 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;
}
}매치메이킹 시스템 지표
매치메이킹이 잘 진행되고 있는지 어떻게 측정하나요? 모니터링할 주요 지표는 다음과 같습니다.
| 미터법 | 공식 / 정의 | 이상적인 목표 |
|---|---|---|
| 일치 품질평가점수 | 1 - |avg_team1 - avg_team2| /avg_global | > 0.85 |
| 대기 시간 P95 | 대기열에 있는 시간의 95번째 백분위수 | < 60초 |
| 조기퇴사율 | 처음 20%에서 포기한 게임 비율 | < 5% |
| 승률 균형 | 팀 승률은 50%에서 멀다 | 5% 미만 |
| 평균 서버 지연 시간 | 게임 서버의 평균 대기 시간 | < 60ms |
| 대기열 채우기 비율 | 2분 이내에 일치하는 요청 비율 | > 95% |
매치메이킹 모범 사례
- 배치 일치: K-인자가 높은 5~10개의 시작 게임을 사용하여 새로운 플레이어를 빠르게 배치
- 유휴 시 RD 감쇠: 2주 이상 활동이 없는 플레이어의 등급 편차가 증가합니다.
- 가중 팀 순위: 팀게임의 경우 단순평균이 아닌 가중평균 평점을 사용합니다.
- 대기열 크기를 모니터링합니다. 대기열이 비어 있으면(온라인 플레이어가 거의 없음) 기준을 적극적으로 완화하세요.
- 랭크와 캐주얼 분리: 서로 다른 로직을 갖춘 모드는 두 유형의 플레이어 모두의 경험을 보호합니다.
결론
효과적인 매치메이킹 시스템을 위해서는 등급 알고리즘에 대한 수학적 이해가 필요합니다. 대기 시간과 품질의 균형을 맞추고 대기 시간으로부터 보호하는 지능형 대기열 관리 스머핑 같은 나쁜 행동. Glicko-2는 정확성의 최고의 균형을 나타냅니다. 대부분의 최신 경쟁 게임에 대한 구현 가능성.
다음 기사에서는 실시간 상태 동기화: 게임 경험을 창출하기 위한 롤백 넷코드, 클라이언트 예측 및 서버 조정 상당한 네트워크 대기 시간이 있어도 원활하게 실행됩니다.
다음 게임 백엔드 시리즈
- 기사 04: 실시간 상태 동기화 및 넷코드 롤백
- 기사 05: 서버측 치트 방지 아키텍처