312 lines
14 KiB
TypeScript
312 lines
14 KiB
TypeScript
/**
|
||
* UCL Bracket Simulator
|
||
*
|
||
* Monte Carlo simulation of the UEFA Champions League 16-team knockout bracket.
|
||
*
|
||
* Algorithm:
|
||
* 1. Load the bracket scoring event and all playoff matches from DB
|
||
* 2. Load each team's resolved Elo (the input policy already blended any raw
|
||
* Elo and futures odds into a single sourceElo before the run)
|
||
* 3. Per-match win probability = eloWinProbabilityWithParity(eloA, eloB, parityFactor).
|
||
* Odds are NOT blended in per-match here — that would double-count the futures
|
||
* signal already baked into the Elo.
|
||
* 5. Simulate `iterations` tournaments, respecting already-completed matches
|
||
* 6. Track integer placement counts per tier (champion / finalist / SF loser / QF loser).
|
||
* At conversion, exact denominators guarantee column sums of 1.0 by construction:
|
||
* - probFirst = champion / N
|
||
* - probSecond = finalist / N
|
||
* - probThird/probFourth = sfLoserCount / (2*N) — 2 SF losers per sim
|
||
* - probFifth–probEighth = qfLoserCount / (4*N) — 4 QF losers per sim
|
||
* - R16 losers → all 0 (score 0 points per scoring rules)
|
||
*
|
||
* Bracket path follows the same matchNumber pairing used by advanceWinnerTemplate():
|
||
* nextMatchNumber = Math.ceil(matchNumber / 2)
|
||
* i.e. R16 match 1 + R16 match 2 → QF match 1, R16 match 3 + R16 match 4 → QF match 2, …
|
||
*
|
||
* In-progress handling:
|
||
* - Completed matches (isComplete + winnerId + loserId set) use the actual result in
|
||
* every simulation — giving eliminated teams an exact EV equal to their scored points.
|
||
* - Incomplete matches are simulated using the blended probability.
|
||
*
|
||
* Notes:
|
||
* - Requires futures odds in sourceOdds (American format) to be imported first.
|
||
* - Falls back to a 1500 Elo (coin flip vs. equals) when no Elo is resolved.
|
||
* - `parityFactor` (season config) tunes per-match variance; default 400.
|
||
*/
|
||
|
||
import { database } from "~/database/context";
|
||
import { eq, and } from "drizzle-orm";
|
||
import * as schema from "~/database/schema";
|
||
import { eloWinProbabilityWithParity } from "~/services/probability-engine";
|
||
import type { Simulator, SimulationResult } from "./types";
|
||
import { positiveConfigNumber } from "./config-access";
|
||
|
||
// ─── Simulation parameters (defaults; overridable via season config) ───────────
|
||
|
||
const DEFAULT_NUM_SIMULATIONS = 50000;
|
||
|
||
/** Elo parity factor. Defaults to 400 (standard formula). */
|
||
const DEFAULT_PARITY_FACTOR = 400;
|
||
|
||
// ─── Odds helper ──────────────────────────────────────────────────────────────
|
||
|
||
/** Convert American odds to implied probability (with vig). Exported for testing. */
|
||
export function americanToImpliedProb(odds: number): number {
|
||
if (odds > 0) return 100 / (odds + 100);
|
||
return Math.abs(odds) / (Math.abs(odds) + 100);
|
||
}
|
||
|
||
// ─── Simulator ────────────────────────────────────────────────────────────────
|
||
|
||
export class UCLSimulator implements Simulator {
|
||
async simulate(sportsSeasonId: string, config: Record<string, unknown> = {}): Promise<SimulationResult[]> {
|
||
const db = database();
|
||
const parityFactor = positiveConfigNumber(config, "parityFactor", DEFAULT_PARITY_FACTOR);
|
||
const numSimulations = Math.round(positiveConfigNumber(config, "iterations", DEFAULT_NUM_SIMULATIONS));
|
||
|
||
// 1. Find the bracket scoring event for this sports season.
|
||
// UCL has exactly one playoff_game event per season.
|
||
const bracketEvent = await db.query.scoringEvents.findFirst({
|
||
where: and(
|
||
eq(schema.scoringEvents.sportsSeasonId, sportsSeasonId),
|
||
eq(schema.scoringEvents.eventType, "playoff_game")
|
||
),
|
||
});
|
||
|
||
if (!bracketEvent) {
|
||
throw new Error(
|
||
`No bracket event found for sports season ${sportsSeasonId}. ` +
|
||
`Create a playoff_game scoring event and set up the bracket first.`
|
||
);
|
||
}
|
||
|
||
// 2. Load all playoff matches for this bracket event.
|
||
const allMatches = await db.query.playoffMatches.findMany({
|
||
where: eq(schema.playoffMatches.scoringEventId, bracketEvent.id),
|
||
orderBy: (m, { asc }) => [asc(m.matchNumber)],
|
||
});
|
||
|
||
if (allMatches.length === 0) {
|
||
throw new Error(
|
||
`No playoff matches found for the bracket event. ` +
|
||
`Generate the bracket from the admin panel first.`
|
||
);
|
||
}
|
||
|
||
// 3. Group matches by round, ordered by number of matches descending.
|
||
// Round of 16 (8) → Quarterfinals (4) → Semifinals (2) → Finals (1)
|
||
const byRound = new Map<string, typeof allMatches>();
|
||
for (const m of allMatches) {
|
||
if (!byRound.has(m.round)) byRound.set(m.round, []);
|
||
byRound.get(m.round)?.push(m);
|
||
}
|
||
|
||
const sortedRoundMatches = [...byRound.values()]
|
||
.toSorted((a, b) => b.length - a.length)
|
||
.map((matches) => matches.sort((a, b) => a.matchNumber - b.matchNumber));
|
||
|
||
if (sortedRoundMatches.length < 4) {
|
||
throw new Error(
|
||
`Expected 4 rounds (R16, Quarterfinals, Semifinals, Finals), ` +
|
||
`found ${sortedRoundMatches.length}. Check the bracket structure.`
|
||
);
|
||
}
|
||
|
||
const r16Matches = sortedRoundMatches[0]; // 8 matches
|
||
const qfMatches = sortedRoundMatches[1]; // 4 matches
|
||
const sfMatches = sortedRoundMatches[2]; // 2 matches
|
||
const finalMatches = sortedRoundMatches[3]; // 1 match
|
||
|
||
if (r16Matches.length !== 8) {
|
||
throw new Error(
|
||
`Expected 8 Round of 16 matches, found ${r16Matches.length}. ` +
|
||
`This simulator only supports the standard UCL 16-team format.`
|
||
);
|
||
}
|
||
|
||
// Validate all R16 matches have participants (the draw must be entered).
|
||
for (const m of r16Matches) {
|
||
if (!m.participant1Id || !m.participant2Id) {
|
||
throw new Error(
|
||
`Round of 16 match ${m.matchNumber} is missing participants. ` +
|
||
`Assign all 16 teams to the bracket before running simulation.`
|
||
);
|
||
}
|
||
}
|
||
|
||
// 4. Collect all 16 participant IDs from the R16 draw (order matters for pairings).
|
||
// r16Matches is sorted by matchNumber, so participantIds[0..1] = match 1, [2..3] = match 2, …
|
||
const participantIds: string[] = [];
|
||
for (const m of r16Matches) {
|
||
participantIds.push(m.participant1Id ?? "", m.participant2Id ?? "");
|
||
}
|
||
const participantSet = new Set(participantIds);
|
||
|
||
// 5. Load the resolved single Elo (input policy already blended any raw Elo
|
||
// and futures odds into sourceElo before the run).
|
||
const evRows = await db
|
||
.select({
|
||
participantId: schema.seasonParticipantExpectedValues.participantId,
|
||
sourceElo: schema.seasonParticipantExpectedValues.sourceElo,
|
||
})
|
||
.from(schema.seasonParticipantExpectedValues)
|
||
.where(eq(schema.seasonParticipantExpectedValues.sportsSeasonId, sportsSeasonId));
|
||
|
||
// 6. Build the Elo map; teams without a resolved Elo fall back to 1500.
|
||
const eloMap = new Map<string, number>(participantIds.map((id) => [id, 1500]));
|
||
for (const r of evRows) {
|
||
if (r.sourceElo !== null && r.sourceElo !== undefined && participantSet.has(r.participantId)) {
|
||
eloMap.set(r.participantId, r.sourceElo);
|
||
}
|
||
}
|
||
|
||
// 7. Build per-round lookup maps keyed by matchNumber for O(1) access in the hot loop.
|
||
const r16ByNum = new Map(r16Matches.map((m) => [m.matchNumber, m]));
|
||
const qfByNum = new Map(qfMatches.map((m) => [m.matchNumber, m]));
|
||
const sfByNum = new Map(sfMatches.map((m) => [m.matchNumber, m]));
|
||
const finalMatch = finalMatches[0];
|
||
|
||
// ─── Helpers ──────────────────────────────────────────────────────────────
|
||
|
||
/** Pure-Elo win probability for p1 vs p2 (single resolved Elo per team). */
|
||
const blendedWinProb = (p1: string, p2: string): number => {
|
||
const elo1 = eloMap.get(p1) ?? 1500;
|
||
const elo2 = eloMap.get(p2) ?? 1500;
|
||
return eloWinProbabilityWithParity(elo1, elo2, parityFactor);
|
||
};
|
||
|
||
const simMatch = (p1: string, p2: string): { winner: string; loser: string } => {
|
||
const w = Math.random() < blendedWinProb(p1, p2) ? p1 : p2;
|
||
return { winner: w, loser: w === p1 ? p2 : p1 };
|
||
};
|
||
|
||
// 9. Integer placement counts per tier.
|
||
// Using separate integer maps avoids fractional accumulation error (e.g. += 0.25 × 50k).
|
||
// R16 losers are never counted → all probs stay 0 → EV = 0.
|
||
const championCounts = new Map<string, number>(participantIds.map((id) => [id, 0]));
|
||
const finalistCounts = new Map<string, number>(participantIds.map((id) => [id, 0]));
|
||
const sfLoserCounts = new Map<string, number>(participantIds.map((id) => [id, 0]));
|
||
const qfLoserCounts = new Map<string, number>(participantIds.map((id) => [id, 0]));
|
||
|
||
// 10. Run Monte Carlo simulations.
|
||
for (let s = 0; s < numSimulations; s++) {
|
||
// ── Round of 16 ──────────────────────────────────────────────────────
|
||
// R16 losers: no count added (0 points per scoring rules)
|
||
const r16Winners: string[] = [];
|
||
for (let i = 1; i <= 8; i++) {
|
||
const m = r16ByNum.get(i);
|
||
if (!m) continue;
|
||
if (m.isComplete && m.winnerId) {
|
||
r16Winners.push(m.winnerId);
|
||
} else {
|
||
const { winner } = simMatch(m.participant1Id ?? "", m.participant2Id ?? "");
|
||
r16Winners.push(winner);
|
||
}
|
||
}
|
||
|
||
// ── Quarterfinals ─────────────────────────────────────────────────────
|
||
// Bracket path: QF match N gets winner of R16 match (2N-1) and (2N).
|
||
// r16Winners is 0-indexed: [0,1] = R16 matches 1,2 → QF match 1, etc.
|
||
const qfWinners: string[] = [];
|
||
for (let i = 1; i <= 4; i++) {
|
||
const dbMatch = qfByNum.get(i);
|
||
let winner: string;
|
||
let loser: string;
|
||
|
||
if (dbMatch?.isComplete && dbMatch.winnerId && dbMatch.loserId) {
|
||
winner = dbMatch.winnerId;
|
||
loser = dbMatch.loserId;
|
||
} else {
|
||
const p1 = r16Winners[(i - 1) * 2];
|
||
const p2 = r16Winners[(i - 1) * 2 + 1];
|
||
({ winner, loser } = simMatch(p1, p2));
|
||
}
|
||
|
||
qfWinners.push(winner);
|
||
qfLoserCounts.set(loser, (qfLoserCounts.get(loser) ?? 0) + 1);
|
||
}
|
||
|
||
// ── Semifinals ───────────────────────────────────────────────────────
|
||
// SF match N gets winner of QF match (2N-1) and (2N).
|
||
const sfWinners: string[] = [];
|
||
for (let i = 1; i <= 2; i++) {
|
||
const dbMatch = sfByNum.get(i);
|
||
let winner: string;
|
||
let loser: string;
|
||
|
||
if (dbMatch?.isComplete && dbMatch.winnerId && dbMatch.loserId) {
|
||
winner = dbMatch.winnerId;
|
||
loser = dbMatch.loserId;
|
||
} else {
|
||
const p1 = qfWinners[(i - 1) * 2];
|
||
const p2 = qfWinners[(i - 1) * 2 + 1];
|
||
({ winner, loser } = simMatch(p1, p2));
|
||
}
|
||
|
||
sfWinners.push(winner);
|
||
sfLoserCounts.set(loser, (sfLoserCounts.get(loser) ?? 0) + 1);
|
||
}
|
||
|
||
// ── Final ─────────────────────────────────────────────────────────────
|
||
let champion: string;
|
||
let finalist: string;
|
||
|
||
if (finalMatch?.isComplete && finalMatch.winnerId && finalMatch.loserId) {
|
||
champion = finalMatch.winnerId;
|
||
finalist = finalMatch.loserId;
|
||
} else {
|
||
({ winner: champion, loser: finalist } = simMatch(sfWinners[0], sfWinners[1]));
|
||
}
|
||
|
||
championCounts.set(champion, (championCounts.get(champion) ?? 0) + 1);
|
||
finalistCounts.set(finalist, (finalistCounts.get(finalist) ?? 0) + 1);
|
||
}
|
||
|
||
// 11. Convert counts to probability distributions.
|
||
// Exact denominators guarantee each paired column group sums to 1.0 by construction:
|
||
// probFirst/Second → N total (1 per sim)
|
||
// probThird/Fourth → sfLoserCounts / (2*N) — 2 SF losers per sim
|
||
// probFifth–Eighth → qfLoserCounts / (4*N) — 4 QF losers per sim
|
||
const N = numSimulations;
|
||
const results: SimulationResult[] = participantIds.map((participantId) => {
|
||
const c = championCounts.get(participantId) ?? 0;
|
||
const f = finalistCounts.get(participantId) ?? 0;
|
||
const sf = sfLoserCounts.get(participantId) ?? 0;
|
||
const qf = qfLoserCounts.get(participantId) ?? 0;
|
||
return {
|
||
participantId,
|
||
probabilities: {
|
||
probFirst: c / N,
|
||
probSecond: f / N,
|
||
probThird: sf / (2 * N),
|
||
probFourth: sf / (2 * N),
|
||
probFifth: qf / (4 * N),
|
||
probSixth: qf / (4 * N),
|
||
probSeventh: qf / (4 * N),
|
||
probEighth: qf / (4 * N),
|
||
},
|
||
source: "ucl_bracket_monte_carlo",
|
||
};
|
||
});
|
||
|
||
// 12. Per-position normalization — belt-and-suspenders safety net for floating-point
|
||
// division residuals. Columns are already near-exactly 1.0 after step 11, but this
|
||
// guarantees the invariant before probabilities are persisted.
|
||
const positionKeys: Array<keyof typeof results[0]["probabilities"]> = [
|
||
"probFirst", "probSecond", "probThird", "probFourth",
|
||
"probFifth", "probSixth", "probSeventh", "probEighth",
|
||
];
|
||
for (const key of positionKeys) {
|
||
const colSum = results.reduce((s, r) => s + r.probabilities[key], 0);
|
||
const residual = 1.0 - colSum;
|
||
if (residual !== 0) {
|
||
const maxResult = results.reduce((best, r) =>
|
||
r.probabilities[key] > best.probabilities[key] ? r : best
|
||
);
|
||
maxResult.probabilities[key] += residual;
|
||
}
|
||
}
|
||
|
||
return results;
|
||
}
|
||
}
|