Der „Turm von Hanoi“ ist eine Denksportaufgabe. Sie war immer wieder Gegenstand zahlreicher Untersuchungen einerseits der Denk- und Lernpsychologie, andererseits der KI (Künstliche Intelligenz). Sie weist formale Eigenschaften auf, die sie zu einem guten Demonstrationsbeispiel für Techniken der KI macht. Gleichzeitig ist sie von mittlerer Schwierigkeit, so dass sich daran gut in psychologischen Experimenten Lernprozesse und ähnliches beobachten lässt, ohne dass diese Experimente all zu lange dauern müssen.

Die Aufgabe

In der Urversion werden als Material etwa fünf bis sechs gelochte Scheiben unterschiedlicher Grösse verwendet. Diese Scheiben stecken zu Beginn der Grösse nach geordnet auf einem Pflock, so dass sich die grösste Scheibe zuunterst befindet. Zusätzlich sind noch zwei weitere, zu Beginn leere Pflöcke vorhanden. Die Aufgabe besteht nun darin, den ganzen Scheibenstapel vom Startpflock auf einen der anderen Pflöcke, den Zielpflock, umzuschichten. Dabei müssen folgende Regeln eingehalten werden: 1) Aufs Mal darf immer nur eine Scheibe von einem Pflock auf einen der anderen Pflöcke umgelegt werden, und 2) es darf nie eine grössere Scheibe auf eine kleiner zu liegen kommen. Das Problem besteht also darin, den dritten Pflock geschickt als Ausweichstelle zu benutzen, so dass der ganze Umbau möglich wird.

Formale Aspekte der Aufgabe

Werden n Scheiben verwendet, dann beträgt die Anzahl notwendiger Bewegungen 2ⁿ-1. Sie verdoppelt sich also in etwa mit jeder zusätzlichen Scheibe. Bei 3 Scheiben genügen 7 Bewegungen. Bei 6 Scheiben sind bereits 63 Bewegungen notwendig. Für psychologische Experimente bedeutet das, dass man den zur Lösung notwendigen Aufwand, die Gefahr, dass jemand einen Fehler macht und die Wahrscheinlichkeit, dass die Aufgabe durch Zufall löst, sehr einfach in einem sehr grossen Bereich variieren kann.

Die Aufgabe lässt sich leicht in zwei Aufgaben zerlegen. Es seinen fünf Scheiben auf dem ersten Posten und diese sollen alle auf den dritten Pfosten verschoben werden. Dann muss man dazu zuerst die vier oberen Scheiben auf den zweiten Pfosten transportieren, dadurch wird die grösste Scheibe frei und kann auf den dritten Pfosten verschoben werden, und abschliessend müssen dann noch die vier Scheiben von zweiten Posten ebenfalls auf den dritten Pfosten. Beherrscht man also die Aufgabe mit vier Scheiben, dann ist die Aufgabe mit fünf Scheiben kein Problem mehr. Das gilt natürlich für jede Anzahl Scheiben, d.h. jede Aufgabe lässt sich sukzessive auf immer einfachere Aufgaben reduzieren, bis nur noch die triviale Aufgabe bleibt, eine einzige Scheibe von einem Pfosten auf einen anderen zu bewegen. Der Turm von Hanoi taucht deshalb in Lehrbücher zum Programmieren immer wieder als Aufgabe auf, anhand der die Prinzipien rekursiver Programmstrukturen geübt werden können (z.B. Winston & Horn, 1981).

Wegen der rekursiven Struktur der Aufgabe lässt sich der Zustandsraum des Problems sehr schön regelmässig darstellen. Ein Bild des Zustandsraums erhält man, indem man zuerst einmal für jede mögliche Art, wie die Scheiben auf die drei Pfosten verteilt sein können, einen Punkt zeichnet. Dann verbindet man immer zwei Punkte mit einer Linie, wenn diese beiden Punkte zwei Zuständen entsprechen, die durch das Bewegen einer Scheibe ineinander übergeführt werden können. Im einfachste Fall – mit einer Scheibe – ist der Zustandsraum ein Dreieck.

Fügt man eine zweite Scheibe hinzu, zeigen sich die Bewegungen der kleineren Scheibe als Dreiecke im Dreieck der Bewegungen der grösseren Scheibe.

Hat man den Zustandsraum aufgezeichnet, wird die Bewältigung der Aufgabe deutlich vereinfacht.

Analoge Aufgaben

Rekursive Höhlenlabyrinthe: Der Zustandsraum des Turm von Hanoi ist identisch mit dem Plan einer rekursiven Höhle mit drei Ausgängen pro Höhle. Die Anzahl Scheiben entspricht der Ersetzungstiefe. Würde man also in jeder Höhle ein Modell des Turms von Hanoi im entsprechenden Zustand aufstellen und würde man bei den Ausgängen anschreiben, welcher Scheibenbewegung sie entsprechen, könnte jemand anhand seines Wissens über der Turm von Hanoi den Weg zu Ausgang planen.

