SpawELO: un pequeño sistema gratuito de matchmaking para LAN parties

• SpawELO se creó para automatizar la selección de equipos en una LAN party de amigos que lleva 16 años, porque elegir equipos de Dota 2 a mano cada vez se volvió difícil.
• Debido a las diferencias de nivel y a la asistencia variable, el draft manual solía generar equipos parecidos repetidos y desequilibrios cuando había un número impar de personas.
• La primera implementación usó 35 partidas históricas y puntuaciones Elo para encontrar la combinación con la suma de puntos más cercana entre equipos, y luego ajustaba las puntuaciones reflejando repetidamente los resultados de las partidas.
• Tras cambiar a un modelo de predicción de tasa de victoria, se ajustó el Elo de los jugadores con pérdida L2 y retropropagación, pero al tratar todas las victorias como 100% apareció sobreajuste por memorizar partidas pasadas.
• El método final trata los resultados de las partidas como victorias probabilísticas del 75% o 95% para reducir el sobreajuste, y apunta a crear emparejamientos de equipos incluso con composiciones de número impar como 4v5.

---

El problema de elegir equipos que apareció en una LAN party

• El grupo de amigos organizó al menos una LAN party por año durante los últimos 16 años; normalmente dura 4 o 5 días y en los momentos pico participan unas 12 personas.
• El juego principal es Dota 2, y también juegan Counter-Strike, Wolfenstein: Enemy Territory, Warcraft 3 y Blobby Volley.
• Los asistentes llegan y se van a distintas horas, y algunos se ausentan a mitad de la reunión para cuidar a sus hijos, así que no siempre juegan con la misma cantidad de personas.
• Dota 2 normalmente se juega 5v5, una partida dura unos 40 minutos, y las partidas desbalanceadas como 4v5 suelen inclinarse hacia un lado.
• Dentro del grupo hay una mezcla de personas que juegan Dota 2 regularmente y otras que solo juegan durante la LAN party, por lo que hay una gran diferencia de nivel.

Límites del draft manual

• El método anterior normalmente consistía en que las dos personas mejores o con menos experiencia fueran líderes y eligieran integrantes por turnos, como al armar equipos en el patio de la escuela.
• El orden de selección era: el primer líder elegía a 1 persona, el segundo líder elegía a 2, luego el primero volvía a elegir 2, y al final cada líder elegía 1.
  • Era una variante para reducir la ventaja de quien elegía primero.
• Como la diferencia de nivel era grande, a menudo terminaban formándose equipos parecidos o iguales, y también se reducía la diversión de hacer el draft cada vez.
• Elegir equipos manualmente tomaba tiempo y era engorroso, y había el problema de que nadie quería ser líder.
  • Cuando la cantidad de personas no cuadraba, el desequilibrio de equipos era especialmente grande.

Primera implementación: partidas pasadas y suma de Elo

• Cuando creció la frustración con el proceso de selección de equipos en la última LAN party, se escribió rápidamente código para automatizarlo.
• Primero se recopilaron datos de 35 partidas pasadas y se cargaron en Colab; cada partida incluía la lista de jugadores del equipo ganador y del equipo perdedor.
• La idea básica era calcular la puntuación de cada jugador con Elo rating.
  • Todos los jugadores empiezan con 1000 puntos.
  • Al ganar, obtienen puntos; al perder, pierden puntos.
  • La probabilidad de victoria se calcula solo con la diferencia de Elo entre dos jugadores.
• La primera implementación simple sumaba 20 puntos a cada jugador ganador y restaba 20 puntos a cada jugador perdedor.
• La composición de equipos se generaba revisando todas las combinaciones de los jugadores solicitados y eligiendo la combinación con la menor diferencia en la suma de Elo del equipo.
  • En el ejemplo, se dividieron 8 personas en dos equipos; un equipo se calculó con 4100 puntos y el otro con 4080.

Mejora del modelo Elo con cálculo iterativo

• Se consideró que recorrer solo una vez las 35 partidas no aprovechaba suficientemente los datos, así que los datos históricos se procesaron repetidas veces.
• La actualización Elo mejorada no aplicaba simplemente ±20 puntos, sino que otorgaba más puntos al vencer a un rival más fuerte y restaba menos al perder contra un rival más fuerte.
  • Por ejemplo, si Spawek, con 1260 puntos, vence a Goovie, con 900 puntos, solo obtiene 4.47 puntos.
  • Si Status, con 900 puntos, vence a Dragon, con 1100 puntos, obtiene 30.38 puntos.
• Como el cálculo no era persona contra persona sino por equipos, se usaba la suma de Elo del equipo ganador y del perdedor, y los puntos de actualización se distribuían de forma equitativa entre los integrantes.
• Este método también se usó durante la LAN party, y después de cada partida se agregaban nuevos datos para volver a armar equipos durante el resto de la reunión.
• A veces, cuando se generaba un match claramente desbalanceado, se agregaba a los datos una “partida falsa” con el ganador esperado y luego se volvían a generar los equipos.

