Wie der Team Balancer in World of Tanks Blitz funktioniert

WoT Blitz ist ein mobiler Panzer-Shooter, in dem Spieler im 7-gegen-7-Format kämpfen.
Ein Matchmaker oder Balancer ist ein Mechanismus, der basierend auf der Aufstellung der Spieler, die in den Kampf eintreten möchten, die Zusammensetzung der Teams bildet.

Panzer haben die folgenden Parameter, die für das Matchmaking wichtig sind:

• Level. Je nach Level ändern sich die Eigenschaften der Panzer (z. B. Geschwindigkeit, Panzerdurchdringung). Auf der 1. Ebene - den schwächsten Panzern, auf der 10. - den stärksten.
  
• Typ Es gibt 4 Arten von Panzern in WoT Blitz: leichte, mittlere, schwere und Panzerzerstörer (Panzerabwehr-Artillerie mit Eigenantrieb)
  

Die einfachste Implementierung eines Matchmakers besteht darin, Spieler zufällig in Teams zu werfen. In diesem Fall haben Spieler mit niedrigem Level jedoch keine Chance, zumindest etwas Schaden zu verursachen, und das Spielen wird uninteressant.

Anforderungen

Die Liste der Anforderungen an den Balancer wurde auf der Grundlage des Feedbacks der Gaming-Community erstellt und wird bis heute regelmäßig aktualisiert.

Zum Zeitpunkt des Schreibens des Artikels für reguläre Schlachten bestand die Liste aus folgenden Elementen:


Es ist eine sehr interessante Aufgabe, einen Matchmaker zu entwickeln, insbesondere unter Berücksichtigung einer solchen Anzahl von Einschränkungen. Und Lösungsansätze können ziemlich viel sein.

Balancer bildet ein Spielerpaar

Anfangs wurde in mobilen Panzern ein Balancer verwendet, den er von seinem großen Bruder geerbt hatte - Desktop-Panzer. Im Allgemeinen arbeitete er ziemlich gut, aber er hatte mehrere Probleme: Erstens gab er keine klaren Garantien, um die Anforderungen zu erfüllen; Zweitens war das Hinzufügen neuer Anforderungen ziemlich schwierig.


Beginn der Schlacht

Daher wurde ein weiterer Balancer geschrieben, der nach folgendem Algorithmus arbeitete:

• Wir teilen die Spieler je nach Stufe und Art der Ausrüstung in Gruppen ein.
• Aus den resultierenden Spielern bilden wir Paare;
• Wir verteilen Paare für verschiedene Teams: Nehmen Sie jedes Paar, werfen Sie den ersten Spieler in das erste Team, den zweiten in das zweite;
• In den empfangenen Teams stellen wir das endgültige Gleichgewicht wieder her: Um die meisten Anforderungen zu erfüllen, ersetzen wir einige Spieler eines Teams durch Spieler eines anderen Teams.

Der resultierende Balancer arbeitete 5-10 Mal schneller als die vorherige Version und stellte zunächst Teams zusammen, die zu diesem Zeitpunkt alle Anforderungen erfüllten. Neue Regeln wurden hinzugefügt, indem zusätzliche Ausgleichsausweise geschrieben wurden.

Am Anfang hat alles gut funktioniert. Aber im Laufe der Zeit war es umso schwieriger, eine Neuausrichtung zu schreiben, je mehr Regeln hinzugefügt wurden. Das neue Gleichgewicht sollte aufgrund seiner Arbeit nicht die Arbeit der vorherigen brechen. Es wurde klar, dass dies der Weg ins Nirgendwo ist.


Fehler im Matchmaker - ein 9 gegen 9 Team hat sich versammelt

Simulierter Glühbalancer

In der endgültigen Version haben wir uns für einen Balancer entschieden, der nach dem folgenden Algorithmus funktioniert. Alle Spieler, die auf die Schaltfläche "To Battle" klicken, fallen in die allgemeine Warteschlange. Ein Endlosschleifen-Balancer führt Folgendes aus:

• Wählt zufällige Kampfparameter (zufällige Kampfstufe (von 1 bis 10), Zufallsmodus, zufällige Karte);
  
• Findet in der Warteschlange alle Spieler, die die oben ausgewählten Kriterien erfüllen (mit einem Panzer eines geeigneten Levels in den Kampf gezogen, den ausgewählten Modus aktiviert, die ausgewählte Karte geladen);
  
• Der Versuch, Teams zu bilden, die alle oben genannten Anforderungen erfüllen (Beschreibung unten);
  
