Ranking-Verfahren für 1st-person-shooter

Statische Rankings

In diesem Abschnitt geht es um das Problem, mit Hilfe vorhandener Daten die Spielstärken der Spieler gegeneinander abzuschätzen. Hierbei wird die Spielstärke eines Spielers als eine zu suchende Konstante angesehen. Eine zeitliche Entwicklung ist hier noch nicht vorgesehen. Diese wird im Abschnitt über dynamische Rankings behandelt.

Die Daten

Folgende Daten sollen vorhanden sein:

nDie Gesamtzahl der Spieler
a_ijDieser Eintrag einer quadratischen n×n-Matrix a gibt an, wie wieviele frags Spieler i gegen Spieler j erzielt hat (d.h. wie oft Spieler i Spieler j getötet hat). Der Eintrag a_ii gibt die Anzahl der suicides von Spieler i an.

Die Daten können über ein oder mehrere Spiele gesammelt worden sein. Besser sind mehrere Spiele. Sind die frag-Zahlen a_ij zu klein, bekommt man Probleme mit der statistischen Relevanz. Dies werde ich im Abschnitt über die statistische Relevanz noch kurz diskutieren.

Das Ranking als Optimierungsproblem

Wir versuchen nun, jedem Spieler eine Spielstärke g_i zuzuordnen. (Diese nennen wir auch "Güte".) Die Spielstärken sollten nach Möglichkeit so gewählt sein, daß man aus g_i und g_j sofort ablesen kann, wie gut Spieler i im direkten Vergleich mit Spieler j ist:

   (g_i-g_j) = (a_ij-a_ji)/(a_ij+a_ji)

Offensichtlich sollten die g_i zwischen 0 und 1 liegen. Obige Gleichheit wird natürlich nicht für alle i,j zu erfüllen sein. (Es kann z.B. sein, daß Spieler 1 besser 2 ist, 2 besser als 3, und 3 wiederum besser als 1.) Deshalb versuchen wir die Zahlen g_i so zu wählen, daß die Summe der Fehlerquadrate (summiert über alle Paare (i,j) (i!=j)) minimiert wird. Die Lösung ist

   g_i = 1/n * \sum_{j!=i} (a_ij+a_ji)/(a_ij+a_ji)

Gibt es (i,j) mit a_ij+a_ji=0, so ist das Problem nicht wohlgestellt. Leider kommt dies in der Praxis recht häufig vor, weil sich nicht alle zwei Spieler treffen. Wir schlagen vor, die entsprechenden Summanden einfach wegzulassen und die Zahl n in der Formel für das g_i entsprechend zu verkleinern.

Suicides

In obige Formel geht die Anzahl der Selbsttötungen eines Spielers nicht ein, und sie ist auch nicht ohne Probleme einzubauen. Was man machen könnte, ist z.B. die Zahl a_ii/B_i abzuziehen, wobei B_i die Gesamtzahl aller frags, in die Spieler i verwickelt war, ist. Alternativ könnte man versuchen, die Selbsttötungen des Spielers i anteilsmäßig unter seinen Gegenspielern aufzuteilen, bevor man die Formel anwendet.

Dennoch bleiben alle Möglichkeiten, die Anzahl der suicides nachträglich einzubauen, recht willkürlich, und ihre Auswirkungen sind nicht so klar. In der Praxis stellte uns keine Lösung wirklich zufrieden.

Das Problem der statistischen Relevanz

Bei den ersten Proben mit dieser Formel in der Praxis stellt sich schnell heraus, daß Spieler besonders gut abschnitten, die kaum mitgespielt hatten. Ja, je länger jemand mitgespielt hatte, desto kleiner wurden seine Chancen, im Ranking auf den oberen Plätzen zu landen. Und zwar war das Problem, daß Spielstände von 1:0 oder 2:0 zwischen zwei Spielern die Statistik deutlich dominierten.

Versuche, die entsprechenden Quotienten in der Formel entsprechend abzuwerten oder geringer zu gewichten, scheinen theoretisch sauber, ließen sich in der Praxis jedoch nur unzureichend realisieren. Letztlich erwies es sich als das einzig Praktikable, die Liste der Spieler soweit auszudünnen, daß nur noch ein "Kern" von Spielern blieb, von denen jeder gegen jeden genug frags geschafft hatte, um eine ordentliche Bewertungsgrundlage zu bilden.

Das Problem mit der Datenmenge

Ein weiterer gravierender Nachteil dieser Methode des ranking ist, daß die Menge der im Speicher zu haltenden Daten a_ij quadratisch mit der Anzahl der Spieler steigt. Zwar ist der Großteil der a_ij Null, aber eine Nicht-Speicherung dieser Nullen wiederum erhöht den Programmieraufwand und die Fehleranfälligkeit immens.

