Seit mehr als drei Jahren zeigte das Online-Rätselspiel Digit Party den Spielern manchmal eine perfekte Punktzahl an … die in Wirklichkeit unmöglich zu erreichen war.
Das Prinzip des Spiels ist einfach. Ein Raster enthält 25 Felder, in die der Spieler nach und nach Zahlen einträgt. Identische Werte bringen Punkte, wenn sie sich berühren, auch diagonal. Drei zusammenliegende 8er können so 24 Punkte bringen, während ein einzelner 8er nichts einbringt.
Zwei Raster mit zwei unterschiedlichen Anordnungen bei derselben Ziehung, die verschiedene Verbindungen zeigen.
Am Ende einer Partie zeigt Digit Party auch die theoretisch maximal mögliche Punktzahl an. Genau diese Zahl war das Problem. Seine Schöpfer, die Mathematiker Vincent Vatter und Robert Brignall, wussten, wie man einen Wert berechnet, den kein Spieler überschreiten konnte. Doch diese Grenze war nicht immer tatsächlich erreichbar.
Um zu verstehen, warum, muss man das Raster als Ordnungsproblem betrachten. Jede Zahlengruppe hat für sich genommen eine ideale Anordnung: die 4er zusammen, die 8er zusammen usw. Doch alle diese Anordnungen müssen sich anschließend dieselben 25 Felder teilen. Und manchmal verhindert das, was für eine Gruppe perfekt ist, dass eine andere Gruppe ihre beste Anordnung erreicht.
Mit anderen Worten: Die Addition der bestmöglichen Ergebnisse für jede Zahl ergibt nicht zwangsläufig das beste Gesamtergebnis des gesamten Rasters. Genau das führte das Spiel in die Irre. Von 1.096 täglichen Rastern, die in drei Jahren angeboten wurden, zeigten 55 somit ein unerreichbares Ziel. Der Fehler war gering: etwa zwei Punkte im Durchschnitt und höchstens sechs, bei Punktzahlen, die meist zwischen 150 und 200 lagen.
Nun musste noch eine Methode gefunden werden, die schnell genug war, um das Problem zu beheben. Theoretisch kann Digit Party etwa 13,9 Millionen verschiedene Ziehungen erzeugen. Die Forschenden stellten jedoch fest, dass viele sich mathematisch ähneln. Entscheidend ist vor allem, wie oft jede Zahl vorkommt, nicht ihr exakter Wert.
Indem sie Ziehungen mit derselben Struktur zusammenfassten, reduzierten sie die Millionen Möglichkeiten auf 1.291 Grundfälle. In 891 Fällen können alle Zahlengruppen gleichzeitig ihre beste Anordnung erreichen. Bei den übrigen 400 muss man irgendwo den Verlust einiger Punkte in Kauf nehmen.
Die Forschenden berechneten daher im Voraus die vorteilhaftesten Kompromisse. Wenn das Raster beispielsweise nicht erlaubt, alle 4er und alle 8er perfekt zu gruppieren, kann es besser sein, bei den 4ern ein paar Punkte zu opfern. Die 8er sind mehr wert und können diesen Verlust ausgleichen. Das Spiel kann nun sofort das tatsächliche Maximum für jede Ziehung ermitteln.
Diese Geschichte knüpft an ein klassisches Optimierungsproblem an: Mehrere für sich genommen hervorragende Entscheidungen ergeben nicht zwangsläufig gemeinsam die beste Gesamtlösung. Dasselbe Prinzip findet sich, wenn man Zeitpläne organisieren, ein Fahrzeug beladen oder Aufgaben in einer Fabrik verteilen muss.
Eine weitere Frage bleibt offen. Die Kenntnis der maximalen Punktzahl verrät noch immer nicht, wie ein Spieler spielen muss, um sie zu erreichen, denn die Zahlen erscheinen erst eine nach der anderen. Selbst die beiden Schöpfer von Digit Party wissen noch nicht, welche Strategie die beste ist.