Algoritmo para crear equipos equitativos/equitativos según rankings de jugadores

Question

Tengo un conjunto de datos de clasificación de jugadores, edad y sexo de los jugadores, y me gustaría crear equipos igualados.

• Los equipos tendrán la misma cantidad de jugadores (actualmente 8 equipos de 12 jugadores).
• Los equipos deben tener la misma relación de hombre a mujer o similar.
• Los equipos deben tener una distribución/curva de edad similar.

Me gustaría probar esto en Haskell pero la elección del lenguaje de codificación es el aspecto menos importante de este problema.

Answer 1

Esto es bin packing problem, o multi-dimensional knapsack problem. Björn B. Brandenburg ha realizado a bin packing heuristics library in Haskell que puede serle útil.

Usted necesita algo así como ...

data Player = P { skill :: Int, gender :: Bool, age :: Int } 

decidir sobre un número de equipos n (supongo que esta es una función del número total de jugadores).

Encuentra la habilidad total deseada por equipo:

teamSkill n ps = sum (map skill ps)/n 

hallar la razón de género ideales:

genderRatio ps = sum (map (\x -> if gender x then 1 else 0))/length ps 

Encuentra la varianza edad ideal (que querrá el paquete Math.Statistics):

ageDist ps = pvar (map age ps) 

Y debe asignar las tres restricciones algunas ponderaciones para llegar a una puntuación para un equipo determinado:

score skillW genderW ageW team = skillW * sk + genderW * g + ageW * a 
    where (sk, (g, a)) = (teamSkill 1 &&& genderRatio &&& ageDist) team 

El problema se reduce a la minimización de la diferencia en los puntajes entre los equipos. Un enfoque de fuerza bruta llevará tiempo proporcional a Θ (n ^k-1). Dado el tamaño de su problema (8 equipos de 12 jugadores cada uno), esto se traduce a alrededor de 6 a 24 horas en una PC moderna típica.

EDITAR

Un enfoque que puede funcionar bien para usted (ya que no se necesita una solución exacta en la práctica) es recocido simulado, o mejora continua por permutación aleatoria:

1. Elige equipos al azar.
2. Obtenga una puntuación para esta configuración (consulte más arriba).
3. Cambia aleatoriamente jugadores entre dos o más equipos.
4. Obtenga un puntaje para la nueva configuración. Si es mejor que el anterior, consérvelo y repita el paso 3. De lo contrario, descarte la nueva configuración y pruebe el paso 3 nuevamente.
5. Cuando el puntaje no ha mejorado para un número fijo de iteraciones (experimente para encontrar la rodilla de esta curva), deténgase. Es probable que la configuración que tiene en este punto sea lo suficientemente cercana al ideal. Ejecute este algoritmo varias veces para ganar la confianza de que no ha alcanzado un óptimo local considerablemente peor que el ideal.

Answer 2

enfoque casi trivial para los dos equipos:

1. Ordenar todos los jugadores por su evaluación de habilidades/rango.
2. Asigna el equipo A al mejor jugador.
3. equipo B Asignar los próximos dos mejores jugadores
4. asignar un equipo de los próximos dos mejores jugadores
5. Goto 3
6. final cuando estás fuera de los jugadores.

No es muy flexible, y sólo funciona en una ranking de la columna, por lo que no tratará de obtener perfiles similares sexo o edad. Pero hace que los equipos sean equitativamente equilibrados si la distribución de entrada es razonablemente fluida. Además, no siempre termina cuando el equipo A tiene el jugador de repuesto cuando hay un número impar.

Answer 3

Idea:

1. Ordenar jugadores por la habilidad
2. Asignar a los mejores jugadores en orden (es decir: el equipo A: 1er jugador, equipo B: segundo jugador, ...)
3. Asignar peores jugadores en ordenar
4. Loop en 2
5. evaluar posibles correcciones y realizar ellos (es decir: si el equipo a tiene una habilidad total de 19 con un jugador con habilidad 5 y el equipo B tiene una habilidad total de 21 con un jugador con la habilidad 4, intercambiarlos)
6. evaluar las posibles correcciones sobre la distribución de género y realizar ellos
7. evaluar las posibles correcciones sobre la distribución de la edad y realizarlas

Answer 4

