Skip to main content
Version: 2.0.0

Skill-based matchmaking with OpenSkill

Prerequisites

You need a module and a client connected to it. If you don't have them yet, follow the quickstart for your language first. This guide builds on Build a matchmaking queue, so read that one first.

In this guide, you'll put players of similar skill in the same match, and update each player's skill after every match. Skill is measured with OpenSkill, an open-source rating system that, like TrueSkill, rates players in teams as well as one-on-one. Matches have two teams, and a single constant switches between 1v1 and 2v2. You'll use a schedule table to look for matches every second, allowing a wider skill gap the longer players wait.

How it works​

  • A public player_rating table holds each player's rating: mu, their estimated skill, and sigma, how uncertain that estimate is. New players start at a mu of 25 and a sigma of 8.33.
  • A join_queue reducer adds the caller to the queue with their current mu.
  • A match_players reducer runs every second. It sorts the waiting players by mu, and creates a match from any group of neighbours whose skill gap is small enough. The allowed gap grows with time spent waiting, so nobody waits forever.
  • Each match has two teams. Players are dealt to the teams so that both get a similar total skill.
  • A finish_match function, which your game logic calls when a match ends, updates the rating of every player in it.

Install OpenSkill​

Add the openskill package to your module:

npm install openskill

Define the tables​

Start from the tables of the matchmaking queue guide, and make three changes:

  • queue_entry also stores the player's mu, so match_players can sort the queue without looking up every rating.
  • match_player has a team column, 0 or 1.
  • A new player_rating table holds every player's rating. It's public, so anyone can see anyone's rating.

Then add matchmaking_timer, the schedule table that calls match_players.

import { ScheduleAt } from 'spacetimedb';
import { schema, table, t, SenderError, type InferSchema, type ReducerCtx } from 'spacetimedb/server';
import { rate, rating } from 'openskill';

// Players on each team: 1 for 1v1 matches, 2 for 2v2, and so on.
const TEAM_SIZE = 2;
const MATCH_SIZE = 2 * TEAM_SIZE;

// The largest skill gap allowed in a match, and how much it grows
// for each second the longest-waiting player has waited.
const STARTING_GAP = 2;
const GAP_GROWTH_PER_SECOND = 0.2;

const playerRating = table(
  { name: 'player_rating', public: true },
  {
    identity: t.identity().primaryKey(),
    mu: t.f64(),
    sigma: t.f64(),
  }
);

const queueEntry = table(
  { name: 'queue_entry' },
  {
    identity: t.identity().primaryKey(),
    joinedAt: t.timestamp(),
    mu: t.f64(),
  }
);

const gameMatch = table(
  { name: 'game_match' },
  {
    id: t.u64().primaryKey().autoInc(),
    createdAt: t.timestamp(),
  }
);

const matchPlayer = table(
  { name: 'match_player' },
  {
    identity: t.identity().primaryKey(),
    matchId: t.u64().index('btree'),
    team: t.u8(),
  }
);

const matchmakingTimer = table(
  { name: 'matchmaking_timer' },
  {
    scheduledId: t.u64().primaryKey().autoInc(),
    scheduledAt: t.scheduleAt(),
  }
);

const spacetimedb = schema({ playerRating, queueEntry, gameMatch, matchPlayer, matchmakingTimer });
export default spacetimedb;

type Ctx = ReducerCtx<InferSchema<typeof spacetimedb>>;

Join the queue​

Insert the timer row from the init reducer, so match_players runs every second. init only runs when the database is created. Publishing new code to an existing database doesn't run it again: to start matchmaking there, insert the timer row from another reducer, once.

Then change join_queue. It gives new players OpenSkill's default rating, and adds the caller to the queue with their current mu. It no longer creates matches: match_players does.

Keep leave_queue, client_disconnected and the my_match view from the matchmaking queue guide as they are.

