Strategie / Algorithmus zur geschichtlichen Aufteilung fairer Teams

20

Wir sind eine Gruppe von Menschen, die regelmäßig gemeinsam Unihockey spielen. Jede Sitzung beginnt mit der entmutigenden Aufgabe, Teams zu teilen ...

Was ist also besser als eine Anwendung, um Teams automatisch auszuwählen?

Was wäre eine gute Strategie, um die optimalen Teams zu finden? Mit optimal meine ich Teams so gleich wie möglich.

Irgendwelche Ideen?

Bearbeiten: Um es klar zu machen, wären die Daten, auf denen ich die Kommissionierung stützen muss, ungefähr so:

[{ 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
quelle
4
Was ist Unihockey?
Dynamische
1
Ich gehe davon aus, dass Sie nur Mannschaftswerte und keine Einzelbeitragswerte haben?
Gort the Robot
1
@Dynamic: Ich gehe davon aus, dass es ein anderer Name für Floor Hockey ist - Hockey, das auf einer Turnhalle mit einem kleinen Gummiball statt mit einem Puck auf Eis gespielt wird (und natürlich ohne Schlittschuhe).
FrustratedWithFormsDesigner
2
Sie möchten vielleicht klarstellen, dass die einzigen Informationen, die in diesem Algorithmus verwendet werden, die Anzahl der Gewinn- / Verlustteams sind, in denen jeder Spieler gespielt hat.
TehShrike
2
@TehShrike Für jedes gespielte Match habe ich Informationen darüber, wer in welchem ​​Team gespielt hat und wie hoch das Endergebnis war. Z.B. {Team1: ["a", "b", "c"], Team2: ["d", "e", "f"], Punktzahl: "10-5"}
Vegar

Antworten:

6

Das erste, was zu berücksichtigen ist, ist ein für etwas Lässiges. Es wird kein System zur Ermittlung der Runden für die Fußball-Weltmeisterschaft entwickelt. Es ist für Gelegenheitsspiele mit einer Gruppe von Leuten gedacht, die lieber ein gutes Spiel als einen einseitigen Gewinn genießen.

Ich erinnere mich, dass Google einen Tischfußball-Gewinnchancengenerator hat. Daran wurde ein bisschen mehr gearbeitet als daran. Als ich eine Referenz dafür suchte, fand ich einen Artikel in SO und einen True Skill- Rechner, der von Microsoft für die Xbox verwendet wird .

Bei einem viel einfacheren Ansatz erhält jeder Spieler die Punktzahl des Verhältnisses der Punkte, die sein Team für das Spiel hat. Für Spiel 1 würde Spieler A 1,25 (10/8) erhalten, während Spieler D 0,8 Punkte (8/10) erhalten würde. Finde den Mittelwert aller Zahlen und das ist die Punktzahl des Spielers.

Für die beschriebenen Spiele gilt Folgendes:

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

Zu diesem Zeitpunkt haben Sie ein ähnliches Problem wie beim Partitionsproblem mit der Einschränkung, dass jedes Team die gleiche Anzahl von Spielern benötigt und die Werte nicht exakt sein müssen (sondern nur so nah wie möglich).

Gemeinschaft
quelle
Gleiche Anzahl von Spielern oder so nah wie möglich, wenn eine ungerade Anzahl von Spielern auftaucht ;-)
Vegar
Danke für den Hinweis auf das Partitionsproblem ! Sie rocken, @ user40980
Eric Gopak
3

Schneller und schmutziger Ansatz:

Berechnen Sie eine Punktzahl für jeden Spieler, bei der es sich um die Gesamtpunktzahl der Mannschaft handelt, auf der sich der Spieler befand, geteilt durch die Gesamtpunktzahl im Spiel für jedes Spiel, an dem er teilgenommen hat. Sortieren Sie die Spieler anschließend nach der Punktzahl. Platzieren Sie den ersten Spieler in Team A. Fügen Sie diese dann für jeden Spieler zu dem Team mit der niedrigsten Gesamtpunktzahl hinzu, bis die Hälfte der Spieler einem Team angehört. Alle verbleibenden Spieler gehen in die andere Mannschaft.

Gort den Roboter
quelle
Dieser Ansatz kann funktionieren, auch wenn die angegebene Personenkombination völlig neu ist.
Vegar
Besser zu machen sieht nach einer Variante des Rucksackproblems aus . Die Gewichte könnten ebenfalls relevant sein - so wie ich mich erinnere, wurde der schwerste Spieler (ich) immer als letzter ausgewählt.
Steve314
Es ist bekannt, dass dieser gierige Ansatz eine 4/3-Annäherung an die optimale Lösung
Radek,
3

Wenn Sie nicht in die berauschende Welt der Bayesianischen Priors (pdf) eintauchen möchten , ist es ein interessanter Ansatz, allen Spielern eine Gesamtreihenfolge zuzuweisen (basierend auf Gewinn- / Verlustverhältnissen, kumulierten Punkten usw.) und dann in zu teilen Teams verwenden die Paritätsfunktion wie folgt.

Nehmen Sie die sortierte Liste der Spieler (beste bis schlechteste) und unterteilen Sie sie in Teams Gerade und Ungerade, basierend auf der Anzahl von 1 Bits in ihrem Index (beginnend bei 0). Das ergibt folgende Verteilung:

  • 0000 (am besten) - gerade
  • 0001 - Ungerade
  • 0010 - Ungerade
  • 0011 - Eben
  • 0100 - Ungerade
  • 0101 - Eben
  • 0110 - Eben
  • 0111 - Ungerade

...etc.

Durch die Paritätsfunktion wird sichergestellt, dass in jedem Team die gleiche Anzahl von Spielern vorhanden ist, und zwar für eine gerade Anzahl von Spielern. Es wird dann abwechselnd den Vorteil des ungeraden Spielers für die eine oder die andere Mannschaft geben, so dass sich die Effekte im Laufe der Zeit ausgleichen.

Diese Funktion funktioniert am besten, wenn die Verteilung der Spielerfähigkeiten flach ist. In der Realität folgt die Fähigkeit des Spielers in der Regel der "Summe der Zufallswerte" -Verteilung, auch bekannt als "Gaussian". (Beachten Sie jedoch, dass diese Annahme in Systemen wie TruSkill pauschal angewendet wird.)

Um große Qualifikationslücken auszugleichen, können Sie Permutationen auf diese Liste anwenden. Um zum Beispiel einem sehr starken Top-Spieler 0000 entgegenzuwirken, können Sie den Spieler 0011 gegen einen ungeraden Spieler mit niedrigerem Rang wie 0100 tauschen. Dies ist der Punkt, an dem die Hand wellig wird, aber zumindest ein guter Ausgangspunkt, der dies nicht tut erfordern ein genaues Maß an absoluter Geschicklichkeit, sondern einfach eine Reihenfolge basierend auf relativen Fähigkeiten.

Richard Nelson
quelle
2

Je nachdem, wie viel Zeit Sie haben, beginnen Sie die ersten Sitzungen, indem Sie zufällig Mannschaftskapitäne auswählen und vor jedem Spiel einen Entwurf erstellen. Behalte im Auge, welche Auswahl ein Spieler trifft. Frühere Picks erhalten höhere Bewertungen:

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

Winning a game = 5 pts

All dies hängt von der Anzahl der Spieler pro Team ab. Die Gesamtpunktzahl muss möglicherweise in einen Tages- oder Spieldurchschnitt umgerechnet werden, wenn große Unterschiede bei der Teilnahme bestehen. Sie können auch ein Team für eine größere Gewinnspanne auszeichnen.

Spieler, die früh ausgewählt und in einem Gewinnerteam gespielt wurden, erhalten die meisten Leistungspunkte.

Lassen Sie dann den Computer die Ausarbeitung (Auswahl von Teams) durchführen, indem Sie die Leistungspunkte für jedes Team ausgleichen und Teams mit nahezu gleichen Bewertungen gegeneinander antreten. Spieler, die frühzeitig ausgewählt werden, aber weiterhin in verlorenen Teams spielen, werden in der Rangliste gestrichen.

JeffO
quelle
Gute Antwort! Dies kann für ein durchschnittliches Team funktionieren, aber einige Teams sind strategisch. Wenn Sie beispielsweise möchten, dass Ihre gesamte Mannschaft Verteidiger ist, haben Sie insgesamt schlechtere Spieler, die in höheren Runden spielen. Aber ich schätze, ich habe nicht nach Canonical gefragt: P. Vielen Dank!
Dynamische
Das ist ein guter Anfang. In den ersten Runden wird nichts basierend auf der Mannschaftswertung einzeln angewendet, da Sie Teammitglieder haben, die in jeder Runde zusammen spielen.
Gort the Robot
1

Die einfachste Lösung wäre, eine Note / ein Gewicht der geschätzten Fertigkeit anzugeben und zu versuchen, die Punktzahl für jedes Team auszugleichen.

Von dort aus können Sie ein Bayes'sches Netzwerk mit diesen Werten erstellen und dann basierend auf dem beobachteten Ergebnis jedes Abgleichs in den vorhandenen Verlaufsdaten rückwärts schließen.

Als Punkt von Interesse meinerseits: Infer.NET macht es relativ einfach, sich dies vorzustellen und möglicherweise umzusetzen, und es könnte die Gewinnchancen bei bestimmten Teammatchups vorhersagen. Infer.NET ist etwas, worauf ich mich in letzter Zeit wirklich einlasse.

Steven Evers
quelle
Hätten Sie genügend Daten, um aussagekräftig zu sein, und gäbe es wahrscheinlich nur eine Handvoll Spiele?
Gort the Robot
Ich hatte gehofft, dies mit Javascript oder Ruby zu lösen, aber infer.net sieht trotzdem interessant aus.
Vegar
@StevenBurnap: Hängt davon ab, wie gut / genau Ihre anfänglichen Vermutungen zur Spielerfähigkeit sind - was Sie für die meisten oder alle Systeme tun müssen. Der Vorteil der Verwendung des Netzwerks besteht darin, dass Sie im Laufe der Zeit neue Ergebnisse für jeden Spieler ableiten können, um diesen Wert zu verbessern.
Steven Evers
1

Nehmen wir zur Diskussion an, Sie können jedem Spieler einen ganzzahligen Wert zuweisen und diese Werte addieren sich, dh ein Spieler mit der Punktzahl X ist genauso wertvoll wie drei Spieler mit den Punktzahlen A, B und C, wenn A + B + C = X. Das Ziel ist es dann, die Gruppe in zwei Teams aufzuteilen, so dass beide Teams ungefähr den gleichen summierten Wert haben.

Dies ist die Optimierungsversion des bekannten PARTITION-Problems, die NP-vollständig ist. Daher ist Ihr Problem nach allem, was wir wissen, schwer zu lösen. PARTITION ist jedoch schwach NP-vollständig und lässt einige sinnvolle Approximationsstrategien zu.

Ein Beispiel ist a gieriger Ansatz, ähnlich dem, was Steven vorschlägt. Dies ist eine 4/3-Annäherung, dh das stärkere Team ist nie mehr als ca. 33% stärker als eine optimale Aufteilung.

Beachten Sie, dass Sie möglicherweise zusätzliche Einschränkungen haben, z. B. dass Sie mindestens eine feste Anzahl von Spielern pro Team benötigen. Wenn Sie also Michael Jordan in eine Klasse von Vorschulkindern einordnen, können Sie keine fast fairen Teams mit voller Anzahl bilden. Eine solche (konstante) Untergrenze der Teamgröße sollte die Härte des zugrunde liegenden Problems nicht beeinträchtigen, könnte jedoch die für das allgemeine Problem gültigen Approximationsgrenzen zerstören.

Raphael
quelle
1
Sie können nicht sehr viele Spieler auf eine Turnhalle passen. Bei bis zu 20 Spielern sind nur 92378 Kombinationen zu prüfen, vorausgesetzt, Sie möchten 10 auf einer Seite haben. Es dauert jedoch nicht sehr viele Spieler, bis die Anzahl der Kombinationen eine erschöpfende Suche unpraktisch macht.
Kevin Cline
@ Kevincline: Richtig. Ich habe implizit angenommen, dass Brute Force keine Option ist (ansonsten, warum fragen?).
Raphael
In jedem Team würden niemals mehr als sechs Personen sein. Öfter vier.
Vegar
@Vegar: Dann ist Ihre Frage mehr, wie Sie Team-Scores nutzen können, um den Wert des Spielers zu modellieren, und weniger, was Algorithmen angeht, oder?
Raphael
1
Die Genauigkeit des Algorithmus ist wahrscheinlich nicht so wichtig, es sei denn, Sie können einen Weg finden, Menschen anhand ihres Talents genau zu bewerten. Mit dem vorliegenden Problem haben wir nur Mannschaftswertung und eine Handvoll Versuche. Jede Spielerbewertung wird eine wilde Schätzung sein.
Gort the Robot
0

Wie lächerlich willst du werden? Sie können immer mehrere lineare Regressionen verwenden, um Koeffizienten für jeden Spieler basierend auf den Punktzahlen seiner Teams in früheren Spielen zu generieren. Sortieren Sie dann die Liste und wählen Sie.

In Wirklichkeit würde es wahrscheinlich nicht funktionieren, da es nicht die Dynamik zwischen den Spielern modelliert, aber es gibt Ihnen einen Grund, mit R herumzuspielen . (<- siehe, ich habe es programmierbezogen gehalten)

GrandmasterB
quelle
1
Ich überlege, einen Antrag zu stellen, um eine 2-minütige Aufgabe zweimal pro Woche zu vermeiden, und zwinge mich, fast die gleiche Zeit für die Aufzeichnung der Ergebnisse für zukünftige Berechnungen aufzuwenden. So ziemlich lächerlich, denke ich ...
Vegar
-1

Wenn Sie möchten, dass Ihr Algorithmus vernünftig ist, können einfache Algorithmen ihn einfach nicht schneiden. Sie werden Ihnen oft seltsame Ergebnisse liefern

Sie müssen sich für etwas wie ELO oder Trueskill entscheiden (ELO funktioniert jedoch nicht für Teams ohne Änderungen).

catbert
quelle
1
Das stimmt nicht. Es muss einen Algorithmus geben, der funktionieren würde.
Dynamische