SpawELO – kostenloses kleines Matchmaking-System für LAN-Partys

• Bei der LAN-Party einer Freundesgruppe, die seit 16 Jahren besteht, wurde es zunehmend schwieriger, die Dota-2-Teams jedes Mal manuell zusammenzustellen, daher entstand SpawELO zur Automatisierung der Teamwahl
• Wegen großer Leistungsunterschiede und schwankender Teilnehmerzahlen führte ein manueller Draft oft zu wiederholt ähnlichen Teams und Ungleichgewichten bei ungerader Spielerzahl
• Die erste Umsetzung nutzte 35 vergangene Matches und Elo-Werte, um die Teamkombination mit der geringsten Differenz der aufsummierten Teamwerte zu finden, und passte die Werte anschließend durch wiederholtes Einbeziehen der Spielergebnisse an
• Nach dem Wechsel zu einem Modell zur Vorhersage von Siegchancen wurden die Spieler-Elo-Werte mit L2-Loss und Backpropagation angepasst, doch weil alle Siege als 100 % behandelt wurden, kam es zu Overfitting durch das Auswendiglernen vergangener Spiele
• Der endgültige Ansatz behandelt Spielergebnisse als probabilistische Siege mit 75 % oder 95 %, um Overfitting zu verringern, und zielt auf Team-Matching ab, das auch bei ungeraden Aufstellungen wie 4v5 funktioniert

---

Das Problem der Teamwahl auf der LAN-Party

• Die Freundesgruppe veranstaltet seit 16 Jahren mindestens einmal pro Jahr eine LAN-Party, die normalerweise 4 bis 5 Tage dauert und zu Spitzenzeiten etwa 12 Teilnehmende hat
• Das Hauptspiel ist Dota 2, daneben werden auch Counter-Strike, Wolfenstein: Enemy Territory, Warcraft 3 und Blobby Volley gespielt
• Die Teilnehmenden kommen und gehen zu unterschiedlichen Zeiten, und manche müssen zwischendurch weg, um sich um ihre Kinder zu kümmern, daher wird nicht jedes Spiel mit derselben Besetzung gespielt
• Dota 2 wird normalerweise als 5v5 gespielt und ein Match dauert etwa 40 Minuten; unausgeglichene Spiele wie 4v5 kippen leicht auf eine Seite
• In der Gruppe gibt es sowohl Leute, die regelmäßig Dota 2 spielen, als auch solche, die nur bei der LAN-Party spielen, daher sind die Leistungsunterschiede groß

Die Grenzen des manuellen Drafts

• Die bisherige Methode war meist so aufgebaut, dass die stärkste oder die unerfahrenste Person als einer von zwei Captains fungierte und abwechselnd Mitspielende auswählte, ähnlich wie bei der Teamwahl auf dem Schulhof
• Die Reihenfolge der Auswahl war: Der erste Captain wählt 1 Person, der zweite Captain 2, dann wieder der erste 2, und am Ende wählen beide Captains jeweils noch 1 Person
  • Das ist eine Variante, um den Vorteil der ersten Auswahl zu verringern
• Wegen der großen Leistungsunterschiede entstanden am Ende häufig ähnliche oder sogar identische Teams, und auch der Reiz des ständigen Draftens nahm ab
• Die manuelle Teamwahl war zeitaufwendig und umständlich, und niemand wollte gern die Rolle des Captains übernehmen
  • Wenn die Spielerzahl nicht aufging, wurde das Team-Ungleichgewicht besonders groß

Die erste Umsetzung: vergangene Spiele und aufsummiertes Elo

• Als beim letzten LAN-Event die Unzufriedenheit mit der Teamwahl größer wurde, entstand schnell ein Stück Automatisierungscode
• Zuerst wurden Daten aus 35 früheren Matches gesammelt und in Colab geladen; jedes Match enthielt die Listen der Spieler des Sieger- und des Verliererteams
• Die Grundidee war, Spielerwerte mit dem Elo rating zu berechnen
  • Alle Spielenden starten bei 1000 Punkten
  • Wer gewinnt, erhält Punkte, wer verliert, verliert Punkte
  • Die Siegchance wird nur aus der Elo-Differenz zweier Spieler berechnet
• Die erste einfache Implementierung addierte 20 Punkte für Gewinner und zog 20 Punkte bei Verlierern ab
• Die Teamzusammenstellung wurde erzeugt, indem alle Kombinationen der angefragten Spielenden betrachtet und dann die Kombination mit der kleinsten Differenz der Team-Elo-Summen gewählt wurde
  • Im Beispiel wurden 8 Personen in zwei Teams aufgeteilt; ein Team kam auf 4100 Punkte, das andere auf 4080

