Ein Ranglistensystem für beliebige Mehrparteienspiele

Auf dem Manor-Con 1991 in Birmingham fand unter anderem ein 1830-Turnier statt. Die Rahmenbedingungen für dieses Turnier waren derart, daß ich sie zunächst kaum glauben mochte.

In der Ausschreibung für dieses Turnier waren die exakten Bewertungskriterien nicht angegeben (damit niemand 'auf Turnier' spielen konnte). Bekannt waren lediglich folgende Aussagen:

Da bei den beiden letzten 1830-Meisterschaften ausgiebig über das Bewertungssystem diskutiert wurde, nehme ich an, daß für ein System, das alle obigen Bedingungen erfüllen könnte, Interesse oder gar Verwendung bestehen könnte.

Das System läßt sich mit kleinen Änderungen auf beliebige Spiele ausweiten, solange diese ein Endergebnis produzieren, das jedem Spieler eine Punktzahl zuordnet, die repräsentiert, wie gut der Spieler abgeschnitten hat (hat X doppelt so viele Punkte wie Y, dann soll dies bedeuten, daß er doppelt so erfolgreich war).
Dies ist eine wichtige Forderung für das im folgenden zu beschreibende Verfahren - man kann also z. B. nicht eine Menge von Golf-Auswertungen in Form der Schlag-Anzahlen eingeben, weil bei Golf ein Spieler mit einer niedrigeren Schlagzahl mehr erreicht hat. (Aber statt dessen z. B. die Ranglistenpunktzahlen, die in den einzelnen Partien zugeteilt wurden - das habe ich für die GOLF-Partien des AB inzwischen ausprobiert.)

Wie geht das nun alles? Ich habe Dane Maslen, den Spielleiter in Birmingham, gefragt, und er hat mir (obwohl er einige Details nicht aufdecken wollte) folgendes erzählt:

Bewertung einzelner Partien

Die Leistung aller Spieler soll auf eine Skala abgebildet werden, die vom konkreten Spielverlauf (bei 1830 z. B., ob das Spielende durch Leerung der Bank ausgelöst wurde oder ob ein Spieler geplatzt ist - wodurch die Geldbeträge der Spieler relativ stark differieren können) relativ unabhängig sein soll.
Es wird also eine 'Durchschnitts-Bewertung' benötigt, so daß alle Punktzahlen in Prozent dieses Durchschnittswertes ausgedrückt werden können.

Bisher wurde in 1830-Turnieren

als Norm-Wert (100%) ausprobiert.
Alle drei Verfahren konnten allerdings nicht uneingeschränkt überzeugen:

Dane konstruierte dagegen das folgende Pascal'sche Dreieck

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 ... ... ... ... ... 1

, in dem jeweils ein Element als Summe der beiden schräg darüberliegenden Elemente gebildet wird. Diese Zahlen werden nun als Gewichte der Einzelergebnisse der Spieler verwendet.

In einer Vierer-Partie wird also die Durchschnitts- bzw. Referenzzahl E aus den Einzelergebnissen E1, E2, E3 und E4 (für die Plazierungen 1-4) nach der Formel

E = ((1 * E1) + (3 * E2) + (3 * E3) + (1 * E4)) / (E1 + E2 + E3 + E4)

berechnet.

Ähnlich wie beim Median werden also Ergebnisse der mittelplazierten Spieler stärker, aber nun nicht mehr ausschließlich in das Ergebnis einbezogen. Jeder Spieler kann durch seine Leistung neben der eigenen Punktzahl auch die Referenzzahl noch ein wenig steigern (und damit die Ergebnisse aller anderen Spieler drücken), was er nach der Median-Methode nur als Mittelplazierter kann.

