На это задание я наткнулся в процессе недавнего поиска работы - питерская компания занимающаяся разработкой игр предлагала его выполнить до отклика на HH (на вакансию Go-разработчика). То есть "присылайте отклик вместе со ссылкой на ваше решение" или в этом духе. А я обожаю тестовые задания - такой шанс быстро напедалить с нуля какой-то код и потом спокойно про него забыть :) Здесь задачка была сформулирована не слишком конкретно - мне такие кажутся скорее "поводом поговорить" - поэтому любопытно обсудить подобный кейс с сообществом, знатоками и сочувствующими.

Задача и рассуждения

Написать сервис осуществляющий "matchmaking" игроков по командам - то есть формирующий команды заданного размера N из очереди игроков ожидающих подключения к игровому серверу. При этом нужно минимизировать:

• разницу в скиллах

• сетевой лаг

• время ожидания в очереди.

Иными словами, на сервер приходят игроки и хотят подключиться к игре. Они добавляются в очередь ожидания и у каждого есть некий айдишник и два параметра (скилл и лаг). Время ожидания также предполагается учитывать, но естественно оно растёт по мере ожидания. Ну и мы хотим объединять игроков в команды минимизируя совокупность этих параметров.

Задачка наверняка старая. Несложная, но в ней много моментов о которых надо подумать. Например, мы решили что "минимизировать" проще всего если выбирать для очередной команды игроков с минимальной разницей показателей. Рассмотрим пример.

Пример: пришли 4 игрока, одновременно, с одинаковым лагом - а скиллы у них распределены так 1050, 1180, 1220, 1350 - как их смэтчить в команды по 2 человека?

Если мы решим выбирать каждый раз игроков с минимальной разницей - то сначала нужно выбрать пару (1180, 1220) - их разница скиллов всего 40. К сожалению это оставит для следующей команды пару (1050, 1350) с разницей 300. Вата и Танк пользуясь сленгом некоторых игр :)

Этот пример показывает что "минимизация" в данном контексте не очень-то хорошо определена.

Другая проблема возникает из-за присутствия "ожидания" в алгоритме. Мы пытаемся оперировать не только теми данными которые есть (теми игроками что уже в очереди) но и нашими ожиданиями на тех которые ещё придут. Например в примере выше мы можем сформировать две команды (1050, 1180) и (1220, 1350) с тем чтобы ни в одной из них не было разницы скилла больше 200 (конечно такие команды не стоит запускать друг против друга). Но возможно выгоднее было бы сформировать только одну команду (1180, 1220) с минимальной разницей - а двух других участников оставить ждать пока в очередь добавятся какие-то более подходящие кандидаты.

Мой подход к решению

Поскольку в авторской формулировке оставалось огромное поле для неопределенности и свободы, я решил сделать предлагаемый сервис достаточно гибким. Из своего скромного опыта в бигдате и рекоммендерах (немножко похоже - мы и тут в общем-то строим рекоммендер для подбора игроков а не товаров) я представляю ситуацию так что в команде обычно есть отдельный человек придумывающий логику (условный data-scientist) - и один либо несколько дата-инженеров которые эту логику доводят до прода в виде сервисов, баз, очередей и так далее.

Достаточно гибким решение можно сделать если сам алгоритм мэтчинга в сервисе будет воплощён отдельным скриптом. Чем больше я думал, тем больше мне нравилась эта идея - алгоритм можно будет менять без пересборки кода! Это может быть полезно:

• потому что для мэтчинга в разных играх может требоваться разный алгоритм (не компилировать же разные версии сервиса)

• потому что в разное время суток нагрузка может различаться (и время ожидания в очереди например)

• потому что мы можем захотеть потестировать какие-то изменения, например на одном из серверов кластера

Кроме того - если алгоритм выражается отдельным небольшим скриптом, то его может писать этот самый условный дата-сайентист - не прибегая к разработчикам с блокнотом и прося "переложить вот это на Go".

Итак, сам сервис на Go - какой скриптовый язык выбрать? Наверняка это вопрос холиварный, я решил попробовать Lua - если вы мало про него слышали - он смахивает на Python только проще и меньше. Вот к примеру "наивный" скрипт который собирает команды игроков просто "подряд", без учёта их параметров:

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

В скрипте должны быть заранее (извне) определены переменные users (массив ожидающих в очереди пользователей) и group_size (размер команды). После работы цикла у каждого пользователя из массива будет проставлено поле group - и в нём номер команды к которой он причислен. То же самое можно написать и иначе, главное не назначать номера команды для тех нескольких игроков которые "в остатке", не образуют полной команды - пусть ждут дальше.

Сам код сервиса на Go - это не очень интересно (лежит у меня в гитхабе, можно смотреть - но это не пример для подражания наверное) - понятно что он должен принимать запросы, например по HTTP, на подключение игрока, с упомянутыми параметрами - складывать игроков в очередь и периодически вызывать для этой очереди скрипт matchmaking-а который в этот самый сервис на данный момент загружен. По условиям сформированные команды нужно было просто напечатать в консоль. Там были и дополнительные не очень интересные детали (предусмотреть чтобы очередь могла храниться в базе и т.п.) - всё это примерно понятно как сделать.