export const init = spacetimedb.init(ctx => {
  ctx.db.matchmakingTimer.insert({
    scheduledId: 0n,
    scheduledAt: ScheduleAt.interval(1_000_000n),
  });
});

export const joinQueue = spacetimedb.reducer(ctx => {
  if (ctx.db.queueEntry.identity.find(ctx.sender)) {
    throw new SenderError('already in the queue');
  }
  if (ctx.db.matchPlayer.identity.find(ctx.sender)) {
    throw new SenderError('already in a match');
  }
  let player = ctx.db.playerRating.identity.find(ctx.sender);
  if (!player) {
    const { mu, sigma } = rating();
    player = ctx.db.playerRating.insert({ identity: ctx.sender, mu, sigma });
  }
  ctx.db.queueEntry.insert({ identity: ctx.sender, joinedAt: ctx.timestamp, mu: player.mu });
});

Match players of similar skill​

match_players sorts the waiting players by mu, so players of similar skill are next to each other. It then slides along the sorted list, looking at each group of neighbours big enough to fill a match:

  • If the gap between the group's strongest and weakest player is small enough, it creates a match with them and moves past them.
  • Otherwise, it moves on by one player.

The allowed gap starts at STARTING_GAP (StartingGap in C#) and grows with the time the group's longest-waiting player has waited. A player whose skill is far from everyone else's still gets a match, after waiting longer.

To create a match, it deals the players to the two teams in the order A, B, B, A, A, B, B, A, and so on. Because the players are sorted by skill, this gives both teams a similar total skill. In a 1v1 match, it simply puts one player on each team.

export const matchPlayers = spacetimedb.reducer(
  { onSchedule: matchmakingTimer },
  { arg: matchmakingTimer.rowType },
  ctx => {
    const waiting = Array.from(ctx.db.queueEntry.iter()).sort((a, b) => a.mu - b.mu);
    let i = 0;
    while (i + MATCH_SIZE <= waiting.length) {
      const group = waiting.slice(i, i + MATCH_SIZE);
      const gap = group[MATCH_SIZE - 1].mu - group[0].mu;
      const longestWait = Math.max(
        ...group.map(entry => Number(ctx.timestamp.since(entry.joinedAt).micros) / 1_000_000)
      );
      if (gap > STARTING_GAP + GAP_GROWTH_PER_SECOND * longestWait) {
        i += 1;
        continue;
      }

      const game = ctx.db.gameMatch.insert({ id: 0n, createdAt: ctx.timestamp });
      group.forEach((entry, k) => {
        ctx.db.queueEntry.identity.delete(entry.identity);
        // Teams in the order A, B, B, A, A, B, B, A, ...
        const team = Math.floor((k + 1) / 2) % 2;
        ctx.db.matchPlayer.insert({ identity: entry.identity, matchId: game.id, team });
      });
      i += MATCH_SIZE;
    }
  }
);

match_players sorts the whole queue every second, which stays fast with thousands of waiting players. It's a scheduled reducer, so clients can't call it.

Larger teams

The same code works for any team size: set TEAM_SIZE (TeamSize in C#) to 5 for 5v5 matches. The more players a match needs, the wider their skill gap tends to be, so players wait longer for a match. Raise STARTING_GAP or GAP_GROWTH_PER_SECOND (StartingGap or GapGrowthPerSecond in C#) to keep waits short.

Update ratings when a match ends​

Add a finish_match function that takes a match and the team that won. It hands both teams' ratings to OpenSkill, winners first, saves the new ratings, then deletes the match so its players can join the queue again.

OpenSkill raises the winners' mu and lowers the losers'. The more surprising the result, the bigger the change: beating a much stronger team moves ratings more than beating a weaker one. Every match also lowers each player's sigma, as OpenSkill grows more certain of their skill.

finish_match is a plain function, not a reducer. Call it from your own game logic when a match ends, for example in the reducer that applies the winning move. If clients could call it, players could report wins they never earned.

function finishMatch(ctx: Ctx, matchId: bigint, winningTeam: number) {
  const players = Array.from(ctx.db.matchPlayer.matchId.filter(matchId));
  const ratingOf = (identity: typeof ctx.sender) => ctx.db.playerRating.identity.find(identity)!;
  const winners = players.filter(p => p.team === winningTeam).map(p => ratingOf(p.identity));
  const losers = players.filter(p => p.team !== winningTeam).map(p => ratingOf(p.identity));

  // rate takes the teams in the order they finished.
  const [newWinners, newLosers] = rate([winners, losers]);
  winners.forEach((player, k) => ctx.db.playerRating.identity.update({ ...player, ...newWinners[k] }));
  losers.forEach((player, k) => ctx.db.playerRating.identity.update({ ...player, ...newLosers[k] }));

  for (const player of players) {
    ctx.db.matchPlayer.identity.delete(player.identity);
  }
  ctx.db.gameMatch.id.delete(matchId);
}

OpenSkill can also rate draws and matches with more than two teams. See the documentation of openskill.js, OpenSkillSharp or skillratings for details.

Show the player's rating and rank​

On the client, subscribe to the player's own row in player_rating, along with my_match to learn about new matches, as in the matchmaking queue guide.

mu alone is a poor rating to show players: a new player who wins their first match jumps straight to the top. Instead, show mu - 3 * sigma, which OpenSkill calls the ordinal. It's a cautious estimate of the player's skill: it starts near 0, and climbs as the player wins and OpenSkill grows more certain of their skill.

To show a rank such as Bronze or Gold, split that rating into tiers. Because the rating starts near 0, every new player starts in Bronze and climbs from there. Adjust the tiers to your game: few players get above 35.

import { DbConnection, tables } from './module_bindings';

const conn = DbConnection.builder()
  .withUri('ws://localhost:3000')
  .withDatabaseName('my-game')
  .onConnect((ctx, identity) => {
    ctx
      .subscriptionBuilder()
      .subscribe([tables.playerRating.where(r => r.identity.eq(identity)), tables.myMatch]);
  })
  .build();

function rankOf(rating: number): string {
  if (rating >= 35) return 'Diamond';
  if (rating >= 25) return 'Platinum';
  if (rating >= 15) return 'Gold';
  if (rating >= 5) return 'Silver';
  return 'Bronze';
}

function showRating(player: { mu: number; sigma: number }) {
  const rating = player.mu - 3 * player.sigma;
  console.log(`Your rating: ${rating.toFixed(1)} (${rankOf(rating)})`);
}

// The player's row is inserted when they first join the queue,
// then updated after each match.
conn.db.playerRating.onInsert((_ctx, player) => showRating(player));
conn.db.playerRating.onUpdate((_ctx, _old, player) => showRating(player));

What's next?​

You now have matchmaking that puts players of similar skill together, and learns their skill from every match:

  • player_rating stores each player's OpenSkill rating, and finish_match updates it when a match ends, from your game logic only.
  • match_players runs every second, matches neighbours in skill, and widens the allowed gap the longer players wait.
  • TEAM_SIZE (TeamSize in C#) switches between 1v1 and team matches, and teams are dealt so their total skill is similar.
  • Clients show a cautious rating, mu - 3 * sigma, and a rank based on it.

To support several game modes, such as 1v1 and 5v5, give each mode its own queue and its own ratings: a player's skill in one mode says little about the other.

  • Add a mode column to queue_entry, pass the mode to join_queue, and have match_players match each mode separately, with that mode's team size.
  • Add a mode column to player_rating. A player now has one row per mode, so identity can't be the primary key anymore: use an auto-incremented id instead, and a multi-column index on identity and mode to find a player's rating in a mode.

To learn more about the features used here, see Schedule Tables, Reducers and Subscriptions.

To show the best players, sort them by mu - 3 * sigma in a top 100 leaderboard. Next, you can make a turn-based game with turn timeouts.