Hat man nun eine solche Referenzzahl, dann kann man die Ergebnisse aller Spieler normieren. Man könnte z. B. nun sämtliche Ergebnisse direkt in Prozente dieser Norm-Zahl umrechnen. (Dies wäre auch die direkte Anwendung der bisherigen Ausführungen auf die 1830-Meisterschafts-Wertung und ähnlich der zuletzt verwendeten Median-Wertung.) Dies allerdings würde einen knappen zweiten Platz ebenso hoch bewerten wie einen Sieg. Daher verwendete Dane eine völlig andere Bewertung:

Bei einer Beispiel-Partie (1830/Bankrott) mit 6 Spielern und den Ergebnissen

(E1=5000, E2=4800, E3=4700, E4=4500, E5=4400, E6=1000)

ergeben sich als Referenzwert 4500 und als Ranglistenwerte nach Danes Methode

S1 := 5000/4500 = 1.111, S2 := 0.960, S3 := 0.940, S4 := 0.900, S5 := 0.880, S6 := 0.200,

bei strikter Normierung auf den Referenzwert aber

S1 := 5000/4500 = 1.111, S2 := 1.067, S3 := 1.044, S4 := 1.000, S5 := 0.978, S6 := 0.222.

Der Sieger wird von Dane also deutlich bevorzugt; sein Abstand zum Zweiten ist weitaus größer als dessen Abstand zum Vorletzten. Bei der strikten Normierung ist es umgekehrt.

Ich bin der Meinung, daß in einem Spiel, in dem die Ergebnisse der Spieler mit Siegpunkten bewertet werden, ein Sieg bei einem minimalen Abstand (der während der Partie oft gar nicht erkennbar ist) einem zweiten Platz nicht so massiv vorgezogen werden sollte, und würde daher eher alle Spieler auf den berechneten Referenzwert skalieren. (Was ich im folgenden auch immer voraussetzen werde.)

Gewichtung von Partien mit unterschiedlich vielen Spielern

Nach Dane Maslens Verfahren wird der Sieger stark beschenkt. Dies macht bezüglich der durchschnittlichen Wertung einer Partie für eine Partie mit wenigen Spielern mehr aus als für eine Partie mit vielen Spielern.
Dane besitzt, um diesen Effekt zu korrigieren, eine Tabelle mit vielen, vielen Ergebnissen von 1830-Partien und hat aus diesen die entsprechenden Gewichtungsfaktoren empirisch ermittelt:

Spieler23456
Faktor1.031.071.111.151.21

(Werte nur ungefähr korrekt, weil spontan aus Danes Gedächtnis.)

Diese Faktoren müßte man für das zu behandelnde Spiel selbst ermitteln.
Wenn man allerdings alle Einzelergebnisse der Spieler gleichermaßen auf den Referenzwert normiert, sollte dieses Problem nicht auftreten.

Es läge nahe, alle Spielwerte mit einem Faktor zu multiplizieren, so daß ihre Summe gleich der Anzahl der Teilnehmer ist und damit der Mittelwert der Ergebnisse jeder einzelnen Partie 1.0 beträgt. (Das würde auch die Korrektur von Dane mit erledigen.)
Die Sache hat aber einen Haken: Gerade durch eine solche Normierung würde ein "Ausreißer", also ein klarer Erster bzw. Letzter, nun doch wieder starken Einfluß auf das Ergebnis aller Spieler bekommen, was durch das Pascalsche Dreieck ja gerade verhindert werden sollte. Also doch lieber nicht. Ob der Punkteschnitt einer Partie etwas höher oder etwas niedriger ist, hat auf das Ergebnis des Einzelnen ja keinen Einfluß.

In jedem Falle sollten alle Partie-Ergebnisse in etwa vergleichbar sein - vorausgesetzt, es waren jeweils gleich starke Spieler daran beteiligt. Dazu aber später mehr.

Bewertung mehrerer Partien

