News: Geistreiches Klötzchenspiel
Millionen von Spielsüchtigen haben nur ein Ziel vor Augen: Noch eine Reihe mit Klötzchen pflastern, noch ein höheres Niveau erreichen. Doch das Computerspiel Tetris - das bestätigen jetzt Mathematiker - ist nicht nur für Menschen eine echte Herausforderung.
Es ist der Klassiker der Computerspiele und fesselt Generationen von Spielern immer wieder aufs Neue: Tetris. Ziel des Spiels, das von der Grundidee ein wenig an Bauklötzchenspielen erinnert, ist es, möglichst viele Zeilen mit geometrischen Figuren auszufüllen. Doch so einfach, wie das klingt, ist es nicht.
Der Spieler hat zunächst ein rechteckiges Spielbrett auf dem Schirm, das aus quadratischen Feldern besteht. Zu Beginn liegen schon einige Figuren auf dem Brett. Nach und nach fallen nun weitere quadratische, rechteckige, L-förmige, T-förmige und andere Figuren von oben langsam herunter. Bevor diese unten ankommen, muss der Spieler sie so drehen, dass sie möglichst vollständig eine Zeile füllen.
Ist eine Zeile komplett, wird sie gelöscht und alle darüberliegenden rutschen um eine Zeile hinunter. Der Spieler verliert, sobald eine Figur nicht mehr passt, weil ihr Platz von einer bereits im Spiel vorhandenen Figur blockiert wird. Wie jeder passionierte Tetris-Spieler bestätigen wird, erweist sich diese scheinbar einfache Aufgabe als echte Kopfnuss.
Das bestätigen jetzt auch Erik Demaine und seine Kollegen vom Massachusetts Institute of Technology in Cambridge, die das Thema Spieltheorie ganz wörtlich nahmen. Sie untersuchten, wie lange ein Computer für das Spiel braucht, und wie viel Speicherplatz er dabei benötigt.
Die Forscher stellten fest, dass es sich bei Tetris um ein so genanntes NP-vollständiges Problem handelt. NP-vollständig heißt: Es gibt keine strategische Lösung. Vielmehr bleibt einem Computer, um den optimalen Spielzug zu finden, nichts anderes übrig, als alle denkbaren Spielzüge durchzuprobieren. Und dieser Prozess ist ab einem gewissen Schwierigkeitsgrad so zeitraubend, dass er nicht mehr durchführbar ist. Es ist damit mathematisch mit dem traveling salesman problem verwandt, bei dem der kürzeste Weg durch mehrere Städte gefunden werden soll.
Tetris ist also derart komplex, dass sogar Computer vor dem Problem kapitulieren. Demaine bestätigt damit, was viele intuitiv schon seit langem wissen, und liefert gleichzeitig leidenschaftlichen Tetris-Spieler die perfekte mathematische Ausrede: "Ihr löst wirklich anspruchsvolle Probleme."
Außerdem: Vielleicht hat gerade deshalb der Mensch eine - wenn auch winzige - Chance, bei diesem Spiel den Computer zu schlagen. Voraussetzung dafür ist, eine Zeile besteht aus so vielen Gitterquadraten, dass der Rechner den optimalen Spielzug unmöglich rechtzeitig herausfinden kann.
Beide, sowohl Mensch als auch Maschine müßten dann auf Mustererkennung zurückgreifen, um das Problem zu lösen. Der Computer wäre darin zwar immer noch um einiges, aber nicht hoffnungslos schneller als der Mensch. Und der kann immerhin noch Glück haben – eine Maschine nicht.
Der Spieler hat zunächst ein rechteckiges Spielbrett auf dem Schirm, das aus quadratischen Feldern besteht. Zu Beginn liegen schon einige Figuren auf dem Brett. Nach und nach fallen nun weitere quadratische, rechteckige, L-förmige, T-förmige und andere Figuren von oben langsam herunter. Bevor diese unten ankommen, muss der Spieler sie so drehen, dass sie möglichst vollständig eine Zeile füllen.
Ist eine Zeile komplett, wird sie gelöscht und alle darüberliegenden rutschen um eine Zeile hinunter. Der Spieler verliert, sobald eine Figur nicht mehr passt, weil ihr Platz von einer bereits im Spiel vorhandenen Figur blockiert wird. Wie jeder passionierte Tetris-Spieler bestätigen wird, erweist sich diese scheinbar einfache Aufgabe als echte Kopfnuss.
Das bestätigen jetzt auch Erik Demaine und seine Kollegen vom Massachusetts Institute of Technology in Cambridge, die das Thema Spieltheorie ganz wörtlich nahmen. Sie untersuchten, wie lange ein Computer für das Spiel braucht, und wie viel Speicherplatz er dabei benötigt.
Die Forscher stellten fest, dass es sich bei Tetris um ein so genanntes NP-vollständiges Problem handelt. NP-vollständig heißt: Es gibt keine strategische Lösung. Vielmehr bleibt einem Computer, um den optimalen Spielzug zu finden, nichts anderes übrig, als alle denkbaren Spielzüge durchzuprobieren. Und dieser Prozess ist ab einem gewissen Schwierigkeitsgrad so zeitraubend, dass er nicht mehr durchführbar ist. Es ist damit mathematisch mit dem traveling salesman problem verwandt, bei dem der kürzeste Weg durch mehrere Städte gefunden werden soll.
Tetris ist also derart komplex, dass sogar Computer vor dem Problem kapitulieren. Demaine bestätigt damit, was viele intuitiv schon seit langem wissen, und liefert gleichzeitig leidenschaftlichen Tetris-Spieler die perfekte mathematische Ausrede: "Ihr löst wirklich anspruchsvolle Probleme."
Außerdem: Vielleicht hat gerade deshalb der Mensch eine - wenn auch winzige - Chance, bei diesem Spiel den Computer zu schlagen. Voraussetzung dafür ist, eine Zeile besteht aus so vielen Gitterquadraten, dass der Rechner den optimalen Spielzug unmöglich rechtzeitig herausfinden kann.
Beide, sowohl Mensch als auch Maschine müßten dann auf Mustererkennung zurückgreifen, um das Problem zu lösen. Der Computer wäre darin zwar immer noch um einiges, aber nicht hoffnungslos schneller als der Mensch. Und der kann immerhin noch Glück haben – eine Maschine nicht.
Schreiben Sie uns!