algo-rank-trueskill
用 TrueSkill 替團隊與多人對戰的玩家評分
中文翻譯
---
name: "algo-rank-trueskill"
description: "實作 TrueSkill 評分系統，用於多人與團隊的競技排名。當使用者需要替團隊遊戲的玩家評分、處理多人（非 1 對 1）對戰、或建立帶有不確定性追蹤的配對系統時使用，即使他們說的是「團隊評分系統」、「多人排名」或「配對評分」也一樣。"
metadata:
category: "WP-44 排名演算法"
tags: ["ranking", "trueskill", "matchmaking", "bayesian-rating"]
---
# TrueSkill 評分系統
## 概述
TrueSkill（Microsoft Research）把每個玩家的實力建模成高斯分布 N(μ, σ²)，μ 是估計的實力，σ 是不確定性。支援團隊和多人對戰（不只 1 對 1）。保守評分 = μ - 3σ。玩的場數越多，不確定性越低。用訊息傳遞（message passing）做貝氏推論。
## 何時使用
**觸發條件：**
- 要替團隊制或多人（3 位以上參與者）遊戲的玩家評分
- 要建立能平衡對戰品質的配對系統
- 除了實力評分，還需要不確定性的估計
**何時不要用：**
- 單純的 1 對 1 排名、不需要不確定性時（Elo 比較簡單）
- 非競技性的排名（產品評分，用 Wilson Score）
## 演算法
```
鐵律：實力評分有「兩個」成分，平均值「和」不確定性
TrueSkill 把實力表示成 N(μ, σ²)。新玩家的 σ 很高（不確定）。
打過很多場之後，σ 縮小（有信心）。保守評分 μ - 3σ 能確保玩家
是依照「很可能達到的最低實力」排名，而不是估計的平均值。
絕對不要只用 μ 來排名。
```
### 階段 1：輸入驗證
初始化：μ₀ = 25、σ₀ = 25/3（預設值）。蒐集比賽結果，包含隊伍組成和名次順序。
**關卡：** 比賽結果有效、隊伍組成已定義。
### 階段 2：核心演算法
1. 每場比賽，從各隊的實力分布算出預期結果
2. 比較實際結果和預期結果
3. 用貝氏更新每個玩家的 (μ, σ)：
- μ 往表現的方向移動（贏家上升，輸家下降）
- σ 下降（看過結果之後不確定性變小）
- 更新幅度和 σ 成正比（不確定的玩家變動更大）
4. 保守排名 = μ - 3σ
### 階段 3：驗證
檢查：活躍玩家的 σ 隨時間下降。依保守評分排在前面的玩家，贏的比預期多。對戰品質指標（平手機率）合理。
**關卡：** 評分系統產出符合直覺的排名、σ 收斂。
### 階段 4：輸出
回傳玩家評分，並附上不確定性的界線。
## 輸出格式
```json
{
"ratings": [{"player": "P1", "mu": 32.5, "sigma": 2.1, "conservative": 26.2, "games_played": 50}],
"metadata": {"initial_mu": 25, "initial_sigma": 8.33, "beta": 4.17, "tau": 0.083}
}
```
## 範例
### 輸入輸出範例
**輸入：** 隊伍 [A(25,8.3), B(25,8.3)] 打敗隊伍 [C(25,8.3), D(25,8.3)]
**預期：** A、B 的 μ 上升約 2-3 分，σ 下降約 0.5。C、D 的 μ 下降，σ 下降。保守評分隨之調整。
### 邊界情況
| 輸入 | 預期 | 原因 |
|-------|----------|-----|
| 新手對老手 | 新手的 μ 變動更大 | σ 較高 = 不確定性較大 = 更新幅度較大 |
| 1 對 1 對戰 | 退化成類似 Elo 的行為 | TrueSkill 在 1 對 1 時會簡化成單純的情況 |
| 混戰（8 位玩家） | 所有配對都會比較 | 原生支援多人，Elo 沒有 |
## 常見陷阱
- **計算成本**：因子圖（factor graph）上的訊息傳遞比 Elo 昂貴。玩家數達百萬時，要用近似法（EP 截斷）。
- **團隊實力的彙總**：TrueSkill 把個人的高斯分布加總成團隊實力。這假設彼此獨立，所以有相關性的玩家實力（默契好的固定隊伍）會建模不足。
- **動態實力**：σ 只會下降。如果玩家的實力真的有變（進步或退步），要每個時間區段加上一個小的漂移項 τ，讓 σ 慢慢回升。
- **部分參與**：玩家中途加入或提早離開時，他的貢獻不明確。需要部分參與權重的延伸做法。
- **專利狀態**：TrueSkill 是 Microsoft 的專利（2024 年到期）。TrueSkill 2 增加了更多功能，但要確認授權。
## 參考資料
- TrueSkill 因子圖的推導，見 `references/factor-graph.md`
- 配對品質指標，見 `references/matchmaking.md`英文原文
---
name: "algo-rank-trueskill"
description: "Implement TrueSkill rating system for multiplayer and team-based competitive ranking. Use this skill when the user needs to rate players in team games, handle multiplayer (non-1v1) matchups, or build a matchmaking system with uncertainty tracking — even if they say 'team rating system', 'multiplayer ranking', or 'matchmaking rating'."
metadata:
category: "WP-44 排名演算法"
tags: ["ranking", "trueskill", "matchmaking", "bayesian-rating"]
---
# TrueSkill Rating System
## Overview
TrueSkill (Microsoft Research) models each player's skill as a Gaussian distribution N(μ, σ²) where μ is estimated skill and σ is uncertainty. Supports teams and multiplayer (not just 1v1). Conservative rating = μ - 3σ. Uncertainty decreases with more games. Uses Bayesian inference via message passing.
## When to Use
**Trigger conditions:**
- Rating players in team-based or multiplayer (3+ participant) games
- Building matchmaking systems that balance match quality
- When you need uncertainty estimates alongside skill ratings
**When NOT to use:**
- For simple 1v1 ranking with no uncertainty (Elo is simpler)
- For non-competitive ranking (product ratings — use Wilson Score)
## Algorithm
```
IRON LAW: Skill Rating Has TWO Components — Mean AND Uncertainty
TrueSkill represents skill as N(μ, σ²). New players have high σ
(uncertain). After many games, σ shrinks (confident). The conservative
rating μ - 3σ ensures players are ranked by their LIKELY MINIMUM
skill, not their estimated average. Never use μ alone for ranking.
```
### Phase 1: Input Validation
Initialize: μ₀ = 25, σ₀ = 25/3 (default). Collect match results with team compositions and finishing order.
**Gate:** Valid match results, team compositions defined.
### Phase 2: Core Algorithm
1. For each match, compute expected outcome from team skill distributions
2. Compare actual vs expected outcome
3. Update each player's (μ, σ) using Bayesian update:
- μ shifts toward performance (up for winners, down for losers)
- σ decreases (less uncertain after observing outcome)
- Amount of update is proportional to σ (uncertain players change more)
4. Conservative rank = μ - 3σ
### Phase 3: Verification
Check: σ decreases over time for active players. Top-ranked players by conservative rating win more than expected. Match quality metric (draw probability) is reasonable.
**Gate:** Rating system produces intuitive rankings, σ converges.
### Phase 4: Output
Return player ratings with uncertainty bounds.
## Output Format
```json
{
"ratings": [{"player": "P1", "mu": 32.5, "sigma": 2.1, "conservative": 26.2, "games_played": 50}],
"metadata": {"initial_mu": 25, "initial_sigma": 8.33, "beta": 4.17, "tau": 0.083}
}
```
## Examples
### Sample I/O
**Input:** Team [A(25,8.3), B(25,8.3)] beats Team [C(25,8.3), D(25,8.3)]
**Expected:** A,B μ increases ~2-3 pts, σ decreases ~0.5. C,D μ decreases, σ decreases. Conservative ratings adjust.
### Edge Cases
| Input | Expected | Why |
|-------|----------|-----|
| New vs veteran player | New player μ changes more | Higher σ = more uncertainty = larger updates |
| 1v1 match | Degenerates to Elo-like behavior | TrueSkill reduces to simple case for 1v1 |
| Free-for-all (8 players) | All pairs compared | Multiplayer native support, unlike Elo |
## Gotchas
- **Computational cost**: Message passing in factor graphs is more expensive than Elo. For millions of players, use approximations (EP truncation).
- **Team skill aggregation**: TrueSkill sums individual Gaussians for team skill. This assumes independence — correlated player skills (practiced teams) are undermodeled.
- **Dynamic skill**: σ only decreases. If a player's skill genuinely changes (improvement or decline), add a small drift term τ per time period to increase σ gradually.
- **Partial play**: If a player joins mid-game or leaves early, their contribution is ambiguous. Need partial-play weight extension.
- **Patent status**: TrueSkill was patented by Microsoft (expired 2024). TrueSkill 2 adds more features but check licensing.
## References
- For TrueSkill factor graph derivation, see `references/factor-graph.md`
- For matchmaking quality metrics, see `references/matchmaking.md`