Elo MMR

Elo-MMR: Ein Bewertungssystem für Massive-Multiplayer-Wettbewerbe

Dies ist ein Paket, das Implementierungen mehrerer Bewertungssysteme für Mehrspieler-Wettbewerbe enthält: Glicko All-Pairs, BAR BT-All-Pairs, Codeforces, Topcoder, TrueSkill-SPb und das neue System Elo-MMR. Alles unter MIT-Lizenz, mit Ausnahme des Inhalts von deprecated/cpp/trueskill.

Bewertungssysteme bewerten die Fähigkeiten von Spielern, die an einer gemeinsamen Aktivität teilnehmen. Der Elo-MMR-Algorithmus wurde für Aktivitäten entwickelt, bei denen eine mittlere bis große Anzahl von Spielern bei Wettkampfveranstaltungen gewertet wird und die Ergebnisse aus einem der folgenden Gründe nicht über verschiedene Veranstaltungen hinweg standardisiert werden können:

• Bei jeder Veranstaltung gibt es neue Herausforderungen, beispielsweise Hindernisparcours, Klettern und akademische Olympiaden.

• Die Teilnehmer werden im Vergleich zu anderen Teilnehmern derselben Veranstaltung bewertet, möglicherweise von einer Jury mit einem gewissen Grad an Subjektivität, wie im Standardtanz, Eiskunstlauf und Turnen.

• Wie bei den meisten Brettspielen interagieren die Teilnehmer während derselben Veranstaltung intensiv mit anderen.

In diesen Situationen ist es oft nützlich, die Qualität eines Spielers zu quantifizieren. Bewertungen könnten verwendet werden, um den Fortschritt eines Spielers während eines Trainingsprogramms zu verfolgen, Motivationsziele festzulegen, wahrscheinliche Champions vorherzusagen oder Einladungsveranstaltungen nur für Anfänger oder nur für Experten zu erstellen. Drei Eigenschaften von Elo-MMR machen es für diese Zwecke besonders gut geeignet:

• Massively Multiplayer: Der Algorithmus ist schnell und numerisch stabil, selbst bei Tausenden oder Millionen einzeln bewerteten Teilnehmern.

• Incentive-kompatibel: Je besser Sie bei Wettbewerben abschneiden, desto höher ist Ihre Bewertung.

• Robuste Antwort: Ein sehr schlechtes (oder sehr gutes) Ereignis kann Ihre Bewertung nicht allzu sehr verändern.

Hinweis: Theoretisch kann Elo-MMR auch bei Mannschaftswettbewerben eingesetzt werden, es sind jedoch weitere Untersuchungen erforderlich, um die besten Möglichkeiten hierfür zu ermitteln.

Erste Schritte

Installieren Sie zunächst Rust. Führen Sie im Verzeichnis multi-skill/ den Befehl aus

 RUST_LOG=debug cargo run --release --bin rate mmr-fast codeforces

UPDATE: Es ist jetzt auch möglich, das Bewertungssystem über eine Konfigurationsdatei auszuführen. Hier ist ein Beispiel: (Diese Konfigurationsdatei ist veraltet, wir werden sie in Kürze aktualisieren.)

 RUST_LOG=debug cargo run --release --bin rate file: ../experiments/codeforces/mmr-fast-acc.json

Versuchen Sie es, um die neue Checkpointing-Funktion zu testen

 RUST_LOG=debug cargo run --release --bin rate_from_configs ../experiments/testing/mmr-cf-1to10.json ../experiments/testing/mmr-cf-11to20.json

Dadurch werden Statusprüfpunktdateien im Verzeichnis experiments/testing/ erstellt.

Was bedeutet der erste Befehl?

RUST_LOG=debug legt eine Umgebungsvariable fest, um während der Ausführung zusätzliche Informationen an das Terminal zu drucken. Beachten Sie, dass Umgebungsvariablen unter Windows unterschiedlich eingestellt sind.

cargo run kompiliert ein Rust-Projekt und führt es aus.

