Sunday, 7 January 2018

The limitations of matchmaking without server logic

I've previously explained how Steam, Microsoft, Sony and Nintendo all offer similar generic matchmaking systems based on rooms. These systems are great for quickly getting things going and are fine for most smallish games. However, if matchmaking is very important for your game and the requirements for matchmaking become more complex, these generic systems turn out to be pretty limiting. Today I'd like to discuss how we tried several approaches to get the best out of such generic systems in our game Awesomenauts and how the problems we encountered ultimately led us to develop our own matchmaking servers altogether.

Keep in mind that whether these problems are truly important depends on the game. If your game is a bit more casual, or has fewer players per match, or less focus on online multiplayer, or allows late-join, then the requirements for matchmaking become a lot less stringent. Depending on how demanding the matchmaking for your game is, none of these problems might be enough reason to skip the great convenience of using an existing matchmaking system.



The main problem is that these generic matchmaking systems don't allow serious logic to run on the server. The server keeps a list of gamerooms that the player might join, but the decision which room to actually join is made by the client. With this in mind, let's have a look at some of the client-based matchmaking algorithms we tried in Awesomenauts.

The 'growing search range' approach

The standard approach to client-based matchmaking is to have a growing search range. The client starts by asking the server for a list of all the rooms that can be joined and then checks whether any of those rooms are near geographically (to achieve low ping) and are similar in terms of skill. A good starting point might for example be that the other players in the matchroom need to be in the same country/state and differ by at most 500 skillpoints (in a system where 10,000 is the average skill of all players). If several suitable rooms are found, then we join the one closest.

This algorithm is simple enough, but the challenge is what to do when no suitable rooms are found. If you're adamant on always having high quality match-ups, then you might choose to simply wait for more suitable players to appear. However, unless your game has an enormous player count this probably results in really long waiting times for the user, or even in never finding a full match at all.

Therefore we increase the search distance over time. For example, we might double the allowed geographical distance and skill difference every 20 seconds. We keep doing this until we've found a suitable match. If at the biggest search range we still haven't found anyone to play with, then we simply keep waiting and searching.

An important note here is that while searching, the player also has her own room open for others to join. As soon as someone joins your room, you stop searching and just wait until enough players have joined for the match to be started. If you join someone else's room, you close your own room. To avoid problematic edge cases like two players joining each other's rooms simultaneously we add a simple rule: if the other room has only one player in it then we only join it if that room has a lower roomID than our own room. This may seem limiting but in practice doesn't matter much: if I can join your room because you have similar skill, then you can (eventually) join my room as well. It doesn't matter who joins who as long as we end up together.

This is roughly the matchmaking algorithm that Awesomenauts had at launch. What we didn't know back then, is that in many cases the result is little better than just joining a random room. For example, let's say a new player starts searching every 5 seconds. In a game with matches of 20 minutes, this means we have 240 concurrent players, which is pretty nice for a smaller indie game (multiplayer games that are an okay success on Steam are generally in the range of 400 to 2000 concurrent players). In the case of Awesomenauts a full match needs 6 players, which means it would take 30 seconds for a complete group to start searching. For decent matchmaking we don't want to play with just anyone though: we want a good match in terms of ping and skill. Only 1 in 4 players will be even remotely acceptable to play with (in practice probably even less), so we need to wait 2 minutes for enough players for a match. However, this won't happen: by the time we've waited that long we will have grown our search radius so far that we will have joined some other match already.

The result is that this algorithm isn't as good at finding a good matchup as one might think initially. We tried playing around with how quickly the search range grows and such, but we couldn't find a way that achieved a big enough improvement.

League-based matchmaking

Back then we got a lot of complaints about matchmaking not producing good match-ups, so we concluded that we needed something different. What we came up with was to add a league system to Awesomenauts and limit matchmaking based on that. We added this to the game in September 2012, a few months after launch. The idea is that we divide the leaderboards into 9 leagues, based on player skill. These leagues weren't just intended for matchmaking, but also for the player experience: it's cooler to be in league 2 than to be in place 4735, even though that might actually be the same thing.



