一、公平匹配是在线竞技的灵魂
MOBA游戏的核心体验建立在实力均衡的对局之上。本文实现两大经典评分系统：
- Elo评分：1959年Arpad Elo为国际象棋设计的评分算法，至今仍是竞技游戏标准
- Glicko-2：Mark Glickman对Elo的改进，引入评分偏差（Rating Deviation）衡量置信度
最终目标是构建一个能动态评估玩家实力、快速收敛真实水平、生成均衡团队的匹配系统。
二、Elo评分系统核心算法
Elo的核心假设：玩家表现服从逻辑分布，预期胜率仅由双方评分差决定。
/**
* Elo评分系统实现
* 核心公式：E_A = 1 / (1 + 10^((R_B - R_A)/400))
*/
public class EloSystem {
static class Player {
String id;
double rating; // 当前评分（通常1500为新手基准）
int gamesPlayed; // 对局数
public Player(String id, double initialRating) {
this.id = id;
this.rating = initialRating;
this.gamesPlayed = 0;
}
}
private final double kFactorBase = 32; // 基础K值（评分变化幅度因子）
/**
* 计算玩家A对玩家B的预期胜率
* @param ratingA 玩家A的当前评分
* @param ratingB 玩家B的当前评分
* @return [0,1] 范围内的预期胜率
*/
public double expectedScore(double ratingA, double ratingB) {
return 1.0 / (1.0 + Math.pow(10.0, (ratingB - ratingA) / 400.0));
}
/**
* 单场比赛后更新两位玩家的评分
* @param playerA 玩家A
* @param playerB 玩家B
* @param scoreA A的实际得分：1=胜, 0.5=平, 0=负
*/
public void updateRating(Player playerA, Player playerB, double scoreA) {
double expectedA = expectedScore(playerA.rating, playerB.rating);
double expectedB = 1.0 - expectedA;
double scoreB = 1.0 - scoreA;
// 动态K值：新手变化快，老手变化慢
double kA = calculateKFactor(playerA);
double kB = calculateKFactor(playerB);
// Elo更新公式
double newRatingA = playerA.rating + kA * (scoreA - expectedA);
double newRatingB = playerB.rating + kB * (scoreB - expectedB);
playerA.rating = newRatingA;
playerB.rating = newRatingB;
playerA.gamesPlayed++;
playerB.gamesPlayed++;
System.out.printf("Update: %s %.0f->%.0f (exp=%.3f, actual=%.1f, K=%.0f)%n",
playerA.id, playerA.rating - kA*(scoreA-expectedA), newRatingA, expectedA, scoreA, kA);
System.out.printf("Update: %s %.0f->%.0f (exp=%.3f, actual=%.1f, K=%.0f)%n",
playerB.id, playerB.rating - kB*(scoreB-expectedB), newRatingB, expectedB, scoreB, kB);
}
/**
* 动态K因子计算
* 策略：前10局用K=40快速收敛，之后K=32，高分段(2400+)用K=16
*/
double calculateKFactor(Player p) {
if (p.gamesPlayed < 10) return 40;
if (p.rating >= 2400) return 16;
return kFactorBase;
}
/**
* 5v5团队评分：假设团队实力为成员评分之和（简化模型）
* 实际应用中可引入位置权重、协同系数等
*/
public double teamRating(Player[] team) {
double sum = 0;
for (Player p : team) sum += p.rating;
return sum / team.length; // 团队平均评分
}
/**
* 计算两队的预期胜率
*/
public double[] teamExpectedScore(Player[] teamA, Player[] teamB) {
double rA = teamRating(teamA);
double rB = teamRating(teamB);
double eA = expectedScore(rA, rB);
return new double[]{eA, 1.0 - eA};
}
}
三、Glicko-2：带置信度的动态评分
Elo的缺陷：所有评分被视为同等精确。新手打3局后的1500分与老手打3000局后的1500分完全不同。Glicko-2用RD（Rating Deviation）量化不确定性。
/**
* Glicko-2评分系统
* 扩展了Elo：每个玩家有评分μ、偏差φ、波动率σ三个参数
*/
public class Glicko2System {
static class GlickoPlayer {
String id;
double mu; // 评分（Glicko-2内部使用，通常比Elo低1500）
double phi; // 评分偏差 RD（越大越不确定）
double sigma; // 波动率（衡量评分的不稳定性）
// 转换常量：Glicko-2内部尺度 → 常规评分
static final double SCALE = 173.7178;
public GlickoPlayer(String id, double rating, double rd, double volatility) {
this.id = id;
// 转换为Glicko-2内部尺度
this.mu = (rating - 1500) / SCALE;
this.phi = rd / SCALE;
this.sigma = volatility;
}
/** 转换回常规评分显示 */
double getRating() { return mu * SCALE + 1500; }
double getRD() { return phi * SCALE; }
}
private final double tau = 0.5; // 波动率约束参数（通常0.3~1.2）
/**
* Glicko-2核心更新函数
* @param player 待更新玩家
* @param opponents 对手列表
* @param scores 对每位对手的实际得分（1=胜, 0.5=平, 0=负）
*/
public void updateRating(GlickoPlayer player, GlickoPlayer[] opponents, double[] scores) {
// 1. 计算每个对手的g(φ_j)和E(μ, μ_j, φ_j)
double[] gPhi = new double[opponents.length];
double[] expected = new double[opponents.length];
for (int i = 0; i < opponents.length; i++) {
gPhi[i] = g(opponents[i].phi);
expected[i] = E(player.mu, opponents[i].mu, opponents[i].phi);
}
// 2. 计算方差估计 v
double v = 0;
for (int i = 0; i < opponents.length; i++) {
v += sq(gPhi[i]) * expected[i] * (1 - expected[i]);
}
v = 1.0 / v;
// 3. 计算评分改进量 Δ
double delta = 0;
for (int i = 0; i < opponents.length; i++) {
delta += gPhi[i] * (scores[i] - expected[i]);
}
delta *= v;
// 4. 更新波动率 σ（通过迭代法求解）
double newSigma = updateVolatility(player.phi, delta, v, player.sigma);
// 5. 更新偏差 φ* → φ
double phiStar = Math.sqrt(sq(player.phi) + sq(newSigma));
double newPhi = 1.0 / Math.sqrt(1.0 / sq(phiStar) + 1.0 / v);
// 6. 更新评分 μ
double newMu = player.mu + sq(newPhi) * delta / v;
player.mu = newMu;
player.phi = newPhi;
player.sigma = newSigma;
}
/** g函数：削弱高RD对手的影响力 */
double g(double phi) {
return 1.0 / Math.sqrt(1.0 + 3.0 * sq(phi) / sq(Math.PI));
}
/** E函数：预期胜率 */
double E(double mu, double muJ, double phiJ) {
return 1.0 / (1.0 + Math.exp(-g(phiJ) * (mu - muJ)));
}
/**
* 波动率更新：通过 Illinois 算法求解非线性方程
*/
double updateVolatility(double phi, double delta, double v, double sigma) {
double a = Math.log(sq(sigma));
double eps = 0.000001;
double A = a;
double B = (sq(delta) > sq(phi) + v) ? Math.log(sq(delta) - sq(phi) - v) : a;
if (B <= a) B = a + tau;
double fA = f(A, phi, delta, v, a, tau);
double fB = f(B, phi, delta, v, a, tau);
// Illinois 算法（二分法的改进）
while (Math.abs(B - A) > eps) {
double C = A + (A - B) * fA / (fB - fA);
double fC = f(C, phi, delta, v, a, tau);
if (fC * fB < 0) {
A = B; fA = fB;
} else {
fA = fA / 2.0;
}
B = C; fB = fC;
}
return Math.exp(A / 2.0);
}
double f(double x, double phi, double delta, double v, double a, double tau) {
double ex = Math.exp(x);
double num = ex * (sq(delta) - sq(phi) - v - ex);
double den = 2.0 * sq(sq(phi) + v + ex);
return num / den - (x - a) / sq(tau);
}
double sq(double x) { return x * x; }
}
四、5v5团队匹配与平衡算法
将10位等待玩家划分为两队，使团队评分期望最接近50:50，同时最小化等待时间与位置冲突。
/**
* MOBA匹配系统
* 目标：将队列中的玩家划分为两队，实力差最小化
*/
public class MatchmakingSystem {
static class QueuedPlayer {
String id;
double rating; // Glicko-2评分
double rd; // 评分偏差
long queueTime; // 入队时间戳（毫秒）
String[] roles; // 偏好位置 [上单, 打野, 中单, ADC, 辅助]
public QueuedPlayer(String id, double rating, double rd, String[] roles) {
this.id = id; this.rating = rating; this.rd = rd; this.roles = roles;
this.queueTime = System.currentTimeMillis();
}
/** 综合评分：考虑评分不确定性的下限估计 */
double conservativeRating() {
return rating - 2 * rd; // 95%置信下限
}
}
private final List<QueuedPlayer> queue = new ArrayList<>();
private final double maxRatingDiff = 200; // 允许的最大团队评分差
private final long maxWaitTime = 30000; // 最大等待30秒后放宽匹配条件
/** 玩家入队 */
public void enqueue(QueuedPlayer player) {
queue.add(player);
}
/**
* 尝试从队列中构建一场均衡对局
* 算法：枚举 + 剪枝（10选5共252种组合，计算量极小）
*/
public MatchResult tryMatch() {
if (queue.size() < 10) return null;
// 取队列中最早的10+N位玩家，扩大匹配池
int poolSize = Math.min(queue.size(), 20);
List<QueuedPlayer> pool = new ArrayList<>(queue.subList(0, poolSize));
MatchResult best = null;
double bestScore = Double.NEGATIVE_INFINITY;
// 枚举所有5人组合作为Team A
int n = pool.size();
int[] indices = new int[5];
// 使用递归/回溯生成组合
List<int[]> combinations = generateCombinations(n, 5);
for (int[] combo : combinations) {
List<QueuedPlayer> teamA = new ArrayList<>();
List<QueuedPlayer> teamB = new ArrayList<>();
boolean[] inA = new boolean[n];
for (int idx : combo) {
teamA.add(pool.get(idx));
inA[idx] = true;
}
for (int i = 0; i < n; i++) {
if (!inA[i]) teamB.add(pool.get(i));
}
if (teamB.size() != 5) continue;
// 评估此分组的质量
double score = evaluateMatch(teamA, teamB);
if (score > bestScore) {
bestScore = score;
best = new MatchResult(teamA, teamB, score);
}
}
// 如果最优匹配的评分仍低于阈值，返回null继续等待
if (best != null && bestScore > 0) {
// 从队列中移除已匹配玩家
for (QueuedPlayer p : best.teamA) queue.remove(p);
for (QueuedPlayer p : best.teamB) queue.remove(p);
return best;
}
return null;
}
/**
* 匹配质量评分函数（越高越好）
* 综合：评分均衡 + 位置覆盖 + 等待时间补偿
*/
double evaluateMatch(List<QueuedPlayer> teamA, List<QueuedPlayer> teamB) {
double ratingA = teamA.stream().mapToDouble(p -> p.rating).sum();
double ratingB = teamB.stream().mapToDouble(p -> p.rating).sum();
double ratingDiff = Math.abs(ratingA - ratingB);
// 评分均衡分数（越接近0越高）
double balanceScore = Math.max(0, 1.0 - ratingDiff / maxRatingDiff);
// 位置覆盖分数：每队是否5个位置齐全
double roleScoreA = roleCoverageScore(teamA);
double roleScoreB = roleCoverageScore(teamB);
double roleScore = (roleScoreA + roleScoreB) / 2.0;
// 等待时间补偿：等待越久越应该优先匹配
double waitScore = 0;
long now = System.currentTimeMillis();
for (QueuedPlayer p : teamA) waitScore += (now - p.queueTime) / 1000.0;
for (QueuedPlayer p : teamB) waitScore += (now - p.queueTime) / 1000.0;
waitScore = Math.min(1.0, waitScore / (10 * maxWaitTime));
// 加权综合
return balanceScore * 0.5 + roleScore * 0.3 + waitScore * 0.2;
}
/**
* 位置覆盖评分：理想情况下每队5人各一个主位置
*/
double roleCoverageScore(List<QueuedPlayer> team) {
// 简化为5个位置，每个位置由偏好该位置的玩家担任
Set<String> covered = new HashSet<>();
for (QueuedPlayer p : team) {
if (p.roles.length > 0) covered.add(p.roles[0]);
}
return covered.size() / 5.0; // [0, 1]
}
List<int[]> generateCombinations(int n, int k) {
List<int[]> result = new ArrayList<>();
int[] combo = new int[k];
generateComboHelper(n, k, 0, 0, combo, result);
return result;
}
void generateComboHelper(int n, int k, int start, int depth, int[] combo, List<int[]> result) {
if (depth == k) {
result.add(combo.clone());
return;
}
for (int i = start; i <= n - k + depth; i++) {
combo[depth] = i;
generateComboHelper(n, k, i + 1, depth + 1, combo, result);
}
}
static class MatchResult {
List<QueuedPlayer> teamA, teamB;
double qualityScore;
MatchResult(List<QueuedPlayer> a, List<QueuedPlayer> b, double s) {
teamA = a; teamB = b; qualityScore = s;
}
@Override
public String toString() {
double avgA = teamA.stream().mapToDouble(p -> p.rating).average().orElse(0);
double avgB = teamB.stream().mapToDouble(p -> p.rating).average().orElse(0);
return String.format("Match(Q=%.3f): TeamA[avg=%.0f] vs TeamB[avg=%.0f]",
qualityScore, avgA, avgB);
}
}
}
五、赛后评分更新与置信度衰减
Glicko-2要求：长期不活跃的玩家，其RD应逐渐增大（评分不确定性增加）。
/**
* 评分维护系统：赛后更新 + 不活跃衰减
*/
public class RatingMaintenance {
private final Glicko2System glicko = new Glicko2System();
private final Map<String, Glicko2System.GlickoPlayer> players = new HashMap<>();
/** 记录比赛结果并更新所有参与者评分 */
public void recordMatch(MatchResult match, int winner) {
// winner: 0=平局, 1=TeamA胜, 2=TeamB胜
List<Glicko2System.GlickoPlayer> teamAPlayers = new ArrayList<>();
List<Glicko2System.GlickoPlayer> teamBPlayers = new ArrayList<>();
for (MatchmakingSystem.QueuedPlayer qp : match.teamA) {
teamAPlayers.add(players.computeIfAbsent(qp.id,
id -> new Glicko2System.GlickoPlayer(id, qp.rating, qp.rd, 0.06)));
}
for (MatchmakingSystem.QueuedPlayer qp : match.teamB) {
teamBPlayers.add(players.computeIfAbsent(qp.id,
id -> new Glicko2System.GlickoPlayer(id, qp.rating, qp.rd, 0.06)));
}
// 将5v5简化为每位玩家 vs 对方团队平均评分
double avgA = teamAPlayers.stream().mapToDouble(p -> p.mu).average().orElse(0);
double avgB = teamBPlayers.stream().mapToDouble(p -> p.mu).average().orElse(0);
// 更新Team A玩家
for (Glicko2System.GlickoPlayer p : teamAPlayers) {
double score = (winner == 1) ? 1.0 : (winner == 0) ? 0.5 : 0.0;
// 创建一个"虚拟对手"代表对方团队平均水平
Glicko2System.GlickoPlayer virtualOpponent =
new Glicko2System.GlickoPlayer("avgB", avgB * Glicko2System.GlickoPlayer.SCALE + 1500, 50, 0.06);
glicko.updateRating(p, new Glicko2System.GlickoPlayer[]{virtualOpponent}, new double[]{score});
}
// 更新Team B玩家
for (Glicko2System.GlickoPlayer p : teamBPlayers) {
double score = (winner == 2) ? 1.0 : (winner == 0) ? 0.5 : 0.0;
Glicko2System.GlickoPlayer virtualOpponent =
new Glicko2System.GlickoPlayer("avgA", avgA * Glicko2System.GlickoPlayer.SCALE + 1500, 50, 0.06);
glicko.updateRating(p, new Glicko2System.GlickoPlayer[]{virtualOpponent}, new double[]{score});
}
}
/**
* 不活跃评分衰减：RD随时间增长
* 公式：φ_new = sqrt(φ^2 + c^2·t)，其中c为系统常数，t为未参赛周期数
*/
public void applyInactivityDecay(String playerId, int periods) {
Glicko2System.GlickoPlayer p = players.get(playerId);
if (p == null) return;
double c = 0.1; // 衰减常数
double newPhi = Math.sqrt(sq(p.phi) + sq(c) * periods);
// RD上限约束（通常不超过350）
p.phi = Math.min(newPhi, 350.0 / Glicko2System.GlickoPlayer.SCALE);
}
double sq(double x) { return x * x; }
/** 打印玩家评分状态 */
public void printPlayerRating(String playerId) {
Glicko2System.GlickoPlayer p = players.get(playerId);
if (p == null) return;
System.out.printf("Player %s: Rating=%.0f ± %.0f (σ=%.4f)%n",
playerId, p.getRating(), p.getRD(), p.sigma);
}
}
六、完整模拟与收敛验证
public class MatchmakingMain {
public static void main(String[] args) {
// 创建10位真实实力不同的玩家（仅模拟知道其"隐藏真实实力"）
double[] trueSkills = {1200, 1350, 1400, 1450, 1500, 1550, 1600, 1650, 1800, 2000};
String[] names = {"P1","P2","P3","P4","P5","P6","P7","P8","P9","P10"};
EloSystem elo = new EloSystem();
Glicko2System glicko = new Glicko2System();
EloSystem.Player[] eloPlayers = new EloSystem.Player[10];
Glicko2System.GlickoPlayer[] glickoPlayers = new Glicko2System.GlickoPlayer[10];
for (int i = 0; i < 10; i++) {
eloPlayers[i] = elo.new Player(names[i], 1500); // 统一从1500开始
glickoPlayers[i] = new Glicko2System.GlickoPlayer(names[i], 1500, 350, 0.06);
}
// 模拟1000场随机对局
Random rnd = new Random(42);
for (int game = 0; game < 1000; game++) {
int a = rnd.nextInt(10);
int b = rnd.nextInt(10);
if (a == b) continue;
// 胜负由真实实力决定（加入随机性模拟真实比赛）
double skillDiff = trueSkills[a] - trueSkills[b];
double winProb = 1.0 / (1.0 + Math.exp(-skillDiff / 200.0));
double scoreA = rnd.nextDouble() < winProb ? 1.0 : 0.0;
// Elo更新
elo.updateRating(eloPlayers[a], eloPlayers[b], scoreA);
// Glicko-2更新（批量简化：每次只更新两个玩家）
glicko.updateRating(glickoPlayers[a],
new Glicko2System.GlickoPlayer[]{glickoPlayers[b]}, new double[]{scoreA});
glicko.updateRating(glickoPlayers[b],
new Glicko2System.GlickoPlayer[]{glickoPlayers[a]}, new double[]{1.0 - scoreA});
}
// 验证收敛性：评分是否接近真实实力
System.out.println("=== Convergence Test ===");
System.out.println("Player | TrueSkill | Elo | Glicko | Glicko RD");
System.out.println("-------|-----------|--------|--------|----------");
for (int i = 0; i < 10; i++) {
System.out.printf("%-6s | %9.0f | %6.0f | %6.0f | %8.0f%n",
names[i], trueSkills[i], eloPlayers[i].rating,
glickoPlayers[i].getRating(), glickoPlayers[i].getRD());
}
// 匹配系统测试
System.out.println("\n=== Matchmaking Test ===");
MatchmakingSystem matcher = new MatchmakingSystem();
for (int i = 0; i < 10; i++) {
String[] roles = {"上单","打野","中单","ADC","辅助"};
matcher.enqueue(new MatchmakingSystem.QueuedPlayer(
names[i], eloPlayers[i].rating, 50, new String[]{roles[i % 5]}));
}
MatchmakingSystem.MatchResult match = matcher.tryMatch();
if (match != null) {
System.out.println(match);
}
}
}
预期输出：
– Elo和Glicko-2评分都向真实实力收敛
– Glicko-2的RD随对局数增加而减小（高置信度）
– 匹配系统将2000分与1200分玩家分开，中间分段混排
七、复杂度分析
| 模块 | 时间复杂度 | 说明 |
|---|---|---|
| Elo单局更新 | O(1) |
固定公式计算 |
| Glicko-2单局更新 | O(n) |
n=对手数，Illinois算法迭代 |
| 5v5匹配枚举 | O(C(20,5)) = 15504 |
实际仅约1.5万次评估，毫秒级 |
| 匹配质量评估 | O(1) |
固定公式 |
| 整体系统 | O(queuesize + matches) |
支持每秒数万次匹配请求 |
核心收获：
1. Elo = 逻辑回归：预期胜率公式本质上是对数几率模型
2. K值动态化：新手需要快速收敛，高手需要稳定评分
3. Glicko-2 RD = 置信区间：将”这个玩家有多强”升级为”我们对他的实力有多确定”
4. 匹配 = 组合优化：10人分队在组合空间中最小化目标函数
从国际象棋到英雄联盟，60年来评分算法的演进证明：好的匹配系统比好的游戏设计更重要——没有公平的对局，再精美的技能也无人问津。
