matchmaker-ts

https://github.com/wwlib/matchmaker-ts

matchmaker-ts is a tool for designing and analyzing multiplayer matchmaking.

Build & Run

yarn
yarn start

Documentation

https://wwlib.github.io/matchmaker-ts/typedoc/index.html

Getting Started

matchmaker-ts provides a GUI for controlling and testing the server. The GUI also allows matchmaker-ts to act as a client app that can connect to the server.

For example:

• mock clients/players can be generated by clicking the addMockClient button
• these will be added to lobbies and matched
• clicking the step button below the stats graph will add the current number-of-lobbies and number-of-clients as graph data points
• clicking the startSim button will cause new clients to be created continuously (rapidly)
• periodically clicking step will add real time data points to the graph
• clicking the on button below the stats graph will cause the graph to update continuously
• Note: this is not yet well-optimized and may not perform well over time

Using the client app:

• launch another instance of matchmaker-ts (on the same machine, for now)
• in both clients, click the connect button
• then type messages in the clients' <input> fields
• the messages should be relayed between clients and displayed in the <messages> fields
• Note: when these special clients connect to the server they are added to a ChatLobby which does not attempt any matchmaking. This allows the clients to chat indefinitely. Up to 8 clients will be added to the special ChatLobby. Subsequent connections are treated normally.

Overview and Architecture

matchmaker-ts is a real time multiplayer server written in TypeScript with an Electron/React front-end for analysis and testing.

Director

The Director coordinates the servers subsystems.

• Instantiates the ConnectionManager
• Manages communication with the Database
• Manages the lifecycle of Lobbies
• whenever a new player connects, the Director either:
  • adds the player to an existing Lobby or
  • creates a new Lobby appropriate for that player
• Manages the lifecycle of authenticated TCPClientSessions
• Creates and destroys ClientProxy instances used to relay messages between TCPClientSessions and GameWorlds (Lobbies)
• Manages the creation of clients used for testing the server
• mock clients = a mock TCPClientSession + ClientProxy
• mock clients are added to Lobbies just like actual clientSession
• Manages the creation/clean-up of (mock) PlayerAccounts

Pub/Sub

• The Director currently uses a local/in-memory pub/sub module (PubSubJS) to relay messages between TCP connections and Lobby/GameWorlds
• Greater scalability could be achieved by using Redis which would allow messages to be shared between multiple server instances

Primary/Replica

• The Director is designed to have two modes: Primary and Replica (unimplemented)
• In Primary mode, the Director acts as the authoritative Database and owner/director of Lobby/GameWorld instances
• The Replica Director would rely on the Primary Director to distribute Lobby/GameWorld creation/management responsibility across all instances.
• In Replica mode, the Director would instantiate a ConnectionManager and accept TCP connections routed to it by a load balancer. Messaging between Primary and Replica instances would be via pub/sub
• A more scalable approach would allow Replica instances to also create/manage Lobby/GameWorld instances

Matchmaking

The Director coordinates matchmaking by:

• finding the most appropriate Lobby instance for each new player/client
• each existing Lobby is queried to see if it will accept the player: Lobby: willAcceptPlayer(player: PlayerAccount): boolean
• if no Lobby will accept the player, a new lobby is created for that player: Director: addLobbyWithPlayerAccount(player: PlayerAccount): Lobby

Lobby instances accept players based on configurable criteria:

• PlayerLocation (i.e. NorthAmericaEast)
• Player MMR score: using an mmrRange, i.e {min: 1001, max: 1800}
• Unimplemented: latency, business priority, behavior profile (history of quitting), etc.

Matching

• The Lobby is responsible for matching players
• The current matching algorithm is simplistic and assumes 1v1 matching (teams are not supported, yet)
• Periodically (every deltaTime, i.e. 1 second) every player in the lobby is compared to every other player to determine if a match is acceptable: willMatchClients(client1: ClientProxy, client2: ClientProxy): boolean
• A greedy approach is used so that matchable players are immediately matched
• Players will be matched if the difference between their MMR scores is less than the Lobby's maxClientMMRDifference (i.e. 100 points)
• If a pair's combined wait time in the lobby exceeds the Lobby's maxCombinedClientWaitTime (i.e. 30 seconds) the pair will be matched

GamePlay

• The current implementation does not involve actual or simulated gameplay
• As soon as a match is made, the players are disposed by the Director: handleGameOver(client1: ClientProxy, client2: ClientProxy): void

ClientProxy

The ClientProxy class acts as a bridge between the TCPClientSessions (sockets) and Lobby/GameWorld instances. This abstraction anticipates the need to distribute socket connections across server instances/machines for scalability. The ClientProxy publishes and subscribes to channels identified by the player's UUID. The ClientProxy receives messages when the TCPClientSession publishes to the player's inbound channel ([UUID].in) and relays these to the Lobby/GameWorld to which the player has been added. The TCPClientSession sends messages via the socket which it receives via the player's [UUID].out channel. As noted, this would allow for TCPClientSessions to be hosted by multiple servers/machines.