• Wenn es möglich war, ein Team zu bilden, werfen Sie diese Spieler aus der Warteschlange und der Kampf beginnt.
  

Um Teams aus der Liste der geeigneten Spieler zu bilden, wird die Annealing-Simulationsmethode verwendet. Lesen Sie hier mehr über die Methode selbst.


Suchen Sie nach einem globalen Maximum, indem Sie das Tempern simulieren

Im Zusammenhang mit der Anwendung auf die Bildung von Teams lautet der Algorithmus wie folgt:

• Es beginnt mit zwei leeren Teams;
  
• Bei jeder Iteration wird der Status von Befehlen zufällig geändert. Führen Sie dazu einen der folgenden Vorgänge aus:
  
  
  • Fügt der ersten oder zweiten Mannschaft einen zufälligen Spieler aus der Liste der geeigneten Spieler hinzu (wir nehmen auch eine zufällige Mannschaft);
    
  • Entfernt einen zufälligen Spieler aus einem zufälligen Team.
    
  • Ersetzt einen zufälligen Spieler aus der Liste der geeigneten durch einen der vorhandenen Spieler im ersten oder zweiten Team.
    
  • Ändert einen zufälligen Spieler aus dem ersten Team in einen zufälligen Spieler aus dem zweiten Team.
    
  
  
• Ruft eine Schätzung des resultierenden Zustands ab. Ruft dazu die Auswertungsfunktion auf. Die Funktion geht die Liste der Anforderungen durch und erhöht bei Verletzung jedes Gegenstands die Strafe. Je stärker der Punkt verletzt wird, desto höher ist die Strafe. Zum Beispiel ist die Strafe für ein 2x2-Team höher als die Strafe für ein 6x6-Team.
  
• Abhängig von der Änderung des Werts der geschätzten Funktion und der aktuellen Temperatur bestimmen wir die Wahrscheinlichkeit eines Übergangs in einen neuen Zustand.
  
• Wir setzen den Prozess fort, bis entweder die Temperatur das eingestellte Minimum erreicht oder der Wert der Bewertungsfunktion Null erreicht (in diesem Fall sind alle Anforderungen erfüllt und der Kampf kann gestartet werden).
  

Der Hauptvorteil dieses Ansatzes: Um neue Anforderungen hinzuzufügen, reicht es aus, die Bewertungsfunktion zu ändern. Es ist nicht erforderlich, Code zu schreiben, der beschreibt, wie genau das erreicht wird, was wir wollen. Fügen Sie einfach eine Regel hinzu, die das gebildete Team betrachtet und angibt, ob es gut ausbalanciert ist oder nicht.

Ein gutes Beispiel für das Hinzufügen solcher Regeln sind Bewertungskämpfe. In Bewertungskämpfen beim Matchmaker tauchten mehrere neue Regeln gleichzeitig auf:

• Die Teams müssen in Bezug auf die Bewertung ausgewogen sein (der Unterschied in der Gesamtbewertung der Spieler zwischen den Teams sollte einen bestimmten Wert nicht überschreiten).
  
• Der Unterschied in der Bewertung zwischen den Spielern sollte minimal sein (Spieler aus der Bronze-Liga sollten nicht mit Spielern aus dem Diamanten in Streit geraten).
  

Beispiel für ein Diamond League-Spielerprofil

Die erste Regel wird durch Ändern der Bewertungsfunktion implementiert: Es wurde eine Strafe hinzugefügt, wenn die maximal zulässige Differenz in der Bewertung überschritten wurde. Die zweite Regel wird implementiert, indem die Funktion geändert wird, mit der geeignete Spieler aus der Warteschlange gezogen werden.

Der Nachteil dieses Ansatzes ist die langsame Geschwindigkeit. Im Vergleich zur Vorgängerversion begann die aktuelle Version trotz einiger Optimierungen etwa zehnmal langsamer zu arbeiten. Übrigens über die Optimierung. Der größte Teil des Servers (außer Netzwerk und Physik) für das Spiel ist in Python geschrieben. Der Balancer wurde in C ++ neu geschrieben und mit vielen Threads parallelisiert. Von Python kommt eine Anforderung zum Bilden eines Befehls im Plus-Code an. Ferner startet jeder der Ströme unabhängig das Glühverfahren. Sobald ein Thread eine Lösung findet, stoppen die restlichen Threads den Suchvorgang und die gefundene Lösung wird an Python zurückgegeben.


Wartezeit und Warteschlangengröße auf dem RU-Server (5 Sekunden in normalen Schlachten und 10 Sekunden in Bewertungsschlachten)

