Tarea de prueba de un estudio de juegos (emparejamiento, análisis) / Sudo Null IT News

Me encontré con esta tarea durante una búsqueda de trabajo reciente: una empresa de desarrollo de juegos de San Petersburgo se ofreció a completarla antes de responder a HH (para la vacante de desarrollador de Go). Es decir, “enviar una respuesta junto con un enlace a su solución” o algo así. Y me encantan las tareas de prueba: es una gran oportunidad para escribir rápidamente un código desde cero y luego olvidarlo con calma 🙂 Aquí el problema no se formuló de manera muy específica; me parecen más bien una “razón para hablar”, por lo que es interesante discutir tal caso con la comunidad, expertos y simpatizantes.

Problema y razonamiento

Escriba un servicio que realice “emparejamiento” de jugadores por equipos, es decir, forme equipos de un tamaño determinado N a partir de una cola de jugadores que esperan conectarse al servidor del juego. En este caso, es necesario minimizar:

En otras palabras, los jugadores llegan al servidor y quieren conectarse al juego. Se agregan a la cola de espera y cada uno tiene una ID determinada y dos parámetros (habilidad y retraso). El tiempo de espera también debe tenerse en cuenta, pero, naturalmente, aumenta a medida que se espera. Bueno, queremos unir a los jugadores en equipos minimizando la totalidad de estos parámetros.

Probablemente el problema sea antiguo. No es complicado, pero hay muchas cosas en las que debes pensar. Por ejemplo, decidimos que la forma más sencilla de “minimizar” es seleccionar jugadores con la mínima diferencia de rendimiento para el siguiente equipo. Veamos un ejemplo.

Ejemplo: 4 jugadores llegaron al mismo tiempo, con el mismo retraso – y sus habilidades se distribuyen así: 1050, 1180, 1220, 1350 – ¿cómo unirlos en equipos de 2 personas?

Si decidimos elegir jugadores con la diferencia mínima cada vez, primero debemos elegir un par (1180, 1220); su diferencia de habilidades es solo 40. Desafortunadamente, esto dejará un par para el siguiente equipo (1050, 1350). con una diferencia de 300. Cotton y Tank usando jerga algunos juegos 🙂

Este ejemplo muestra que la “minimización” en este contexto no está muy bien definida.

Otro problema surge de la presencia de “espera” en el algoritmo. Estamos tratando de operar no sólo con los datos que tenemos (los jugadores que ya están en la cola) sino también con nuestras expectativas para los que aún vendrán. Por ejemplo, en el ejemplo anterior, podemos formar dos equipos (1050, 1180) y (1220, 1350) para que ninguno de ellos tenga una diferencia de habilidades superior a 200 (por supuesto, dichos equipos no deben competir entre sí). . Pero quizás sería más rentable formar un solo equipo (1180, 1220) con una diferencia mínima y dejar que los otros dos participantes esperen hasta que se agreguen a la cola algunos candidatos más adecuados.

Mi enfoque hacia la solución.

Dado que la formulación del autor dejaba un enorme campo de incertidumbre y libertad, decidí flexibilizar bastante el servicio propuesto. Desde mi modesta experiencia en bigdata y recomendadores (es un poco similar: básicamente también estamos creando un recomendador aquí también para seleccionar jugadores y no productos), imagino una situación en la que el equipo generalmente tiene una persona separada a la que se le ocurre la lógica. (un científico de datos condicional) – y uno o varios ingenieros de datos que ponen a la venta esta lógica en forma de servicios, bases de datos, colas, etc.

La solución puede ser bastante flexible si el propio algoritmo de coincidencia en el servicio se implementa en un script separado. Cuanto más pensaba, más me gustaba esta idea: ¡el algoritmo se podía cambiar sin reconstruir el código! Esto puede resultar útil:

porque emparejar en diferentes juegos puede requerir un algoritmo diferente (no compilar diferentes versiones del servicio)
porque en distintos momentos del día la carga puede variar (y el tiempo de espera en la fila, por ejemplo)
porque es posible que queramos probar algunos cambios, por ejemplo, en uno de los servidores del clúster

Además, si el algoritmo se expresa en un pequeño script separado, entonces este científico de datos muy convencional puede escribirlo, sin recurrir a los desarrolladores con un bloc de notas y pedirles que “traduzcan esto a Go”.

Entonces, el servicio Go en sí: ¿qué lenguaje de programación elegir? Seguramente esta es una pregunta holivar, decidí probar Lua; si no has oído mucho sobre él, se parece a Python, solo que más simple y más pequeño. Aquí, por ejemplo, hay un guión “ingenuo” que reúne equipos de jugadores simplemente “en una fila”, sin tener en cuenta sus parámetros:

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

Las variables deben definirse de antemano (externamente) en el script. usuarios (conjunto de usuarios esperando en cola) y tamaño_grupo (tamaño del equipo). Después de que se ejecute el ciclo, cada usuario de la matriz tendrá un campo grupo – y contiene el número del equipo al que está asignado. Lo mismo se puede escribir de otra manera, lo principal es no asignar números de equipo a los pocos jugadores que “quedan” y no forman un equipo completo; déjelos esperar más.

El código de servicio en Go en sí no es muy interesante (está en mi github, puedes verlo, pero probablemente no sea un ejemplo a seguir): está claro que debería aceptar solicitudes, por ejemplo a través de HTTP, para conectar un reproductor. con los parámetros mencionados: agregue jugadores a la cola y llame periódicamente al script de emparejamiento para esta cola, que actualmente está cargado en este mismo servicio. Según las condiciones, los comandos generados sólo tenían que imprimirse en la consola. También hubo detalles adicionales no muy interesantes (siempre que la cola se pueda almacenar en la base de datos, etc.); todo esto está aproximadamente claro sobre cómo hacerlo.