Dies ist ein prinzipielles Problem des Verfahrens, das nicht umgangen werden kann.

Dynamische Rankings

In diesem Abschnitt nun geht es um Rankings, die versuchen, eine zeitliche Entwicklung der Spielstärken wiederzugeben. Die verwendete Mathematik richtet sich hierbei nach derjenigen, die auch für die Weltranglisten für Schach und Tischtennis verwendet wird (ELO-Leiter). Nimmt man konstante Spielstärken an, so konvergieren in diesem Fall die errechneten Spielstärken im Laufe der Zeit gegen die richtigen Werte.

Eine Liga-Tabelle

Zunächst behandeln wir den den oben erwähnten Weltranglisten sehr ähnlichen Fall einer Liga, in der die Spieler paarweise (als zu zweit) gegeneinander spielen. Jedem Spieler i sei eine aktuelle Stärke g_i zugeordnet. Die Wahrscheinlichkeit, daß Spieler i gegen Spieler j gewinnt, ist per Konvention

   w_ij = 1 / (1+10^((g_i-g_j)/400))

Die Zahl 400 bestimmt hierbei lediglich, wie hoch die Punktezahlen in der Ligatabelle sein sollen. Nun sollen Spieler i und Spieler j gegeneinander gespielt haben. Wie sind g_i und g_j anzupassen? Ist a_i die Anzahl der frags von Spieler i und a_j die von Spieler j, so liegt die Zahl

   e_ij = a_i / (a_i+a_j)

zwischen 0 und +1 und gibt an, wie stark Spieler i gespielt hat. Geht ein Spiel 0:0 aus, so wird e_ij=0,5 gesetzt.

Die neuen Stärken der Spieler i und j werden nun wie folgt berechnet:

   g_neu_i = g_i + K * (e_ij-w_ij)
   g_neu_j = g_j + K * (e_ji-w_ji)

Wird einer der beiden neuen Werte kleiner als Null, so wird er auf Null gesetzt. Die Zahl K gibt an, wie dynamisch die Tabelle ist. Bei großem K reichen ein paar Siege, und schon schnellt man die Tabelle hoch. Genauso schnell kann man aber bei ein paar verlorenen Spielen auch wieder absacken. Bei kleinem K muß man über längere Zeit durchschnittlich gut spielen, um aufzusteigen. Wenn man zwischendurch mal ein paar Spiele verliert, macht das nicht so viel aus. K=40 ist ein vernünftiger Wert.

Man beachte, daß aus obiger Formel folgt, daß man heruntergestuft werden kann, selbst wenn man ein Spiel gewinnt. Nämlich dann, wenn man es nicht hoch genug gewinnt.

Die Einberechnung der suicides

Bei den Duellen wird die Zahl der suicides nicht gesondert angegeben, sondern sie wird von der Anzahl der frags abgezogen. Deshalb kann sie normalerweise nicht mehr gesondert einberechnet werden. Eine Ausnahme bildet der Fall, daß a_i oder a_j oder beide negativ sind. In diesem Fall kann man die obige Formel nicht benutzen.

Deshalb wird, wenn einer der Werte negativ ist, er von beiden Werten abgezogen. Einige Beispiele:

    6 : -2   wird zu   +8 :  0
   -3 : -5   wird zu   +5 : +3

Die zeitliche Reduktion

Spieler, die aufgehört haben zu spielen, oder die zu selten spielen, sollen in der Tabelle langsam abfallen. Ansonsten könnten Spieler, die eine sehr hohe Punktzahl erreicht haben, einfach aufhören zu spielen und sich auf ihren Lorbeeren ausruhen.

Deshalb werden von allen Stärken g_i in regelmäßigen Abständen Punkte abgezogen. Fällt dabei ein Spieler unter die Null-Punkte-Grenze, so bekommt er wieder Null Punkte zugeschrieben.

Woher die Punkte kommen

Vielleicht ist einem Leser aufgefallen, daß die Summe der g_i in obiger Formel sich nicht ändert: \sum g_i = \sum g_neu_i. Die einzige Ausnahme ist, wenn ein g_i negativ wird und deshalb auf Null gesetzt wird. Letztlich müssen also alle Punkte, die im Ranking auftauchen, einmal von unten nach oben durchgereicht worden sein.

Dynamische Rankings für Deathmatches

