scouting herramienta futbol algorithm language-agnostic haskell functional-programming

algorithm - herramienta - Algoritmo para crear equipos equitativos/pareados en función de la clasificación de los jugadores



scouting futbol es la herramienta (7)

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

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

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

  1. Asigna valores de puntos a los niveles de habilidad, género y edad.
  2. Asigna la suma de los puntos para cada criterio a cada jugador.
  3. Ordenar jugadores por su valor en puntos calculado
  4. Asigna el siguiente jugador al primer equipo.
  5. Asigne jugadores al segundo equipo hasta que tenga> = puntos totales que el primer equipo o el equipo alcance el máximo de jugadores.
  6. Realiza 5 para cada equipo, regresando al primer equipo, hasta que todos los jugadores estén asignados

Puede modificar los valores de nivel de habilidad, género y edad para cambiar la distribución de cada uno.

Bien,

Mi respuesta no es acerca de las estrategias de puntuación de los equipos / jugadores porque todos los publicados son buenos, pero probaría una fuerza bruta o un enfoque de búsqueda aleatoria . No creo que valga la pena crear un algoritmo genético.

Saludos.

Dado el número de jugadores por equipo y la ración de género (que puede calcular fácilmente). El problema restante se llama problema de n-partición , que desafortunadamente es NP-completo y, por lo tanto, muy difícil de resolver exactamente. Deberá usar 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 la clasificación por edad y la asignación de una manera alternativa.

Digamos que tienes seis jugadores (para un ejemplo simple ). Podemos usar el mismo algoritmo que une a los oponentes en torneos de eliminación simple y adaptarlos para generar equipos "par" basados ​​en el criterio que elija.

Primero clasifica a tus jugadores de mejor a peor. No tomes esto demasiado literalmente. Desea una lista de jugadores ordenada por los criterios que desea separarlos .

¿Por qué?

Echemos un vistazo a los torneos de eliminación simple por un segundo. La idea de utilizar un algoritmo para generar coincidencias óptimas de eliminación única es evitar el problema de que los "mejores jugadores" se reúnan demasiado pronto en el torneo. Si los mejores jugadores se encuentran demasiado pronto, uno de los mejores jugadores será eliminado al principio, lo que hará que el torneo sea menos interesante. Podemos usar este emparejamiento "óptimo" para generar equipos en los que los "mejores" jugadores se distribuyen uniformemente entre los equipos. Luego distribuye los segundos mejores jugadores, etc, etc.

Así que enumere a sus jugadores según el criterio que desea que se separen : primero los hombres, luego las mujeres ... ordenados por edad y segundo. 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

Luego, aplicaremos el algoritmo de eliminación simple que utiliza su "rango" (que es solo su número de jugador) para crear "buenos emparejamientos".

El generador de torneo de eliminación simple básicamente funciona así : toma su rango (número de jugador) y revierte los bits (binario). Este nuevo número que creas se convertirá 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, la ranura 1 juega la ranura 2, 3-vs-4, 5-vs-6. Vamos a usar estos "emparejamientos" para generar equipos óptimos .

Mirando el número de jugador arriba, ordenado por su "número de ranura", aquí está la lista que encontramos:

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

Cuando divides las máquinas tragamonedas en equipos (dos o más), obtienes a los jugadores en la ranura 1-3 en comparación con los jugadores en la ranura 4-6. Ese es el mejor / óptimo agrupamiento que puedes obtener.

Esta técnica se escala muy bien con muchos más jugadores, múltiples criterios (solo agruparlos correctamente) y múltiples equipos.

Enfoque casi trivial para dos equipos:

  1. Ordena a todos los jugadores por tu habilidad / evaluación de rango.
  2. Asigna al equipo A el mejor jugador.
  3. Asigna al equipo B los siguientes dos mejores jugadores
  4. Asigna al equipo A los siguientes dos mejores jugadores
  5. goto 3
  6. Termina cuando te quedes sin jugadores.

No es muy flexible, y solo funciona en una columna de clasificación, por lo que no intentará obtener perfiles de género o edad similares. Pero sí hace que los equipos estén bien emparejados si la distribución de entrada es razonablemente suave. Además, no siempre termina con el equipo A que tiene el jugador de repuesto cuando hay un número impar.

Este es un problema de empaquetado de contenedores , o un problema de mochila multidimensional . Björn B. Brandenburg ha creado una biblioteca de heurísticas para el empaquetado de contenedores en Haskell que puede ser útil.

Necesitas algo como ...

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

Decidir sobre varios equipos n (supongo que esto 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

Encuentra la proporción de género ideal:

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

Encuentre la variación de edad ideal (querrá el paquete Math.Statistics):

ageDist ps = pvar (map age ps)

Y debe asignar a las tres restricciones algunas ponderaciones para obtener 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 las puntuaciones entre los equipos. Un enfoque de fuerza bruta tomará un tiempo proporcional a Θ (n k − 1 ). Dado el tamaño de su problema (8 equipos de 12 jugadores cada uno), esto se traduce en aproximadamente 6 a 24 horas en una PC moderna típica.

EDITAR

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

  1. Elige equipos al azar.
  2. Obtenga una puntuación para esta configuración (ver más arriba).
  3. Intercambia jugadores aleatoriamente entre dos o más equipos.
  4. Consigue un puntaje para la nueva configuración. Si es mejor que la anterior, guárdela y repita el paso 3. De lo contrario, descarte la nueva configuración y vuelva a intentar el paso 3.
  5. Cuando la puntuación no haya mejorado para un número fijo de iteraciones (experimento 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 confianza de que no ha alcanzado un óptimo local que es considerablemente peor que el ideal.

Idea:

  1. Ordenar jugadores por habilidad
  2. Asigna los mejores jugadores en orden (ej .: equipo A: 1er jugador, equipo B: 2do jugador, ...)
  3. Asigna los peores jugadores en orden
  4. Lazo en 2
  5. Evalúe las posibles correcciones y realicelas (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 habilidad 4, cámbielos)
  6. Evaluar posibles correcciones en la distribución de género y realizarlas.
  7. Evaluar posibles correcciones en la distribución por edades y realizarlas.