Stratégie / algorithme pour diviser les équipes équitables en fonction de l'histoire

Nous sommes un groupe de personnes qui jouent régulièrement au floorball ensemble. Chaque session commence par la tâche ardue de diviser les équipes ...

Alors quoi de mieux qu'une application pour sélectionner automatiquement des équipes?

Donc, étant donné un historique de combinaisons d'équipes et de résultats, et une liste de personnes se présentant pour cette session particulière, quelle serait une bonne stratégie pour trouver les équipes optimales? Par optimal, je veux dire des équipes aussi égales que possible.

Des idées?

Edit: Pour être clair, les données sur lesquelles je dois baser la cueillette seraient quelque chose comme ceci:

[{ 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
 }]

La première chose à considérer, c'est pour quelque chose de décontracté. Il ne s'agit pas de concevoir un système pour déterminer les rondes pour la coupe du monde de ballon au sol. C'est pour les jeux décontractés avec un groupe de personnes qui aiment un bon jeu plutôt qu'une victoire déséquilibrée.

Je me souviens que Google avait un générateur de cotes de baby-foot. Un peu plus de travail a été fait à ce sujet que je n'en fais. À la recherche d'une référence pour cela, j'ai trouvé un article dans SO et une calculatrice True Skill utilisée par Microsoft pour la xbox .

En adoptant une approche beaucoup plus simpliste, chaque joueur obtient le score du rapport de points que son équipe a pour le match. Pour le match 1, le joueur A gagnerait 1,25 (10/8) tandis que le joueur D gagnerait 0,8 points (8/10). Trouvez la moyenne de tous les nombres et c'est le score du joueur.

Pour l'ensemble des jeux décrits, cela fournit:

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

À ce stade, vous avez un problème similaire à celui du problème de partition avec la contrainte que chaque équipe a besoin du même nombre de joueurs et les valeurs n'ont pas besoin d'être exactes (mais aussi proches que possible).

Approche rapide et sale:

Calculez un score pour chaque joueur qui est le total des points pour le camp sur lequel le joueur était divisé par le total des points dans le jeu pour chaque jeu auquel il a participé. Ensuite, triez les joueurs par score. Placez le premier joueur dans l'équipe A. Ensuite, pour chaque joueur, ajoutez-les à l'équipe avec le score global le plus bas jusqu'à ce que la moitié des joueurs soient dans une équipe. Tous les joueurs restants vont dans l'autre équipe.

Si vous ne voulez pas vous plonger dans le monde grisant des prieurs bayésiens (pdf) et autres, une approche intéressante consiste à attribuer un ordre total à tous les joueurs (basé sur la ration de gain / perte, les points cumulés, etc.), puis à diviser en équipes utilisant la fonction de parité comme suit.

Prenez la liste triée des joueurs (du meilleur au pire) et séparez-les en équipes paires et impaires en fonction du nombre de 1 bits dans leur index (à partir de 0). Cela donne la distribution suivante:

• 0000 (meilleur) - Pair
• 0001 - Impair
• 0010 - Impair
• 0011 - pair
• 0100 - Impair
• 0101 - Pair
• 0110 - Pair
• 0111 - Impair

...etc.

La fonction de parité assurera un nombre égal de joueurs dans chaque équipe, pour un nombre pair de joueurs. Il alternera alors en donnant l'avantage du joueur impair à l'une ou l'autre équipe de telle sorte que les effets tendent à s'équilibrer au fil du temps.

Cette fonction fonctionne mieux lorsque la répartition des compétences des joueurs est plate. En réalité, les compétences des joueurs ont tendance à suivre la distribution de la «somme des valeurs aléatoires», alias la gaussienne (bien que méfiez-vous des applications générales de cette hypothèse dans des systèmes tels que TruSkill).

Afin de compenser les écarts de compétences importants, vous pouvez appliquer des permutations à cette liste. Par exemple, pour contrer un très bon joueur 0000, vous pouvez échanger le joueur 0011 avec un joueur impair de rang inférieur, tel que 0100. C'est là que les choses ondulent, mais au moins cela fournit un bon point de départ qui ne fonctionne pas. nécessitent une mesure précise de la compétence absolue, mais simplement un ordre basé sur la compétence relative.

