Estrategia / algoritmo para dividir equipos justos en función de la historia

20

Somos un grupo de personas que juegan al floorball juntos de manera regular. Cada sesión comienza con la desalentadora tarea de dividir equipos ...

Entonces, ¿qué sería mejor que una aplicación para elegir equipos automáticamente?

Entonces, dado un historial de combinaciones de equipos y resultados, y una lista de personas que se presentan a esta sesión en particular, ¿cuál sería una buena estrategia para encontrar los equipos óptimos? Por óptimo, quiero decir equipos lo más iguales posible.

¿Algunas ideas?

Editar: para que quede claro, los datos en los que tengo que basar la selección serían algo como esto:

[{ team1: ["playerA", "playerB", "playerC"],
   team2: ["playerD", "playerE", "playerF"],
   goals_team1: 10,
   goals_team2:  8 
 },
 { team1: ["playerD", "playerB", "playerC"],
   team2: ["playerA", "playerE", "playerG"],
   goals_team1:  2,
   goals_team2:  5
 },
 { team1: ["playerD", "playerB", "playerF"],
   team2: ["playerA", "playerE", "playerC"],
   goals_team1:  4,
   goals_team2:  2
 }]
Vegar
fuente
44
¿Qué es el floorball?
Dinámico
1
¿Supongo que solo tiene puntajes de equipo y ningún puntaje de contribución individual?
Gort the Robot
1
@ Dinámico: supongo que es otro nombre para Floor Hockey: el hockey se juega en el piso de un gimnasio con una pequeña pelota de goma en lugar de hielo con un disco (y no patines, por supuesto).
FrustratedWithFormsDesigner
2
Es posible que desee aclarar que la única información que se utilizará en este algoritmo es cuántos equipos ganadores / perdedores ha estado en cada jugador.
TehShrike
2
@TehShrike Para cada partido jugado, tengo información sobre quién jugó en qué equipo y cuál fue el puntaje final. P.ej. {Equipo1: ["a", "b", "c"], Equipo2: ["d", "e", "f"], Puntuación: "10-5"}
Vegar

Respuestas:

6

Lo primero a considerar, esto es para algo casual. No está diseñando un sistema para determinar rondas para la copa mundial de pelota de piso. Es para juegos casuales con un grupo de personas que disfrutan de un buen juego en lugar de una victoria desigual.

Recuerdo que Google tenía un generador de probabilidades de futbolín. Se trabajó un poco más en eso que yo en esto. Buscando una referencia para eso, encontré un artículo en SO y una calculadora True Skill que Microsoft usa para xbox .

Adoptando un enfoque mucho más simplista, cada jugador obtiene el puntaje de la proporción de puntos que su equipo tiene para el juego. Para el Juego 1, el jugador A obtendría 1.25 (10/8) mientras que el jugador D obtendría 0.8 puntos (8/10). Encuentra la media de todos los números y esa es la puntuación del jugador.

Para el conjunto de juegos descritos, esto proporciona:

  A 1.42
  B 1.22
  C 0.72
  D 1.07
  E 1.27
  F 1.40
  G 2.50

En este punto, tiene un problema similar al del problema de partición con la restricción de que cada equipo necesita el mismo número de jugadores y los valores no necesitan ser exactos (sino lo más cercanos posible).

Comunidad
fuente
El mismo número de jugadores, o lo más cerca posible si aparece un número impar de jugadores ;-)
Vegar
Gracias por la referencia al problema de partición ! Eres genial, @ user40980
Eric Gopak
3

Enfoque rápido y sucio:

Calcule un puntaje para cada jugador que sea el total de puntos para el lado en el que estaba ese jugador dividido por el total de puntos en el juego para cada juego en el que participó. Luego ordene a los jugadores por puntaje. Coloque al primer jugador en el equipo A. Luego, para cada jugador, agréguelos al equipo con el puntaje agregado más bajo hasta que la mitad de los jugadores estén en un equipo. Todos los jugadores restantes van al otro equipo.

