Lesson 22: Matchmaking & Ratings

⚖️ Fair or Fast?

Picture a pickup basketball court. When lots of people are there, you can wait a few minutes and get a game against players at your level. On a quiet morning, waiting for the perfect opponent means waiting forever, so you take whoever shows up. A matchmaker faces that choice every second: a strict skill rule gives fair games and long queues; a loose one gives fast games that are often one-sided.

The usual answer is a search window that widens with time. A new ticket in the queue only accepts opponents within 50 rating points. Every second it waits, it accepts 25 more, up to a limit. Busy queues produce close matches almost at once; quiet queues still produce a match eventually. Try it: each row is a player waiting in the queue, the dot is their rating, and the bar is the range of ratings they will accept.

Press Growth to compare 10, 25 and 60 points per second. Slow growth gives higher average quality and longer waits; fast growth does the opposite. A bar turns red when it hits its limit of ±400: that player will now take almost anyone.

📈 Elo Ratings

To match by skill you need a number for skill. The Elo system, designed by Arpad Elo for chess, is simple and still widely used. It has two formulas. The first predicts a result: player A's expected score against B, where a win counts 1, a draw 0.5 and a loss 0.

expected_a = 1 / (1 + 10 ** ((rating_b - rating_a) / 400))

The second corrects the ratings after the game by how surprising the result was. K is the most one game can move a rating.

change = K * (score_a - expected_a)
rating_a += change
rating_b -= change        # zero-sum: B loses exactly what A gains

This complete program prints both formulas at work:

def expected_score(rating_a, rating_b):
    """Elo's prediction of A's score against B (1 = win, 0.5 = draw, 0 = loss)."""
    return 1 / (1 + 10 ** ((rating_b - rating_a) / 400))


def update_elo(rating_a, rating_b, score_a, k=32):
    change = k * (score_a - expected_score(rating_a, rating_b))
    return rating_a + change, rating_b - change


print("gap   A's expected score")
for gap in (0, 100, 200, 400, 800):
    print(f"{gap:4}   {expected_score(1500 + gap, 1500):.3f}")

print()
for a, b, result in ((1500, 1500, 1), (1600, 1200, 1), (1200, 1600, 1), (1600, 1200, 0.5)):
    new_a, new_b = update_elo(a, b, result)
    print(f"{a} vs {b}, A scores {result}: A -> {new_a:.1f}, B -> {new_b:.1f}")

gap   A's expected score
   0   0.500
 100   0.640
 200   0.760
 400   0.909
 800   0.990

1500 vs 1500, A scores 1: A -> 1516.0, B -> 1484.0
1600 vs 1200, A scores 1: A -> 1602.9, B -> 1197.1
1200 vs 1600, A scores 1: A -> 1229.1, B -> 1570.9
1600 vs 1200, A scores 0.5: A -> 1586.9, B -> 1213.1

Read the last four lines as stories. Equal players trade 16 points (half of K). The favorite who wins as expected gains only about 3, but the underdog who pulls off the upset gains about 29. And a draw is bad news for the favorite: it was expected to score 0.909, got 0.5, and loses about 13 points. Because every game is zero-sum, the average rating of the whole player base never changes; only the order does.

Ratings start at the same number for everyone (1500 here), so a new player's rating is a guess that improves with every game. How fast it improves depends on K: a big K learns quickly but jumps around; a small K is steady but slow. FIDE, the international chess federation, uses a K of 40 for new players and 10 for its top players, for exactly that reason.

🎯 The Matchmaker: Oldest First, Both Agree

Each player in the queue has a ticket: who they are, when they joined, and a sequence number. The window is a pure function of how long the ticket has waited, in seconds:

BASE_WINDOW = 50               # rating gap a brand-new ticket accepts
WINDOW_GROWTH = 25             # extra rating points accepted per second of waiting
MAX_WINDOW = 400               # the window never grows past this


def search_window(waited):
    """How far from its own rating a ticket will accept, after waiting `waited` seconds."""
    return min(MAX_WINDOW, BASE_WINDOW + WINDOW_GROWTH * waited)