The matchmaking rule we combined with these leagues is that players could only join matches in the 3 nearest leagues. So a league 4 player could join matches that are leagues 3, 4 or 5. A league 1 player (the top league) could only join matches in leagues 1, 2 and 3. Having such a hard limit should keep players from experiencing extremely big skill differences with their opponents or teammates.

For this to work you need to know the player's skill pretty well, so an important question is how well the game actually knows each player's skill. This is an important issue in any matchmaking system and is such a big topic that I'm not going to discuss this today. For today's blogpost let's just assume that the game has a somewhat decent idea what a player's actual skill is.

Another important issue is what to do if there are few players online. Having hard limits on who can join who means that in some cases you might not find opponents quickly enough. For this reason we stretched the allowed league range a bit further when few players were playing at that specific moment. The Steam API contains this information so implementing this is simple.

An easy mistake here is to simply split the leaderboards evenly. So for example if there are 90,000 players in the leaderboards, then numbers 80,001 to 90,000 are league 9. However, this doesn't work: some players play much more than others and players who stopped playing are still in the leaderboards. If these would be evenly spread out over the community this wouldn't be a problem, but of course they aren't: top players play much more than bottom players.

Our solution was that we measured how many matches were actually being played each day in each league and adjusted the league sizes based on that. Our implementation was bit clunky so we had to adjust this by hand occasionally, but it worked most of the time. The result is that league 2 is only a few percent of the leaderboards while league 9 is around 55 percent, resulting in equal numbers of matches being played every day in each league.



The league system was a big improvement for the matchmaking in Awesomenauts: not only did it make the matchmaker much better at matching similar players, it also provided a fun extra reward system, since wanting to be in a certain league is a fun challenge.

One specific problem with league based matchmaking is that going up a league makes too big a difference. If you go from the top of league 3 to the bottom of league 2 you suddenly get way better opponents, even though your own skill might have only marginally improved. Also, the skill difference between the top of a league and the bottom of that same league can be really huge, especially in the top leagues. While our matchmaker also looked for the best room to join in terms of exact skill (besides just the league requirements), it wasn't very good at this because of the problems with the growing-search-region algorithm I described earlier in this blogpost. A way to lessen this problem is to have more and smaller leagues, but we felt having dozens of leagues makes league climbing less fun for players.

The lack of server logic

While leagues were an improvement, this approach didn't fix the big problem that there's no logic running on the servers. Each client decides for themselves based on incomplete information. This is very limiting to how clever your matchmaking can be. There are lots of situations in which this algorithm will fail to produce optimal match-ups. Here's an example:



As you can see, in this case the algorithms described above fail to find the best possible match-up. Perfect matchmaking is impossible without huge player counts, but the matchmaker should do its best to find the best combinations with what's available.

Below is another example of a type of situation that this algorithm doesn't handle well. This one shows that this particular algorithm is particularly bad at matching premades with other premades: as soon as a single solo player joins, there's no room anymore for another premade that might start searching a little bit later.



Undoubtedly some super complex distributed algorithm is possible that can always find the optimal match-ups without any logic running on the servers. However, at that point the complexity of the algorithm becomes so high and debugging so difficult that I think running the matchmaking logic on a server instead is a much more viable solution. So we started developing our own matchmaking system (called Galactron) with our own servers. This was added to Awesomenauts in 2016.

In this post I've shown a number of problems we've encountered with generic room-based matchmaking systems and how we tried different approaches to work around those. However, not all of the issues with our early matchmaking approach were caused by the limitations of generic room-based matchmaking. Some issues were caused by how we had actually implemented our side of it. Those make for an interesting read by themselves so my next blogpost will be about the things we could have done better within the confines of generic room-based matchmaking.

Saturday, 23 December 2017

