11

I am interested to know if there is an existing algorithm to start a multiplayer game, for example, poker. What steps do we need to take when the player enters the "matchmaking phase"?

I expect something like:

  1. Player N enter the matchmaking room.
  2. The player is saved in a database in "Waiting" status.
  3. Every 10 seconds, the server starts a job and selects 5 players in the status "Waiting" and sends each of them the websocket link where they have to connect to play.
  4. The players selected for the game are removed from the database.

I know this is not a good algorithm, it was also an example to let you know which level of detail I would like.

Is there a good algorithm to do this? Since it is a well known problem I expect something but I have not found much online.

Edit 1: Some more details since it seems this problem is too general at the moment:

  1. Assume we are developing a poker app
  2. the app is planned to be used by millions of players
  3. I expect a distributed system (since it has to scale for millions of users)
  4. we can start the game if there are at least 4 players and a maximum of 8 (per match).
  5. Regarding the choice of the players in the match I would like to keep this part simple. Let's say each player has a "score" that correspond to the number of match where he/she won.
  6. No constraints on the technology used (queue, sql-db, no-sql db etc).
18
  • 4
    What makes you say it's not a 'good' algorithm? It might be perfectly adequate depending on your requirements. I would say at the very least you'd want to select as many groups of 5 that you can each time or you could easily fall behind if more than 5 people are joining every 10 seconds.
    – JimmyJames
    Commented Oct 25, 2023 at 20:18
  • 10
    The main problem here is that you completely skip the detailed requirements. What exactly do you expect from an algorithm here? The problem may sound like it should have been solved sufficiently often that there should be a standard solution, but in fact most implementations would have their own requirements and peculiarities which may or may not apply to you. (continued) Commented Oct 26, 2023 at 7:39
  • 7
    For example, you might want to select groups based on affinity, comparable player strength, likeliness to conspire against other players, etc. These choices would influence the algorithm considerably. If you have none of these requirements, the most simple algorithm (such as your proposed one) that you can implement in an hour or two would likely suffice, and that's not something that requires consulting the combined wisdom of thousands of SE readers :-) Commented Oct 26, 2023 at 7:39
  • 7
    The GameDev stack is likely to have better answers for how matchmaking lobbies work. Commented Oct 26, 2023 at 8:43
  • 6
    Instead of every 10 seconds, I would try matchmaking immediately when a player enters the "waiting" state. Why wait 10 seconds when enough players are ready? Why run a job every 10 seconds when noone at all is willing to play? Commented Oct 26, 2023 at 13:00

4 Answers 4

24

I'm hesitant to call this an algorithm but there are two basic approaches to this kind of thing: polling and events.

What you are describing is polling: on some sort of schedule, you check and see if there are enough players to start a game.

The other approach is event-based: when someone joins you check to see if there are enough players to start a game.

There was a time when I would have told you that events are always superior to polling. I've come to learn however that both techniques have their place. Polling has been overused but it has advantages. The key advantage is that it's easy to implement and has some inherent fault-tolerance: if you have some sort of temporary issue (like a network issue) that's been resolved, polling will tend to resume without issue. Events can be trickier in such scenarios.

In your case, the main advantage of polling might be that it might reduce the amount of spurious starts. What I mean is that if you have someone who joins the room and then immediately leaves, you are much less likely to start a game that suddenly ends because one of the players has left.

You can solve for that in the event-based approach, but it tends to be a little trickier. The big advantage with events is that under heavy load, you will tend to spread your game starts out. If you use polling, you might end up usage spikes every 10 seconds and idle times between.

In a nutshell, I think both approaches are valid and you can combine the two to do things like generate an event every 10 seconds to make sure nothing has been dropped.

18
  • 7
    @AM13 The problem is that there are many potential solutions, but which one is appropriate for your situation is unknown. I will give you the general answers for free. Figuring out which one is a good choice in a real-world situation is how I put food on the table. That said, with more context, I can give more specific advice.
    – JimmyJames
    Commented Oct 25, 2023 at 21:35
  • 1
    The advantage of polling is you can let the event make a minor change of state and wait for the poll to deal with that state. This protects you from bursts that could overload. It's how hardware interrupts work. Commented Oct 25, 2023 at 22:50
  • 1
    @AM13: it sounds like your ideal algorithm is "when there's 5+ players in the queue, then move the first 5 to a game" Commented Oct 26, 2023 at 16:42
  • 1
    @candied_orange You can use a queue without using polling. You can use polling without a queue.
    – JimmyJames
    Commented Oct 26, 2023 at 20:25
  • 2
    @JimmyJames I can agree with that. Commented Oct 26, 2023 at 20:37
