-
- Theoretische Informatik als Lieferant
von Spiel-Ideen
Dominosteine auf der unendlichen Ebene
- Das Spiel mit den zweigeteilten Steinen,
die an gleichwertigen Enden aneinandergefügt werden, ist
ein Einwanderer aus Fernost: Dominos sind in China schon seit
tausend Jahren bekannt. Erst Anfang des 18. Jahrhunderts fanden
die gepunkteten Steine den Weg nach Europa, wo sie heute in der
Spielesammlung kaum einer Familie fehlen. Triominos - nach demselben
Prinzip anlegbare Dreiecke - machen ihnen neuerdings Konkurrenz,
und Tüftler kennen Pentominos oder andere Polyominos als
ausgefallene Art des Puzzlespiels. Dass Dominosteine mit wenigen
einfachen Veränderungen ganz neue, spannende Spielvarianten
ermöglichen könnten, ist dagegen ein Einfall, der bisher
nicht realisiert wurde. Die Idee stammt von Horst Müller,
Professor am Institut für Informatik der Universität
Erlangen-Nürnberg, und die Anregung dazu hat er aus seinem
Berufsfeld bezogen, der Theoretischen Informatik.
-
- Bunte, flache Klötze, per Hand sorgfältig
lackiert - und das auf dem Arbeitstisch eines Wissenschaftlers?
Die Antwort auf die Frage, ob diese Holzteilchen zum Zeitvertreib
und zur Ablenkung da sind oder vielleicht doch mit Informatik
zu tun haben, lautet: beides. Es sind Dominos, wie sie in mathematisch
formulierbaren Problemen auftauchen. Anders als bei den gewohnten
länglichen Spielsteinen, die zwei Felder mit je einer Punktzahl
tragen, wird ihnen für jede der vier Seiten eine bestimmte
Eigenschaft zugewiesen.
-
- Die einfachste Variante, die auf Professor
Müllers Tisch liegt, trägt deshalb auf der quadratischen
Oberfläche vier Farbfelder, wie durch ein Kreuz von Eck
zu Eck unterteilt. So wird klar, welche Farbe welcher Seite zugeordnet
ist. Wie beim üblichen Dominospiel gleiche Punktwerte zueinander
passen, müssen hier gleiche Farben - blau, grün oder
gelb - aufeinander treffen. Die Vierfarb-Dominos dürfen
jedoch nicht gedreht werden: ein Teil, dem Gelb für den
"Norden" zugewiesen wurde, muß immer mit der
gelben Kante nach oben liegen.
-
- Wenn Professor Müller in seiner Vorlesung
über "Perlen der Theoretischen Informatik" über
Varianten des Domino-Problems spricht, geht es allerdings nicht
um ein Spiel, bei dem die Gegner versuchen, ihre Steine möglichst
schnell anzusetzen, um als erster nichts mehr auf der Hand zu
haben. Es geht um Entscheidbarkeit, um Berechenbarkeit. In die
Anwendung übersetzt, bedeutet das: Kann ein Algorithmus
- eine Rechenvorschrift - gefunden werden, mittels derer ein
Computer eine bestimmte Aufgabe lösen kann, oder ist das
für diese Aufgabe prinzipiell unmöglich? Für Computer,
die nur eine begrenzte Anzahl von Rechenoperationen ausführen
können, gibt es Probleme, vor denen sie unweigerlich versagen
müssen.
-
- Das beschränkte und das uneingeschränkte
Domino-Problem sind Fachleuten als Beispiele für Entscheidbarkeit
oder Unentscheidbarkeit bekannt. Die Frage lautet: Können
derartige Domino-Teile, wenn sie in unbegrenzter Zahl, aber mit
festgelegten Eigenschaften zur Verfügung stehen, eine unendliche
Fläche völlig ausfüllen? Dass über die Möglichkeit,
eine Ebene auf diese Art zu "parkettieren", nichts
gesagt werden kann, wenn die Eigenschaften der Dominos nicht
genauer beschrieben werden, lässt sich beweisen. Andernfalls
kommt es darauf an, um welche Art von Domino-Steinen es sich
handelt.
-
- Für die vierfarbigen Plättchen
beispielsweise lässt sich allein durch Ausprobieren relativ
schnell eine Anordnung aus wenigen Teilen finden, die - wie eine
Wandkachel oder ein Tapetenmuster - in jeder Richtung immer wieder
aneinandergesetzt werden könnte und deshalb auch bis ins
Unendliche reicht. Sehr viel schwieriger wird es, wenn die Domino-Seiten
keine Farbeigenschaft haben, sondern etwa schräg aufgesetzte,
herausragende oder eingekerbte Dreiecke darüber bestimmen,
ob zwei Seiten aneinandergefügt werden können. Auch
wenn sich für konkrete Dominosteine das Problem als nicht
berechenbar erweist, bleibt das Ausprobieren noch offen - mit
viel Geduld und Glück könnte ja ein Parkett zustandekommen.
Nur dann ist tatsächlich die Entscheidung gefallen. "Wenn
es nicht funktioniert, kann man nichts darüber sagen, ob
es nicht grundsätzlich möglich wäre", erklärt
Professor Müller.
-
- Tiefer in die theoretische Informatik einzudringen,
ist jedoch nicht nötig, um deren Definition von Dominosteinen
für den Entwurf neuer Spiele zu nutzen. Mathematische Regeln
liegen vielen gebräuchlichen Spielen zugrunde, und Spielbegeisterte
wenden sie an, ohne dass ihnen dies überhaupt bewußt
wird. Professor Müller, der sich auch mit Labyrinthen auskennt,
hat mehrere, sowohl einfache wie komplexe Domino-Varianten vorrätig,
die zu Puzzles für Denksportler oder zu Legespielen mit
Wettbewerbsregeln tauglich wären. Informatik und Mathematik
als Quellen für Spiel-Ideen zu benutzen, ist keineswegs
ein abwegiger Gedanke. M.C. Escher, als Grafiker für seine
Einfälle berühmt, schrieb vor fast dreißig Jahren
über die Mathematiker seines Bekanntenkreises: "Wie
verspielt die gelehrten Damen und Herren doch sein können!"
-
- Kontakt:
Prof. Dr. Horst Müller, Professur für Theoretische
Informatik
Martensstraße 3, 91058 Erlangen
Tel.: 09131/85 -27911, Fax: 09131/85 -27239
E-Mail: mueller@informatik.uni-erlangen.de
Beispiele im Internet (mit Abbildungen):
http://www3.informatik.uni-erlangen.de/Lectures/Mueller/perlen/Domino-Problem/Skript.html
-
- Mediendienst FORSCHUNG Nr. 587 vom 02.02.2001
Sachgebiet Öffentlichkeitsarbeit (Pressestelle)
pressestelle@zuv.uni-erlangen.de