Dies ist ein Punkt, der bei einer Meisterschaft nicht unbedingt auftreten muß (da man ja administrativ sicherstellen kann, daß jeder Teilnehmer gleich viele Partien absolvieren muß). Dennoch kann man auch mit unterschiedlich vielen Partien pro Spieler fertig werden.
Interessant ist dieser Punkt aber für lokale Ranglisten von Spielen, bei denen nicht immer dieselben Spieler teilnehmen, etwa für einen regionalen Spielerkreis oder ein Zine.

Naheliegend wäre zunächst einmal eine einfache Durchschnittsbildung der Ergebnisse pro Spieler. Diese würde aber einen Teilnehmer mit vielen Partien gegenüber einem Neuling, der nur einen Glückstreffer gelandet hat (und später nie mehr mitspielt, um seinen Ranglistenplatz nicht zu beschädigen!), benachteiligen.
Was man also haben will, ist eine Skalierungsfunktion, die für einen Neuling eine Abwertung vornimmt, sich bei hinreichend vielen Partien eines Spielers aber asymptotisch immer mehr an einen Grenzwert annähert. Es bietet sich daher an, die Summe von N; Partien nicht durch N, sondern durch N+X zu teilen.

Nun haben aber unterschiedliche Werte von X unterschiedliche Wirkungen. Je höher X ist, desto mehr wird es belohnt, daß man viele Partien in der Wertung hat.
Möchte man ein Rangliste für ein selten gespieltes Spiel aufstellen, bei dem ein großer Teil der erfaßten Teilnehmer nur wenige, vielleicht gar nur eine Partie absolviert haben, dann ist es vermutlich sinnvoll, an Spielerfahrung schon zwischen 5 und 6 Partien nicht mehr deutlich zu unterscheiden, also eine schon bald abflachende Gewichtungskurve einzubauen, sprich: ein kleines X zu verwenden.

Beispiel:

Liegt aber ein Spiel vor, bei dem für jeden Teilnehmer eine große Art von Einzelergebnissen verfügbar ist, dann würde eine Division etwa durch N+1 für die meisten Spieler wenig bewirken, da die '1' bei großem N relativ bedeutungslos würde, sprich: es würde nun eben doch wieder für jeden Teilnehmer in etwa das arithmetische Mittel seiner Ergebnisse bestimmt. Hier würde sich also ein größeres X anbieten, wodurch erst eine größere Anzahl an Partien als "Spielerfahrung" bzw. "regelmäßig erbrachte Leistung" gewertet würden.

Daraus habe ich den Schluß gezogen, daß eine vernünftige Wahl für X direkt aus den vorliegenden Eingabedaten bestimmt werden kann. Ich schlage vor, X = M-1 zu setzen, wobei M das arithmetische Mittel der Anzahlen der von den einzelnen Teilnehmern absolvierten Partien ist. Damit würde sich die Funktion zur Belohnung der Spielerfahrung der Menge der vorhandenen Spielerfahrung anpassen.

Für ein Spiel, bei dem von allen Beteiligten gerade die erste Partie gespielt worden ist, wird für jeden Spieler sein Ergebnis durch (1 + M-1), also durch 1 geteilt. Dies gilt immer dann, wenn alle Beteiligten gleich viele Partien in der Wertung haben.

Bewertung unterschiedlich stark besetzter Partien

Alle bisherigen Punkte konnte man, wenngleich mühsam, noch per Hand vornehmen. Um das durch diese Überschrift angedeutete höchste Ideal zu erreichen, wird es allerdings eines Programmes bedürfen.

Vorweg noch zur Motivation: Es ist nach wie vor offen, ob es für ein Mehrpersonenspiel-Turnier günstig ist, daß Teilnehmer (die eventuell von weit her zu einem Turnier angereist sind) ausscheiden müssen. Andererseits besteht die Gefahr, daß sie bei schlechter Position unmotiviert spielen und ggf. andere Partien verzerren.

Es wäre also vorteilhaft, wenn

Beides macht Meisterschaften bestimmt fairer und die Ergebnisse regulärer.