Segunda mejora: cambio a un modelo de predicción de tasa de victoria

• La siguiente mejora consistió en tratar el Elo no como una simple tabla de puntuaciones, sino como un modelo que predice la tasa de victoria del equipo.
• El modelo guarda el Elo de cada jugador y calcula la probabilidad de victoria comparando SUM(Elo) de los dos equipos.
• Se aplica una pérdida L2 simple al conjunto completo de datos de partidas.
  • Se calcula la suma de Elo del equipo ganador y del equipo perdedor.
  • Se calcula la probabilidad de victoria.
  • Se suma como pérdida el cuadrado de la diferencia entre la probabilidad real y la probabilidad predicha.
• Para el entrenamiento se usa backpropagation.
  • Con propagación hacia adelante se calcula la tasa de victoria predicha.
  • Con la pérdida y la derivada de la función de tasa de victoria se calcula cómo afecta el Elo de cada jugador a la pérdida.
  • Se actualizan los valores Elo con LEARNING_RATE = 10_000.0 e ITERATIONS = 10001.
• Este método logró reducir la pérdida, pero los valores Elo no convergieron.

Resultados de partidas probabilísticos para reducir el sobreajuste

• El modelo de estilo ML generó sobreajuste al tratar la tasa de victoria real de todas las partidas pasadas como 1.0, es decir, victoria del 100%.
• Al memorizar cada partida en vez de generalizar, en algunas partidas la tasa de victoria predicha se acercaba casi a 1, como 0.999994567526197.
• Como el objetivo no es codificar tal cual los resultados pasados, sino formar buenos equipos, se cambió el enfoque para usar resultados probabilísticos en lugar de victorias y derrotas deterministas.
• Al revisar más los registros de partidas pasadas, se dividió el carácter de las partidas en dos tipos.
  • En las partidas cerradas, la tasa de victoria real del equipo ganador se estableció en 75%.
  • En las partidas claramente inclinadas hacia un lado, la tasa de victoria real del equipo ganador se estableció en 95%.
• La diferencia de Elo necesaria para una tasa de victoria del 75% es de unos 200 puntos, y la diferencia de Elo necesaria para una tasa de victoria del 100% va desde unos 500 puntos hasta infinito, lo que dificulta que el modelo memorice todas las partidas.
• Después de cambiar las funciones loss y backpropagation para usar real_probability = game["win_probability"] en vez de real_probability = 1, la pérdida bajó rápidamente y el Elo de los jugadores convergió a un nivel razonable.

Lineups incluso con número impar de personas

• El nuevo sistema puede predecir la probabilidad de victoria y armar equipos incluso con número impar de personas.
• Un ejemplo del primer lineup para la LAN party que empieza en dos semanas es el siguiente:
  • team 1: Elo 2660
  • team 2: Elo 2655
• El lineup de ejemplo tiene 4 personas en un lado y 5 en el otro.
  • team 1: Spawek, Bixkog, Bania, Goovie
  • team 2: Hypys, Muhah, J, Vifon, Status

[GN⁺]

Opiniones en Hacker News

