Ab in die Freiheit!

Unter dem Titel „100 Gefangene“ ist eine Rätselaufgabe bekannt, die eine verblüffende Lösung hat.

Es geht darum, dass eine Gruppe von 100 Gefangenen freikommen kann, wenn es jedem einzelnen von ihnen gelingt, ein Rätsel zu lösen.

Die Gefangenen tragen auf ihrer Mütze eine Zahl von 1 bis 100.

Getrennt voneinander werden sie in einen Raum geführt, in dem sich ein Schrank mit 100 Schubladen befindet. In jeder Schublade befindet sich ein Zettel, auf dem eine Zahl zwischen 1 und 100 steht. Jede Zahl kommt genau einmal vor. Es gibt keine Information darüber, wie die Zettel verteilt sind.

Jeder Gefangene darf maximal 50 Schubladen öffnen. Findet er dabei den Zettel mit der Nummer, die auf seiner eigenen Mütze steht, hat er das Rätsel gelöst.

Die Gefangenen dürfen sich darüber absprechen, wie sie beim Öffnen der Schubladen vorgehen wollen, aber in dem Raum mit dem Schrank befindet sich immer nur ein einzelner Gefangener. Hat er das Rätsel gelöst, wird er in einen anderen Raum geführt, er kann also nicht mit den Gefangenen sprechen, die noch nicht an der Reihe waren.

Auch alle anderen Methoden des Informationsaustauschs (z.B. bestimmte Schubladen einen Spalt offen stehen lassen) sind nicht erlaubt.

Findet irgendein Gefangener den Zettel mit seiner eigenen Nummer nicht, so müssen alle zurück in ihre Zellen.

Welche Absprache können die Gefangenen treffen, damit ihre Chance auf die Freiheit möglichst groß ist?

In dem Wikipedia-Artikel (und an vielen anderen Stellen im Web) wird erklärt, dass bei zufälliger Anordnung der Zettel die Gefangenen ihre Chance auf über 30% heben können, wenn sie nicht zufällig Schubladen öffnen, sondern folgendes Verfahren anwenden:

Nummeriere die Schubladen gedanklich durch. 
Links oben ist die erste, rechts unten die hundertste Schublade.
Öffne als erstes die Schublade, deren Nummer deiner eigenen Mütze
entspricht. Lies die Zahl auf dem Zettel und öffne von nun an immer
als nächstes die Schublade, die der Zahl auf dem Zettel entspricht.

Wie an anderer Stelle erklärt wird, sind die Gefangenen immer dann erfolgreich, wenn es bei den Ketten, die durch die Verweise der Zettel festgelegt sind, keine Sequenz gibt, die länger als 50 ist.

Die Wahrscheinlichkeit dafür kann mathematisch berechnet werden, sie kann aber auch mit einem einfachen Programm ermittelt werden, indem man die Situation oft genug simuliert. Ein typisches Programm (Python) dieser Art sieht etwa so aus:

import random

def prüfe ( schubladen, öffnungen ) :
    random.shuffle ( schubladen )
    for gefangener in range ( len (schubladen) ) :
        schublade = gefangener
        for _ in range ( öffnungen ):
            schublade = schubladen[schublade]
            if schublade == gefangener: break
        if schublade != gefangener: return 0 
    return 1

gefangene   = 100
versuche    = 50
experimente = 10000

schrank     = list ( range (gefangene) )

erfolge     = sum( [ prüfe(schrank,versuche) 
              for _ in range (experimente) ] )

print ( f'Gewinnhäufigkeit = { erfolge / experimente}')

Das Programm liefert als Ergebnis einen Wert von ca 0,31. FERTIG!

Na ja, man könnte auch die Frage stellen, ob es noch andere Strategien gibt. Oder man überlegt, ob das Gefängnis einen einfachen Weg hat, diese Strategie der Häftlinge zu durchkreuzen, wenn es Wind davon bekommt. Und dann kann man wiederum fragen, ob die Gefangenen eine Chance haben, eine hinterlistige Gefängnisleitung zu durchschauen …
Man könnte auch graphische Darstellungen der Zettelverkettung zeigen; man könnte die Verteilungsfunktion der Erfolgswahrscheinlichkeit bei unterschiedlichen Zahlen für Gefangene und zulässige Schubladen-Öffnungen erstellen…

Wenn man zu allen solchen Fragen ein Programm schreiben will, droht ganz schnell die Gefahr, dass der Code sehr unübersichtlich wird. Man darf nicht damit beginnen, auf den Algorithmus zu schauen, also auf das WIE der Lösung, sondern man muss erst einmal die Welt der Beteiligten (das WER) abbilden und diese dann – wie in einem Theaterstück – miteinander in Szene setzen.