The matcher walks the queue from the oldest ticket down, and gives each one the closest opponent that fits:

@dataclass
class Ticket:
    player: SimPlayer
    joined: float                  # simulation time the ticket was created
    seq: int                       # unique and increasing: breaks ties, never collides


class Matchmaker:
    def __init__(self):
        self.queue = []                        # oldest ticket first
        self.next_seq = itertools.count(1)

    def add(self, player, now):
        self.queue.append(Ticket(player, now, next(self.next_seq)))

    def find_matches(self, now):
        """Pair tickets, oldest first. Two tickets match only if the rating gap fits
        inside BOTH search windows; among those, the closest rating wins."""
        matched = set()
        pairs = []
        for i, a in enumerate(self.queue):
            if a.seq in matched:
                continue
            window_a = search_window(now - a.joined)
            best, best_gap = None, None
            for b in self.queue[i + 1:]:
                if b.seq in matched:
                    continue
                gap = abs(a.player.rating - b.player.rating)
                if gap <= min(window_a, search_window(now - b.joined)):
                    if best is None or gap < best_gap:
                        best, best_gap = b, gap
            if best is not None:
                matched.update((a.seq, best.seq))
                pairs.append((a, best))
        self.queue = [t for t in self.queue if t.seq not in matched]
        return pairs

Three decisions in there fix bugs from the older matchmaking code this lesson replaces:

• Both windows must accept (min, not max). With max, a player who has waited a long time drags a brand-new player into a lopsided game the newcomer never agreed to. With min, the long-waiter's wide window helps only when the other player's window reaches too.
• Oldest first. Serving the longest wait first keeps anyone from being skipped forever. If you keep tickets in a heapq instead of a list, push (ticket.joined, ticket.seq, ticket) so the smallest item, the oldest ticket, pops first. The old code pushed -joined, which made the newest ticket pop first and left the longest waiters at the bottom.
• IDs from a counter, not the clock. The old code named matches and parties f"match_{int(time.time() * 1000)}", so two made in the same millisecond got the same ID. itertools.count() never repeats, and the sequence number also breaks ties in a heap, so Python never has to compare two Ticket objects.

Time here is simulation time in seconds, passed in as now. That makes the matcher easy to test (a test can jump ahead 20 seconds) and lets the simulator run faster than real time. A live server would pass time.monotonic(), which never jumps backward when the computer's clock is adjusted.

🤝 Match Quality and Balanced Teams

How good is a match? Elo already answers it: a perfect match is a coin flip. This match quality is 1.0 when the expected score is 0.5 and falls to 0.0 as the result becomes certain:

def match_quality(rating_a, rating_b):
    """1.0 for a coin flip, falling to 0.0 as the result becomes certain."""
    return 1 - abs(expected_score(rating_a, rating_b) - 0.5) * 2

A 100-point gap scores 0.72; a 400-point gap scores 0.18. Averaging it over every match gives you one number to watch while you tune the window.

For team games, the simplest approach treats each team as one player whose rating is the team's average, and gives every member the same rating change. That is a simplification (it can't tell a carried player from a carrying one), and it is where systems such as Glicko-2 and TrueSkill go further by also tracking how uncertain each rating is. It is still a good start, as long as the two teams are balanced. To split players into teams, sort them by rating and draft:

def alternate(ratings):
    """A, B, A, B, ... down the sorted list."""
    order = sorted(ratings, reverse=True)
    return order[0::2], order[1::2]


def snake_draft(ratings):
    """A, B, B, A, A, B, B, A, ...: whoever picked second picks first next round."""
    team_a, team_b = [], []
    for i, rating in enumerate(sorted(ratings, reverse=True)):
        if i % 4 in (0, 3):
            team_a.append(rating)
        else:
            team_b.append(rating)
    return team_a, team_b