Verbessertes Elo-Modell durch iterative Berechnung

• Da ein einmaliges Durchgehen der 35 Matches die Daten nicht gut genug ausnutzte, wurden die historischen Matchdaten mehrfach wiederholt verarbeitet
• Das verbesserte Elo-Update wendete nicht einfach ±20 Punkte an, sondern vergab mehr Punkte für einen Sieg gegen stärkere Gegner und zog weniger ab bei einer Niederlage gegen stärkere Gegner
  • Im Beispiel erhält Spawek mit 1260 Punkten nur 4,47 Punkte, wenn er Goovie mit 900 Punkten schlägt
  • Status mit 900 Punkten erhält 30,38 Punkte, wenn er Dragon mit 1100 Punkten besiegt
• Da nicht Einzelspieler gegen Einzelspieler, sondern Teams bewertet wurden, wurden die Team-Elo-Summen des Sieger- und Verliererteams verwendet und die Aktualisierung gleichmäßig auf die Teammitglieder verteilt
• Dieser Ansatz wurde sogar während der LAN-Party genutzt; nach jedem Spiel konnten neue Daten hinzugefügt und für den Rest der Party neue Teams erstellt werden
• Wenn gelegentlich ein klar unausgeglichenes Match erzeugt wurde, wurde ein „Fake-Match“ mit dem erwarteten Sieger zu den Daten hinzugefügt und die Teams anschließend neu generiert

Die zweite Verbesserung: ein Modell zur Vorhersage von Siegchancen

• Die nächste Verbesserung behandelte Elo nicht mehr nur als einfache Punktetabelle, sondern als Modell zur Vorhersage der Siegchance eines Teams
• Das Modell speichert das Elo jedes Spielers und berechnet die Gewinnwahrscheinlichkeit, indem es SUM(Elo) beider Teams vergleicht
• Auf den gesamten Match-Datensatz wurde ein einfacher L2-Loss angewendet
  • Die Elo-Summe des Siegerteams und des Verliererteams wird berechnet
  • Die Gewinnwahrscheinlichkeit wird berechnet
  • Die quadrierte Differenz zwischen realer und vorhergesagter Wahrscheinlichkeit wird als Loss addiert
• Für das Training wurde backpropagation verwendet
  • Im Forward-Pass wird die vorhergesagte Gewinnwahrscheinlichkeit berechnet
  • Mit dem Loss und der Ableitung der Wahrscheinlichkeitsfunktion wird berechnet, wie stark das Elo jedes Spielers den Loss beeinflusst
  • Die Elo-Werte werden mit LEARNING_RATE = 10_000.0 und ITERATIONS = 10001 aktualisiert
• Dieser Ansatz senkte den Loss erfolgreich, aber die Elo-Werte konvergierten nicht

Probabilistische Spielergebnisse zur Verringerung von Overfitting

• Das ML-artige Modell verursachte Overfitting, weil es alle realen historischen Siegchancen als 1.0, also 100 % Sieg, behandelte
• Statt zu generalisieren, merkte sich das Modell die einzelnen Spiele, sodass die vorhergesagte Gewinnwahrscheinlichkeit in manchen Fällen fast 1 erreichte, etwa 0.999994567526197
• Da das Ziel nicht darin bestand, vergangene Ergebnisse exakt zu kodieren, sondern gute Teams zu bilden, wurden statt deterministischer Ergebnisse probabilistische Resultate verwendet
• Nach einer genaueren Sichtung der historischen Matchdaten wurden Spiele in zwei Typen eingeteilt
  • Enge Spiele erhielten für das Siegerteam eine reale Gewinnwahrscheinlichkeit von 75 %
  • Klar einseitige Spiele erhielten für das Siegerteam eine reale Gewinnwahrscheinlichkeit von 95 %
• Für eine Siegchance von 75 % ist eine Elo-Differenz von etwa 200 Punkten nötig, während für 100 % Sieg eine Differenz von etwa 500 Punkten bis unendlich nötig wäre; dadurch wird es für das Modell schwieriger, sich alle Spiele zu merken
• Nachdem in den Funktionen loss und backpropagation statt real_probability = 1 nun real_probability = game["win_probability"] verwendet wurde, sank der Loss schnell, und auch die Spieler-Elo-Werte konvergierten auf ein vernünftiges Niveau