New song: Grom

Here's my newest song: "Grom"! It's a loud cello trio! I deliberately make the strings rattle a bit to get a more aggressive sound, which was a fun thing to fool around with.



This is actually an older composition: I wrote this one in 2012 to play together with the other cellists of the Kunstorkest, which I was a member of at the time. Since at the Kunstorkest we were supposed to play subtly and rarely truly loudly, I wanted to write something that's super loud and unsubtle, just for the fun of doing something different. At the time I never actually recorded it though, so I did that now and here it is! :)

Sheet music for this one can be found at music.joostvandongen.com. I've also made arrangements for violin and viola, which can also be found there.

PS. Until I took that photo I never realised how evil a cello's bridge can look...

Monday, 4 December 2017

The Daysailer and the Night Cave

I've finished a new song! It's a longer instrumental track with an extensive cello solo towards the end. :)



For this track I had a lot of fun playing around with delay (echo). The rhodes (the piano-like instrument that's heard throughout) has a rhythmic echo at every 8th note. This means that the rhodes is basically constantly playing harmonies with the notes it played just before, which is a pretty interesting effect. At 2:58 I even switch to playing triplets on the rhodes while the delay keeps going in normal 8th notes. So the echo and the original notes have a different rhythm there, which gives an even more interesting effect.

In case anyone wants to give playing it a try, here's the sheet music for the cello part, plus a recording of the song without the cello, to play along to:

This is the longest track I've finished so far and I'm really happy with the result. I hope you enjoy it! ^_^

Tuesday, 21 November 2017

Lament

I've recorded a new piece! It's a short sad cello solo called 'Lament'.

The composition itself isn't really new: I wrote it way back in 2001. However, I never managed to record it to my own satisfaction and thus never published it online. After all these years I've now finally managed to make a recording that I'm happy with. It's not perfect of course, but I finally dare publish it and share the sheet music.



In case anyone wants to give it a try, here's the sheet music:

I found another recording I made of this one from 2010. I wasn't happy with it back then and indeed, listening to it now makes me realise that I did get quite a bit better at recording my cello since then. Part of that is in technique, like having a better microphone, using a clicktrack and stitching together recordings to combine the best parts from several recordings. But I can also hear that I have more control of my cello now: especially my vibrato get better and there's less unwanted noises in my recordings now. I've been playing cello since I was a kid back in 1992 and it's really nice to hear that I'm still getting better at it by practising a lot in my spare time.

Sunday, 12 November 2017

The Master Waits

I've composed and recorded a new song! :) It's called The Master Waits and it's a duet for either two cellos, or viola and cello. Here's a recording:



I'd be honoured if anyone else were to play this (not that I expect many cellists read this blog ;) ), so here's the sheet music:

This composition came about when I was improvising a bit and discovered that you get a pretty cool sound if you pluck the open C string at every beat and then add various chords on top of that. I had so much fun with that that I decided to write a composition around this idea. :)

Initially I thought this one was pretty easy to play, but it turned out to be really hard to get the pitch exactly right for all of those chords. Keep in mind that unlike a guitar, a cello doesn't have frets, so if you're finger is only 1mm off, it already sounds bad. There's quite a lot of dissonance here (on 0:19 the plucking part even plays G and g# together) which is always difficult to play. On top of that comes that when plucking you can't listen and adjust the pitch as you go: it needs to be right immediately. Luckily I made different mistakes each time I recorded this piece, so with 4 recordings for each part I got every note right at least once. A somewhat sad score, but after stitching those recordings together it sounds great so it really doesn't matter.

I had a lot of fun composing and playing this one, so I hope others will have fun listening to it. Enjoy! :)

Sunday, 5 November 2017

The Light Deep Down

I've made a new song! It's an instrumental track that features a lot of cello, in combination with vocals and digital instruments.