Gort the Robot
fuente
Este enfoque puede funcionar, incluso si la combinación de personas dada es totalmente nueva.
Vegar
Hacerlo mejor parece una variante del problema de la mochila . Los pesos también pueden ser relevantes: según recuerdo, el jugador más pesado (yo) siempre fue el último elegido.
Steve314
Se sabe que este enfoque codicioso da una aproximación de 4/3 a la solución óptima (Wikipedia)
Radek
3

Si no desea profundizar en el embriagador mundo de los antecedentes bayesianos (pdf) y tal, un enfoque interesante es asignar un orden total a todos los jugadores (en función de la proporción de victorias / derrotas, puntos acumulativos, etc.) y luego dividir en Los equipos que utilizan la función de paridad son los siguientes

Tome la lista ordenada de jugadores (de mejor a peor) y sepárelos en equipos pares e impares según el número de 1 bits en su índice (comenzando en 0). Eso da la siguiente distribución:

  • 0000 (mejor) - Incluso
  • 0001 - impar
  • 0010 - impar
  • 0011 - Incluso
  • 0100 - impar
  • 0101 - Incluso
  • 0110 - Incluso
  • 0111 - impar

... etc.

La función de paridad asegurará un número igual de jugadores en cada equipo, para cualquier número par de jugadores. Luego se alternará dando la ventaja del jugador impar a un equipo u otro de tal manera que los efectos tienden a equilibrarse con el tiempo.

Esta función funciona mejor cuando la distribución de la habilidad del jugador es plana. En realidad, la habilidad del jugador tiende a seguir la distribución de "suma de valores aleatorios", también conocida como la gaussiana (aunque tenga cuidado con las aplicaciones generales de esa suposición en sistemas como TruSkill).

Para compensar las grandes brechas de habilidades, puede aplicar permutaciones a esta lista. Por ejemplo, para contrarrestar a un jugador superior 0000 muy fuerte, puede intercambiar el jugador 0011 con un jugador impar de menor rango, como 0100. Aquí es donde las cosas se ponen onduladas, pero al menos proporciona un buen punto de partida que no requieren una medida precisa de habilidad absoluta, pero simplemente un orden basado en la habilidad relativa.

Richard Nelson
fuente
2

Dependiendo de cuánto tiempo tenga, comience las primeras sesiones seleccionando aleatoriamente a los capitanes de equipo y obtenga un borrador antes de cada juego. Mantenga un registro de qué selección va un jugador. Las elecciones anteriores obtienen calificaciones más altas:

Round #1 = 8 pts, Round #2 = 6 pts, Round #3 = 4 pts, etc

Winning a game = 5 pts

Todo esto dependerá del número de jugadores por equipo. Es posible que sea necesario convertir los puntos totales a un promedio diario o del juego si hay una gran discrepancia en la participación. También puede otorgar un equipo por un margen de victoria mayor.

Los jugadores que fueron seleccionados temprano y jugaron en un equipo ganador obtienen la mayor cantidad de puntos de poder.

Luego, deje que la computadora haga el bosquejo (selección de equipos) equilibrando los puntos de poder para cada equipo y colocando equipos con calificaciones casi iguales entre sí. Los jugadores que sean seleccionados temprano, pero que continúen jugando en equipos perdedores caerán en la clasificación.

JeffO
fuente
¡Gran respuesta! Esto puede funcionar para el equipo promedio, pero algunos equipos son estratégicos. Por ejemplo, si quieres que todo tu equipo sea defensor, entonces tendrías peores jugadores en general en rondas más altas. Pero, supongo que no pedí canónico: P. ¡Gracias!
Dinámico
Esa es una excelente manera de comenzar. Durante las primeras rondas, cualquier cosa basada en la puntuación del equipo no se aplicará individualmente, ya que tendrás miembros del equipo que jugarán juntos en cada ronda.
Gort the Robot
1

La solución más fácil sería proporcionar una calificación / peso de la habilidad estimada e intentar equilibrar el puntaje de cada equipo.

A partir de ahí, podría sembrar una red bayesiana con estos valores y luego inferir hacia atrás en función del resultado observado de cada enfrentamiento en los datos históricos que tiene.