players = [1800, 1700, 1600, 1500, 1400, 1300, 1200, 1100]
for name, split in (("alternate", alternate), ("snake", snake_draft)):
    a, b = split(players)
    print(f"{name:9}  A={a} sum {sum(a)}   B={b} sum {sum(b)}   gap {abs(sum(a) - sum(b))}")

alternate  A=[1800, 1600, 1400, 1200] sum 6000   B=[1700, 1500, 1300, 1100] sum 5600   gap 400
snake      A=[1800, 1500, 1400, 1100] sum 5800   B=[1700, 1600, 1300, 1200] sum 5800   gap 0

Alternating (A, B, A, B) gives team A the better player in every pair, so its advantage adds up. A snake draft (A, B, B, A, A, B, B, A) reverses the order each round, like picking teams in the schoolyard where the captain who picked second gets the next first pick. The older matchmaking code called its alternation a "snake draft"; the i % 4 in (0, 3) test is what makes it a real one. Evenly spaced ratings like these balance exactly. Real ratings usually don't: with [2100, 1500, 1480, 1450, 1400, 1390, 1380, 1000] the snake draft leaves a gap of 200 (alternating leaves 1020), so a real game might try swapping pairs of players afterward to shrink it.

⏰ Ready Checks That Time Out

Once a match is found, many games ask every player to press Accept within a few seconds, so nobody loads into a game with a player who has walked away. The older code had a timeout function, but nothing ever called it: a ready check where one player never answered simply waited forever. A timer only fires if something counts it down, so give the check an update(dt) that the server calls every tick, clicks or no clicks:

class ReadyCheck:
    """Every matched player must press Accept within `timeout` seconds."""

    def __init__(self, player_ids, timeout=10.0):
        self.waiting_for = set(player_ids)
        self.accepted = set()
        self.time_left = timeout
        self.result = None                    # None while running, then "go" or "expired"

    def accept(self, pid):
        if self.result is None and pid in self.waiting_for:
            self.waiting_for.remove(pid)
            self.accepted.add(pid)
            if not self.waiting_for:
                self.result = "go"

    def update(self, dt):
        """Call every frame. The timer runs whether or not anyone clicks."""
        if self.result is None:
            self.time_left -= dt
            if self.time_left <= 0:
                self.result = "expired"
        return self.result


# Tickets are (joined, seq, name): sorting them puts the longest wait first.
queue = [(40.0, 9, "Dee")]                    # someone who queued after the match was made
matched = [(12.0, 3, "Ada"), (15.5, 5, "Bo"), (21.0, 7, "Cy")]
accept_at = {"Ada": 1.0, "Bo": 2.5}           # Cy has gone to make a sandwich

check = ReadyCheck([name for _, _, name in matched], timeout=10.0)
t, dt = 0.0, 0.1
while check.update(dt) is None:
    t += dt
    for name, when in accept_at.items():
        if abs(t - when) < dt / 2:
            check.accept(name)
            print(f"t={t:4.1f}s  {name} accepted")
print(f"t={t:4.1f}s  ready check {check.result}; never answered: {sorted(check.waiting_for)}")

if check.result == "expired":
    back = [ticket for ticket in matched if ticket[2] in check.accepted]
    queue = sorted(queue + back)              # same tickets, same joined times: front of the line
print("queue now:", [name for _, _, name in queue])

t= 1.0s  Ada accepted
t= 2.5s  Bo accepted
t=10.0s  ready check expired; never answered: ['Cy']
queue now: ['Ada', 'Bo', 'Dee']

When the check expires, the players who did accept go back into the queue with their original tickets. Because the queue is ordered by join time, they land ahead of Dee, who queued later: nobody is punished for someone else's sandwich. The player who never answered is dropped from the queue (many games also add a short queue ban, so walking away has a cost).

🏋️ Practice Exercise: Matchmaking Simulator