Selon le temps dont vous disposez, commencez les premières sessions en sélectionnant au hasard les capitaines d'équipe et préparez un brouillon avant chaque partie. Gardez une trace du choix d'un joueur. Les choix plus tôt obtiennent des notes plus élevées:

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

Winning a game = 5 pts

Tout cela dépendra du nombre de joueurs par équipe. Le nombre total de points peut devoir être converti en une moyenne quotidienne ou de jeu s'il y a un grand écart de participation. Vous pouvez également attribuer une équipe pour une plus grande marge de victoire.

Les joueurs qui ont été sélectionnés tôt et qui ont joué dans une équipe gagnante obtiennent le plus de points de puissance.

Ensuite, laissez l'ordinateur faire la rédaction (sélection des équipes) en équilibrant les points de puissance pour chaque équipe et en mettant les équipes avec des notes presque égales les unes contre les autres. Les joueurs qui sont sélectionnés tôt, mais qui continuent à jouer sur des équipes perdantes, vont baisser dans le classement.

La solution la plus simple serait de fournir un grade / poids de la compétence estimée et d'essayer d'équilibrer le score de chaque équipe.

À partir de là, vous pouvez amorcer un réseau bayésien avec ces valeurs, puis déduire en arrière en fonction du résultat observé de chaque correspondance dans les données historiques dont vous disposez.

Comme un point d'intérêt de ma part: Infer.NET rend cela relativement facile à envisager et potentiellement à mettre en œuvre, et il pourrait prédire les chances de gagner des affrontements d'équipe donnés. Infer.NET est quelque chose dans lequel je commence vraiment à m'intéresser ces derniers temps.

Supposons, pour les besoins de la discussion, que vous pouvez attribuer à chaque joueur une valeur entière et que ces valeurs s'additionnent, c'est-à-dire qu'un joueur avec un score X est aussi précieux que trois joueurs avec des scores A, B et C, si A + B + C = X. Le but est alors de séparer le groupe en deux équipes afin que les deux équipes aient une valeur sommative à peu près égale.

Il s'agit de la version d'optimisation du fameux problème PARTITION qui est NP-complete. Par conséquent, votre problème est difficile à résoudre pour tout ce que nous savons . Cependant, PARTITION est faiblement NP-complet et admet certaines stratégies d'approximation raisonnables.

Un exemple est une approche gourmande similaire à ce que propose Steven. Il s'agit d'une approximation de 4/3, c'est-à-dire que l'équipe la plus forte n'est jamais plus d'environ 33% plus forte qu'une répartition optimale.

Notez que vous avez probablement des contraintes supplémentaires telles que vous avez besoin d'au moins un nombre fixe de joueurs par équipe. Donc, si vous mettez Michael Jordan dans une classe d'enfants d'âge préscolaire, vous ne pourrez pas créer des équipes presque équitables qui ont un nombre complet. Une telle limite inférieure (constante) sur la taille de l'équipe ne devrait pas avoir d'incidence sur la dureté du problème sous-jacent, mais elle pourrait détruire les limites d'approximation valables pour le problème général.

À quel point voulez-vous devenir ridicule? Vous pouvez toujours utiliser une régression linéaire multiple pour générer des coefficients pour chaque joueur en fonction des scores de leurs équipes dans les jeux précédents. Triez ensuite la liste et sélectionnez.

En réalité , il ne serait probablement pas le travail car il ne modélise pas la dynamique entre les joueurs, mais ça va vous donner une raison de jouer avec R . (<- voyez, je l'ai gardé lié à la programmation)

Si vous voulez que votre algorithme soit raisonnable, des algorithmes simples ne suffiront pas. Ils vous donneront souvent des résultats étranges

Vous devrez aller avec quelque chose comme le système ELO ou Trueskill (ELO ne fonctionne pas pour les équipes sans modifications, cependant).