Wie ist vor allem letzteres nun zu erreichen?

Nach der bisherigen Beschreibung kann man jedem Spieler eine (auf die von ihm absolvierte Anzahl von Partien normierte) Ranglistenpunktzahl zuordnen, die er aufgrund seiner Ergebnisse erreicht hat. Diese Liste der Gesamtpunktzahlen kann man nun geeignet skalieren, und zwar am besten so, daß die Summe über alle Spieler von Stärke mal Partiezahl gleich der Summe der Teilnehmerzahlen an allen erfaßten Partien ist. Wieso das, wird im folgenden klar werden.

Hat man diese skalierten Stärkewerte, dann kann man aus ihnen nun die Stärkewerte eines jeden Tisches, also das Niveau einer jeden gespielten Partie, ausrechnen (z. B. als Mittelwert der Stärkewerte der Teilnehmer, da im Idealfall alle Teilnehmer gleich stark am Ausgang der Partie beteiligt waren).

Diesen Wert kann man nun als Gewicht (Faktor) für die Punktzahlen aller Einzelergebnisse verwenden. Damit werden die ursprünglich gespielten Partien nun neu bewertet: Saßen an einem Tisch lauter Spieler, die insgesamt hohe Punktzahlen erzielt haben, dann werden ihre Ergebnisse nun allesamt mit einem hohen Partie-Niveau bewertet. Diese Partie-Niveaus werden sich um den Wert von 1.0 bewegen (bei starken Partien höher, bei schwachen niedriger; genau so habe ich die oben beschriebene Normalisierung gewählt) und können daher in Prozenten einer theoretischen Durchschnittspartie ausgedrückt werden.

Nach dieser Neu-Bewertung aller Partien führt man von den vorherigen Berechnungen die Bestimmung aller Spieler-Ergebnisse und die Normierung aller Ranglistenwerte noch einmal durch und erhält nun ebenfalls wieder eine Gesamtbewertung für jeden Spieler. Diesmal ist schon berücksichtigt, wie schwer ein Spieler es in seinen Partien hatte - jedenfalls ungefähr. Denn durch diese Berücksichtigung ändern sich natürlich gerade diejenigen Werte, die im 2. Durchgang der Berechnung als Stärkefaktoren verwendet wurden! Also müßte man nun erneut die gesamte Berechnung mit den neuen Stärkefaktoren durchführen ...

Wenn man dieses Verfahren (per Rechner) einige Male durchlaufen läßt, dann pendeln sich die Punktzahlen während dieses Iterationsverfahrens schließlich auf stabile Werte ein. Das klingt auch plausibel, weil sich die Stärkewerte normalerweise eher aus den Ergebnissen der einzelnen Spieler ableiten als aus den Stärkewerten der Tischnachbarn (die meist zwischen 0.5 und 1 liegen) - ein Spieler, der eine Partie gewonnen hat, wird dafür praktisch immer eine ordentliche Punktzahl erhalten, auch wenn er überwiegend mit Versagern gespielt hat (schließlich hat er ja die erwartete Leistung gebracht).

Tendenziell werden die Ranglistenwerte (da sie ja bei der Skalierung auf die Zahl der Partien pro Spieler kleiner werden als die Summe der arithmetischen Mittel) im Schnitt kleiner als 1 sein, also für die Berechnung der Partie-Niveaus jeweils nach oben skaliert werden müssen.
Daraus kann man schließen, daß - würde man die Partie-Niveaus direkt als arithmetisches Mittel dieser Ranglistenwerte bestimmen - die neu bestimmten Werte immer kleiner werden würden. Um diesem Effekt zu begegnen, ist die oben erwähnte Skalierung der Ranglistenwerte auf einen Durchschnitt von 1 erforderlich.