Из любопытных вопросов - как этот алгоритм должен масштабироваться. Допустим мы подаём на вход скрипта достаточно большую накопившуюся очередь - а скрипт окажется сложным, может быть сравнивает каждого с каждым и так далее ("квадратичный" по времени или хуже) - как сделать так чтобы это не тормозило?

Немного подумав я пришёл к выводу что вот это как раз неважно - если юзеров слишком много, мы масштабируемся "вширь", запуская новые инстансы нашего matchmaker-а - и идеально будет если очереди у всех мэтчмэйкеров свои и не связаны между собой. Действительно, если юзер пришёл и рандомно "упал" в одну из очередей - для него нет особой разницы что он мог бы смэтчиться с игроками из других очередей или только из этой - главное чтобы в очереди было достаточное количество людей чтобы нашёлся хороший мэтч. То есть масштабирование происходит по критерию размера очередей - например если мы понимаем что за секунду на подключение приходит больше 1000 человек - пора запускать ещё один инстанс.

Возвращаясь к алгоритму - то что я предложил в качестве решения выражено другим скриптом, лишь чуть более длинным (euclid_matcher.lua). В его начале мы считаем некое общее значение score для каждого игрока (основываясь на скилле и лаге) - как расстояние в евклидовом пространстве где по одной оси скилл, по другой лаг - только масштабирующие коэффициенты можно менять, как и линейность по осям (например скилл ведь имеет логарифмический характер).

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)

Ну и дальше мы просто идём по массиву score (отсортированному) и выбираем команды игроков нужного размера подряд. Безусловно это не обязательно оптимально - и не учитывает явным образом "время ожидания" - но по самому способу построения мы зато уверены что никому из игроков не придётся ждать слишком долго (не будет ситуации что много игроков пришедших позже уже отправились играть а ты сидишь и ждёшь - то есть алгоритм всё ждёт лучшего варианта).

Повторюсь, главный замысел такого решения в том, что я как программист не пытаюсь фантазировать неизвестный алгоритм исходя из неизвестных мне данных и желаний заказчика - а предоставляю инструмент который заказчику (при минимальной моей поддержке) позволит воплощать разные подходы и экспериментировать.

Детали реализации

Из интересных деталей встретившихся мне - только пожалуй само взаимодействие Go и Lua. Стандартная версия Lua написана в расчете на встраивание в С-шный код. Но делать какие-то вызовы через дополнительный (и более низкий) уровень мне не хотелось. Так что я нашёл реализацию Lua на самом Go (от Shopify, смотри зависимость на гитхаб в go.mod) - правда она доведена лишь до версии 5.2, но это не большая беда.

При этом как и в Си, здесь не оказалось какого-то волшебного очень простого метода для того чтобы вызвать скрипт целиком проставив в него то да сё. Поэтому пришлось потратить полчасика на то чтобы освоиться в общих чертах с базовыми принципами работы интерпретатора Lua. Чтобы продемонстрировать о чем речь - вот код который загружает массив users и переменную 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")

То есть мы оперируем на стеке, есть вызовы чтобы поместить в стек нужные значения а потом из стека отправить их в глобальные переменные, или в массив (который тоже тут же на стеке) - отсюда все эти немного удручающие индексы "минус 2" и т.п. - это позиции на стеке интерпретатора Lua. К счастью это и всё - больше подобного кода в сервисе нет (выборка результата выглядит проще).

Если вам интересно станет "погонять" это живьём - в коде есть большой и маленький тесты в виде простых шелл-скриптов (в папочке /tests) - ну и видео-презентация записанная для проверяющих.

Результаты

Фидбэк от потенциальных работодателей (пришлось несколько раз напоминать барышне HR-у в ходе дальнейших созвонов) - был не очень позитивным, примерно так:

Не нравится что в решение задачи вовлечён другой язык (дополнительная сложность), что выбор и реализацию алгоритма не будет делать сам разработчик.

На этот счет впрочем я абсолютно не расстроился - т.к. для меня тестовое задание это и возможность оценить что в голове у моих будущих потенциальных коллег, насколько схоже или по-разному мы подходим к решению проблем. Если они меня не поняли (или мне не удалось сделать свою идею достаточно понятной) - да ещё при таком расплывчатом условии - наверное из нас не получилось бы хорошего "мэтча" :)

Тем более что работодатель настойчиво желал работы в офисе а я в приоритете рассматривал удалёнку - ездить через весь город (с Пионерской на Ладожскую) всё же по нашим временам не каждый день хочется.

Заключение

Поделившись своими, быть может сомнительными и наивными идеями, я был бы рад услышать и другие мысли от тех, кто не поленился доскроллить до конца :) Случалось ли вам самим добавлять скриптинг в проекты (когда ясно что одними конфигурационными параметрами уже не справишься) - или вы относитесь к этому негативно (особенно если скрипты на каком-нибудь заморочном языке). И как воспринимаете тестовые задния от работодателей.