"""Matchmaking Simulator: Advanced Lesson 22 practice exercise (solution).

Forty simulated players queue for 1v1 matches. Each has a hidden true skill;
everyone starts at a rating of 1500. The matchmaker pairs players whose
ratings are close, widening each ticket's search window the longer it waits.
Matches are decided by the true skills, and Elo updates the ratings.

Left: every player as a dot, true skill across, rating up. Watch the dots
settle toward the diagonal as the ratings learn the skills.
Right: the queue, oldest ticket first, with each ticket's search window.

SPACE pause   UP/DOWN simulation speed   R restart
"""
import itertools
import random
from dataclasses import dataclass

import pygame


WIDTH, HEIGHT = 900, 540
K_FACTOR = 32                  # the most rating one game can move
START_RATING = 1500
BASE_WINDOW = 50               # rating gap a brand-new ticket accepts
WINDOW_GROWTH = 25             # extra rating points accepted per second of waiting
MAX_WINDOW = 400               # the window never grows past this
MATCH_TIME = 4.0               # seconds a match lasts
PLAYER_COUNT = 40
SEED = 7
SPEEDS = [1, 5, 20, 60]        # simulated seconds per real second
MAX_STEP = 0.1                 # simulate in steps no longer than this (seconds)

BG = (17, 24, 39)
PANEL = (31, 41, 55)
TEXT = (229, 231, 235)
DIM = (148, 163, 184)
GRID = (55, 65, 81)
QUEUED = (251, 191, 36)
PLAYING = (96, 165, 250)
IDLE = (156, 163, 175)
WINDOW_BAR = (74, 222, 128)


# ------------------------------------------------------------------ the maths
def expected_score(rating_a, rating_b):
    """Elo's prediction of A's score against B: 0.5 when equal, about 0.91 at +400."""
    return 1 / (1 + 10 ** ((rating_b - rating_a) / 400))


def update_elo(rating_a, rating_b, score_a, k=K_FACTOR):
    """New (rating_a, rating_b) after one game. score_a is 1 win, 0.5 draw, 0 loss."""
    change = k * (score_a - expected_score(rating_a, rating_b))
    return rating_a + change, rating_b - change          # zero-sum: B loses what A gains


def search_window(waited):
    """How far from its own rating a ticket will accept, after waiting `waited` seconds."""
    return min(MAX_WINDOW, BASE_WINDOW + WINDOW_GROWTH * waited)


def match_quality(rating_a, rating_b):
    """1.0 for a coin flip, falling to 0.0 as the result becomes certain."""
    return 1 - abs(expected_score(rating_a, rating_b) - 0.5) * 2


# ------------------------------------------------------------------ the queue
@dataclass
class SimPlayer:
    pid: int
    skill: float                   # hidden: only the simulation knows it
    rating: float = START_RATING
    state: str = "idle"            # idle, queued or playing
    rest: float = 0.0              # seconds until an idle player queues again
    games: int = 0


@dataclass
class Ticket:
    player: SimPlayer
    joined: float                  # simulation time the ticket was created
    seq: int                       # unique and increasing: breaks ties, never collides


class Matchmaker:
    def __init__(self):
        self.queue = []                        # oldest ticket first
        self.next_seq = itertools.count(1)

    def add(self, player, now):
        self.queue.append(Ticket(player, now, next(self.next_seq)))

    def find_matches(self, now):
        """Pair tickets, oldest first. Two tickets match only if the rating gap fits
        inside BOTH search windows; among those, the closest rating wins."""
        matched = set()
        pairs = []
        for i, a in enumerate(self.queue):
            if a.seq in matched:
                continue
            window_a = search_window(now - a.joined)
            best, best_gap = None, None
            for b in self.queue[i + 1:]:
                if b.seq in matched:
                    continue
                gap = abs(a.player.rating - b.player.rating)
                if gap <= min(window_a, search_window(now - b.joined)):
                    if best is None or gap < best_gap:
                        best, best_gap = b, gap
            if best is not None:
                matched.update((a.seq, best.seq))
                pairs.append((a, best))
        self.queue = [t for t in self.queue if t.seq not in matched]
        return pairs


