Test task from a game studio (matchmaking, analysis)

I came across this task during a recent job search – a St. Petersburg game development company offered to complete it before responding to HH (for the vacancy of a Go developer). That is, “send a response along with a link to your solution” or something like that. And I love test tasks – such a chance to quickly write some code from scratch and then calmly forget about it 🙂 Here the problem was not formulated very specifically – these seem to me more like a “reason to talk” – so it’s interesting to discuss such a case with the community, experts and sympathizers.

Problem and reasoning

Write a service that performs “matchmaking” of players by teams – that is, it forms teams of a given size N from a queue of players waiting to connect to the game server. In this case, you need to minimize:
– difference in skills
– network lag
– waiting time in line.

In other words, players come to the server and want to connect to the game. They are added to the waiting queue and each has a certain ID and two parameters (skill and lag). Waiting time is also supposed to be taken into account, but naturally it increases as you wait. Well, we want to unite players into teams while minimizing the totality of these parameters.

The problem is probably old. It's not complicated, but there are a lot of things you need to think about. For example, we decided that the easiest way to “minimize” is to select players with the minimum difference in performance for the next team. Let's look at an example.

Example: 4 players arrived at the same time, with the same lag – and their skills are distributed like this: 1050, 1180, 1220, 1350 – how to match them into teams of 2 people?

If we decide to choose players with the minimum difference each time, then first we need to choose a pair (1180, 1220) – their skill difference is only 40. Unfortunately, this will leave for the next team a pair (1050, 1350) with a difference of 300. Cotton and Tank using slang some games 🙂

This example shows that “minimization” in this context is not very well defined.

Another problem arises from the presence of “wait” in the algorithm. We are trying to operate not only with the data that we have (those players who are already in the queue) but also with our expectations for those who will still come. For example, in the example above, we can form two teams (1050, 1180) and (1220, 1350) so that none of them has a skill difference greater than 200 (of course, such teams should not be run against each other). But perhaps it would be more profitable to form only one team (1180, 1220) with a minimal difference – and leave the other two participants to wait until some more suitable candidates are added to the queue.

My approach to the solution

Since the author’s formulation left a huge field for uncertainty and freedom, I decided to make the proposed service quite flexible. From my modest experience in bigdata and recommenders (it’s a little similar – we’re basically building a recommender here too for selecting players and not goods), I imagine a situation in which the team usually has a separate person who comes up with the logic (a conditional data-scientist) – and one or several data engineers who bring this logic to sale in the form of services, databases, queues, and so on.

The solution can be made quite flexible if the matching algorithm itself in the service is implemented in a separate script. The more I thought, the more I liked this idea – the algorithm could be changed without rebuilding the code! This may be useful:

because matching in different games may require a different algorithm (do not compile different versions of the service)
because at different times of the day the load may vary (and the waiting time in line, for example)
because we may want to test some changes, for example on one of the cluster servers

In addition, if the algorithm is expressed in a separate small script, then this very conventional data scientist can write it – without resorting to developers with a notepad and asking them to “translate this into Go.”

So, the Go service itself – which scripting language to choose? Surely this is a holivar question, I decided to try Lua – if you haven’t heard much about it – it looks like Python, only simpler and smaller. Here, for example, is a “naive” script that assembles teams of players simply “in a row”, without taking into account their parameters:

assert(users, "global variable 'users' should be defined")
assert(group_size, "global variable 'group_size' should be defined")