Line-ups auch bei ungerader Spielerzahl

• Das neue System kann auch bei ungerader Spielerzahl die Gewinnwahrscheinlichkeit vorhersagen und Teams erstellen
• Ein Beispiel für das erste Line-up der in zwei Wochen beginnenden LAN-Party sieht so aus
  • team 1: Elo 2660
  • team 2: Elo 2655
• Das Beispiel-Line-up besteht aus 4 Spielern auf der einen und 5 auf der anderen Seite
  • team 1: Spawek, Bixkog, Bania, Goovie
  • team 2: Hypys, Muhah, J, Vifon, Status

[GN⁺]

Meinungen auf Hacker News

• Ich frage mich, ob jemand bei teambasierten Spielen schon einmal einen Ansatz verwendet hat, der nicht auf Elo/TrueSkill basiert.
  Das Elo eines Teams zu summieren oder zu mitteln und damit Matchmaking zu betreiben, fühlt sich wie ein Behelf an, bei dem man ein Modell für individuelles Matchmaking in Team-Matchmaking hineinpresst.
  Außerdem gehen dabei viele Informationen über Synergien und Antisynergien innerhalb des Teams verloren, etwa dass A und B zusammen stärker sind als die Summe ihrer individuellen Elo-Werte, A und C zusammen aber schwächer.

  • Meiner Ansicht nach sorgt Elo in teambasierten Spielen am Ende dafür, dass außer Sieg/Niederlage nichts übrig bleibt.
    Im Sport kann ein Team verlieren und am Saisonende trotzdem All-Stars oder einen MVP stellen; umgekehrt kann jemand in einem Meisterteam sein, ohne eine Schlüsselfigur zu sein.
    In Team-eSports hängt alles am Sieg, sodass Spieler wie die ligaweit besten Verteidiger, Angreifer oder Supporter nicht gut erfasst oder anerkannt werden.
    Wie in vielen Sportarten sollte man bis zu einem gewissen Grad Advanced Metrics verfolgen und einbeziehen. Ein Spieler ist nicht Elo selbst, sondern eher Werte wie Assists pro Spiel, Rebounds, Punkte, RBIs oder Yards.
    Dann sieht man leichter, ob ein Team mehr Scoring oder mehr Defensive braucht, und das Matchmaking kann sich natürlicher ausrichten als nur nach „braucht mehr Gewinner/braucht mehr Verlierer“.
  • Auch dort, wo Elo bereits verwendet wird, nutzt man nicht reines Elo. Spieleentwickler justieren das Matchmaking mit Faktoren wie Anzahl der Personen in der Warteschlange, Zeit seit dem letzten Spiel, Gesamtzahl der Spiele, Meldungen oder Anzahl gekaufter kosmetischer Items.
    Die Stärke von Elo liegt darin, wie viele Informationen man für die Kosten bekommt. Der Kern ist, dass es eine einzelne Zahl ist, die alles repräsentiert.
    Es beschreibt die schöne Vielfalt der Natur nicht perfekt, ist aber nahe an der effizientesten Abstraktion, die 70 % dessen enthält, was man über die Stärke eines Gegners wissen muss.
  • Zustimmung. Elo ist ein grobes, aber einfaches statistisches Modell, und sein größter Vorteil ist, dass es leicht zu verstehen und herzuleiten ist.
    Schön wäre ein mehrdimensionaler Spielerstärke-Vektor oder ein Embedding, das mehr Informationen enthält, sowie ein darauf aufbauendes, stärker nichtlineares Modell.
    In vielen Spielen braucht ein Team zum Beispiel normalerweise Support-Spieler, aber mit nur einer Zahl lässt sich diese Information nur unzureichend ins Matchmaking einbringen.
  • Ich habe viel darüber nachgedacht, aber es scheint keine eine ultimative Lösung zu geben; es hängt stark von der Disziplin und den gespielten Regelvarianten ab.
    Beim Tischfußball zum Beispiel gibt es Spieler, die sowohl Einzel als auch Doppel spielen; zwei hervorragende Verteidiger im selben Team können trotzdem gegen schwächere Gegner verlieren, die besser zu den jeweiligen Positionen passen.
    Spiele, in denen ein Team einen einzelnen Spieler stark mittragen kann, wie Counter-Strike, Apex, Overwatch und in gewissem Maß Dota, unterscheiden sich ebenfalls. In Counter-Strike kann ein schwacher Teamkollege ohne ausreichende Fähigkeiten oder ohne Headset das ganze Spiel ruinieren, während man in Overwatch eine Support-Klasse wählen, sich hinten ausruhen und darauf warten kann, dass der Rest des Teams gewinnt.
    Es gibt auch Chemie. Wie man auch am Arbeitsplatz sieht, können Synergien, die nur in bestimmten Kombinationen entstehen, oder einfache Unterschiede im Spielstil das Ergebnis verändern.
    Selbst bei Varianten, die ähnlich wirken, etwa beim Billard, kann ein Spieler in einer Disziplin glänzen und in einer anderen nicht richtig zurechtkommen.
  • Ich habe einmal PageRank ausprobiert, und das funktionierte ziemlich gut. Ich habe Siege als Links betrachtet, Punkte vom Verlierer zum Gewinner fließen lassen und die Linkstärke mit der Zeit abnehmen lassen.