--release erstellt einen Release-Build, dessen Kompilierung länger dauert, der jedoch schneller ausgeführt wird als ein Dev-Build.

--bin rate wählt den Einstiegspunkt multi-skill/src/bin/rate.rs aus.

mmr-fast ist ein Befehlszeilenargument, das das Bewertungssystem angibt. Versuchen Sie mmr für eine langsamere, aber präzisere Version von Elo-MMR.

codeforces ist ein Befehlszeilenargument, das den Datensatz angibt.

Es kann ein optionales ganzzahliges Argument folgen, um anzugeben, wie viele Wettbewerbe verarbeitet werden sollen.

Was bewirkt dieser Befehl?

Es ruft Daten aus den Codeforces-Wettbewerben ab, die in data/codeforces/contest_ids.json angegeben sind. Wenn ein Wettbewerb nicht bereits im cache/codeforces/ gespeichert ist, wird er dort über die Codeforces-Online-API heruntergeladen. Schließlich werden die resultierenden Fähigkeitsbewertungen aller Teilnehmer in data/codeforces/ratings_output.csv gespeichert.

Bitte beachten Sie, dass Ihr erster Codeforces-Durchlauf langsamer sein wird, da die Wettbewerbsstände von der Codeforces-API abgerufen werden. Es kann sogar fehlschlagen, wenn Codeforces.com Ausfallzeiten hat oder feststellt, dass Sie zu viel Bandbreite genutzt haben. Wenn dies passiert, warten Sie bitte ein paar Minuten und versuchen Sie es erneut.

Wie kann ich Teilnehmer meiner eigenen Spiele bewerten?

Wettbewerbe werden im JSON-Format gespeichert, wobei die Platzierungen in der Reihenfolge vom ersten bis zum letzten Platz aufgeführt sind. Hier ist eine Beispiel-Wettbewerbsdatei, in der die spitzen Klammern und Auslassungspunkte durch Ihre eigenen Daten ersetzt werden sollten:

 {
    "name": <str, human-readable name of the contest>, 
    "time_seconds": <int, seconds since the Unix epoch>, 
    "standings": [[<str, player 0's name>, <int, low rank>, <int, high rank>], 
                  [<str, player 1's name>, <int, low rank>, <int, high rank>],
                  ...]]
    "weight": <optional float, defaults to 1 if not included>,
    "perf_ceiling": <optional float, defaults to infinity if not included>
}

Die niedrigen und hohen Ränge sind 0-indiziert und unterscheiden sich für Spieler, die an einem Unentschieden beteiligt sind. Sie geben den Bereich der Spieler an, mit denen dieser Spieler gleichauf ist. Wenn zum Beispiel an der Spitze ein Dreiergleichstand herrscht, haben die Spieler 0, 1 und 2 jeweils einen niedrigen Rang von 0 und einen hohen Rang von 2.

Wenn Sie den obigen Codeforces-Befehl mindestens ein paar Sekunden lang ausgeführt haben, haben Sie einige Beispiel-Wettbewerbsdateien in cache/codeforces/ heruntergeladen, die Sie als Referenz verwenden können.

Unter Berücksichtigung dieses Dateiformats können Sie Ihre eigenen Wettbewerbe wie folgt durchführen:

• Nummerieren Sie Ihre Dateien mit aufeinanderfolgenden Ganzzahlen, wobei der erste Wettbewerb in 0.json gespeichert wird, der zweite in 1.json und so weiter.

• Platzieren Sie Ihre Dateien im cache/{dataset_name}/ .

• Führen Sie abschließend den gleichen Befehl aus, wobei jedoch codeforces durch {dataset_name} ersetzt wurden.

Mathematische Details

Bitte sehen Sie sich den vollständigen Beitrag an, der auf der Webkonferenz 2021 veröffentlicht wurde. Wenn Sie diese Kiste in Ihrer Forschung verwenden, denken Sie bitte darüber nach, unseren Beitrag zu zitieren.