Queue (matchmaking) support

Queue (matchmaking) support

For the discussion of infrastructure improvements and changes.

Moderator: Moderators

Post Reply
gajop
Moderator
Posts: 3015
Joined: 05 Aug 2009, 20:42

Queue (matchmaking) support

Post by gajop » 16 Feb 2015, 07:03

The proposal has been updated, see below!

2015. We need matchmaking.
This proposal extends the lobby protocol with a queue system which is the essential part of MM (matchmaking). It includes a player<->server interface and a MM bot<->server interface.

The actual MM implementation is left to the bot, but the protocol in which the bot is expected to communicate is also specified. The reasoning behind this is that there is no simple MM algorithm, it can depend greatly on a specific game and so on.

The protocol is still well defined, pretty general and still supports all of the functionality one might expect to have in such a system.

Current proposal:

Queue object:
(mandatory)
name (unique, used as a persistent identifier, specified by the MM bot)
title
canTeamJoin

(optional)
gameNames
mapNames
engineVersions
minPlayers
maxPlayers

(extensions - custom params)
min/max elo
...


Player<->Server::
Streaming open/closed queues:
<- QUEUEOPENED {queue:queue}
<- QUEUECLOSED {name:name}
(there's no QUEUEUPDATE! if queue object changes - which it usually shouldn't - it needs to be closed and opened again)

(redundant?) -> LISTQUEUES
(redundant?) <- LISTQUEUES {queues:[{queue1}, {queue2}]}

-> JOINQUEUE {name:name, params:[{key1:val1}, ...]} (params could be preferences such as: geographic regions/languages, etc.)
<- JOINQUEUE {name:name}
Should clients be allowed to join multiple queues at the same time? (the current proposal allows it)
<- JOINQUEUEFAILED {name:name, reason:reason}
-> LEAVEQUEUE {name:name} (confirmation needed)
<- LEFTQUEUE {name:name, reason:reason}

<- READYCHECK {name:name, responseTime:responseTime}
-> READYCHECKRESPONSE {name:name, response:response, responseTime:responseTime}
<- READYCHECKRESULT {name:name, result:result} (result is a "pass" or "fail", which could be displayed to the client)
Regarding READYCHECKRESULT implementation, should we send additional information (some other games do it), such as how many players failed, passed or timeouted?

MM bot<->Server:
-> OPENQUEUE {queue:queue} (the name is specified and must be unique)
<- OPENQUEUE {name:name}
-> CLOSEQUEUE {name:name}

<- JOINQUEUEREQUEST {name:name, userNames:userNames params:[{key1:val1}, ...]}
-> JOINQUEUEACCEPT {name:name, userNames:userNames}
-> JOINQUEUEDENY {name:name, userNames:userNames, reason:reason}

<- QUEUELEFT {name:name, userNames:userNames} (not to be confused with LEFTQUEUE, this one is sent to the MM bot and includes a list of all userNames in the team)
-> REMOVEQUEUEUSERS {name:name, userNames:userNames, reason:reason} (this one doesn't require confirmation)

-> READYCHECK {name:name, userNames:userNames, responseTime:responseTime}
Players who failed a ready check are automatically dropped from the queue. Response time is in seconds.

Two ways of handling ready checks (MM bot vs lobby server):
(Prefered) 1) We make the MM bot handle ready checks, but it makes the protocol more complicated for the MM bots and likely takes more bandwidth. MM bot gets each response from the user and sends the unified result to the lobby server.
<- READYCHECKRESPONSE {name:name, userNames:userNames, response:response, responseTime:responseTime}
-> READYCHECKRESULT {name:name, userNames:userNames, result:result} ("fail" or "pass")
The players would also get the result indirectly from the MM bot.

2) Lobby server handles it. It adds more strain to the lobby server and allows for less customization on the MM bot side, but it also makes the MM bot easier to implement. Lobby server sends the unified result to the MM bot.
<- READYCHECKRESPONSES {name:name, result:result, responses:[{userName:userName1, response:response1, responseTime:responseTime1}, ... ]} (responses can be omitted if result is "pass", verify!)

Team support: (playing with friends)
-> INVITETEAM {userName:userName}
<- INVITETEAM {userName:userName}
-> INVITETEAMACCEPT {userName:userName}
-> INVITETEAMDECLINE {userName:userName}
<- INVITETEAMACCEPTED {userName:userName}
<- INVITETEAMDECLINED {userName:userName, reason:reason} ("decline", "timeout", "unsupported")