# ------------------------------------------------------------------ the simulation
class Simulation:
    def __init__(self, seed=SEED, count=PLAYER_COUNT):
        self.rng = random.Random(seed)
        self.players = [SimPlayer(i + 1, self.rng.uniform(900, 2100), rest=self.rng.uniform(0, 3))
                        for i in range(count)]
        self.matchmaker = Matchmaker()
        self.now = 0.0
        self.live = []                          # (player a, player b, finish time)
        self.matches = 0
        self.quality_total = 0.0
        self.wait_total = 0.0
        self.start_error = self.rating_error()

    def rating_error(self):
        return sum(abs(p.rating - p.skill) for p in self.players) / len(self.players)

    def step(self, dt):
        self.now += dt
        for p in self.players:
            if p.state == "idle":
                p.rest -= dt
                if p.rest <= 0:
                    p.state = "queued"
                    self.matchmaker.add(p, self.now)
        still_live = []
        for a, b, finish in self.live:
            if self.now < finish:
                still_live.append((a, b, finish))
                continue
            a_wins = self.rng.random() < expected_score(a.skill, b.skill)   # true skill decides
            a.rating, b.rating = update_elo(a.rating, b.rating, 1 if a_wins else 0)
            for p in (a, b):
                p.state, p.rest, p.games = "idle", self.rng.uniform(1, 4), p.games + 1
        self.live = still_live
        for ta, tb in self.matchmaker.find_matches(self.now):
            self.matches += 1
            self.quality_total += match_quality(ta.player.rating, tb.player.rating)
            self.wait_total += (self.now - ta.joined) + (self.now - tb.joined)
            ta.player.state = tb.player.state = "playing"
            self.live.append((ta.player, tb.player, self.now + MATCH_TIME))

    def advance(self, seconds):
        """Simulate `seconds`, in steps of at most MAX_STEP."""
        while seconds > 1e-9:
            dt = min(MAX_STEP, seconds)
            self.step(dt)
            seconds -= dt


# ------------------------------------------------------------------ drawing
PLOT = pygame.Rect(50, 36, 430, 430)
LOW, HIGH = 800, 2200


def to_plot(skill, rating):
    x = PLOT.left + (skill - LOW) / (HIGH - LOW) * PLOT.width
    y = PLOT.bottom - (rating - LOW) / (HIGH - LOW) * PLOT.height
    return x, max(PLOT.top, min(PLOT.bottom, y))


def draw(screen, fonts, sim, speed, paused):
    font, small = fonts
    screen.fill(BG)
    pygame.draw.rect(screen, PANEL, PLOT)
    for value in range(1000, 2200, 200):
        x, _ = to_plot(value, LOW)
        _, y = to_plot(LOW, value)
        pygame.draw.line(screen, GRID, (x, PLOT.top), (x, PLOT.bottom))
        pygame.draw.line(screen, GRID, (PLOT.left, y), (PLOT.right, y))
        if value % 400 == 200:                                             # 1000, 1400, 1800
            screen.blit(small.render(str(value), True, DIM), (x - 14, PLOT.bottom + 26))
            screen.blit(small.render(str(value), True, DIM), (PLOT.left - 38, y - 7))
    pygame.draw.line(screen, DIM, PLOT.bottomleft, PLOT.topright, 2)      # rating == skill
    colors = {"idle": IDLE, "queued": QUEUED, "playing": PLAYING}
    for p in sim.players:
        pygame.draw.circle(screen, colors[p.state], to_plot(p.skill, p.rating), 5)
    screen.blit(small.render("true skill (hidden) ->", True, DIM), (PLOT.left, PLOT.bottom + 8))
    screen.blit(small.render("rating", True, DIM), (PLOT.left, PLOT.top - 22))

    x0 = 520
    games = sim.matches
    lines = [
        f"time {sim.now:6.1f} s   speed x{speed}{'   PAUSED' if paused else ''}",
        f"matches {games}   in queue {len(sim.matchmaker.queue)}",
        f"avg quality {sim.quality_total / games if games else 0:.2f}   "
        f"avg wait {sim.wait_total / (2 * games) if games else 0:.1f} s",
        f"rating error {sim.rating_error():.0f} (started {sim.start_error:.0f})",
    ]
    for i, line in enumerate(lines):
        screen.blit(font.render(line, True, TEXT), (x0, 40 + i * 26))
    screen.blit(small.render("queue (oldest first): rating, wait, window", True, DIM), (x0, 160))
    for i, t in enumerate(sim.matchmaker.queue[:12]):
        y = 186 + i * 26
        waited = sim.now - t.joined
        window = search_window(waited)
        pygame.draw.rect(screen, WINDOW_BAR, (x0 + 170, y + 4, window / MAX_WINDOW * 190, 12))
        label = f"P{t.player.pid:02d} {t.player.rating:5.0f} {waited:4.1f}s"
        screen.blit(small.render(label, True, TEXT), (x0, y))
    screen.blit(small.render("SPACE pause   UP/DOWN speed   R restart", True, DIM), (x0, HEIGHT - 34))