Como un punto de interés de mi parte: Infer.NET hace que esto sea relativamente fácil de imaginar y potencialmente implementar, y podría predecir las probabilidades de ganar dados los enfrentamientos de equipo. Infer.NET es algo en lo que realmente estoy empezando a entrar últimamente.

Steven Evers
fuente
¿Tendrían suficientes datos para ser significativos, dado que probablemente solo habría un puñado de juegos?
Gort the Robot
Esperaba resolver esto con javascript o ruby, pero infer.net se ve interesante de todos modos.
Vegar
@StevenBurnap: depende de cuán buenas / precisas sean tus conjeturas iniciales en cuanto a la habilidad del jugador, lo que tendrás que hacer para la mayoría o todos los sistemas. El beneficio de usar la red es que podrás inferir nuevas puntuaciones para cada jugador a medida que pase el tiempo para mejorar ese valor.
Steven Evers
1

Supongamos, en aras de la discusión, que puede asignar a cada jugador un valor entero y esos valores se suman, es decir, un jugador con puntaje X es tan valioso como tres jugadores con puntajes A, B y C, si A + B + C = X. El objetivo es entonces separar el grupo en dos equipos para que ambos equipos tengan aproximadamente el mismo valor sumado.

Esta es la versión de optimización del famoso problema de PARTICIÓN que es NP-complete. Por lo tanto, su problema es por lo que sabemos que es difícil de resolver. Sin embargo, PARTITION es débilmente NP-completo y admite algunas estrategias de aproximación razonables.

Un ejemplo es un enfoque codicioso similar a lo que propone Steven. Esta es una aproximación de 4/3, es decir, el equipo más fuerte nunca es más de un 33% más fuerte que una división óptima.

Tenga en cuenta que probablemente tenga restricciones adicionales, como que necesita al menos una cantidad fija de jugadores por equipo. Entonces, si pones a Michael Jordan en una clase de preescolares, no podrás crear equipos casi justos que tengan un número completo. Tal límite inferior (constante) en el tamaño del equipo no debería afectar la dureza del problema subyacente, pero podría destruir los límites de aproximación válidos para el problema general.

Rafael
fuente
1
No puedes meter muchos jugadores en el piso de un gimnasio. Con hasta 20 jugadores, suponiendo que quieras 10 de un lado, solo hay 92378 combinaciones para verificar. Pero no se necesitan muchos jugadores antes de que la cantidad de combinaciones haga que una búsqueda exhaustiva no sea práctica.
Kevin Cline
@kevincline: Correcto. Supuse implícitamente que la fuerza bruta no era una opción (de lo contrario, ¿por qué preguntar?).
Raphael
Nunca habría más de seis personas en cada equipo. Más a menudo cuatro.
Vegar
@Vegar: Entonces tu pregunta es más cómo explotar los puntajes del equipo para modelar el valor del jugador y menos sobre algoritmos, ¿verdad?
Raphael
1
A menos que pueda encontrar una manera de calificar a las personas exactamente por su talento, la precisión en el algoritmo probablemente no sea tan importante. Con el problema en mente, solo tenemos puntaje de equipo y un puñado de pruebas. Cualquier calificación de jugador será una estimación descabellada.
Gort the Robot
0

¿Qué tan ridículo quieres ser? Siempre puede usar la regresión lineal múltiple para generar coeficientes para cada jugador en función de los puntajes de sus equipos en juegos anteriores. Luego ordena la lista y selecciona.

En realidad, probablemente no funcionaría, ya que no modelar la dinámica entre los jugadores, sino que va a darle una razón para jugar con R . (<- mira, lo mantuve relacionado con la programación)

Gran maestro B
fuente
1
Estoy considerando hacer una aplicación para evitar una tarea de 2 minutos dos veces por semana, lo que me obliga a pasar casi la misma cantidad de tiempo registrando resultados para cálculos futuros. Supongo que bastante ridículo ...
Vegar
-1

Si desea que su algoritmo sea razonable, los algoritmos simples simplemente no lo cortarán. A menudo te darán resultados extraños

Tendrá que optar por algo como el sistema ELO o Trueskill (aunque ELO no funciona para equipos sin modificaciones).

catbert
fuente
1
Esto no es verdad Tiene que haber un algoritmo que funcione.
Dinámico