There's more cello here than you might realise: the eerie scratching sound at the beginning and ending is also cello! :) Normally as a cellist you wouldn't want to make a sound like that, but here it adds to the atmosphere nicely. This sound is achieved by slowly playing on the open G or C string, too close to the bridge while applying too little pressure.

The cello solo at 1:57 has distortion applied to it, making it sound a bit closer to an electric guitar than a cello normally would.

I've made sheet music for the cello part, and a recording of the song without the cello so that it can be played along to. The result is quite different from any other cello music I know and I find it quite fun to play along to. Here it is, in case anyone wants to give it a try:

The vocals towards the end were sung by Joyce Scheeren and the faster bass in the second half was played by Thomas van Dijk.

I've been writing music for years but have always been struggling with actually finishing anything, so I'm really glad that I've managed to finish and share two new songs in just two weeks. I've got a bunch more almost finished, so I hope I can keep up the pace.

Tuesday, 24 October 2017

Never be ashamed of your process if the result is good

Over the years I've composed quite a few songs that include my cello, but I never dared actually record and release them. I did publish some recordings before, but I've always marked them as "unfinished" or "quick sketch" or some other excuse, planning to practice more and make a better recording later on. Today I finally have one that I consider "finished", but the process ended up quite different from what I expected back then. It's called Growl, and it's a loud cello duet. Have a listen!



I'd love for others to also play this composition, so I've made sheet music for it as well. Let me know if you end up playing this composition: I'd be honoured and would like to hear how it went!
I've also made a start with making a page that collects all my music and sheet music. It currently doesn't contain much yet, but I intend to record and release all my compositions. That means I have a lot of work ahead of me, as I need to record another duet, two solo cello pieces, two trios and a bunch of songs that combine cello with electronic instruments. I'll add songs to music.joostvandongen.com as soon as they're finished.

The reason I never finished recordings before is that playing cello well enough for a recording is incredibly difficult. This is difficult on any instrument and the particular challenge of cello is to play perfectly in tune. There are no frets like on a guitar, so place your fingers a millimeter too high or low and you're out of tune. Since most compositions require jumping around the fingerboard it's a huge challenge to always jump exactly the right amount.

I always figured I would solve this by practising more, and indeed I did practise quite a lot (for a hobby player, that is). However, by now I've played cello for over 25 years and I'm still not there. I'm not a professional cellist who can practice several hours every day for years, so I've finally concluded that I'm just not going to get good enough to live up to my own requirements. But I want to share my compositions! So I've reached a different conclusion: while I'm going to keep practising to get better, I'm henceforth also going to 'cheat' wherever needed to make recordings sound better.

I use two main cheats. One is that I play with a clicktrack: while recording I hear the ticks of a metronome on my headphones so that I play at a constant speed.

The other and bigger cheat is that I record the song a bunch of times. I then mix and match parts from each recording to get a complete recording that sounds acceptable. I tend to make different mistakes every time I play a song, so if I record it enough times I'm bound to get every note right at least once. Growl is a duet, so two cello parts, and each of the two cellos in Growl is a combination of six different recordings. Heck, if needed I can even use autotune to correct an individual note (this is used exactly once in Growl).

Mixing recordings together works a lot better than I had expected beforehand: if I mask the seams carefully then afterwards I can't even tell where they are. You might think you can hear them, but the lifting or shifting of the bow sounds so similar to a seam in the mix that you need to be a real specialist to be able to tell the difference.

Working like this makes me a bit cynical, since I wanted to be a good enough cellist to just record everything once and it's perfect, and clearly I'm not. However, if there's one thing game development has taught me, it's that it doesn't matter how you make something. The only thing that matters is the end result. If it's fun to play, then it doesn't matter whether the AI is truly intelligent or just pretending to be so. It's okay if everything is smoke and mirrors as long as the player doesn't notice it. The same goes for any creative endeavour: if it sounds/looks/feels good then it is good. There's no higher goal other then the end result and your creation isn't any worse or better depending on how you got there.