Messages

matchmaker-ts anticipates the need to optimize message sizes and uses schemapack to pack JavaScript Objects (JSON) into compact binary messages.

Note: The currently implemented message types use string payloads. Packing is most effective with simpler payload types.

Scalability Considerations

The standard way to scale multiplayer matching to millions of players/connections it to run multiple server instances fed by a load balancer. In this architecture, each server manages thousands of connections, lobbies and game worlds. Messages are routed between server instances using a pub/sub service like Redis. Redis also serves as the shared, in-memory database for all server instances.

matchmaker-ts anticipates this architecture by using a local pub/sub module (PubSubJS) that could be swapped out for node-redis. As noted above, the Director is designed to have Primary and Replica modes where the Replica Director would rely on the Primary Director to distribute Lobby/GameWorld creation/management responsibility across all instances.

For example: Amazon's GameLift service can provide a highly scalable multi-server architecture using redis. GameLift's matchmaking service also provides a configurable, scalable mechanism for matchmaking.

• https://aws.amazon.com/gamelift/

• https://hackernoon.com/serverless-websockets-with-aws-lambda-fanout-15384bd30354

• https://aws.amazon.com/blogs/database/how-to-build-a-chat-application-with-amazon-elasticache-for-redis/

• https://medium.com/containers-on-aws/scaling-a-realtime-chat-app-on-aws-using-socket-io-redis-and-aws-fargate-4ed63fb1b681

• https://medium.com/digg-data/the-way-of-the-gopher-6693db15ae1f

Performance

There is room for a lot of performance tuning in the current implementation. As noted above, the matching algorithm is simplistic. The Electron wrapper is useful for design and development. A headless node instances would be used in production.

TODO: Use workers to improve matching performance.

Matching Considerations

Matching is an interesting (hard) problem and the subject of previous and ongoing research. These relevant links address both intuitive and counter-intuitive strategies for maximizing player engagement:

AWS

• https://aws.amazon.com/blogs/gametech/matchmaking-your-way-amazon-gamelift-flexmatch-and-game-session-queues/
• https://docs.aws.amazon.com/gamelift/latest/developerguide/match-configuration.html
• https://aws.amazon.com/blogs/gametech/fitting-the-pattern-serverless-custom-matchmaking-with-amazon-gamelift/

Research

• https://www.firstpost.com/tech/gaming/university-of-michigan-researchers-create-better-matchmaking-algorithms-for-multiplayer-games-3725015.html
• https://arstechnica.com/gaming/2018/01/ea-has-tested-online-matchmaking-algorithms-to-favor-engagement-not-fairness/
• https://digit.hbs.org/submission/video-game-matchmaking-a-data-driven-take-from-blizzard/
• https://www.researchgate.net/figure/MMR-distribution-of-players_fig1_236887261
• https://en.wikipedia.org/wiki/Stable_marriage_problem
• http://www.diva-portal.se/smash/get/diva2:873273/FULLTEXT01.pdf
• http://papers.www2017.com.au.s3-website-ap-southeast-2.amazonaws.com/proceedings/p1143.pdf
• http://joostdevblog.blogspot.com/2014/11/why-good-matchmaking-requires-enormous.html
• http://sce.carleton.ca/~mfloyd/iccbr11games/papers/Jimenez-Rodriguez.pdf

MMR/ELO

• https://fivethirtyeight.com/features/how-we-calculate-nba-elo-ratings/
• https://metinmediamath.wordpress.com/2013/11/27/how-to-calculate-the-elo-rating-including-example/

Experience

• https://www.epicgames.com/fortnite/forums/battle-royale/royale-with-cheese/139705-connecting-to-matchmaking-service-takes-forever-nowadays-how-can-queue-be-full-o-o
• https://www.epicgames.com/fortnite/forums/suggestions-advice/172539-skill-based-matchmaking

Approach

• https://wiki.guildwars2.com/wiki/PvP_Matchmaking_Algorithm
• https://www.reddit.com/r/learnprogramming/comments/7rdlzf/how_is_online_game_matchmaking_done_from_a/
• http://www.atonet.se/matchmaking.html
• https://github.com/eerwitt/node-match-maker

Data/ML

Using ML (Deep Learning) could be a valubale approach to creating an 'intelligent' adaptive matching strategy - especially given that non-obvious, counter-intuitive factors can contribute to player engagement, retention and overall profitability.

Teams vs 1v1

Teams are conceptually like a Lobby, made up of players who have often explicitly chosen to play as a team. An approach to team matching would give players a mechanism for joining a specific TeamLobby and then matching TeamLobby instances in a TeamMatchingLobby.

AWS: GameLift

• https://docs.aws.amazon.com/gamelift/latest/developerguide/match-examples.html