Ein Spiel auf vier mal vier Feldern mit Suchtpotenzial, das gab es schon einmal. 1879 begann Matthias J. Rice in Boston das so genannte 15-Puzzle zu vermarkten: Auf 15 der 16 Feldern saßen fortlaufend numerierte Steine, das 16. Feld war eine Lücke. Die Steine waren durch Schieben in die korrekte Reihenfolge zu bringen. (Dass das nicht für jede Start-Permutation möglich ist, nutzte Spieleerfinder Sam Loyd aus, um mit einem Preis von 1000 Dollar den Hype um das Spiel noch weiter anzuheizen.)
Nun hat Gabriele Cirulli, ein 19jähriger Programmierer aus Norditalien, mit dem Computerspiel "2048" auf 16 Feldern auch einen ganz schönen Rummel erzeugt - und sein Spiel dürfte vor allem Mathematiker ziemlich reizen. Es geht diesmal nicht um Permutationen, sondern um Zweierpotenzen. Die Regeln sind einfach: Zu Anfang sind zwei zufällig ausgewählte Felder mit einer 2 oder einer 4 gefüllt. Drückt man nun eine der vier Pfeiltasten, dann "rutschen" alle bereits gefüllten Felder in die entsprechende Richtung, so weit sie können. Stoßen dabei zwei Felder mit gleichen Zahlen zusammen, dann vereinigen sie sich zu einem neuen Feld mit doppeltem Inhalt. Und: Nach jedem Zug wird ein weiteres, jetzt leeres Feld mit einer 2 oder 4 gefüllt. Ziel ist, die Felder mit möglichst wenigen Zügen mit möglichst großen Zahlen zu füllen.
Cirulli hat sein Spiel unentgeltlich und in Open Source ins Netz gestellt -- er will damit offenbar Urheberrechtsstreitigkeiten aus dem Weg gehen, denn es gibt einige Spiele, die "2048" zumindest sehr ähnlich sind.
Das Spiel hat eine Reihe von Mathematikern gepackt. Der Kombinatoriker Greg Kuperberg etwa schreibt auf Facebook, er halte es für eine gute Strategie, so genannte ebene Partitionen zu erzeugen: Die Felder sollten so gefüllt werden, dass die Zahlen von einer Ecke ausgehend immer kleiner werden. Tatsächlich scheint es eine gute Strategie zu sein, nicht alle Pfeiltasten zu verwenden, sondern nur zwei Richtungen, zum Beispiel "oben" und "rechts".
Grundsätzlich gilt: Man sollte in möglichst vielen Zügen mindestens zwei Felder vereinigen -- sonst füllt man sich mit der Zeit das Spielfeld, bis man bewegungsunfähig wird. Auf Facebook wird bereits diskutiert, ob man das Spiel nicht als Zwei-Personen-Spiel betrachten kann: Einer versucht große Zahlen zu erzeugen, der andere wählt möglichst gemein Felder, die er mit 2 oder 4 initiiert. Wie sehen Gewinnstrategien für diese beiden Spieler aus? So könnten die nächsten Nachrichten zu 2048 nicht auf twitter oder Facebook, sondern bei www.Arxiv.org zu finden sein.
Der Anfang aller Mathematik besteht darin, Fragen zu stellen. Und, wie schon gesagt: Das Spiel 2048 wirft eine Menge mathematische Fragen auf. Jürgen Richter-Gebert, von dem auch die nette iOrnament-Version von 2048 stammt, hat einige davon gesammelt und wir haben seinen Fragenkatalog noch etwas erweitert, insbesondere, was die zwei-Personen-Spiele angeht. Einige Fragen drängen sich sofort auf, wenn man den Score betrachtet:
- Was ist bei einem n x n-Brett der höchstmögliche Wert, der prinzipiell erreichbar ist?
- (Wie) kann man den Score nur vom Spielfeld ablesen, wenn man annimmt, dass nur 2-er Felder neu hinzukommen?
- (Wie) kann man aus Score und Bordposition berechnen wieviele 2-er und wieviele 4-er-Felder im Laufe des Spieles erzeugt wurden?
- Was ist der höchste erreichbare Score und was ist der niedrigste Score, mit dem man ein 2048 erreichen kann?
- Wie viele mögliche Endpositionen gibt es?
Man kann das Spiel "normal" spielen, man kann aber auch spielen, ohne jemals einen Blick auf das Spielfeld zu werfen - die Strategie dabei nennt man dann aus naheliegenden Gründen eine "Blindstrategie". Und dabei gibt es wiederum zwei Möglichkeiten: Man folgt einer festen Regel oder man "würfelt" dabei auch. Ersteres ist eine deterministische Blindstrategie, letzteres eine randomisierte. Und sofort ergeben sich neue Fragen - allen voran: Wie sieht die beste Blindstrategie aus? Doch was heißt "beste"? Das kann natürlich zweierlei bedeuten: Bester Score, höchster Wert im Feld. Und so könnte man weiterfragen:
- Welchen Score darf man mit einer randomisierten oder deterministischen Blindstrategie erwarten?
- Welchen Wert im Feld darf man erwarten, mit einer randomisierten oder deterministischen Blindstrategie?
- Wie sieht die "beste" deterministische Blindstrategie aus?
- Kann man deterministisch oder randomisiert "besser" spielen, wenn man eingeschränkte Informationen über das Geschehen auf dem Spielbrett erhält - zum Beispiel darüber, wo ein neuer Stein aufgetaucht ist (aber nicht: welchen Wert er hat)?
Wohl am Spannendsten ist es aber, das Spiel als 2-Personen-Spiel aufzufassen: Alice spielt klassisch und Bob setzt die neuen Steine - und zwar so gemein, dass Alice zum Beispiel keine hohen Scores oder Werte im Spielfeld bekommen kann und aufgeben muss. Kernfrage hier: Welche Strategie (randomisiert, deterministisch) muss Bob verwenden? Und wie könnte man sinnvoll festlegen, dass Alice oder Bob gewonnen haben? Bis zu welchem Wert muss Alice also zum Beispiel "durchhalten", um gewonnen zu haben und dabei eine faire Chance gehabt zu haben?
Interessant könnte dabei auch die Struktur des Graphen sein, der sich aus den möglichen Spielzügen für Alice bzw. Bob ergibt: Jeder Knoten entspricht einer Konstellation auf dem Spielfeld. Von ihm aus kann man - je nachdem, ob man Alice oder Bob ist, zu anderen Konstellationen gelangen. Wie sieht dieser Graph aus?
Falls Bob gewonnen hat, sobald Alice aufgeben muss, muss er das Spielfeld so besetzen, dass es "voll läuft" - in anderen Worten, bei mehr als der Hälfte der Spielzüge muss er Alice dazu zwingen, "Leerzüge" zu machen, die die Anzahl ihrer Spielsteine nicht reduzieren. Offensichtlich kann Bob Alice leicht zwingen, eine Reihe aus abwechselnden 2-er und 4-er-Steinen zu bekommen; damit ist bereits ein Viertel des Spielfeldes belegt. Doch dann wird es komplizierter - egal, was Bob tut, Alice wird innerhalb der nächsten beiden Zügen sicher einen Stein vernichten können. Wir glauben dennoch, dass Bob ziemlich gute Chancen hat, mit einer deterministischen Strategie in O(n) Schritten - also in einer Anzahl von Schritten, die durch eine lineare Funktion in n beschränkt ist - Alice zum Aufgeben zu zwingen. Aber das muss erst bewiesen werden...
Von Jürgen "iOrnament" Richter-Gebert erfahren wir: Es gibt inzwischen auch eine Version von "2048", die ganz ohne Zahlen auskommt!