Im Fixpunkt der Iteration werden aus Partien, die mit einem derartig hochskalierten Partie-Niveau versehen wurden, wieder Spielerstärken bestimmt, die (nach wie vor) im Schnitt kleiner als 1 sind. Die Spielerstärken selbst werden also nie einen Fixpunkt erreichen - aber das Verfahren wird einen Skalierungsfaktor > 1 liefern, für den ein weiterer Iterationsschritt immer wieder dieselben Ergebnisse liefern wird. (Dieser Abschnitt muß nicht von jedem verstanden werden ... Ergänzung für Mathematiker: Christian Götze hat später gezeigt, daß das Verfahren - nach der entsprechenden Skalierung - gegen den Eigenvektor der zugeordneten Auszahlungsmatrix konvergiert.)

In jedem Durchgang der Iteration kann man nun eine Abstandsfunktion zwischen alten und neuen Werten berechnen, z. B. die Summe der Quadrate der Abweichungen der jeweils neuen von den alten Ranglistenwerten. Je kleiner dieser Funktionswert wird, desto stabiler wird die Ranglistenbewertung; unterschreitet dieser Genauigkeitswert einen vorzugebenden kleinen Wert Epsilon, dann kann die Berechnung beendet werden.
(Inhaltliche Ergänzung: Bei der Berechnung der Partie-Niveaus geht es letztlich mehr um die Spielstärke der Teilnehmer als um die Reproduktion von deren Leistung. Deshalb haben wir später die Abwertung bei der Bewertung mehrerer Partien aus dem eigentlichen Iterationsprozeß zur Berechnung der wahren Spielstärke aller Spieler herausgenommen und wenden diese Abbildung nur noch auf das Ergebnis der Iteration an. Andernfalls würde man dafür bestraft, gegen Spieler mit wenigen Partien im Datenbestand zu spielen, selbst wenn diese durch ihre Leistungen eine gute Spielstärke demonstriert haben.)

Anwendung

Warum nun diese höchst trocken klingenden erschöpfenden Ausführungen mit so vielen Details?

Ich glaube, daß man mit einem Verfahren, das so wie hier beschrieben arbeitet, für eine Vielzahl von Turnieren beliebiger Spiele ein Schema zur Bewertung erhalten kann, das die anfangs erwähnten Vorteile zusammenfaßt:

Mit einem solchen Verfahren könnte man z. B. in einer 1830-Meisterschaft zwei Vorrunden spielen lassen und dann

stecken, hätte somit spannende Partien mit einheitlichem Niveau und trotzdem müßte niemand befürchten, von Spielern leichterer Partien zu einfach überholt zu werden. Ein geschenkter Sieg in der Trostrunde bringt keine Medaillenchance mehr, weil die Partie aufgrund der schwachen Besetzung ein niedriges Partie-Niveau besitzt - wenn ein Spieler im Finale aber platzt, kann er noch weit zurückfallen.

Da mir die Automatisierung des Verfahrens nach der bisherigen Voranalyse nicht mehr besonders schwierig erschien, habe ich ein Programm erstellt, welches das in diesem Artikel beschriebene Verfahren zur Erstellung einer Rangliste aus einzelnen Partie-Ergebnissen verwendet.
Ich rufe alle, die in den nächsten Monaten irgendwelche Turniere veranstalten wollen, auf, mit mir über ihre Bewertungskriterien zu diskutieren, und alle, die das hier beschriebene Programm (in Maxon-Pascal und Turbo-Pascal, also mindestens auf Atari und PC) verwenden wollen, mir Ideen für mögliche Parameter, eine erwünschte Eingabesyntax und anderes mehr mitzuteilen. (Bisher ist alles "hart verdrahtet".)
(Inhaltliche Ergänzung: Inzwischen hat Dirk Clemens unter dem Namen ANALYSE ein weitaus besser konfigurierbares Programm veröffentlicht, welches eine Obermenge meines Programms darstellt, allerdings einige inhaltliche Kenntnisse bei der Bändigung der zahlreichen Konfigurationsparameter erfordert.)

