Endergebnisse der Würfelliga aus dem Programmierwettbewerb

Das Abschlussturnier des Würfelwettbewerbs [1] ergab ein klares Ergebnis: An der Weltspitze geht es brutal eng zu. Die programmierten Bots »rockNroll« , »xubuntix« , »smitty« , »Toralf« und »fpunktk« von Christian Barth und Thomas Wagner, Stefan Schwarzburg, Christoph Tenzer, Toralf Förster sowie Felix Kästner waren merklich erfolgreicher als der Rest des Teilnehmerfelds, allerdings liegen alle nur um etwas mehr als einen halben Prozentpunkt auseinander (siehe Tabelle1).

Der beste Bot »rockNroll« gewann insgesamt 56,77Prozent der 88 800 Spiele, die jeder Bot spielte. Der zweitplatzierte »xubuntix« liegt nur 67 Siege dahinter, was 0,07Prozentpunkten entspricht. Dabei erwies sich »rockNroll« als der "heimstärkste": Er gewann als einziger Bot über 61 Prozent der Spiele, die er selbst begonnen hatte. Die meisten "Auswärtssiege" hingegen heimste »xubuntix« ein, nämlich 53,53Prozent, was allerdings nicht für den Gesamtsieg reichte.

Die in Java implementierte Strategie des Gewinners war relativ einfach: In einer Tabelle legt er die Augenzahlen ab, die er während des aktuellen Durchgangs erreichen will, bevor er an den Gegner abgibt. Der zweitplatzierte Bot kommt sogar mit zwei If-Statements über die eigenen und gegnerischen Punkte sowie 70Zeilen Python-Skript aus, um zu entscheiden, ob er nochmal würfeln will.

Im direkten Duell gibt übrigens »rockNroll« den Ton an, wenn er 54,3 Prozent der Heim- und immerhin 50,3 Prozent seiner Auswärtsspiele abräumt. Trotzdem ist der Bot nicht unbesiegbar: Zuhause verliert der Gewinner gegen die vier Bots »Sebastian« , »ponto« , »picard« und »massimo« mehrheitlich, auswärts gegen den letztgenannten in beachtlichen 61,8Prozent seiner Matches. Dennoch erzielt »rockNroll« über das gesamte Feld die konstantesten Leistungen.

Strammes Programm

Ein Blick in die Tabelle zeigt, dass Bots, die mit dem Würfeln beginnen, überwiegend gewinnen. 93 der 112 Bots im Teilnehmerfeld erzielen dann mehr als 50 Prozent Gewinne. Jeder Bot hatte jeweils 800 Spiele gegen jeden anderen Teilnehmer ausgefochten, je zur Hälfte als erster und als zweiter Spieler. Den nötigen Zufall bezog der Dice-or-Die-Gameserver in der Version 0.5.0 aus einer 1,5GByte großen, echten Zufallszahlendatei, die das Max-Planck-Institut für die Physik des Lichts aus Erlangen beigsteuert hat.

Um das Turnier durchzuführen, bestand für die Jury die Aufgabe darin, jede Paarung in jeder Konstellation 400 Mal spielen zu lassen. Der naive, aber deterministische Ansatz lautet, zwei Schleifen ineinander zu schachteln und so das Würfelspiel dieser Paarung zu starten. Er scheitert am asynchronen Netzprotokoll: Die einzelnen Bots liefern an den Aufrufmechanismus keine einheitliche Vollzugsmeldung zurück, dass sie mit dem Gameserver verbunden sind. Die ist aber notwendig, um die Reihenfolge zu gewährleisten. Denn einige Bots starten schneller als andere, die beispielsweise komplexe Datenstrukturen initialisieren, und sind daher immer der erste Spieler einer Paarung.

Monte-Carlo-Methode

Außerdem würde dieser Ansatz keine Parallelisierung der Matches erlauben: Das Protokoll liefert dem Bot keine Möglichkeit, nur gegen einen ganz bestimmten Bot anzutreten – nämlich gerade denjenigen, den das Steuerungsskript auswählt. Liefen jedoch die Matches seriell ab, hätte dies eine erhebliche Verlängerung der Ausführungszeit zur Folge. Empirische Versuche haben gezeigt, dass der Gameserver in der Lage ist, im Schnitt zehn Spiele gleichzeitig zu koordinieren. Ein serielles Ausführen dauert also zehnmal so lange.

Aus diesem Grund arbeitet das Turnierskript nicht deterministisch, sondern setzt einen probabilistischen Ansatz um: Es ruft in zwanzig parallelen Threads jeweils einen zufälligen Bot auf [2]. Der Gameserver notiert die Ergebnisse, und ein Auswerteskript sucht sich die ersten 400 Ergebnisse aus dem Protokoll heraus. In der Regel funktioniert das prima. Allerdings brauchten einige Bots rund 100-mal so lange wie der Durchschnitt zum Start, etwa weil sie Teile ihres Java-Codes jedes Mal neu übersetzten. Daher hat die Jury zum Abschluss verstärkt die langsamen Bots gegeneinander spielen lassen.

Bei einem halben Dutzend Paarungen war es nicht möglich, in angemessener Zeit automatisiert 400 Begegnungen ausspielen zu lassen. Aus diesem Grund sind alle Ergebnisse der Paarungen auf Prozentwerte normalisiert. Die genaue Betrachtung zeigt jedoch, dass selbst dann, wenn diese Bots alle fehlenden Spiele gewonnen hätten, das Ergebnis nur um Zehntelpunkte differiert hätte.

Abbildung 1: Alle 112 Würfelspieler gegen ihre Gegner spielen zu lassen, bringt selbst Open Office an seine Grenzen. Das große Bild zeigt alle Ligaspiele in der Übersicht. Da die guten Spieler dichter beieinander liegen, lassen sich die schlechten Spieler besser ausmachen: Sie haben waagerechte weiße (weniger als 45 Prozent der Spiele gewonnen) oder senkrechte rote Streifen (mehr als 55 Prozent der Spiele verloren). Meist treffen sich die Linien an der Hauptdiagonalen.