Das klingt komisch, unnötig, befremdlich?

Mag sein, aber es ist erwiesenermaßen der einzige Weg, ein größeres Programm zu schreiben, das „überlebensfähig“ ist, auch wenn jemand anders als der Autor eine Erweiterung vornehmen will. Bei 100 Zeilen merkt man den Effekt noch nicht, bei 1000 Zeilen ist es schon recht nützlich, bei 10.000 Zeilen geht es kaum noch anders. Und wenn man es nicht macht, wird der nächste Autor erklären, dass man das komplette Progranmm wegwerfen und neu schreiben muss, weil er sich nicht zurechtfindet. Über 10.000.000 Lines of Code (solche Systeme gibt es durchaus in der Praxis) wollen wir erst mal gar nicht reden.

Informatiker benutzen das Wort Objektorientierung für diese Art der Softwarestrukturierung. „Theatermodus“ kling aber besser und ist näher dran an dem, was man erreichen will. Es geht nämlich darum, handelnden Subjekten in der Software Gestalt zu geben, die eigene Fähigkeiten, spezifisches Wissen und ein Gedächtnis haben, die Ziele verfolgen und dabei andere für ihre Zwecke einspannen, indem sie ihnen Aufträge erteilen und deren Ergebnisse weiter verwenden.

Unter Objekt stellt man sich Dinge vor, die ein handelnder Mensch (der den vollen Überblick hat) für seine Zwecke benutzt. Ohne ihn liegen die Objekt einfach nur herum. Diese Denkweise führt in die Irre, weil sie „kopflastige“ Software schafft, in der eine allwissende Hauptfunktion (manchmal spöttisch Gott-Funktion genannt) alle anderen Elemente manipuliert. So funktioniert kein Regierungs-kabinett, kein Unternehmen und erst recht kein ordentliches Computerprogramm.

„Versammle souveräne schlaue Subjekte um dich, mach sie miteinander bekannt und dann sorge dafür, dass sie miteinander kooperieren und dabei deinen Zielvorgaben folgen!“ möchte man so manchem Staatschef oder Konzernboss zurufen. In der Softwareentwicklung ist es nicht anders! Nur, dass man sich dort seine Mitarbeiter („Module“, „Komponenten“ oder „Klassen“ genannt) selber backen kann – anders als in der Realität. Außerdem sind sie unendlich gehorsam und fleißig, solange man sie mit elektrischer Energie ernährt. Was will man mehr?

Auf unser Beispiel angewandt, erkennen wir sofort den einzelnen Gefangenen als Subjekt, aber auch die Gruppe der Gefangenen und die Gefängnisleitung. Auch der Schrank mit den Schubladen ist ein guter Kandidat. Denn profane Dinge haben in der Welt der Informatik eine Seele (sind also Klassen), insbesondere wenn sie eine innere Struktur besitzen und wenn sie irgendeine Funktion haben (Der Schrank besteht aus Schubladen, die beweglich sind). Sogar die einzelne Schublade kommt als Kandidat für ein Subjekt unserer Inszenierung in Frage, denn sie kann sich öffnen und schließen und wechselt dabei ihren Zustand.
Eine etwas andere Art von Subjekten sind „Prozesse“, also Schrittfolgen (Rezepte), die in einer bestimmten Reihenfolge oder in bestimmten Intervallen Aktionen anstoßen. In unserem Fall ist das die Simulation, die aus einer Reihe von Experimenten besteht. Jedes Experiment entspricht einem Durchgang, in dem die Gefangenen mit einem bestimmten Schrank um ihre Freiheit ringen. Apropos Freiheit. Wir brauchen noch ein initiales Subjekt („Hauptprogramm“), das alles in Szene setzt; was eignet sich besser dazu als der Wunsch nach Freiheit?