Dado el número de jugadores por equipo y la ración de género (que se puede calcular fácilmente). El problema restante se llama n-partition problem, que lamentablemente es NP-completo y, por lo tanto, es muy difícil de resolver exactamente. Tendrá que utilizar algoritmos aproximativos o heurísticos (algoritmos evolutivos), si el tamaño de su problema es demasiado grande para una solución de fuerza bruta. Una aproximación muy simple sería ordenar por edad y asignar de forma alterna.

Answer 5

1. valores de punto Asignar a los niveles de habilidad, el género y la edad
2. asignar la suma de los puntos para cada criterio a cada jugador
3. Ordenar jugadores por su valor de punto calculado
4. asignar el siguiente jugador al primer equipo
5. Asigna jugadores al segundo equipo hasta que tenga> = puntos totales que el primer equipo o que el equipo alcance el máximo de jugadores.
6. Realizar 5 para cada equipo, bucle de vuelta al primer equipo, hasta que todos los jugadores se les asigna

Usted puede ajustar el nivel de habilidad, el género, la edad y los valores de punto de cambiar la distribución de cada uno.

Answer 6

Bueno,

Mi respuesta no se trata de estrategias de puntuación de equipos/jugadores porque todo el publicado son buenos, pero me gustaría probar un fuerza bruta o una búsqueda al azar enfoque. No creo que valga la pena crear un algoritmo genético.

Atentamente.

Answer 7

Digamos que tiene seis jugadores (por ejemplo, una sencilla ). Podemos usar el mismo algoritmo que empareja a los oponentes en los torneos de eliminación simple y adaptarlo para generar equipos "pares" según los criterios que elija.

Primero clasifica a tus jugadores como mejores y peores. No tomes esto demasiado literalmente. Desea una lista de jugadores ordenados según los criterios que desee por separado ellos.

¿Por qué?

Veamos los torneos de eliminación simple por un segundo. La idea de utilizar un algoritmo para generar partidos de eliminación única óptima es evitar el problema de la reunión de los "mejores jugadores" demasiado pronto en el torneo. Si los mejores jugadores se encuentran demasiado pronto, uno de los mejores jugadores será eliminado al principio, haciendo que el torneo sea menos interesante. Podemos usar este emparejamiento "óptimo" para generar equipos en los que los jugadores "principales" estén repartidos uniformemente entre los equipos. Luego distribuya los segundos mejores jugadores, etc.

Por lo tanto, enumere a los jugadores por los criterios los quiere separados: hombres primero, luego mujeres ... ordenados por edad. Obtenemos (por ejemplo):

Player 1: Male - 18 
Player 2: Male - 26 
Player 3: Male - 45 
Player 4: Female - 18 
Player 5: Female - 26 
Player 6: Female - 45 

continuación, vamos a aplicar el algoritmo de eliminación directa que utiliza su "rango" (que es sólo su número de jugador) para crear "buenos duelos".

El generador de torneo de eliminación simple funciona básicamente como este: tome su rango (número de jugador) e invierta los bits (binario). Este nuevo número que se presenta se convierte en su "ranura" en el torneo.

Player 1 in binary (001), reversed becomes 100 (4 decimal) = slot 4 
Player 2 in binary (010), reversed becomes 010 (2 decimal) = slot 2 
Player 3 in binary (011), reversed becomes 110 (6 decimal) = slot 6 
Player 4 in binary (100), reversed becomes 001 (1 decimal) = slot 1 
Player 5 in binary (101), reversed becomes 101 (5 decimal) = slot 5 
Player 6 in binary (110), reversed becomes 011 (3 decimal) = slot 3 

En un torneo de eliminación simple, ranura 1 juega ranura 2, 3-vs-4, 5-vs-6. Vamos a utilizar estos "pares" para generar equipos óptimos.

Mirando el número de jugador anterior, pincha en "número de ranura", aquí está la lista que se nos ocurrió:

Slot 1: Female - 18 
Slot 2: Male - 26 
Slot 3: Female - 45 

Slot 4: Male - 18 
Slot 5: Female - 26 
Slot 6: Male - 45 

Al dividir las ranuras en equipos (dos o más) se obtiene los jugadores en la ranura 1-3 vs jugadores en la ranura 4-6. Esa es la agrupación mejor/óptima que puede obtener.

Esta técnica se adapta muy bien con muchos más jugadores, múltiples criterios (simplemente agrúpalos juntos correctamente) y múltiples equipos.