Um ein dynamisches Ranking zu erstellen, wenn die Spieler nicht paarweise gegeneinander spielen, sondern wenn viele Spieler in einer map gegeneinander spielen, gibt es eine recht gut funktionierende Lösung: Anstatt der Matrix a_ij verarbeiten wir direkt und der Reihe nach die Einträge in den log-Dateien der Spiele-Server. Jeden frag des Spielers i gegen den Spieler j werten wir als eigenständigen Zweikampf, den Spieler i 1:0 gewonnen hat.

Suicides können in das Ranking als -1:0-Ergebnisse gegen einen imaginären Spieler gleicher Güte eingebaut werden.

Dieses Verfahren funktioniert in der Praxis recht gut und eignet sich auch für sehr große Datenmengen, da für jeden Spieler nur eine reelle Zahl im Speicher oder in einer Datenbank behalten werden muß. Die Log-Dateien der Server können als Daten-Strom gelesen, zeilenweise abgearbeitet und dann weggeworfen werden.

Dynamische Rankings für CTF und andere Mods

Genauso einfach, wie man das Ranking für Multiplayer-Deathmatches anpassen kann, kann man damit andere Spiel-Modifikationen ranken. Hier wird dies am Beispiel CTF (Capture the Flag) gezeigt.

Zunächst sind die wichtigen Ereignisse zu identifizieren. Bei CTF sollen dies hier beispielsweise die Captures und die frags sein. (Es gibt noch andere, die ich hier nicht aufzähle, und die auch vom genauen Spiel abhängen.)

Für jedes dieser Ereignisse vergeben wir eine bestimmte Punktezahl x, beispielsweise 7 Punkte für ein Capture, und 1 Punkt für einen frag. Jedes Ereignis werten wir nun als x:0-Ergebnis für den Spieler, der daran beteiligt war bzw. als 0:x-Ergebnis für den Gegenspieler, sofern ein klar definierter Gegenspieler für das Ereignis überhaupt existiert. Bei Ereignissen, bei denen es keinen klar definierten Gegenspieler gibt, beispielsweise bei Captures, nehmen wir als Güte des Gegners in der Formel einfach das arithmetische Mittel der Güten aller Spieler des gegnerischen Teams.

Team-kills könnte man Einbauen als -1:0-Ergebnisse für den Spieler, der den Team-kill macht. Der getötete Mitspieler soll aber dabei weder herunter- noch hochgestuft werden.

Die Schnelligkeit der Konvergenz

Beim dynamischen Ranking fängt jeder Spieler bei Null an. Dann wird seine Güte im Laufe der Zeit ansteigen, zuerst schnell, dann immer langsamer, und gegen einen Wert konvergieren, der seiner realen Spielstärke entspricht.

Bei dynamischen Rankings in multiplayer-Spielen hängt die Geschwindigkeit der Konvergenz nicht nur von der Konstante K ab, sondern auch davon, in wieviele frags ein Spieler pro Zeiteinheit verwickelt ist. Spielt ein Spieler also sehr hektisch, so wird seine Güte recht schnell konvergieren. Ein anderer Spieler, der zwar genauso stark ist, aber bedächtiger spielt, wird in der ersten Zeit tiefer gerankt werden, weil seine Güte-Kurve nicht so schnell ansteigt.

Ist außerdem eine zeitliche Reduktion eingebaut, so hat der letztere Spieler außerdem noch einen Nachteil: Sein Grenzwert -ein Gleichgewichtszustand zwischen seiner wahren Spielstärke und der zeitlichen Reduktion- wird tiefer sein, als der Grenzwert eines hektischen Spielers mit gleicher Spielstärke.

Was wir noch nicht gemacht haben

Das einzige, was wir bisher ranken können, sind deathmatches, wobei wir auch Zweierduelle hierzu rechnen können. Folgende Sachen würden wir auch gerne ranken:

Verschiedene Rollen
Wie gut ist ein Spieler als sniper, als Sanitäter usw.? Kann man einem Spieler, der verschiedene Rollen spielt, eine "Gesamtstärke" zuordnen?
Clans
Die Wertung von Clans ist vom Prinzip her kein Problem. Man faßt einen Clan einfach als einen (virtuellen) Spieler auf. Man muß dabei lediglich darauf achten, daß die Vorfälle, wo ein Clan-Mitglied aus Versehen getötet wird, was einem suicide des virtuellen Spielers entspricht, irgendwie gewertet werden.

Gibt's dafür ein Programm?

Ja. Der Christoph, Spielern bekannt als AEon, hat ein Programm geschrieben, welches die Log-Dateien von Servern durchforstet und daraus html-Seiten mit allen möglichen Statistiken erstellt: AEstats.

Welche der obigen Verfahren nun im Detail implementiert sind, weiß ich allerdings nicht. Ich war nur für den mathematischen background zuständig.

by Michael Becker, 8/2001. Letzte Änderung: 4/2002.