Una pregunta interesante es cómo debería escalar este algoritmo. Digamos que alimentamos una cola acumulada bastante grande a la entrada del script, y el script resulta ser complejo, tal vez compara a todos con todos y así sucesivamente (“cuadrático” en el tiempo o peor): cómo hacerlo para que no ¿No disminuyes la velocidad?

Después de pensar un poco, llegué a la conclusión de que esto simplemente no importa: si hay demasiados usuarios, escalamos “en amplitud”, lanzando nuevas instancias de nuestro casamentero, y sería ideal si todos los casamenteros tuvieran el suyo propio. colas y no están interconectados. De hecho, si un usuario vino y “cayó” accidentalmente en una de las colas, no le importa mucho que pueda coincidir con jugadores de otras colas o solo de ésta; lo principal es que haya suficientes personas. en la cola para encontrar una buena coincidencia. Es decir, el escalado se produce según el criterio del tamaño de las colas; por ejemplo, si entendemos que más de 1000 personas por segundo se conectan, es hora de lanzar otra instancia.

Volviendo al algoritmo – lo que propuse como solución expresado por otro script, sólo un poco más largo (euclid_matcher.lua). Al principio consideramos un cierto valor general. puntaje para cada jugador (según la habilidad y el retraso), como una distancia en el espacio euclidiano donde la habilidad está en un eje y el retraso en el otro, solo se pueden cambiar los coeficientes de escala, así como la linealidad a lo largo de los ejes (por ejemplo, la habilidad es de naturaleza logarítmica).

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)

Bueno, entonces simplemente repasamos la matriz. puntaje (ordenados) y seleccione equipos de jugadores del tamaño requerido en una fila. Por supuesto, esto no es necesariamente óptimo, y no tiene en cuenta explícitamente el “tiempo de espera”, pero por el método de construcción en sí, estamos seguros de que ninguno de los jugadores tendrá que esperar demasiado (no habrá ninguna situación que muchos jugadores que llegaron más tarde ya se han ido a jugar y tú te sientas a esperar (es decir, el algoritmo todavía está esperando la mejor opción).

Repito, la idea principal de tal solución es que yo, como programador, no estoy tratando de idear un algoritmo desconocido basado en datos desconocidos para mí y los deseos del cliente, sino que estoy proporcionando una herramienta que permitirá cliente (con un mínimo apoyo de mi parte) para implementar diferentes enfoques y experimentar.

Detalles de implementación

De los detalles interesantes que encontré, tal vez sólo la interacción en sí. Ir y lua. La versión estándar de Lua está escrita para integrarse en código C. Pero no quería hacer ninguna llamada a través de un nivel adicional (e inferior). Entonces encontré una implementación de Lua on Go (de Shopify, vea la dependencia de github en go.mod), aunque solo se actualizó a la versión 5.2, pero esto no es un gran problema.

Al mismo tiempo, como en C, no existía un método mágico y muy simple para llamar el script completo poniendo esto y aquello en él. Por lo tanto, tuve que dedicar media hora a familiarizarme con los principios básicos del intérprete de Lua. Para demostrar de qué estamos hablando, aquí está el código que carga la matriz. usuarios y una variable tamaño_grupo:

    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")

Es decir, operamos en la pila, hay llamadas para colocar los valores necesarios en la pila y luego enviarlos desde la pila a variables globales o a una matriz (que también está allí en la pila), de ahí todo estos índices “menos 2” ligeramente deprimentes, etc. p. son posiciones en la pila del intérprete de Lua. Afortunadamente, esto es todo: ya no hay ningún código similar en el servicio (muestrear el resultado parece más simple).

Si está interesado en probarlo en vivo, el código contiene pruebas grandes y pequeñas en forma de scripts de shell simples (en la carpeta /tests) y una presentación en video grabada para los inspectores.

Resultados

Los comentarios de posibles empleadores (tuve que recordarle a la joven que hablara con Recursos Humanos varias veces durante las siguientes llamadas) no fueron muy positivos, más o menos así:

No me gusta que otro lenguaje esté involucrado en la resolución del problema (complejidad adicional), que la elección e implementación del algoritmo no la haga el propio desarrollador.

Sin embargo, esto no me molestó en absoluto, porque… Para mí, una tarea de prueba es también una oportunidad para evaluar lo que piensan mis futuros colegas potenciales, en qué medida somos similares o diferentes a la hora de abordar los problemas. Si no me entendieron (o no logré dejar mi idea lo suficientemente clara) – e incluso con una condición tan vaga – probablemente no hubiéramos hecho una buena “combinación” 🙂

Además, el empleador quería insistentemente trabajar en la oficina y yo consideraba el trabajo remoto como una prioridad: viajar por toda la ciudad (desde Pionerskaya hasta Ladozhskaya) todavía no es algo que quieras hacer todos los días en nuestros tiempos.

Conclusión

Habiendo compartido mis ideas, quizás dudosas e ingenuas, me encantaría escuchar otros pensamientos de aquellos que no fueron demasiado vagos para desplazarse hasta el final 🙂 ¿Alguna vez ha agregado secuencias de comandos a proyectos usted mismo (cuando está claro que no puede? lidiar solo con los parámetros de configuración), o tiene una actitud negativa hacia esto (especialmente si los scripts están en algún lenguaje extraño). ¿Y cómo percibe los informes de las pruebas de los empleadores?