<- JOINTEAM {userNames:userNames, leader:userName} (sent to user that joined a team)
<- JOINEDTEAM {userName:userName} (sent to all users of a team when a new member joins)
-> KICKFROMTEAM {userName:userName}
-> LEAVETEAM
<- LEFTTEAM {userName:userName, reason:reason}

-> SAYTEAM {msg:msg}
<- SAIDTEAM {userName:userName, msg:msg}
New commands for /me style, like it has already been done:
-> SAYTEAMEX {msg:msg}
<- SAIDTEAMEX {userName:userName, msg:msg}
Alternatively, a msgType param could be added to the SAYTEAM/SAIDTEAM commands, which would distinguish SAYTEAM from SAYTEAMEX and require only one command.

-> SETTEAMLEADER {userName:userName}
<- SETTEAMLEADER {userName:userName}

Kick disconnected players from team? (teams with disconnected players can't join queues)
Any changes to the team -> team drops queue
Joining a team -> drop existing queues
Only one team is allowed per client!

In addition to the above mentioned commands, the MM bot is expected to send the CONNECTUSER or a FORCEJOINBATTLE (clients need to support both) to the clients once all users have responded to a ready check.

This document is a draft. Changes will happen.


Old proposal:

Player<->Server:
->LISTQUEUES
<-STARTLISTQUEUES
<-LISTQUEUES queueId, gameNames, mapNames, engineVersions, title, description, minPlayers, maxPlayers, teamJoinAllowed
<-ENDLISTQUEUES

->JOINQUEUE queueId
<-JOINQUEUE queueId
->LEAVEQUEUE queueId
<-LEAVEQUEUE queueId reason (this can happen without a user action, i.e. by being kicked out, by the queue being closed or by the game about to start)

<-READYCHECK queueId responseTime
->READYCHECKRESPONSE queueId answer responseTime

(team queue support)
->INVITETEAM userName
<-INVITETEAM userName
->ACCEPTINVITE userName
->DECLINEINVITE userName
->KICKTEAM userName
-> LEAVETEAM
<- LEAVETEAM userName

MM bot<->Server:
-> ADDQUEUE gameNames, mapNames, engineVersions, title, description, minPlayers, maxPlayers, teamJoinAllowed
<- ADDQUEUE queueId
-> REMOVEQUEUE queueId
-> CLOSEQUEUE queueId
<- QUEUEJOIN queueId, userNames (team
-> REMOVEQUEUEUSER queueId, userName
-> READYCHECK queueId, userNames, responseTime
<- READYCHECKRESPONSE queueId, userName, answer, responseTime
0 x

User avatar
Silentwings
Moderator
Posts: 3565
Joined: 25 Oct 2008, 00:23

Re: Queue (matchmaking) support

Post by Silentwings » 16 Feb 2015, 09:29

So no OPEN/JOINBATTLE? I think it would be good to display the match-made games in progress somewhere + for people to connect and spectate a game in progress. I guess you'd also need games to supply a list of suitable maps & gameoptions?
0 x

gajop
Moderator
Posts: 3015
Joined: 05 Aug 2009, 20:42

Re: Queue (matchmaking) support

Post by gajop » 16 Feb 2015, 10:18

Silentwings wrote:So no OPEN/JOINBATTLE? I think it would be good to display the match-made games in progress somewhere + for people to connect and spectate a game in progress.
Uhh, I don't know about that. Do we want to allow people to spectate MM games? (some might be ranked).
Hm.. well, if you think it's that important, it's always possible to do that and use FORCEJOINBATTLE instead of USERCONNECT, but under no circumstance should all this be visible to the player. All players are also expected to verify that they have the resources before joining the queue, there will be NO downloading after the ready check has passed.
Silentwings wrote: I guess you'd also need games to supply a list of suitable maps & gameoptions?
List of maps are part of the QUEUE object, but I don't see why gameoptions should be known.
Remember that lobby server doesn't do the MM, it just handles queues.
The MM bot (which will have to be configured separately) will take care of all of that and setup playable games.
0 x

User avatar
Silentwings
Moderator
Posts: 3565
Joined: 25 Oct 2008, 00:23

Re: Queue (matchmaking) support

Post by Silentwings » 16 Feb 2015, 15:15

I don't think its all that important to have spectators in MM games, since I imagine one off tournaments and large multiplayer games (which are the main attractions for spectators) would remain on dedicated hosts. Although without the ability to spectate, afaics it would be very difficult to deal with abuse in MM games.
0 x

abma
Spring Developer
Posts: 3535
Joined: 01 Jun 2009, 00:08

Re: Queue (matchmaking) support

Post by abma » 16 Feb 2015, 15:52

imo allowing spectating is up to the MM bot. it could be added by allowing some parameter to be sent to the queue bot in the joinqueue command, i.e.
JOINQUEUE queueId spectator=1
and then, when a game starts, the players is connected as spectator. this should be possible for already running games as well. not sure if support for holepunching is needed / how it can be added. without fully investigating how holepunching works i would expect that the player has to send ip/port to the mm-bot and mm-bot has to send udp packets to the player. so JOINQUEUE should allow custom parameters?!
0 x

abma
Spring Developer
Posts: 3535
Joined: 01 Jun 2009, 00:08

Re: Queue (matchmaking) support

Post by abma » 16 Feb 2015, 15:55

what is READYCHECK for? it asks all player, "wanna start"?

is it needed? if not ready, leave queue?
0 x

gajop
Moderator
Posts: 3015
Joined: 05 Aug 2009, 20:42

Re: Queue (matchmaking) support

Post by gajop » 17 Feb 2015, 04:23

Silentwings wrote:I don't think its all that important to have spectators in MM games, since I imagine one off tournaments and large multiplayer games (which are the main attractions for spectators) would remain on dedicated hosts. Although without the ability to spectate, afaics it would be very difficult to deal with abuse in MM games.
I would hope replays are a far better mechanism of detecting abuse than having to spectate all games.
abma wrote:imo allowing spectating is up to the MM bot. it could be added by allowing some parameter to be sent to the queue bot in the joinqueue command, i.e.
JOINQUEUE queueId spectator=1
and then, when a game starts, the players is connected as spectator. this should be possible for already running games as well.
(queue objects should then have an additional allowSpectators param)
The question is whether we want spectators to be able to browse current MM games and choose a specific one they want to join -> we'd need to rely on the BR support for that then.
abma wrote: not sure if support for holepunching is needed / how it can be added. without fully investigating how holepunching works i would expect that the player has to send ip/port to the mm-bot and mm-bot has to send udp packets to the player. so JOINQUEUE should allow custom parameters?!
Is this really needed? Remember, MM games will all be hosted by dedicated bots (probably different instances from the MM bot). A modified version of Springie, Spads or w/e that is controlled by the MM bot.

Also, JOINQUEUE will probably need to allow custom parameters, but I want to define the most common things and let games add their own. (There might be things like "elo-range=" or "min-level=", etc.)
abma wrote:what is READYCHECK for? it asks all player, "wanna start"?

is it needed? if not ready, leave queue?
It's needed. This should be triggered exactly before the game is about to start (the MM bot has all collected all the required players) to confirm that the players are still here and ready to play.
It's up to the MM bot if they'll be sending it or not, but if sent, the lobby client MUST display it to the user and demand a user confirmation.
0 x

User avatar
Silentwings
Moderator
Posts: 3565
Joined: 25 Oct 2008, 00:23

Re: Queue (matchmaking) support

Post by Silentwings » 17 Feb 2015, 08:18

I would hope replays are a far better mechanism of detecting abuse than having to spectate all games.
No - replays are useful but they can only ever be a small part of a system for handling abuse, because its very time consuming to watch them (and by the time you can, further damage probably already happened). They are the last resort for abuse detection, and are used essentially only in extreme cases. In practice, watching and removing abuse in real time, and having a large enough set of trustworthy enough players able to do this, is the main way that hosts are moderated. It would be hard for this to work without the ability to just join a running battle and see whats happening.
0 x

gajop
Moderator
Posts: 3015
Joined: 05 Aug 2009, 20:42

Re: Queue (matchmaking) support

Post by gajop » 17 Feb 2015, 08:56

Silentwings wrote: No - replays are useful but they can only ever be a small part of a system for handling abuse, because its very time consuming to watch them (and by the time you can, further damage probably already happened). They are the last resort for abuse detection, and are used essentially only in extreme cases. In practice, watching and removing abuse in real time, and having a large enough set of trustworthy enough players able to do this, is the main way that hosts are moderated. It would be hard for this to work without the ability to just join a running battle and see whats happening.
I would be quite surprised if MM would lead to the same amount of spectating as it's done with the current custom game system.
Usually people tend to spectate games because there are only a few large rooms going, so they're there waiting for a spot to open or just idling "since everyone's there".

Anyhow, I think I'll just put a requirement that all lobby clients will also have to support FORCEJOINBATTLE in addition to USERCONNECT and it'll be up to the MM bot if they want to go to the process of opening BRs to support search/browse+spectate or just USERCONNECT which limits things to only spectating upon invitation.
0 x

abma
Spring Developer
Posts: 3535
Joined: 01 Jun 2009, 00:08

Re: Queue (matchmaking) support

Post by abma » 02 Mar 2015, 08:21

when implementing this it would be good to use a generic LIST command:

i.e:

client: LIST type=subscriptions
server: LISTSTART type=subscriptions
server: LIST ...
server: LISTEND type=subscriptions

this could be used for all type of lists. (reduces redundancy in code and docs)

edit:

after some conversation using json seems better as some parameters would be troublesome with current data types in protocol (i.e. mapNames)
0 x

gajop
Moderator
Posts: 3015
Joined: 05 Aug 2009, 20:42

Re: Queue (matchmaking) support

Post by gajop » 02 Mar 2015, 10:45

We'll make the whole queue protocol with JSON and see how that is received.
Regarding that, I assume commands should look like:
COMMAND jsonStr
Example:

Code: Select all

LISTQUEUES { "queues" : [ { "id" : 5, "gameNames" : [ "ba:stable" ], "mapNames" : [ "DSD" ] , "engineVersions" : [ "101" ], "title" : "BADSD24/7", "description" : "Join the grind", "minPlayers" : 10, "maxPlayers" : 30, "teamJoinAllowed" : true }, { "id" : 6, "gameNames" : [ "xta:stable" ], "mapNames" : [ "DSDEvolved" ] , "engineVersions" : [ "102" ], "title" : "XTADSD24/7", "description" : "Join the hipster grind", "minPlayers" : 3, "maxPlayers" : 15, "teamJoinAllowed" : true } ] }
(This is all single line)

If we ever move the entire protocol to JSON (or add support for it), even the cmd str could be inside the JSON object.
0 x

abma
Spring Developer
Posts: 3535
Joined: 01 Jun 2009, 00:08

Re: Queue (matchmaking) support

Post by abma » 02 Mar 2015, 20:28

looks good and docs to write are a lot shorter :)
0 x

gajop
Moderator
Posts: 3015
Joined: 05 Aug 2009, 20:42

Re: Queue (matchmaking) support

Post by gajop » 02 May 2015, 07:35

Updated the proposal.
The major change was to use "name" (string) instead of "queueId", since I think it would be better to have name-identified queues instead (where names aren't generated by the lobby server, but instead specified by the MM bot). The benefit of this is that it would allow us to create clients for specific games, which would provide interfaces to join queues based on their names. Later on we could allow for queue name registration and possibly even only send full queue objects if there was a change, but I don't want to make things too complicated for now.
Additionally nearly all parts of the protocol were extended to be functionality complete.

There are still a few things that are left undecided, and some things might still be missing out, so give it a check.
0 x

User avatar
Nemo
Spring 1944 Developer
Posts: 1376
Joined: 30 Jan 2005, 19:44

Re: Queue (matchmaking) support

Post by Nemo » 07 Jul 2015, 12:51

Yo, gajop -- I started hacking on this a bit. Is lualobby at a point where I can use it to test the player side of this without too much hassle? I've got SPADS and uberserver running locally and started on the server<-->SPADS side, but I'm not super enthused about trying to use springlobby (for example) to handle the player end of things.
0 x

gajop
Moderator
Posts: 3015
Joined: 05 Aug 2009, 20:42

Re: Queue (matchmaking) support

Post by gajop » 07 Jul 2015, 14:50

Wow, that's great, thanks!
I would like you to use lualobby since it has a lot of the interface completed already, but to do so you would need to use my version of spring and pr-downloader as I haven't had the time to finalize those changes and push them upstream. In fact you should use my version of uberserver too since it contains much of this protocol already implemented.

Anyway, this gives me some extra motivation to get those things done (first). I'd like to talk to you in chat if I can catch you one of these days.
0 x

User avatar
Nemo
Spring 1944 Developer
Posts: 1376
Joined: 30 Jan 2005, 19:44

Re: Queue (matchmaking) support

Post by Nemo » 07 Jul 2015, 15:27

Cool, I'll grab your fork of uberserver, I can see various queue related work there :)

For spring and pr-downloader, should I just grab from your forks? https://github.com/gajop/pr-downloader has some plausible-looking work, but https://github.com/gajop/spring seems quite old.

Anyways, yes, I'd be glad to chat, and excited to start playing with lualobby.
0 x

gajop
Moderator
Posts: 3015
Joined: 05 Aug 2009, 20:42

Re: Queue (matchmaking) support

Post by gajop » 08 Jul 2015, 02:37

Yes you can of course just use the forks and complete it yourself. For spring it's important to use the pr-downloader branch:https://github.com/gajop/spring/tree/pr-downloader
0 x

User avatar
Nemo
Spring 1944 Developer
Posts: 1376
Joined: 30 Jan 2005, 19:44

Re: Queue (matchmaking) support

Post by Nemo » 18 Oct 2015, 20:04

Yo, the first draft of the matchbot is substantially done. Here's a video of matchmaking a 1v1: https://www.youtube.com/watch?v=3yK7e-82BGA

There's no UI yet, and currently it only knows how to matchmake random (i.e. not skill based) 1v1. At some point I'll probably give it a simple web UI for seeing current games/players/wait times/whatever, but that only matters if it'll be used :)

Gajop: do you have any thoughts on how you want matchmaking algos to plug in? How team support should look? $other_feature that you think will need substantial development?

Edit: repo: https://github.com/kanatohodets/matchbot
0 x

hokomoko
Spring Developer
Posts: 567
Joined: 02 Jun 2014, 00:46

Re: Queue (matchmaking) support

Post by hokomoko » 18 Oct 2015, 22:01

Wow!
Epic!
Keep up the good work!
0 x

gajop
Moderator
Posts: 3015
Joined: 05 Aug 2009, 20:42

Re: Queue (matchmaking) support

Post by gajop » 19 Oct 2015, 06:54

Nemo wrote:Yo, the first draft of the matchbot is substantially done. Here's a video of matchmaking a 1v1: https://www.youtube.com/watch?v=3yK7e-82BGA
Nice to see this moving :)
Nemo wrote: There's no UI yet, and currently it only knows how to matchmake random (i.e. not skill based) 1v1. At some point I'll probably give it a simple web UI for seeing current games/players/wait times/whatever, but that only matters if it'll be used :)
I think we could make the UI based on the lobby server and thus matchmaking bot agnostic. That would be probably be better.
Nemo wrote: Gajop: do you have any thoughts on how you want matchmaking algos to plug in? How team support should look? $other_feature that you think will need substantial development?
The "custom matchmakers" should be made by handling a few callins for:
- Checking if the player (team) should be accepted in the queue. This would basically get triggered from <- JOINQUEUEREQUEST {name:name, userNames:userNames params:[{key1:val1}, ...]} and would return either a true or false for each player (team)
- Doing periodic updates, which is what the core of the matchmaking algorithms is. It should take a list of players (teams) in the queue with the join parameters and the amount of time in queue. This is where you'd be invoking callouts such as:
---- MakeGame(team configurations, game, map, engine, ...), which would send the readychecks and handle everything in the background (something that the matchmaking algorithm shouldn't be concerned about). This is the most important callout that the custom matchmaking algorithm would invoke. That said, it's perfectly OK to not invoke any of these in every update, even if there are enough players. Implementations may want to keep a short term history to avoid repeating matches between the same players, by waiting a bit of time for other people to come.
---- Update the ETA value for players (teams) in the queue. (We don't actually have this in the lobby protocol yet, but it seems as an obvious feature).
---- Remove players from the queue for whatever reason. (Removals based on successful or failed ready-checks due to absence or negative answer should be done automatically and is not something the matchmaking algorithm should need to take care of).

Team support can be done by simply passing list of teams instead of a list of players in the important places. Keep in mind that the custom algorithms shouldn't be doing the sanity checks such as if people are trying to join 1v1 games in teams, having players appearing twice in the same team, and such. Most of this should be filtered out by the lobby server or the matchmaking bot framework. The algorithms should just be focusing on doing matchmaking with the assumption that the data is "clean".

PS: This is just my view on what would be the most basic structure. I don't want to design the matchmaking bot for you, as it's likely you may create a better API/interface and allow some of the things I mentioned as hardcoded to be customized (e.g. by inheritance and overriding methods), and most importantly I don't want to rob you of the joy of doing it yourself :)
0 x

Post Reply

Return to “Infrastructure Development”