Diese Analogie besteht aber nur zwischen dem originalen Turm von Hanoi mit drei Pfosten und der rekursiven Höhle mit drei Ausgängen. Der Zustandsraum des Turms von Hanoi mit vier Pfosten hat dann aber bereits viel mehr Verbindungen zwischen den einzelnen Zuständen, als im rekursiven Höhlenlabyrinth mit vier Ausgängen pro Höhle vorkommen.

Bälle jonglieren: Kotovsky, Hayes & Simon (1976) verwendeten in ihren Untersuchungen eine ganze Reihe von Aufgaben mit Zustandsräumen, die identisch mit dem des Turm von Hanoi waren. Eine davon beschreiben sie etwa wie folgt: „Drei fünfhändige ausserirdische Monster hielten in ihren Händen drei Kristallkugeln. Wegen der quantentheoretischen Eigenarten ihrer Welt gibt es solche Monster und solche Kristallkugeln nur genau in drei verschiedenen Grössen: klein, mittel und gross. Das kleine Monster hielt die grosse Kugel, das mittlere Monster die kleine Kugel und das grosse Monster die mittlere Kugel. Da diese Situation ihrem ausgeprägten Sinn für Symmetrie widersprach, beschlossen sie die Kugeln von Monster zu Monster weiterzugeben bis jedes Monster die Kugel entsprechend seiner Grösse in Händen hielt. Allerdings konnte das nicht auf beliebige Art geschehen, sondern es mussten die unter Monstern üblichen Umgangsformen eingehalten werden: 1) Es darf immer nur eine Kugel aufs mal bewegt werden. 2) Wenn ein Monster gleichzeitig mehrere Kugeln in den Händen hält, darf nur die grösste dieser Kugeln weitergegeben werden. 3) Ein Kugel darf nicht einem Monster übergeben werden, dass bereits eine noch grössere Kugel in den Händen hält.“

Literatur

Eine etwas zufällige Liste von Arbeiten, die sich alle auf die eine oder andere Art mit dem Turm von Hanoi beschäftigen.

Programmieren

• Kaehler, T. & Patterson, D. (1986) A Taste of Smalltalk. New York: W.W. Norton & Company.
  Illustriert am „Turm von Hanoi“ als durchgehendes Beispiel allerlei Konzepte des Programmierens; natürlich auch Rekursion.
• Winston, D. H. & Horn, B. K. P. (1981) LISP. Reading Mass.
  Klassisches Lehrbuch der LISP-Programmierung; „Turm von Hanoi“ als ein Beispiel.

Künstliche Intelligenz

• Altay Güvernir, H. & Ernst, G. W. (1990). Learning problem solving strategies using refinement and macro generation. Artificial Intelligence 40: 209-243.
  Programme die mit der Zeit lernen, gewisse Aufgaben zu lösen, auch den „Turm von Hanoi“.
• Langley, P. (1985). Learning to search: From Weak methods to domain-specific heuristics. Cognitive Science 9: 217-260.
  Das Programm lernt selbst aufgrund von Versuch und Irrtum, wie man den „Turm von Hanoi“ am besten löst.

Psychologie

• Amarel, S. (1983). Problems of representation in heuristic problem solving: related issues in the development of expert systems. in: Groner, R. Groner, M. & Bischof, W. F. (eds.); Methods of Heuristics , Hillsdale, NJ: Lawrence Erlbaum, 1983, 245-350.
  Sehr detaillierter Versuch verschiedene Arten zu vergleichen, wie man sich die Aufgabe beim „Turm von Hanoi“ im Kopf zurechtlegen kann.
• Anzai, Y. & Simon, H. A. (1979). The theory of learning by doing. Psychological Review 86: 124-140.
  Detaillierte Beobachtung der Lernfortschritte einer Versuchsperson.
• Kotovsky, K., Hayes, J. R., & Simon, H. A. (1985) Why are some problems hard? Evidence from Tower of Hanoi. Cognitive Psychology, 17, 248-294.
  Detaillierte Analyse dazu, was es ausmacht, dass gewisse Aufgaben sehr schwierig sind.
• Simon, H. A. & Hayes, J. R. (1976). The understanding process: Problem isomorphs. Cognitive Psychology 8: 165-190.
  Lassen Versuchspersonen Probleme lösen, die analog zum „Turm von Hanoi“ strukturiert sind. Finden kaum Transfer.
• VanLehn, K. (1991). Rule acquisition events in the discovery of problem-solving strategies. Cognitive Science 15: 1-47.
  Reanalyse der Vp von Anzai & Simon (1979); sehr gut und detailliert.

Links

Wikipdia: Tower of Hanoi
http://en.wikipedia.org/wiki/Tower_of_Hanoi

Mathematische Basteleinen: Der Turm von Hanoi: Eine einfache Einführung in die optimale Strategie und etwas mathematischen Hintergrund
www.mathematische-basteleien.de/hanoi.htm

Tower of Hanoi (TH) Puzzle: Verschiedene kleine Programme, entweder zu selber Spielen oder zum Zuschauen.
hanoitower.mkolar.org

Unterdessen ist Tower of Hanoi auch als App für Smartphones verfügbar.