12

A problem like this isn’t solved by thinking hard about it. What will happen that humans will run into something controlled by an algorithm, and humans can react in a way that has unintended outcomes. They can understand and manipulate the algorithm. They can walk away. They can unintentionally cause the algorithm to produce inappropriate behaviour.

What you do is make some effort to create what you think is useful behaviour. Then you invite real users and observe. You detect when the interaction between humans and algorithm produces a suboptimal outcome and change the algorithm, until you are happy.

Then you try it with a group of drunks, people who think of themselves as alpha males, and Japanese tourists, you observe, learn and improve.

0
0

Following mostly JimmyJames and
candied_orange answers and comments (but also others) this could be an approach:

Using a queue

  1. User clicks "start game", backend receives a request and add user in the queue
  2. Backend check if there at least 5 players. Since not do nothing.
  3. same for 2nd user up to the 5th user. At this point the backend send a message (websocket?) where the users can play.
  • In AWS SQS (for example) there is an API to know the number of element in the queue

problems:

  1. What happen if a user exit the matchmaking phase? How the Backend can know that?
  2. In case of a distributed system, how 2 different istances of the same backend app avoid selecting a player for 2 differnt games on the same time?

Using a DB Same as before but saving in a DB instead of a queue (mysql for example).

  • each save on the DB will trigger the backend operations. The server Backend will check if there are at least 5 players waiting etc.
  • using a DB we can perform a count
  • we can use a select for update so that when an instance selct 5 players they will be marked as "IN_A_MATCH" (distributed system problem solved?)
  • if the user exit the matchmaking phase it will send an event deleting the user from the table on DB.

Problems:

  1. If each DB save will trigger the operation that means that for 5 players 5 thread (?) for checking if is possible start a match will be started. This does not sound right.

comments on this solution will be appreciated.

11
  • 1
    For the queue, that looks like a pretty good start for a happy path. The challenges are going to be all the abnormal cases such as someone dropping out. You can use the WS connectivity as a proxy (you should be able to get a notification on disconnect) but in my experience, WS connections are flaky and you need have client-side code ready to reconnect so immediately dropping them from the queue on disconnect might be a bad user experience.
    – JimmyJames
    Commented Oct 27, 2023 at 15:36
  • 1
    "how 2 different instances of the same backend app avoid" one of the features of a queue (in general) that differentiates it from a topic (kafka topics aside) is that each message is read only by one consumer at a time. That is, if a consumer reads a message, other consumers will not see it when they get from the queue. If the consumer commits the read, it is removed completely. If the consumer rolls-back, the message becomes available for read again. This is one key advantage over using a DB: you will need to implement your isolation mechanism if you roll your own queue on a DB.
    – JimmyJames
    Commented Oct 27, 2023 at 15:42
  • @JimmyJames You are perfectly right no problem in the case of distributed system using a queue. Regarding the user that abandons the matchmaking phase even if we have an event on the front end side that triggers the backend we cannot delete a specific message in queue (as far as I know at least). If we suppose to use a DB for the "isolation mechanism" we could use the select_for_update functionality and in theory, it should work well. There are other reasons why you would avoid this approach?
    – AM13
    Commented Oct 27, 2023 at 17:50
  • You have a few obvious potential race conditions still. If server A finds 5 people waiting and server B finds 5 people waiting and server A puts them in a match and then server B goes to put them in a match... Or if a person drops connection while matchmaking is happening, depending on what order things happen in you either get a server that counted five people but now can't find five to match, or you get the dequeue trying to run after the person is already started in a match. Commented Oct 27, 2023 at 18:49
  • I don't think I'd actually use an off-the-shelf queue for this because I don't know of one that's necessarily a great fig for the problem, I think you'd spend way more time fighting with the queue, but the argument in favor of off-the-shelf software is that a whole team of specialists has spent way more time on it than you ever could and a whole lot of users have already found a bunch of bugs which have hopefully been fixed. (What happens if your server picks up a lock on the table and is then hit by lightning? Who knows!) Commented Oct 27, 2023 at 18:52
-1

Requirements aren't here so it's tough to give a detailed answer, but event-based seems like the best way to go about this. You can even assign a gameId that increments after every game starts when you add a user to the database.

  1. GameId=1
  2. Player saved with Waiting and GameId
  3. If enough players, start the game and increment GameId

Not the answer you're looking for? Browse other questions tagged or ask your own question.