Verliert man bei Tetris nur, weil man nicht optimal spielt oder Fehler macht? Auch mit beliebig viel Bedenkzeit lässt sich eine ungünstige Steinfolge nicht retten. Entscheidend sind fünf schmale Bahnen und eine ungerade Zahl. Wir betrachten ein Spielfeld mit \(10\) Spalten und \(20\) Reihen ohne Zwischenablage (Hold): Jeder neue Stein wird unabhängig und gleichverteilt aus den sieben Tetrominos gezogen. Jede Form besteht aus vier zusammenhängenden Quadraten. Die gesamte Folge darf im Voraus bekannt sein.
Dass ein Spiel fast sicher endet, bedeutet nicht, dass jede denkbare Steinfolge endet. Eine reine Folge von O-Steinen kann man endlos spielen: Je fünf nebeneinandergelegte Quadrate löschen zwei Reihen und leeren das Brett. Bei 7-Bag enthält jeder zufällig gemischte Beutel alle sieben Formen genau einmal; dafür gilt unser Zufallsargument nicht. Heidi Burgiel zeigt in How to Lose at Tetris eine Folge, gegen die auch perfektes Spiel nicht hilft: \(S,Z,S,Z,\ldots\).
S und Z sind Spiegelbilder, nicht verschiedene Drehungen desselben Steins. Die begleitende Erklärung beschreibt die geometrische Idee, die wir hier als Widerspruchsbeweis ausführen. Die naheliegende Behauptung „irgendwann kommen nur Z-Steine, und mit denen verschwindet keine Reihe“ ist falsch. Bereits fünf gleiche, senkrecht gestellte S-Steine liefern auf einem anfangs leeren Brett die folgende Anordnung. Gleiche Buchstaben kennzeichnen jeweils denselben Stein; Punkte markieren freie Felder:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eDie mittlere Reihe ist vollständig und wird gelöscht. Spiegelt man die Anordnung, erhält man dasselbe Gegenbeispiel für Z-Steine. Das Problem ist also nicht das Löschen einzelner Reihen, sondern die Frage, ob man über unbegrenzt viele Steine hinweg sämtliche entstehenden Ungleichgewichte beherrschen kann. Nummerieren wir die Spalten von \(1\) bis \(10\). Mit \(b_i\) bezeichnen wir die Gesamtzahl aller neu in Spalte \(i\) gesetzten Zellen, einschließlich der später gelöschten.
\(h_i\) zählt waagerechte S- oder Z-Steine mit mittlerer Spalte \(i\), \(v_i\) senkrechte Steine in den Spalten \(i\) und \(i+1\). Die Zähler erfassen also den Spielverlauf, nicht nur den aktuell sichtbaren Stapel. Ein waagerechter Stein verteilt seine Zellen im Verhältnis \(1,2,1\) auf drei Spalten, ein senkrechter im Verhältnis \(2,2\) auf zwei Spalten. Beide Spiegelbilder haben dieselbe Spaltenbilanz. Summiert man diese Beiträge über alle Platzierungen, erhält man für jede Spalte:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Außerhalb des Bretts setzen wir alle Zähler auf \(0\); insbesondere gilt \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\). Diese Randkonvention verhindert, dass die Bilanz Steine mitzählt, die über den Spielfeldrand hinausragen würden. Solche Platzierungen sind in unserem Modell nicht erlaubt. Beginnt die betrachtete S/Z-Folge auf einem bereits gefüllten Brett, seien \(a_i\) die anfänglich belegten und \(c_i\) die aktuell belegten Zellen in Spalte \(i\). Nach \(R\) gelöschten Reihen ist:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Solange das Spiel läuft, liegen alle \(a_i,c_i\) zwischen \(0\) und \(20\). Daher gilt \(|b_i-b_j|\leq40\). Bei einem anfangs leeren Brett genügt sogar \(20\). Jede gelöschte Reihe nimmt aus jeder Spalte genau eine Zelle weg. Deshalb kürzt sich die Zahl der gelöschten Reihen beim Vergleich zweier Spalten heraus, auch wenn die Zähler der gesetzten Zellen weiter wachsen. Man zählt belegte Zellen statt Stapelhöhen; bei Löchern unterscheiden sich beide Größen. Schreiben wir diese Schranke allgemein als \(D\), ergibt sich am linken bzw. rechten Rand:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
Für die inneren Spaltenpaare addieren wir jeweils zwei beschränkte Spaltendifferenzen: \(b_4-b_3\) und \(b_2-b_1\) auf der linken, \(b_7-b_8\) und \(b_9-b_{10}\) auf der rechten Seite. Nach Einsetzen der Spaltenbilanz heben sich die dazwischenliegenden Zähler exakt auf. So bleiben auf jeder linken Seite nur nichtnegative Beiträge übrig, die gemeinsam durch \(2D\) begrenzt sind. Damit erhalten wir auch für die beiden inneren Paare eine Obergrenze für die jeweiligen Platzierungszahlen:
$$\begin{aligned}2v_4+h_4+h_5&=(b_4-b_3)+(b_2-b_1)\\&\leq2D,\\2v_6+h_6+h_7&=(b_7-b_8)+(b_9-b_{10})\\&\leq2D.\end{aligned}$$
Addieren wir die vier Ungleichungen, wird jeder horizontale Stein genau einmal gezählt. Auch die vier Arten bahnübergreifender senkrechter Platzierungen gehen mit positiven Koeffizienten ein. Die waagerechten Steine beanspruchen drei Spalten und passen deshalb nicht vollständig in eine der später betrachteten Zweispaltenbahnen. Bei den senkrechten Steinen unterscheiden wir die Bahnen nach der linken Spalte. Da alle Zähler nichtnegativ sind, kann keiner dieser Beiträge durch einen anderen aufgehoben werden:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Waagerechte Platzierungen und senkrechte Platzierungen mit gerader linker Spalte können also insgesamt höchstens \(120\)-mal auf einem leeren bzw. \(240\)-mal auf einem beliebig vorbelegten Brett vorkommen. Das ist eine obere Schranke, keine Behauptung, dass man sie tatsächlich erreichen kann. Unendlich oft lassen sich diese Ausweichzüge jedenfalls nicht einsetzen. Nehmen wir nun an, man könnte die alternierende Folge unendlich lange spielen.
Nach dem letzten der endlich vielen Ausweichzüge wären nur noch senkrechte Platzierungen in fünf festen Bahnen möglich: \((1,2),(3,4),(5,6),(7,8),(9,10)\). Gleiche Formen passen in einer Bahn treppenförmig ineinander: Die Unterseite trifft auf die passende Oberseite des vorherigen Steins. Ein Wechsel von S zu Z oder umgekehrt lässt eine Lücke von einer Zelle Breite und zwei Zellen Tiefe zurück. Der Ausschnitt zeigt einen Z-Stein über einem S-Stein; beide „o“ markieren die Lücke:
.Z
ZZ
Zo
So
SS
.SEin weiterer senkrechter Stein in derselben Bahn kann diese Lücke nicht füllen: Seine zweite Spalte würde mit den benachbarten belegten Zellen kollidieren. Auch Reihenlöschungen helfen nicht, solange die Lücke offen ist, denn ihre beiden Reihen sind gerade nicht vollständig. Eine Reparatur benötigt eine der bereits ausgeschlossenen bahnübergreifenden oder waagerechten Platzierungen. Nach dem letzten Ausweichzug sind solche Lücken somit dauerhaft. Auf einem endlichen Brett können nicht unendlich viele neue, disjunkte Lücken entstehen.
Folglich kann es auch nur noch endlich viele Formwechsel in den Bahnen geben. Eine anfangs leere Bahn ändert daran nichts: Ihr erster S- oder Z-Stein hinterlässt am Boden bereits eine einspaltige Lücke, die sich durch weiteres reines Bahnspiel nicht schließen lässt. In einem vermeintlich unendlichen Spiel muss außerdem jede Bahn unendlich viele Steine aufnehmen. Bliebe eine Bahn irgendwann unberührt, könnte man wegen der beschränkten Spaltenbilanzen auch in den übrigen Bahnen nur noch endlich viele Zellen unterbringen.
Wir erreichen deshalb einen Zeitpunkt, ab dem alle fünf Bahnen dauerhaft belegt und fest einer Form zugeordnet sind. Zählen wir ab diesem Zeitpunkt \(t\) weitere Steine und mit \(n_j(t)\) die Zahl in Bahn \(j\). Jeder dieser Steine trägt zwei Zellen zu jeder Spalte seiner Bahn bei. Weil Reihenlöschungen alle Spalten gleich behandeln, bleiben die Differenzen \(n_j(t)-n_k(t)\) beschränkt. Alle fünf Bahnen müssen langfristig also jeweils ein Fünftel der Steine aufnehmen:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Sind \(k\) der fünf Bahnen für S-Steine reserviert, müsste deren Anteil gegen \(k/5\) gehen. In der alternierenden Folge ist er jedoch \(1/2\): In jedem Präfix unterscheiden sich die Zahlen der S- und Z-Steine höchstens um \(1\). Die Aufteilung der Bahnen müsste beide Anteile gleichzeitig erfüllen. Ein Anteil von der Hälfte lässt sich aber nicht als Summe ganzer Fünftel darstellen. Hier treffen also die Häufigkeit der alternierenden Formen und die ungerade Zahl der gleich stark benutzten Bahnen aufeinander. Damit wäre zwingend:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Die Zahl der Bahnen ist ganzzahlig. Dieser Widerspruch beendet die Annahme eines unendlichen Spiels. Das Argument zeigt zugleich, warum die Brettbreite dazugehört: Bei vier Bahnen wäre eine Aufteilung in zwei S- und zwei Z-Bahnen nicht durch diesen Widerspruch ausgeschlossen. Für den Zufallsbeweis benötigen wir eine endliche Blocklänge \(N\), die unabhängig vom aktuellen Brett zum Verlust führt. „Jede Strategie verliert irgendwann“ allein genügt dafür nicht.
Die Einheitlichkeit folgt aus der endlichen Zahl möglicher Zustände. Nach jeder abgeschlossenen Platzierung gibt es höchstens \(2^{200}\) Belegungsmuster. Dazu kommt die Information, ob als Nächstes S oder Z erscheint, also höchstens \(2^{201}\) Zustände. Würde man \(N=2^{201}\) Steine überleben, hätten die \(N+1\) Zustände vor und nach diesen Zügen eine Wiederholung. Wegen des identischen Bretts und derselben nächsten Form wären die dazwischenliegenden legalen Züge beliebig oft wiederholbar: das gerade ausgeschlossene unendliche Spiel.
Die Grenze zählt auch unerreichbare Brettmuster und sagt keine praktische Spieldauer voraus. Burgiels feinere geometrische Zählung ergibt kleinere Schranken; hier genügt ein endliches \(N\). Sie gilt für alle zulässigen Anfangsbelegungen und beide Phasen der S/Z-Folge. Zerlegen wir die unendliche Zufallsfolge in disjunkte Blöcke der Länge \(N\). Jeder Block ist mit Wahrscheinlichkeit \(q=7^{-N}>0\) genau die festgelegte Folge \(S,Z,S,Z,\ldots\). Die Blöcke sind unabhängig. Dass keiner der ersten \(m\) Blöcke diese Folge enthält, hat deshalb Wahrscheinlichkeit:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Mit Wahrscheinlichkeit \(1\) erscheint also irgendwann ein tödlicher Block, sofern das Spiel nicht ohnehin vorher bereits endet. Das gilt auch mit beliebig viel Bedenkzeit und vollständiger Kenntnis der gesamten Steinfolge. Eine kurze praktische Spieldauer folgt daraus nicht. Ein unkonzentrierter, schlechter Start allein bedeutet keine Niederlage, es sind durchaus überraschende Comebacks möglich. Also – nicht entmutigen lassen und das zeitlose Spiel genießen.