• Auf Kaggle gab es, oder gibt es vielleicht noch, einen Wettbewerb zu Bewertungssystemen.
  https://www.kaggle.com/competitions/chess/discussion/107
  Es gibt ziemlich viele Bewertungssysteme, die besser abschneiden als Elo.

  • In der Rangliste sieht man nur die Namen der Teilnehmer; ich frage mich, wie man die jeweiligen Methoden einsehen kann.

• Für Turniere gefällt mir das Schweizer System, das meines Wissens im Schach beliebt ist.
  [1]: https://en.wikipedia.org/wiki/Swiss-system_tournament

  • Interessanterweise hat unsere lokale Community vor Kurzem Billardturniere im Schweizer System begonnen, und das funktioniert ziemlich gut. Allerdings gibt es einen Kompromiss zwischen Fairness und der Zahl der Spieler, die man einladen kann.
    Bei sechs Runden eignet sich das Schweizer System für höchstens etwa 40 Personen, aber wenn man über 100 Personen einladen will, muss man ein Double-Elimination-Bracket verwenden. Sonst dauert das Turnier eine Woche.
    Das Beste daran ist das gute Preis-Leistungs-Verhältnis. Unabhängig vom Ergebnis spielt man während des gesamten Turniers weiter, und mit dem Fortschreiten des Turniers werden die Gegner dem eigenen Niveau angepasst, sodass alle Spaß haben können.
  • Bei Magic und anderen Kartenspielturnieren ist es ebenfalls verbreitet, wird aber leicht angepasst verwendet. Häufig sieht man Formate wie „sechs Schweizer Runden, danach Top 8 Single Elimination“.
  • Wenn man es grob liest, spielt man in der ersten Runde gegen ein zufälliges Team; danach werden die Spieler in jeder Runde nach kumulativer Punktzahl sortiert und gegen Gegner mit gleicher oder ähnlicher Punktzahl gepaart. Gleichzeitig wird vermieden, zweimal gegen denselben Gegner zu spielen.
    Ich weiß nicht genau, wie man bestimmt, wie viele Runden nötig sind, aber ich bin mir nicht sicher, ob dieses Detail der Kern ist.
    Im Analyseteil heißt es, dass im Vergleich zu einem K.-o.-Turnier, sofern es keine Unentschieden gibt, die Zahl der Runden, die nötig ist, um einen eindeutigen Sieger zu bestimmen, gleich ist.
    Das Schweizer System hat den Vorteil, dass niemand ausscheidet und die Endplatzierung nicht nur den Sieger, sondern bis zu einem gewissen Grad auch die relative Stärke aller Teilnehmer zeigt.
    Wenn ein Spieler jedoch zu weit vorne liegt, kann der Sieg schon vor der letzten Runde feststehen, sodass es nicht immer mit einem dramatischen Finale endet.

• Ich frage mich, ob man es mit dem Shapley-Wert versuchen könnte.

  • Ich wusste nicht, was das bedeutet, und habe es nachgeschlagen: Es ist ein Lösungskonzept aus der kooperativen Spieltheorie, benannt nach Lloyd Shapley, und weist den gesamten von der Koalition aller Spieler erzeugten Überschuss eindeutig den einzelnen Spielern zu.
    Das ist fast direkt aus der Wikipedia-Einleitung, aber ich verstehe es auch nach dem Lesen nicht richtig. Ich frage mich, was hier der Gesamtüberschuss eines kooperativen Spiels ist – so etwas wie die Holzmenge, die ein Team in AoE gesammelt hat?
    Ich weiß auch nicht, wie es helfen soll, das zu „verteilen“; eher scheint mir, dass das das Spielergebnis sein sollte. Es wäre schön, wenn jemand das einfach erklären könnte.