Mit dem Wachstum des Online-Wachstums stieg auch die Belastung des Balancers. In diesem Herbst, als der Online-Server auf dem RU-Server 120.000 erreichte (während des Mad Games-Ereignisses), hörte der Balancer auf, damit umzugehen. Als vorübergehende Maßnahme haben wir einige Regeln deaktiviert, wodurch wir die Last reduzieren konnten. Um solche Probleme in Zukunft zu vermeiden, haben wir den Matchmaker verteilt.

Bewertungssystem

Die besten Spieler der Diamantenliga, 21. April 2019

In vielen MMO-Spielen gibt es neben zufälligen Kämpfen auch Bewertungen / Ranglisten / etc. Die Hauptidee dieses Modus: Gegner werden nicht zufällig gesucht, sondern sind in ihren Fähigkeiten geeignet. Wenn Sie ein Skill-Spieler sind, spielen Sie mit denselben Skill-Spielern, und umgekehrt, wenn Sie nicht wissen, wie man spielt, werden Sie auf dieselben Newcomer stoßen.

Zu Beginn der Saison durchläuft der Spieler eine Reihe von Kalibrierungskämpfen, deren Ergebnisse seine Startposition bestimmen. Abhängig vom weiteren Erfolg des Spiels steigt oder fällt der Spieler dann in der Rangliste. Das Bewertungssystem in Blitz wurde zuallererst für einen korrekten Ausgleich geschaffen. Es wird auf die Fähigkeiten der Spieler geschärft und ist praktisch unabhängig von der Anzahl der gespielten Spiele.

Um Bewertungsschlachten durchzuführen, mussten zwei Probleme gleichzeitig gelöst werden. Zunächst musste ein Bewertungssystem ausgewählt werden (nach welchem ​​Prinzip die Spieler bewertet werden sollten). Zweitens war es notwendig, den Balancer so zu verfeinern, dass er Kämpfe unter Berücksichtigung von Bewertungsbeschränkungen sammelt.

Die Hauptanforderung für das Bewertungssystem ist die Fähigkeit, das Niveau des Spielers genau zu bestimmen. Um zu bewerten, wie genau das eine oder andere Bewertungssystem funktioniert, wurde ein Simulator erstellt, an dessen Eingabe die Geschichte der Schlachten und das ausgewählte Bewertungssystem übermittelt wurden und dessen Ausgabe die Genauigkeit des Systems war.

Die Genauigkeit wurde wie folgt berechnet:

• Allen Spielern wurde eine Startwertung zugewiesen;
  
• Basierend auf den Ergebnissen der einzelnen Schlachten wurde die Bewertung der an dieser Schlacht teilnehmenden Spieler gemäß dem ausgewählten System neu berechnet.
  
• Vor jedem Kampf versuchte das System vorherzusagen, welches Team gewinnen würde.
  
• Als Ergebnis wurde der Prozentsatz der Schlachten berechnet, für die das System die richtige Vorhersage lieferte.
  

Die beliebtesten Bewertungssysteme: Winrate, Elo , Glicko , TrueSkill . Winrate ist der übliche Prozentsatz der Siege. Elo ist ein Bewertungssystem, das ursprünglich für Spiele mit zwei Personen (Schach usw.) entwickelt wurde. In diesem System erhält ein Spieler eine bestimmte Anzahl von Punkten zum Gewinnen / Verlieren, abhängig von der Wertung des Gegners. Glicko ähnelt im Allgemeinen Elo, berücksichtigt jedoch auch, wie lange der Spieler inaktiv war. TrueSkill ist ein proprietäres Bewertungssystem von Microsoft, bei dem jeder Spieler zwei Parameter hat: Bewertung und Systemvertrauen in diese Bewertung.

Bei der Entwicklung der ersten Version von Bewertungskämpfen haben wir Winrate und Elo (mehrere für ein Teamspiel angepasste Optionen) sowie ein einfaches Punktesystem (bei dem die Spieler immer eine feste Anzahl von Bewertungspunkten für den Sieg erhielten und zur Niederlage weggenommen wurden) berücksichtigt.



Die besten Ergebnisse wurden vom Elo-System erzielt, bei dem Ra die Spielerbewertung und Rb die Differenz zwischen der Gesamtbewertung des gegnerischen Teams und der Gesamtbewertung des Spielerteams ist, mit Ausnahme des Spielers selbst.

Die Hauptschwierigkeiten, auf die wir nach dem Start gestoßen sind:

• zu große Unterschiede in der Rangfolge zwischen den Spielern;
  
• die schlecht vorhersehbare Geschwindigkeit, mit der die Spieler punkten (die Liga erreichen).
  

Das erste Problem konnte nicht vollständig gelöst werden, da es zu wenige Geschicklichkeitsspieler gibt, sie lange warten müssen, bis der Kampf beginnt, und sehr oft sehen sie Spieler in ihren Teams schwächer. Um den Effekt abzuschwächen, haben wir Bewertungsschlachten nur zur Hauptsendezeit zur Verfügung gestellt (dh zu einer Zeit, als die maximale Anzahl von Personen auf den Servern spielte).

Wir haben das zweite Problem gelöst, indem wir einen Verlangsamungsfaktor eingeführt haben (dh je weiter der Spieler von der Durchschnittsbewertung entfernt ist, desto schwieriger ist es für ihn, zu steigen oder zu fallen).

Wir haben auch auf verschiedene Weise versucht, die Qualität des Bewertungssystems zu verbessern. In den ersten Versionen haben wir zur Änderung der Bewertung nur Informationen über Sieg / Niederlage verwendet. Aber wir haben ein Teamspiel, und nicht immer führen die guten Aktionen eines bestimmten Spielers zum Sieg des gesamten Teams. Das heißt, selbst wenn der Spieler gut gespielt und die Mannschaft verloren hat, erhielt dieser Spieler das gleiche Minus für die Wertung wie alle anderen Spieler. Um dies zu verhindern, haben wir versucht, die einzelnen Aktionen des Spielers im Kampf zu berücksichtigen.

Zu diesem Zweck haben wir versucht, maschinelles Lernen zu verwenden: Wir haben verschiedene Faktoren gesammelt und versucht, das Modell zu trainieren, um den Sieg / die Niederlage des Teams gemäß den Aktionen des Spielers im Kampf vorherzusagen. Anschließend haben wir dieses Modell verwendet, um den Bewertungsbonuskoeffizienten zu bestimmen (dh, wenn das Team verloren hat, das Verhalten des Spielers jedoch ähnlich war Geben Sie diesen Spielern einen zusätzlichen Bonus, wenn Sie Spieler gewinnen.


Der Spieler des Gewinnerteams, der gut gespielt hat, erhielt eine Bewertung von +40. Und was schlecht ist nur +10

Wir konnten ein gutes Modell bauen, das viel bessere Ergebnisse zeigte als das aktuelle, aber es gab eine Schwierigkeit (die bei maschinellen Lernproblemen oft alles verdirbt). Das Modell war gut, aber manchmal hatte es Fehler, die für Menschen deutlich sichtbar sind. In regelmäßigen Abständen gab es Situationen, in denen ein Spieler, der aus Sicht einer Person gute Ergebnisse zeigte, aus Sicht des Modells einen geringen Bonus erhielt und umgekehrt.

Infolgedessen haben wir das ML-Modell aufgegeben und eine einfachere manuelle Formel gewählt. Diese Formel berücksichtigt nur Kampferfahrung ohne Berücksichtigung von Boni für den Sieg, x2 und andere. Es gibt ein sehr anständiges Ergebnis, obwohl es etwas niedriger als das des ML-Modells ist.

Fazit

• Ein Balancer, der auf einer Glühsimulationsmethode basiert, ermöglichte es uns, von einer Beschreibung der Lösung (Zusammenstellung des Teams) zu einer Beschreibung der Anforderungen (welche Bedingungen nicht verletzt werden sollten) überzugehen.
  
• In Team-Rating-Kämpfen zeigte sich das modifizierte Elo-System unter Berücksichtigung der individuellen Aktionen des Spielers im Kampf gut.
  
• Es lohnt sich nicht immer, komplexe Methoden des maschinellen Lernens anzuwenden (insbesondere wenn die Interpretierbarkeit und Verständlichkeit des Ergebnisses durch eine Person wichtig ist).
  

Wir entwickeln und verbessern den Balancer weiter. Wir haben den negativen Eindruck eines Klassenungleichgewichts fast besiegt. Die Hauptprobleme, auf die unsere Spieler achten, sind das Ungleichgewicht in Bezug auf Geschicklichkeit, Turbulenzen und Afk-Spieler. Dies ist eine ernsthafte Herausforderung, wir arbeiten weiterhin an einem Balancer in diesen Bereichen.

Wenn Sie Fragen / Anregungen zu einem Balancer in WoT Blitz haben, melden Sie sich in den Kommentaren (oder in unserem Forum ) ab.