Damit diese Figuren unseres Theaterstücks Leben bekommen, schreiben wir auf, was sie können (Liste der Fähigkeiten), was sie wissen (Gedächtnis) und eventuell auch, welche unterschiedlichen Zustände sie im Laufe ihres Daseins annehmen können.

  • Die Gefängnisleitung bietet der Gruppe der Gefangenen die Chance auf die Freiheit an. Sie verteilt die Zettel auf die Schubladen des Schranks und führt mit der Gruppe der Gefangenen das Freiheitsexperiment durch. Sie notiert am Ende den Erfolg oder Misserfolg des Experiments.
  • Das Experiment führt die Gruppe der Gefangenen der Reihe nach in das Zimmer mit dem Schrank. Es überwacht, ob ein Gefangener das Rätsel lösen konnte. Es beendet den Vorgang wenn ein Gefangener erfolglos bleibt oder nachdem alle Gefangenen erfolgreich waren. Es teilt am Ende sein Resultat („Freiheit erlangt = JA oder NEIN) mit.
  • Die Gruppe der Gefangenen legt eine Strategie fest. Sie stellt dabei Vermutungen darüber an, wie die Gefängnisleitung die Zettel verteilt haben könnte.
  • Der einzelne Gefangene merkt sich die vereinbarte Strategie und führt sie aus, indem er den Schrank nach dem Zettel fragt, der sich in einer bestimmten Schublade befindet. Er liest den Zettel und kann diese Information nutzen. Er erkennt dabei auch, ob er das Rätsel gelöst hat.
  • Der Schrank weiß, wie seine Schubladen angeordnet sind, etwa so, wie ein Kellner in einem Restaurant einen Plan der Tischnummern hat. Er kann seine Schubladen auffordern, sich zu öffnen und zu schließen. Er versteht (im Gegensatz zur einzelnen Schublade), dass der Gegenstand, den sie enthält, ein Zettel mit einer Zahl ist; er teilt diese Zahl mit, wenn er aufgefordert wird, eine bestimmte Schublade zu öffnen. Er sorgt dafür, dass die entsprechende Schublade sofort nach dem Öffnen wieder geschlossen wird.
  • Die Schublade kann sich öffnen und schließen. Sie kann einen Gegenstand aufnehmen und wieder hergeben. Sie weiß nicht, dass es außer ihr noch andere Schubladen gibt. Sie hat möglicherweise eine Vorstellung davon, wie groß und wie schwer ein Gegenstand sein darf, den sie beherbergt, sie hat aber keine Ahnung von dessen sonstigen Eigenschaften.
  • Die Freiheit ist der Veranstalter und Moderator des Theaterstücks. Sie erschafft die Gefängnisleitung und die Gefangenen. Die Gefängnisleitung baut sich ihren Schrank, wobei dieser wiederum seine Schubladen erzeugt. Die Gefängnisleitung führt die gewünschte Anzahl von Experimenten (mit jeweils neuer Zettelverteilung) durch. Die Freiheit legt zu Beginn jeder Serie von Experimenten fest, welche Strategie die Gefangenen benutzen sollen. Damit sie dies tun kann, zeigt ihr die Gruppe der Gefangenen bei Bedarf eine Liste der möglichen Strategien. Ebenso legt die Freiheit fest, nach welcher Strategie die Gefängnisleitung den Schrank bei der betreffenden Serie von Experimenten konfigurieren soll. Damit sie dies tun kann, liefert die Gefängnisleitung bei Bedarf eine Liste der Strategien, die sie sich ausgedacht hat. Die Freiheit bietet dem menschlichen Benutzer des Systems (irgendwo kommt der Mensch schließlich doch noch ins Spiel) die Möglichkeit, alle Strategien paarweise zu vergleichen oder auch nur ein ganz bestimmtes Paar gegeneinander antreten zu lassen. Der Mensch kann wählen, wie viele Experimente bei jedem Paarvergleich durchgeführt werden sollen.

Ein paar Formulierungen in der obigen Darstellung klingen ziemlich schräg, oder? Zum Beispiel das Verhältnis zwischen dem Schrank und seinen Schubladen (A). Wir haben hier schließlich kein Hochregallager, in dem Reifen, Motorblöcke oder Lenkräder eingelagert werden. Und wenn es schon so kompliziert sein muss, warum wird der Schrank dann nicht aus seinen Schubladen zusammengesetzt? Warum soll er sie erzeugen? Da sträubt sich die Intuition.
(B) Warum muss das Experiment ein eigenes Subjekt sein? Die Gefängnisleitung hat sich den ganzen Prozess doch ausgedacht, sie könnte doch auch den Ablauf durchführen!
(C) Und überhaupt: Warum muss denn so penibel erklärt werden, wie die Freiheit die Subjekte ins Leben ruft, bzw. wie diese dann ihre Kinder und Kindeskinder erzeugen? Warum sind die Figuren nicht einfach von Anfang an da? Warum kann es denn nicht so herrlich einfach sein wie bei dem Python-Progrämmchen mit seinen 20 Zeilen?

Gut, gehen wir die Fragen der Reihe nach durch:

(A) Wenn Schubladen wirlich nichts anderes können sollen als Zahlen beherbergen, dann müssen sie keine „First-Class-Citizens“ in unserem Theaterstück sein. Wir hängen gedanklich vor den Schrank einen Vorhang mit einem einzigen kleinen Loch – etwa so wie am Ende einer Theatervorstellung, wenn die Schauspieler einzeln heraustreten dürfen – oder wie bei der Werkzeugausgabe beim Materiallager. Ob der Schrank lauter identische Schubladen hat und wie diese funktionieren, das kann sowohl dem einzelnen Gefangenen als auch der Gefängnisleitung egal sein. Wir verbergen hinter dem Interface des Schranks die Liste der Schubladen – oder der Tiefgaragenplätze, falls wir später einmal Autos ablegen wollen anstelle von Zetteln. Und weil Software teuer ist, implementieren wir zunächst die Schubladen als einfachen Array von Objekten, die nur aus einer Ganzzahl bestehen. Das Schöne ist, dass die Implementierung später wachsen kann, ohne dass das Interface sich ändert. Wir benötigen nur drei Fähigkeiten (1) „Ding auf Platz x legen“, (2) „Ding auf Platz x zeigen“ und (3) „Ding von Platz x entfernen“. (1) und (3) sind reserviert für Gefängnisleitung, (2) ist verfügbar für einen Gefangenen, der vor dem Schrank steht. Wir haben also genau genommen zwei Interfaces! Dass der Schrank seinen Lagerraum selbst verwaltet, ist also klar. Und genau deshalb muss er ihn auch selber erzeugen! Wenn er dazu einen Schreiner braucht oder eine Architekten, soll er sich selbst darum kümmern. Wir werden ihm nicht irgendwelche Schubladen andienen, von denen er uns dann sagt, dass er diese komischen Dinger nicht gebrauchen kann…

(B) Einen Ablauf zu einem eigenen Subjekt zu erheben, kann sinnvoll sein, muss es aber nicht. Wenn der Ablauf zwischendurch unterbrochen werden kann, wenn er mehrfach parallel ausgeführt werden kann, wenn es diverse Varianten davon gibt – dann sind das gute Anhaltspunkte dafür, ihm eine eigen Klasse zu widmen. In unserem Fall ist es jedoch recht einfach: Die Gefangenen kommen immer der Reihe nach dran, ohne Unterbrechung, ohne Parallelität. Also geben wir uns damit zufrieden, diesen Ablauf als Fähigkeit (=Funktion, Methode) demjenigen Subjekt zuzuordnen, das „die natürliche Verfügungsgewalt“ darüber hat, und das ist in unserem Fall die Gefängnisleitung.

(C) Es gibt Programme, die sich ihren Gesamtzustand so merken, dass er erhalten bleibt, wenn das Programm zuende ist. Der Rechner bietet dafür dauerhaften Speicher an, etwa in Form von klassichen Dateien oder Datenbanken. Wäre unser Programm so beschaffen, dann müssten wir über die Erstbefüllung von Datenbanktabellen nachdenken. Ist es aber nicht. Also fangen wir beim Urknall an. Und deswegen müssen wir die ganze Entstehungsgeschichte unserer Figuren festlegen. Wichtig ist dabei oft, wer zuerst da ist; denn neu hinzukommende Subjekte können bei ihrer Entstehung gleich direkt mit der vorhandenen Welt bekannt gemacht werden. Wenn jedoch einer der Anwesenden mit einem neuen Mitglied der Schauspieltruppe Freundschaft schließen soll, muss man ihm den Neuling extra zeigen, nachdem dieser geboren wurde. Eine bewährte Vorgehensweise ist es daher, die einfacheren Charaktere zuerst zu erzeugen und die höheren Koordinatoren erst später.
In unserem Fall muss sich die Gefängnisleitung an ihre Gefangenen wenden können. Als Informatiker finden wir es daher „natürlich“, zuerst die Gefangenen zu erzeugen und danach das Gefängnis – welch seltsame Welt …. Oder wir bitten das Gefängnis, sich seine Gefangenen selbst zu erzeugen. Wenn wir allerdings eine Prise Idealismus dem Prinzip der Gewaltenteilung spendieren wollen, dann sollte doch der Gefängnisdirektor Diener der Justiz sein, die entscheidet, wer hinein muss. Also besser doch nicht so herum. Der Schrank gehört allerdings ganz klar dem Gefängnis, er kann von diesem also selbst erschaffen werden. Die Freiheit setzt das Ganze in Gang, kommt somit als erstes dran. Damit sie jedoch ihren Dienst tun kann, muss sie im Rahmen ihrer Entstehung zunächst die Gefangenen und dann das Gefängnis erzeugen.
Ja, das klingt umständlich und langatmig. Aber Evolution ist kompliziert. Und der Rechner benötigt nur ein paar Mikrosekunden dafür.


Veröffentlicht am Von
Kategorisiert in Allgemein