Mit einer lokalen Rangliste für ein häufig gespieltes Spiel kann man vielleicht auch Effekte erzielen, die mit anderen Mitteln nicht ohne weiteres möglich sind.

Beispiel:

In einem NMR- und Drop-Out-empfindlichen Spiel (wie etwa Kapitalisten-Diplomacy, bei dem die im AB zuletzt beendete Partie durch den Drop-Out eines Spielers mit zwei Militärkontrollen stark beeinflußt wurde) könnte man gezielt Partien anbieten, bei denen der GM ein gewisses Mindest-Niveau (hier bildlich gemeint) versprechen kann.
Um die entsprechenden Teilnehmer nicht so leicht durch ein schwarzes Schaf unterwandern zu lassen, könnte der GM (statt der nach wie vor nicht praktikablen Schwarzen Liste) die entsprechende Rangliste zu Rate ziehen, in der die führenden Spieler in den vorherigen Partien nicht nur gute, sondern auch regelmäßige Leistungen erbracht haben. Ein Drop-Out endet normalerweise mit 0 Punkten und kann einen Ranglistenplatz durchaus beschädigen - zur "Wiedergutmachung" sind meist mehrere ordentlich gespielte Partien erforderlich. Und das wäre dann ja gerade der Nachweis, daß der einstige "Sünder" sich inzwischen gebessert hat.

(Inhaltliche Ergänzung: Genau dies wurde in den darauffolgenden Jahren im Amtsblatt bei den Kapitaliste-Diplomacy-Partien tatsächlich praktiziert: Bei einer Profi-Partie wurden 1996 die Anmeldungen von in der - von mir geführten - Rangliste weiter oben plazierten Spielern vorrangig berücksichtigt, während für eine Anfängerpartie 1998 bevorzugt Spieler ohne bzw. mit einer schlechteren Plazierung in der Rangliste verwendet wurden.)

Anhang: Ergebnisse des Programmeinsatzes

Meine ersten Erfahrungen mit dem Programm kann ich inzwischen schildern.
Ich habe vier Ranglisten berechnen lassen, für die jeweils etwa 10, 10, 70 bzw. 100 Partien von im Amtsblatt ausgetragenen Spielen (mit bis zu 27 Teilnehmern) verwendet wurden. Die Berechnung dieser Ranglisten dauerte (auf einem Atari bzw. 80286-Rechner) jeweils nur wenige Sekunden bis eine Minute.

Das Programm gibt hierbei aber nicht nur eine ausführliche Spieler-Rangliste aus, sondern auch eine Liste aller bewerteter Partien, wobei zu jeder Partie angegeben wird,

Die als "Anfängerpartie" ausgeschriebene KapDip-Partie Partisanen, bei der keiner der ersten fünf Ranglistenspieler mitgespielt hat, hat ein Partie-Niveau von nur 60.4%; für einen relativ klaren Sieg (170.5% des Referenzwertes) erhielt der Sieger also nur 1.03 unnormalisierte Ranglistenpunkte.
Die Kap-Dip-"Profipartie" Wutanfall, an der die Ranglistenspieler der Positionen 1, 2, 3, 4, 5, 6, 7, 10, 17 und 22 (von 49) teilgenommen haben, bekam dagegen ein Partie-Niveau von 142.2%, so daß die ersten vier Plazierungen (169.3% bis 156.8% des Richtwertes) satte 2.41 bis 2.23 unnormalisierte Ranglistenpunkte wert waren; selbst ein mäßiges Ergebnis von 85.7% des Referenzwertes war mit 1.22 unnormalisierten Ranglistenpunkten wertvoller als der Sieg in der Anfängerpartie! (Und vermutlich auch schwieriger zu erreichen.)

Michael Schröpl
(Original-Artikel für Interzine ca. 1991/92;
inhaltliche Aktualisierung 1998-07-26)