group_count = math.floor(#users / group_size)

for i = 1, group_count do
    for j = 1, group_size do
        cur_user = users[(i-1) * group_size + j]
        cur_user['group'] = i
    end
end

Variables must be defined in advance (externally) in the script users (array of users waiting in queue) and group_size (team size). After the cycle runs, each user from the array will have a field group – and it contains the number of the team to which he is assigned. The same thing can be written differently, the main thing is not to assign team numbers to those few players who are “remaining” and do not form a full team – let them wait further.

The service code itself in Go is not very interesting (it’s in my github, you can look at it – but it’s probably not an example to follow) – it’s clear that it should accept requests, for example via HTTP, to connect a player, with the mentioned parameters – add players into the queue and periodically call the matchmaking script for this queue, which is currently loaded into this very service. According to the conditions, the generated commands just had to be printed into the console. There were also additional not very interesting details (provide that the queue could be stored in the database, etc.) – all this is approximately clear how to do it.

One interesting question is how this algorithm should scale. Let's say we feed a fairly large accumulated queue to the script input – and the script turns out to be complex, maybe compares everyone with everyone and so on (“quadratic” in time or worse) – how to make it so that it doesn't slow down?

After thinking a little, I came to the conclusion that this just doesn’t matter – if there are too many users, we scale “in breadth”, launching new instances of our matchmaker – and it would be ideal if all matchmakers have their own queues and are not interconnected. Indeed, if a user came and randomly “fell” into one of the queues, it doesn’t make much difference to him that he could match with players from other queues or only from this one – the main thing is that there are enough people in the queue to find a good match. That is, scaling occurs based on the size of the queues – for example, if we understand that more than 1000 people come to connect per second, it’s time to launch another instance.

Returning to the algorithm – what I proposed as a solution expressed by another script, only slightly longer (euclid_matcher.lua). At the beginning we consider a certain general value score for each player (based on skill and lag) – like a distance in Euclidean space where skill is on one axis, lag is on the other – only scaling coefficients can be changed, as well as linearity along the axes (for example, skill is logarithmic in nature).

score = {}

for i, user in ipairs(users) do
    s = math.sqrt(math.pow(user['skill'], 2) / 100 + 3 / (user['latency'] + 1))
    table.insert(score, {i, s})
end

table.sort(score, function(a, b) return a[2] < b[2] end)

Well, then we just go through the array score (sorted) and select teams of players of the required size in a row. Of course, this is not necessarily optimal – and does not explicitly take into account the “waiting time” – but by the very method of construction, we are confident that none of the players will have to wait too long (there will be no situation that many players who arrived later have already gone to play and you sit and wait – that is, the algorithm is still waiting for the best option).

I repeat, the main idea of such a solution is that I, as a programmer, am not trying to dream up an unknown algorithm based on data unknown to me and the customer’s desires – but I am providing a tool that will allow the customer (with minimal support from me) to implement different approaches and experiment.

Implementation details

Of the interesting details I encountered, perhaps only the interaction itself Go And Lua. The standard version of Lua is written to be embedded in C code. But I didn’t want to make any calls through an additional (and lower) level. So I found an implementation of Lua on Go itself (from Shopify, see the dependency on the github in go.mod) – although it has only been updated to version 5.2, but this is not a big problem.

At the same time, as in C, there was no magical, very simple method for calling the entire script by putting this and that into it. Therefore, I had to spend half an hour getting familiar with the basic principles of the Lua interpreter. To demonstrate what we're talking about, here's the code that loads the array users and a variable group_size:

    st := lua.NewState()
    lua.OpenLibraries(st)
    st.PushInteger(groupSize)
    st.SetGlobal("group_size")
    st.CreateTable(len(queue), 0)
    for i, user := range queue {
        st.PushInteger(i + 1)
        st.CreateTable(4, 0)
        st.PushString(user.Name)
        st.SetField(-2, "name")
        st.PushNumber(user.Skill)
        st.SetField(-2, "skill")
        st.PushNumber(user.Latency)
        st.SetField(-2, "latency")
        st.PushNumber(ts - user.Time)
        st.SetField(-2, "time")
        st.PushInteger(-1)
        st.SetField(-2, "group")
        st.SetTable(-3)
    }
    st.SetGlobal("users")

That is, we operate on the stack, there are calls to put the necessary values on the stack and then send them from the stack to global variables, or to an array (which is also right there on the stack) – hence all these slightly depressing “minus 2” indexes, etc. p. are positions on the stack of the Lua interpreter. Fortunately, this is all – there is no more similar code in the service (sampling the result looks simpler).

If you are interested in trying it out live, the code contains large and small tests in the form of simple shell scripts (in the /tests folder) – and a video presentation recorded for the inspectors.

Results

Feedback from potential employers (I had to remind the young lady to HR several times during further calls) was not very positive, something like this:

I don’t like that another language is involved in solving the problem (additional complexity), that the choice and implementation of the algorithm will not be made by the developer himself.

However, I was not at all upset about this – because… For me, a test task is also an opportunity to evaluate what is in the minds of my future potential colleagues, how similar or different we are in approaching problems. If they didn’t understand me (or I didn’t manage to make my idea clear enough) – and even with such a vague condition – we probably wouldn’t have made a good “match” 🙂

Moreover, the employer insistently wanted to work in the office, and I considered remote work as a priority – traveling across the whole city (from Pionerskaya to Ladozhskaya) is still not something you want to do every day in our times.

Conclusion

Having shared my, perhaps dubious and naive ideas, I would be glad to hear other thoughts from those who were not too lazy to scroll to the end 🙂 Have you ever added scripting to projects yourself (when it is clear that you can’t cope with configuration parameters alone) – or you have a negative attitude towards this (especially if the scripts are in some weird language). And how do you perceive test reports from employers?