def main():
    pygame.init()
    screen = pygame.display.set_mode((WIDTH, HEIGHT))
    pygame.display.set_caption("Matchmaking Simulator")
    clock = pygame.time.Clock()
    fonts = (pygame.font.Font(None, 26), pygame.font.Font(None, 22))
    sim = Simulation()
    speed_index, paused = 0, False

    running = True
    while running:
        dt = clock.tick(60) / 1000
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                running = False
            elif event.type == pygame.KEYDOWN:
                if event.key == pygame.K_SPACE:
                    paused = not paused
                elif event.key == pygame.K_UP:
                    speed_index = min(len(SPEEDS) - 1, speed_index + 1)
                elif event.key == pygame.K_DOWN:
                    speed_index = max(0, speed_index - 1)
                elif event.key == pygame.K_r:
                    sim = Simulation()
        if not paused:
            sim.advance(dt * SPEEDS[speed_index])
        draw(screen, fonts, sim, SPEEDS[speed_index], paused)
        pygame.display.flip()

    a, b = update_elo(1500, 1500, 1)
    print(f"Elo check: 1500 beats 1500 -> {a:.2f} / {b:.2f}")
    a, b = update_elo(1200, 1600, 1)
    print(f"Elo check: 1200 beats 1600 -> {a:.2f} / {b:.2f}")
    print(f"Matches played: {sim.matches} in {sim.now:.0f} simulated seconds")
    print(f"Rating error: started {sim.start_error:.0f}, now {sim.rating_error():.0f}")
    pygame.quit()


if __name__ == "__main__":
    main()

📓 Learning Journal

📝 Summary

Every matchmaker balances fairness against waiting. Elo gives each player a number whose differences predict results, and nudges it after every game by how surprising the result was. A search window that starts narrow and widens with waiting lets busy queues make close matches and quiet queues still make some match. Serving the oldest ticket first, requiring both windows to agree, and taking IDs from a counter keep the queue fair and bug-free. A real snake draft balances teams better than alternation, and a ready check only times out if something counts it down every tick.

🔭 Looking Ahead

That completes the networking unit, from sockets to a working lobby and matchmaker. Next, in Racing Physics, you start the genre studio with a top-down racer whose car steers with a simple vehicle model and loses grip in believable ways.

❓ Common Questions

🎯 Quick Quiz

🌟 Going Further

• Provisional ratings. Give each simulated player a larger K for their first ten games and 16 after that. Does the rating error fall faster and end lower?
• Busy and quiet hours. Change how long idle players rest, so the queue is sometimes crowded and sometimes nearly empty, and log average wait and quality for each.
• Two-versus-two. Pull four tickets at a time, split them with snake_draft(), and update every player with the team-average rule. Compare the rating error with the one-on-one version.
• Hook it to your lobby. Replace the Lobby Server & Client lesson's "fullest room" quick match with this matcher: give each Client a rating, run find_matches(time.monotonic()) on a timer thread under the lobby lock, and put each pair in a new room with a ready check.
• Read more: Elo rating system and Mark Glickman's Glicko-2 paper; Python docs for heapq and itertools.count.