Тестовое задание от гейм-студии (matchmaking, разбор)

На это задание я наткнулся в процессе недавнего поиска работы — питерская компания занимающаяся разработкой игр предлагала его выполнить до отклика на 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-у в ходе дальнейших созвонов) — был не очень позитивным, примерно так:

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

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

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

Заключение

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