マッチメイキング システム: ELO、Glicko-2、キュー管理
マッチメイキングと、試合が楽しいかイライラするかを決定するサイレント アルゴリズム。 適切に設計されたシステムは、同じレベルのプレイヤーを適切な時間内に集め、分散させます。 チーム間で平等に。不適切に設計されたシステムは、プレイヤーを遠ざける不均衡なゲームを作成します 数日後の試合から。
のようなタイトル カウンターストライク2, ドータ2, リーグ・オブ・レジェンド e ヴァロラント 彼らは評価アルゴリズムを組み合わせた洗練されたマッチメイキングシステムを持っています (ELO、Glicko-2、TrueSkill) キュー管理、スキルベースのマッチメイキング (SBMM)、チームバランシング付き そしてレイテンシの最適化。この記事では、完全なシステムをゼロから構築します。 数学から製品実装まで。
何を学ぶか
- ELO アルゴリズム: 計算、利点、制限事項
- Glicko-2: 正確なマッチメイキングのためのレーティング偏差とボラティリティ
- キュー管理: 待機時間、拡張、バックフィル
- SBMM 対 CBMM: スキル対コネクションベースの議論
- スマーフィング検出とマッチメイキング保護
- リアルタイムキューのための Redis 実装
基礎: ELO システム
1960 年代に物理学者のアルパド・エロによってチェス用に発明された ELO システムは、今でも基礎となっています
多くの最新の評価システムの中で、中心的かつシンプルなアイデア: 各試合後の評価
勝者の期待値は「期待値」に比例して増加し、敗者の値は減少します。
結果の。プレーヤー A の B に対する予想勝利の計算式は次のとおりです。
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、マーク・グリックマン教授によって開発されました。 ボストン大学の博士は、次の 2 つの追加パラメータを導入しています。
- 評価偏差 (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 Sets のおかげでキューイングに最適です。 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) レイテンシの優先順位付け、作成 不均衡な一致が発生する可能性がありますが、最適なネットワーク エクスペリエンスが得られます。ほとんどのゲーム modern はハイブリッド アプローチを使用します。
| アプローチ | プロ | に対して | 使用者 |
|---|---|---|---|
| 純粋なSBMM | バランスの取れたゲーム、公平な体験 | 待ち時間が長くて精神的ストレスがかかる | CS2 ランク、ヴァロラント |
| 純粋なCBMM | 低遅延、短い待ち時間 | 深刻な不均衡、スマーフ問題 | カジュアルモード |
| ハイブリッドSBMM+CBMM | 優れたバランスと遅延 | アルゴリズムの複雑さ | COD、Apex、フォートナイト |
| ランク+カジュアル | さまざまなニーズに対応する個別のモード | 選手層が分かれている | オーバーウォッチ、レインボーシックス |
スマーフィング検出
Lo スサーフィン (初心者と対戦するためのセカンダリアカウントの経験豊富なプレイヤー) そして、マッチメイキングにおける最も厄介な問題の 1 つです。結果に基づく評価はゆっくりと収束します。 スマーフが真のレベルに達するには、50 ～ 100 試合かかります。 Meanwhile, it destroys 何十人もの経験の浅いプレイヤーの経験。
// 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条: サーバー側のアンチチートアーキテクチャ