• Me pregunto si alguien ha usado en juegos por equipos algún enfoque que no esté basado en Elo/TrueSkill.
  Sumar o promediar el Elo del equipo para hacer matchmaking se siente como una solución provisional que fuerza un modelo pensado para matchmaking individual dentro del matchmaking por equipos.
  Además, se pierde mucha información de sinergias internas del equipo: A y B juntos pueden ser más fuertes que la suma de sus Elo individuales, mientras que A y C juntos pueden ser más débiles.

  • Creo que, en juegos por equipos, Elo termina haciendo que no quede nada más que victoria/derrota.
    En los deportes, aunque un equipo pierda, al final de la temporada puede salir un All-Star o un MVP; y, al revés, alguien puede estar en el equipo campeón sin ser una pieza clave.
    En los eSports por equipos todo está atado a ganar, así que no se rastrea ni se reconoce bien la expresión de jugadores como defensores, atacantes o soportes de primer nivel en toda la liga.
    Como en varios deportes, habría que seguir y reflejar cierto nivel de métricas avanzadas. Un jugador se parece más a valores como asistencias por partido, rebotes, puntos, carreras impulsadas o yardas, no al Elo en sí.
    Con eso sería fácil ver si a un equipo le hace más falta anotación o defensa, así que el matchmaking podría ajustarse de forma más natural que con “hace falta más ganadores/perdedores”.
  • Incluso donde ya se usa Elo, no se usa Elo puro. Los desarrolladores de juegos ajustan el matchmaking con factores como la cantidad de gente en la cola, el tiempo transcurrido desde la última partida, el número total de partidas jugadas, el historial de reportes o la cantidad de cosméticos comprados.
    La fortaleza de Elo está en que aporta mucha información en relación con su costo. La clave es que es un solo número que representa todo.
    No explica a la perfección la hermosa diversidad de la naturaleza, pero se acerca a ser la abstracción más eficiente que contiene el 70% de lo que hace falta saber sobre la habilidad del rival.
  • Estoy de acuerdo. Elo es tosco, pero es un modelo estadístico simple, y su mayor ventaja es que es fácil de entender y razonar.
    Sería bueno tener un vector multidimensional de habilidad del jugador o embeddings con más información, y encima de eso modelos más no lineales.
    Por ejemplo, en muchos juegos un equipo normalmente necesita jugadores de soporte, pero un solo número no alcanza para incorporar esa información al matchmaking.
  • Lo he pensado bastante, pero no creo que exista una única solución definitiva; cambia mucho según la disciplina y las variantes de reglas que se jueguen.
    Por ejemplo, en el futbolito hay jugadores que juegan tanto singles como dobles, y dos defensores excelentes en el mismo equipo pueden perder contra rivales más débiles que encajan mejor en cada posición.
    También son distintos juegos como Counter-Strike, Apex, Overwatch y, en cierta medida, Dota, donde el equipo puede sostener mucho. En Counter-Strike, un compañero débil, con poca habilidad o sin audífonos, puede arruinar toda la partida; en Overwatch, puede elegir una clase de soporte, relajarse atrás y esperar a que el resto del equipo gane.
    También está la química. Como se ve en el trabajo, las sinergias que solo aparecen en ciertas combinaciones, o simples diferencias de estilo de juego, pueden cambiar el resultado.
    Incluso en variantes de billar que parecen similares, algunos jugadores brillan en una modalidad pero no les va tan bien en otra.
  • Una vez probé PageRank y funcionó bastante bien. Traté las victorias como enlaces, hice que la puntuación fluyera del perdedor al ganador y que la fuerza del enlace disminuyera con el tiempo.

• Creo que Kaggle tuvo, o todavía tiene, una competencia sobre sistemas de rating.
  https://www.kaggle.com/competitions/chess/discussion/107
  Hay bastantes sistemas de rating que rinden mejor que Elo.

  • En la tabla de posiciones solo se ven los nombres de los participantes; me pregunto cómo se puede consultar el método de cada uno.

• Para torneos me gusta el sistema suizo, que entiendo es popular en ajedrez.
  [1]: https://en.wikipedia.org/wiki/Swiss-system_tournament

  • Como dato interesante, nuestra comunidad local empezó hace poco torneos de billar con sistema suizo y funciona bastante bien. Eso sí, hay un compromiso entre la equidad y la cantidad de jugadores que se puede invitar.
    Con el formato suizo, para 6 rondas conviene un máximo de unas 40 personas, pero si quieres invitar a más de 100 hay que usar un cuadro de doble eliminación. Si no, el torneo dura una semana.
    Lo mejor es la relación costo-beneficio. Independientemente del resultado, sigues jugando durante todo el torneo y, a medida que avanza, los rivales se ajustan a tu nivel, así que todos pueden divertirse.
  • También es común en torneos de Magic y otros juegos de cartas, aunque se usa con algunas modificaciones. Es frecuente ver formatos como “6 rondas suizas y luego eliminación simple entre los 8 mejores”.
  • Leyéndolo por encima, después de enfrentarte a un equipo aleatorio en la primera ronda, en cada ronda se ordena a los jugadores por puntaje acumulado y se los empareja contra rivales con el mismo puntaje o uno parecido. Al mismo tiempo, se evita enfrentar dos veces al mismo rival.
    No tengo claro cómo se decide cuántas rondas hacer, aunque no sé si ese detalle es lo esencial.
    Según la sección de análisis, comparado con un torneo de eliminación directa, y suponiendo que no hay empates, la cantidad de rondas necesarias para determinar un ganador claro es la misma.
    El sistema suizo tiene la ventaja de no eliminar a nadie y de que la clasificación final muestra en cierta medida no solo al ganador, sino también la habilidad relativa de todos los participantes.
    Eso sí, si un jugador se despega demasiado, puede asegurar el campeonato antes de la última ronda, así que no siempre termina con un desenlace dramático.

• Me pregunto qué tal sería probar con el valor de Shapley.

  • No sabía qué significaba, así que lo busqué: es un concepto de solución en teoría de juegos cooperativos, llamado así por Lloyd Shapley, y asigna de forma única a cada jugador el excedente total generado por la coalición completa de jugadores.
    Es casi tal cual la introducción de Wikipedia, pero aun después de leerla no lo entiendo bien. Me pregunto qué sería aquí el excedente total de un juego cooperativo; ¿algo como la cantidad de madera reunida por un equipo en AoE?
    Tampoco entiendo cómo ayudaría “asignarlo”, y me da la impresión de que más bien debería ser el resultado del juego. Me gustaría que alguien pudiera explicarlo en términos sencillos.