Künstliche Intelligenz

Das in letzter Zeit so oft benutzte Schlagwort KI gilt nicht nur für Großcomputer. Machen Sie Ihren C 64 zur Denkmaschine!

Hier beginnt der zweite große Hauptteil des Kurses. Von nun an geht es um Künstliche Intelligenz. Schön gesagt, aber was ist Künstliche Intelligenz eigentlich – nun, ganz einfach, eine künstliche Form von normaler menschlicher Intelligenz!?! Hier wirft sich jedoch gleich die Frage auf, was Intelligenz eigentlich ist. Seit langem bereits streiten sich Mathematiker, Logiker und Philosophen darum, wie man Künstliche Intelligenz oder Intelligenz überhaupt definieren soll. Die Frage, ob der Mensch ein intelligentes Wesen ist, wird wohl jeder (Mensch zumindest) mit Ja beantworten. Es bietet sich daher an, einmal einzelne Handlungen eines Menschen zu betrachten, um dann zu begutachten, ob diese Handlungen als intelligent bezeichnet werden können oder nicht. Auf besonders interessante Aspekte in dieser Hinsicht werde ich im Kapitel »Irrgärten und Mäuse« zu sprechen kommen. Ich muß zugeben, daß ich mich bei der Zusammenstellung der Themen zum Kursabschnitt Künstliche Intelligenz wirklich sehr schwer tat. Wo fängt man am besten an? Wo hört man auf? Wo setzt man Schwerpunkte?

Als eine große Hilfe bei der Auswahl des Kursinhalts erwies sich mir das Buch »Gödel, Escher, Bach – ein endlos geflochtenes Band« von Douglas E. Hofstadter (ISBN 3-608-93039-X). Aufmerksam auf dieses Buch wurde ich durch den Logeleien-Kurs des 64'er, in dessen Rahmen dieses Buch empfohlen wurde. Es ist in der Tat eine Art von Bibel für alle KI-Freaks. Obgleich es keinerlei KI-Programme in Form von Listings zum Abtippen enthält, geht das Buch auf alle Bereiche der KI theoretisch in ausführlichem Maße ein. Das 800 Seiten starke Buch ist an vielen Stellen sehr kompliziert und unter Voraussetzung mathematischer Kenntnisse geschrieben. Trotzdem findet man in ihm zahlreiche Anregungen zum Schreiben von eigenen KI-Programmen. Je mehr ich mich mit KI und dem Schreiben dieses Kursabschnitts beschäftigte, umso mehr drängte sich in mir eine Frage auf: Die Frage, was uns KI eigentlich bringt – warum soll sich der Mensch den Kopf zerbrechen, um eine Maschine zu konstruieren, die so wie er (oder vielleicht noch besser?) denken und grübeln kann? Ich habe diese Frage bisher noch nicht beantworten können und glaube auch nicht, in allernächster Zukunft eine Antwort zu finden. Ich weiß jedoch, was uns KI auf dem C 64 im Rahmen dieses Kurses bringen soll: Nichts weiter als Spaß und Unterhaltung...

Bei KI-Programmierung auf dem C 64, oder sollte ich vielleicht besser sagen, Programmierung von simulierten menschlichen Denken, können in der Tat erstaunliche Resultate erzielt werden.

Besonders interessant ist dabei die Tatsache, daß zum Erzielen dieser Resultate oft sogar geringe Basic-Kenntnisse ausreichen. Die Programmierung von KI-Programmen erfordert ganz andere Überlegungen als die, die zum Schreiben von Spielen und Anwendungsprogrammen notwendig sind. Es geht einfach darum, simple logische Abläufe und Regeln in Programme umzusetzen. Das Problem besteht lediglich darin, die Logik in gewissen Abläufen zu erkennen. Auch hierzu werden im Kapitel »Irrgärten und Mäuse« wahre Musterbeispiele gegeben.

Bei der Einleitung zur KI möchte ich keine großen Worte über Grundlagen des logischen Denkens, logische Schlußfolgerungen oder Reproduzierbarkeit von Grundwissen verlieren. Über diese Themen wurden in letzter Zeit mehrere Artikel in den verschiedenen Fach- und Computerzeitschriften veröffentlicht. Es geht mir vielmehr darum, Ihnen anhand von praktischen Beispielen (Programmen) zu zeigen, wie KI-Simulationen funktionieren.

Am Ende dieses Kursteils können Sie mit Sicherheit selbst entscheiden, was Sie von KI halten sollen. Genug der Einführung, jetzt geht's endlich los...

Das NIM-Spiel

Jeder kennt es und hat es bestimmt auch schon einmal gespielt. Auf dem Tisch liegt eine Anzahl von Gegenständen (meist sind es Streichhölzer). Zwei Spieler dürfen nun abwechselnd 1, 2 oder 3 Gegenstände wegnehmen. Wer den letzten Gegenstand vom Tisch nehmen muß, hat schließlich verloren.

Listing 1 simuliert einen äußerst starken Spielpartner beim NIM-Spiel.

0 rem ***************************
1 rem *      ki-programm 1      *
2 rem * 1985 by michael nickles *
3 rem ***************************
10 rem data's lesen
20 dim x(20)
30 fori=1to20
40 read x(i)
50 next i
60 hz=20: rem anzahl der hoelzer
100 print"{clr}vor ihnen liegt ein haeufchen mit 20    hoelzern."
110 print"sie und der computer koennen nun"
120 print"abwechselnd je 1, 2 oder 3 hoelzer"
130 print"wegnehmen."
140 print"wer das letzte hoelzchen nehmen muss,"
150 print"hat verloren."
220 input"moechten sie anfangen (j/n)";i$
230 ifi$<>"j"andi$<>"n"then220
240 ifi$="j"thenprint"{down}ok. sie fangen an.":goto300
250 ifi$="n"thenprint"{down}ok. dann beginne ich.":goto400
300 :
301 rem spieler ist am zug
302 :
310 input"wieviele hoelzer";n
320 ifn<>1andn<>2andn<>3thenprint"sie koennen nur 1, 2 oder 3 nehmen !":goto310
330 hz=hz-n
340 ifhz<=0thenprint"sie haben verloren !":end
400 :
401 rem computer ist am zug
402 :
410 n=x(hz)
420 print"ich nehme";n;"hoelzer."
430 hz=hz-n
440 ifhz=0thenprint"sie haben gewonnen !":end
500 :
501 rem hoelzeranzahl festlegen
502 :
510 print"es liegen jetzt noch";hz;"hoelzer da !"
520 goto300
1000 data1,1,2,3,1,1,2,3,3,1,2,3,2,1,2,3,1,1,2,3

  0 REM *************************** 
  1 REM *      KI-PROGRAMM 1      * 
  2 REM * 1985 BY MICHAEL NICKLES * 
  3 REM *************************** 
 10 REM DATA'S LESEN 
 20 DIM X(20) 
 30 FOR I=1 TO20 
 40 READ X(I) 
 50 NEXT I 
 60 HZ=20: REM ANZAHL DER HOELZER 
 100 PRINT"{CLR}VOR IHNEN LIEGT EIN HAEUFCHEN MIT 20{SPACE,3SPACE}HOELZERN." 
 110 PRINT"SIE UND DER COMPUTER KOENNEN NUN" 
 120 PRINT"ABWECHSELND JE 1, 2 ODER 3 HOELZER" 
 130 PRINT"WEGNEHMEN." 
 140 PRINT"WER DAS LETZTE HOELZCHEN NEHMEN MUSS," 
 150 PRINT"HAT VERLOREN." 
 220 INPUT"MOECHTEN SIE ANFANGEN (J/N)";I$ 
 230 IF I$<>"J"AND I$<>"N" THEN220 
 240 IF I$="J" THENPRINT"{DOWN}OK. SIE FANGEN AN.":GOTO 300 
 250 IF I$="N" THENPRINT"{DOWN}OK. DANN BEGINNE ICH.":GOTO 400 
 300 : 
 301 REM SPIELER IST AM ZUG 
 302 : 
 310 INPUT"WIEVIELE HOELZER";N 
 320 IF N<>1AND N<>2AND N<>3 THENPRINT"SIE KOENNEN NUR 1, 2 ODER 3 NEHMEN !":GOTO 310 
 330 HZ=HZ-N 
 340 IF HZ<=0 THENPRINT"SIE HABEN VERLOREN !":END 
 400 : 
 401 REM COMPUTER IST AM ZUG 
 402 : 
 410 N=X(HZ) 
 420 PRINT"ICH NEHME";N;"HOELZER." 
 430 HZ=HZ-N 
 440 IF HZ=0 THENPRINT"SIE HABEN GEWONNEN !":END 
 500 : 
 501 REM HOELZERANZAHL FESTLEGEN 
 502 : 
 510 PRINT"ES LIEGEN JETZT NOCH";HZ;"HOELZER DA !" 
 520 GOTO 300 
 1000 DATA 1,1,2,3,1,1,2,3,3,1,2,3,2,1,2,3,1,1,2,3 

Sie werden schnell merken, wie spielstark dieses Programm ist. Zweifellos fraglich ist es allerdings, ob hier KI am Werk ist. Stellen wir uns doch einmal zwei Kinder vor, die zum ersten Mal das NIM-Spiel mit Streichhölzern spielen. Die ersten Spiele werden so verlaufen, daß die Kinder abwechselnd 1, 2 oder 3 Hölzer wegnehmen, ohne groß nachzudenken, bis schließlich eines das letzte Hölzchen nehmen muß und als Verlierer dasteht. Wir nehmen einmal an, es liegen noch 4 Hölzer auf dem Tisch und Kind A ist dran. Ohne große Überlegung weiß es, daß es genau 3 Hölzer – nicht mehr (darf es gemäß der Regel ja auch gar nicht) und nicht weniger – wegnehmen muß, um Kind B das letzte Holz aufzuzwingen und so zu gewinnen. Würde Kind A nur 2 Hölzer wegnehmen, so würden auf dem Tisch 2 Hölzer liegen bleiben. Kind A weiß in diesem Fall, daß Kind B sodann 1 Holz nehmen und dadurch gewinnen würde. Es ist also mehr eine Frage der Zeit, bis die Kinder folgende Regel beziehungsweise Logik des NIM-Spiels durchschauen:

Regel: Liegen nur noch 4 Hölzer auf dem Tisch, so ist derjenige der Sieger, der bei dieser Stellung am Zug ist. Dies setzt natürlich voraus, daß der Ziehende logisch vorgeht – also 3 Hölzer wegnimmt und nicht dummerweise weniger und so den gewissen Sieg verschenkt!

Aufgrund dieser Regel wird es also jeder anstreben, am Zug zu sein, wenn sich 4 Hölzer auf dem Tisch befinden. Hingegen will niemand am Zug sein, wenn sich nur noch 5 Hölzer auf dem Tisch befinden, da er dann sicher verliert. Es wird früher oder später also jeder Spieler daraufhin arbeiten, daß der Gegner dann am Zug ist, wenn 5 Hölzer auf dem Tisch liegen. Und genau das tut das obige Programm. Voraussetzung ist jedoch, daß die Anzahl der Hölzchen bekannt ist, denn nur dann kann bis zum letzten Zug vorausberechnet werden. Bei unserem Programm sind 20 Hölzer festgelegt. Entsprechend sieht die Strategie des Programms aus, die im Feld X gespeichert ist.

Bild 1 zeigt die Vorgehensweise des Programms – wieviele Hölzer es nimmt, wenn eine bestimmte Anzahl von Hölzern auf dem Tisch liegt.

Bild 2 zeigt, auf welche 5 Punkte das Programm hinarbeitet, um den Spieler verlieren zu lassen. Aus Bild 2 geht auch hervor, daß der Spieler keine Gewinnchance hat, wenn er das Programm anfangen läßt. Liegen 20 Hölzer auf dem Tisch und das Programm beginnt, so nimmt es gleich 3 Hölzer weg. Der Spieler ist also erst beim ersten kritischen Punkt dran. Egal, was er macht, beim nachfolgenden Zug bringt ihn das Programm zum nächsten kritischen Punkt. Dies spielt sich solange ab, bis der Spieler beim letzten kritischen Punkt angelangt ist und somit verloren hat.

Es gibt für den Spieler also nur eine einzige Gewinnchance: Er muß dafür sorgen, daß das Programm immer bei den kritischen Punkten am Zug ist. Bei Bild 2 ist noch etwas anderes auffällig: Alle kritischen Punkte haben von ihren benachbarten kritischen Punkten den gleichen Abstand! Nehmen wir einmal an, der Spieler beginnt und nimmt sofort 3 Hölzer weg. Das Programm landet so beim ersten kritischen Punkt und nimmt aus Verlegenheit ein Holz weg. Um das Programm zum nächsten kritischen Punkt zu bringen, muß der Spieler jetzt 3 Hölzer wegnehmen. Er muß also viel, viel Glück haben, wenn er gewinnen will.

Die Gewinn-Reihenfolge lautet: 3, 3, 2, 1, 3.

Dieses KI-Programm ist so primitiv, daß es auf jedem programmierbaren Taschenrechner, ja sogar mit drei Lämpchen, ein paar Drähten, Batterie und Schrauben verwirklicht werden kann (ist eine nette Geschenkidee!).

Ich hoffe, daß es mir anhand dieses Spiels gelungen ist, Ihnen schon etwas klarzumachen, wie man beim Programmieren von KI-Problemen vorgehen muß. Die Vorgehensweise sieht in etwa so aus:

1. Einfach mal mit dem Problem herumspielen, herumprobieren. Also ausprobieren: WAS PASSIERT WENN...
2. Ausprobieren, ob irgendwo logische Abläufe vorhanden sind (Bei unserem Beispiel: Logisch, daß man von 4 Hölzern auf dem Tisch 3 wegnehmen muß, wenn man am Zug ist und gewinnen will).
3. Versuchen, einfache Regeln aufzustellen.
4. Ein Gesamtkonzept entwickeln.
5. Skizzieren, Ablaufpläne erstellen.
6. Programmieren.

Sie sehen schon: Dem eigentlichen Programmieren der Lösung gehen zahlreiche Einzelschritte voran.

Die Gültigkeit dieser fünf Grundregeln kommt auch im folgenden Kapitel voll und ganz zur Geltung – beim Programmieren von Software-Mäusen, die sich in einem Labyrinth zurechtfinden lernen.

Irrgärten und Mäuse – Grundlagen des »Backtracking«

Ein weiteres interessantes Gebiet, das uns noch tiefer in die Grundlagen der Künstlichen Intelligenz einführen wird, ist das Programmieren von »Mäusen«, die den Weg durch ein Labyrinth finden können – also KI-Programme, die Irrgärten »knacken« können. In den USA und in Japan werden zu diesem Thema regelrechte Wettkämpfe ausgetragen. Es geht darum, einen kleinen Roboter so zu konstruieren und programmieren, daß er möglichst schnell den Weg durch ein Labyrinth finden kann. Die Robotermäuse sind hierbei regelrechte Mini-Wunderwerke, zusammengebaut aus Motoren, Zahnrädern, Sensoren und natürlich vollgepackt mit Elektronik und einem Mikroprozessor. Wir wollen uns in diesem Kurs natürlich nicht mit Grundlagen der Mechanik zum Bau einer solchen Robotermaus vertraut machen (was unheimlich viel Geschick erfordert), sondern vielmehr ein Steuerprogramm für so eine Maus entwickeln.

Betrachten Sie bitte einmal das Labyrinth in Bild 3:

Als simpel oder primitiv kann man dieses Labyrinth mit Sicherheit nicht bewerten, denn man sieht auf den ersten Blick lediglich Eingang (Pfeil Ecke links unten) und Ausgang (Pfeil Ecke rechts oben), jedoch keine direkte Verbindung zwischen den beiden. Wir wollen an dieser Stelle einmal versuchen zu analysieren, wie ein Mensch vorgeht, wenn er den Weg durch dieses Labyrinth finden will. Zunächst einmal sieht man, wie bereits gesagt, auf einen Blick Eingang und Ausgang des Irrgartens. Kaum jemand wird jetzt versuchen, eine bestimmte Taktik des Vorgehens zu entwickeln – vielmehr tritt sofort das menschliche Auge in Kraft. Es versucht zunächst, eine möglichst direkte Verbindungslinie zwischen Eingang und Ausgang zu finden. In Sekundenschnelle stellt es dabei fest, daß ein direkter Weg nicht existiert – unter »direktem Weg« verstehe ich einen Weg, der nur sehr wenige Verzweigungen hat. Aus menschlicher Sicht ist für diesen Vorgang kein lobenswerter Denkprozeß, keine Intelligenz notwendig. Der nächste Schritt ist schon etwas komplizierter. Wer zum allererstenmal mit einem solchen Irrgarten konfrontiert wird – zum Beispiel kleine Kinder – versucht nun vom Eingang ausgehend verschiedene Wege – meistens in Richtung Ausgang orientiert – anzusteuern. Man bedient sich hierbei Hilfsmittel wie dem Zeigefinger oder einem Stift zum Entlangfahren des gegangenen Weges.

Der versierte Irrgarten-Freak geht jedoch sicherlich anders vor. Aus seiner Erfahrung mit früheren Irrgärten hat er gelernt, daß Irrgartenkonstrukteure meistens einen sehr indirekten Weg vom Eingang zum Ausgang wählen (also möglichst viele Verzweigungen), um den Irrgarten möglichst kompliziert zu machen. Der Erfahrene wird mit Sicherheit auch nicht jeden erdenklichen Weg bis zum Ende ausprobieren. Er sieht gleich, wo Sackgassen-Gebiete sind, und geht erst gar nicht in diese hinein. Ein Sackgassengebiet ist ein Gebiet des Irrgartens, wo sich ein Weg in verschiedene Richtungen aufteilt, die jedoch alle in Sackgassen enden. Ein ganz deutliches Sackgassengebiet befindet sich in unserem Labyrinth in der linken unteren Ecke, gleich neben dem Eingang.

Sicherlich haben Sie an dieser Stelle bereits bemerkt, daß ich auf die Irrgärten und Mäuse besonders genau eingehen möchte. Dies hat seinen Grund, denn an diesem Beispiel läßt sich sehr gut demonstrieren, wie man vorgehen muß, wenn man intelligente Abläufe programmieren will.

Beim Programmieren von Action-Spielen und auch Adventures muß man sich oft keine allzu großen Grundgedanken machen. Natürlich ist es oft schwer, Ideen programmtechnisch umzusetzen (sei es das Programmieren von schnell bewegter Grafik oder auch Parser für Adventures), man hat jedoch gewisse Regeln, nach denen man sich richten oder an denen man festhalten kann. Bei KI-Programmierung ist dies anders: Die KI steckt noch in ihren Kinderschuhen und wird es höchstwahrscheinlich auch bleiben, solange der Mensch nicht eine Frage geklärt hat. Die Frage, was Intelligenz eigentlich ist, wann ein bestimmer Prozeß als intelligent bezeichnet werden kann und wann nicht. Man denke hierbei zum Beispiel an jemanden, der sich mit Hintergedanken, also mit Absicht dumm stellt, weil er glaubt, damit etwas besser erreichen zu können. Man stellt sich zum Beispiel dumm, weil man zu faul ist, etwas lang und breit zu erklären (zum Beispiel Grundlagen der KI....). Was ich sagen will ist, daß sich aus dem Verhalten eines Menschen heraus nie beurteilen läßt, ob eine Tat nun auf mangelnder Intelligenz oder auf bewußter Simulation von mangelnder Intelligenz beruht. Ich werde mich deshalb auch hüten, an dieser Stelle zu erörtern, wieviel beziehungsweise ob überhaupt Intelligenz zum Knacken von Labyrinthen erforderlich ist. Wir wollen deshalb nun vielmehr versuchen, herauszufinden, wie man ein Programm, das sich in Irrgärten zurechtfindet, programmiert und danach Analogien zum menschlichen Vorgehen suchen.

Ein Profi im Labyrinth

Wie wir festgestellt haben, beruht die menschliche Vorgehensweise hauptsächlich auf visueller Basis, dem Durchchecken des Irrgartens mittels des Auges. Dies ist einfach, da wir das gesamte Labyrinth mit allen Wegen auf einmal überblicken können. Was wird jedoch, wenn wir es mit einem riesigen Labyrinth zu tun bekommen – zum Beispiel auf einer mehrere Quadratmeter umfassenden Papierfläche? Hier ist unsere »Optik« schnell überlastet. Völlig unbrauchbar wird die visuelle Methode schließlich, wenn wir uns vorstellen, daß es sich bei dem Irrgarten um einen unterirdischen, unbeleuchteten Komplex handelt, in dem wir uns direkt befinden. Um dann den Ausgang zu finden, braucht man eine gute Orientierungsfähigkeit (Intelligenz???) und eine große Portion Glück.

In dieser Situation können wir uns eine Robotermaus vorstellen. Sie befindet sich direkt im Irrgarten, hat keinen Gesamtüberblick, ja, weiß nicht einmal, in welcher Richtung sich der Ausgang befindet.

Was die visuelle Basis anbelangt, so wird der Mensch einem Homecomputer mit 64 KByte wie dem C 64 immer überlegen sein. Wenn es jedoch um Orientierungsfähigkeit im Dunkeln geht wie zum Beispiel in Irrgärten, die man nicht auf einmal überblicken kann (weil man sich zum Beispiel selbst in ihnen befindet), ist uns unser C 64 bei geschickter Programmierung bei weitem überlegen, da er Tausende von Schritten speichern kann, also eine Karte vom Irrgarten in seinem »Gedächtnis« mitschreibt. Der Mensch hingegen verliert je nach persönlicher Fähigkeit bereits nach (im Verhältnis zum Computer betrachtet) wenigen Abzweigungen die Orientierung.

Oder vielleicht doch nicht?

Immer an der Wand lang

Im folgenden wollen wir ein einfaches Labyrinth betrachten – die Theorie läßt sich jedoch auch auf jegliche anderen Labyrinthe übertragen.

Das folgende »Schema« zeigt, wie man auch im Dunkeln, allein durch Tastsinn, todsicher aus jedem auch noch so komplexen Labyrinth herausfinden kann. Bei allen Experimenten setzen wir selbstverständlich logisch aufgebaute Labyrinthe voraus, das heißt, geht man von Ort A in nördliche Richtung, um zu Punkt B zu gelangen, so gelangt man von B zurück zu A, indem man sich nach Süden bewegt. Bei Labyrinthen in Adventures (besonders ZORK I) ist dies oft nicht der Fall!

Das Prinzip ist ganz einfach. Angenommen, wir betreten einen stockdunklen Irrgarten. Wir berühren sofort beim Eintreten mit der linken Hand die linke Wand und lassen diesen Kontakt für die gesamte Zeit, die wir uns im Labyrinth aufhalten, nicht abbrechen. Das heißt, wir laufen immer vorwärts, also nie zurück in die Richtung, aus der wir kommen und schleifen beim Vorwärtsgehen unsere linke Hand die Wand entlang. Vorwärtsgehen kann natürlich auch um die Ecke gehen bedeuten. Wichtig ist nur, daß die linke Hand nie den Kontakt mit der Wand verliert.

Wenn Sie das Bild 4 betrachten und einmal mit Ihrem linken Zeigefinger (stellvertretend für die linke Hand) die rote Linie (in Pfeilrichtung) vom Eingang zum Ausgang entlangfahren, werden Sie das Prinzip verstehen.

Hat man erstmal durchgeblickt, ist die Methode sonnenklar und absolut logisch, ja, sogar primitiv – aber draufkommen muß man halt erst einmal. Trotzdem ist es fantastisch, wie einfach man einen irrsinnig komplexen Irrgarten unter Verwendung einer solch einfachen Regel knacken kann. Wer noch mißtrauisch ist (und das sollten Sie bei KI-Programmen immer sein!), kann unser Lösungsprinzip einmal auf den großen Irrgarten (Bild 1) anwenden – es funktioniert garantiert! Wie jede Medaille ihre Kehrseite hat, so hat jedoch auch unsere Methode ihre Haken. Sie ist zum Beispiel nur auf zweidimensionale Irrgärten anwendbar, das heißt, bei Irrgärten, in denen es auch auf und ab geht (zum Beispiel mit Treppen und Leitern), sind wir aufgeschmissen. Auch bei unlogischen Irrgärten, bei denen Richtungsänderungen irreversibel sind, kommen wir nicht sehr weit. Sie können nun einwerfen, daß es beim Irrgarten (Bild 4) viel schneller gehen würde, wenn man sich an der rechten Wand (Hand) orientieren würde. Das stimmt, aber auch hier haben Sie wieder Gebrauch von der visuellen Methode gemacht – und die gilt nicht. Im Prinzip ist es jedoch vollkommen egal, ob wir uns für rechts oder links entscheiden. Wichtig ist nur, daß man seine Entscheidung beim Laufen im Irrgarten immer beibehält. Interessant ist auch die folgende Tatsache: Linker und rechter Lösungsweg schneiden sich nie! – Ausprobieren!

Allerdings hat unsere Methode auch noch einen anderen Nachteil – man lernt nichts daraus. Das heißt, wenn man den Irrgarten ein zweites, drittes oder gar noch öfteres Mal durchläuft, braucht man immer die gleiche Zeit dazu (vorausgesetzt, man bewegt sich immer mit der gleichen Geschwindigkeit vorwärts). Günstiger wäre es, wenn man sich alle Sackgassen im Gedächtnis speichern würde und bei späteren Versuchen erst gar nicht mehr in diese hineinlaufen müßte – dieses »Speichern« ist bei unserer jetzigen Methode nicht möglich. Probieren Sie doch einmal beide Methoden im Irrgarten (Bild 1) aus, die links- oder die rechtsorientierte und die visuelle (die Speichermethode). Sie werden schnell merken, wie Sie bei mehrmaligem Durchwandern des Labyrinths mit der visuellen Methode immer mehr von Ihrem Erfahrungs-Speicher (Intelligenz???) Gebrauch machen werden. Mit der Zeit weiß man halt einfach immer besser, wann etwa man sich links orientieren muß, wann in Richtung Norden, wo man schon einmal eine falsche Richtung eingeschlagen hat (und dies deshalb nun meidet), und findet sich so immer besser zurecht. Nach einiger Zeit kennt man sich schließlich aus – man gelangt, ohne sich zu verirren, vom Eingang zum Ausgang.

Schön und gut, Sie wissen jetzt eine Formel, mit der man sicher aus jedem zweidimensionalen, logisch aufgebauten Labyrinth herausfindet. Wie setzt man eine Lösungsmethode dieser Art jedoch zum Programm um?

Ich möchte Ihnen im folgenden ein Programm vorstellen, das folgende Kriterien erfüllt:

— Der Irrgarten muß nicht im Speicher des C 64 stehen. Das Programm ist in der Lage, jeden zweidimensionalen Irrgarten (mögliche Richtungen: N, S, O, W) mit beliebiger Größe, der in einer Form wie Bild 1 vorliegt, zu knacken.

— Das Programm fragt den »Spieler«, ob bestimmte Richtungen möglich sind. Es erwartet sodann immer eine Antwort in der Form JA oder NEIN. Man muß dem Programm mitteilen, wenn es den Ausgang gefunden hat.

— Das Programm bemerkt es, wenn man versucht, es mit falschen Antworten oder Irrgärten ohne Ausweg zu »leimen«.

— Das Programm merkt sich den richtigen Weg und findet beim zweiten Anlauf den Weg ohne jegliches Verirren.

Rekursive Unterprogramme

Gerade das letzte Kriterium macht uns schwer zu schaffen, da es unser bisheriges Lösungskonzept völlig über den Haufen wirft.

Es muß also ein Neues her (das vom Aufbauprinzip her jedoch gar nicht so verschieden von unserer ersten Methode sein wird).

Die meisten Maus-Programme basieren auf einem Konzept, das die folgende Programmiertechnik erforderlich macht:

Rekursive Unterprogramme sind Unterprogramme oder auch Prozeduren, die sich selbst aufrufen. In höheren Programmiersprachen wie zum Beispiel LISP lassen sich rekursive Vorgänge relativ leicht programmieren. Basic ist hierzu nicht sehr geeignet. Das folgende Beispiel demonstriert auf einfache Art und Weise, wie rekursive Unterprogramme funktionieren:

10 REM REKURSIVES UP - DEMO
20 GOSUB1000:REM REKURSIVES UP AUFRUFEN
1000 REM REKURSIVES UNTERPROGRAMM
1010 :
1020 GOSUB1000:REM SELBSTAUFRUF
1030 :
1040 RETURN

Die Dokumentation hierzu ist kurz und einfach:

In Zeile 10 wird ein Unterprogramm aufgerufen, das in den Zeilen 1000 – 1040 steht. In Zeile 1020 – also innerhalb des Unterprogrammes – ruft es sich selbst auf.

Was wird wohl passieren, wenn wir dieses kurze Programm starten (was Sie ja eh schon getan haben, ohne auf meine Erklärung zu warten)?

Es kommt zu einem
OUT OF MEMORY ERROR IN 1020.

Mißrauisch, wie wir sind, geben wir nun
PRINT FRE(0)+65000 ein.

Dabei kommt heraus, daß 38323 Byte RAM frei sind. Wie kommt es denn dann zum OUT OF MEMORY ERROR, werden Sie sich nun sicher fragen.

Ganz einfach. Der C 64 kann nur eine begrenzte Anzahl von Unterprogrammen nach dem Stapelprinzip (als letztes rein, als erstes raus) verwalten und aufrufen.

Ändern Sie bitte Zeile 101 so ab:
1010 I=I+1.

Wenn Sie nun das Programm starten und nach seinem Abbruch den Wert I im Direktmodus abfragen, erhalten Sie den Wert 23. Das heißt, der C 64 ist in der Lage, maximal 23 Unterprogrammaufrufe zu speichern (die Rücksprungadressen). In anderen Worten läßt sich das Stapel-Prinzip so ausdrücken: Der C 64 findet eine GOSUB-Anweisung. Er nimmt sich nun einen Notizzettel und schreibt auf diesen die Zeile, in der die GOSUB-Anweisung erfolgt ist. Er merkt sich also, wo er weitermachen muß, wenn das Unterprogramm mit RETURN beendet wird. In dem eben notierten Unterprogramm kommt nun plötzlich wieder eine GOSUB-Anweisung vor. Es ist dabei völlig egal, ob ein anderes Unterprogramm aufgerufen wird oder ob sich das Unterprogramm rekursiv selbst aufruft wie in unserem Beispiel. Wieder nimmt der C 64 sich einen Zettel und notiert, wo es weitergeht, wenn dieses Unterprogramm mit RETURN beendet wird. Diesen Notizzettel legt der C 64 nun oben auf den ersten Notizzettel. Jetzt taucht im Programm eine RETURN-Anweisung auf. Woher soll der C 64 nun wissen, wohin er springen muß? Nun, er nimmt einfach den obersten Zettel vom Notizstapel weg (daher der Name Stapel-Prinzip). Auf diesem Zettel steht, wohin er zurückspringen muß. Nach dem Sprung wirft der C 64 den vom Stapel genommenen Notizzettel in den Papierkorb. Bei der nachfolgenden RETURN-Anweisung wird der nächste oberste Zettel vom Stapel genommen, dann der nächste und so weiter. Wenn eine RETURN-Anweisung kommt und der C 64 findet auf seinem »Schreibtisch« keinen Notizzettel, so meldet er sich empört mit RETURN WITHOUT GOSUB ERROR. Versucht man hingegen, ein 24. Unterprogramm aufzurufen, so meldet er sich mit OUT OF MEMORY ERROR IN. Auf seinem Schreibtisch ist leider nur Platz für maximal 23 Notizzettel. Der OUT OF MEMORY ERROR heißt praktisch nichts anderes als »Ich habe keinen Platz mehr für weitere Zettel auf meinem Schreibtisch«.

Der rekursiven Programmierung mittels GOSUB sind also enge Grenzen gesetzt.

Im Listing 2 finden Sie ein Maus-Programm, das auf solch rekursiven Unterprogrammen beruht:

1 rem ********************************
2 rem *   irrgaerten und maeuse i    *
3 rem * <c> 1985 bei michael nickles *
4 rem ********************************
5 poke53280,0:poke53281,0:print"{clr}{rvon}{wht}maus i{rvof}{down}"
10 ri$(1)="links"
11 ri$(2)="geradeaus"
12 ri$(3)="rechts"
20 dimm(20)
100 rem hauptprogramm ----------------
101 :
110 gosub1000
120 print"ich finde keinen ausgang!":end
1000 rem rekursives up ---------------
1001 :
1005 i=0
1010 i=i+1
1015 print"kann ich ";ri$(i); " gehen (j/n)"
1020 inputbe$
1025 ifleft$(be$,1)="n"then1110
1030 m(v)=i
1050 print"ausgang gefunden (j/n)"
1055 inputbe$
1060 ifleft$(be$,1)="j"thenprint"geschafft !":end
1065 ifv=20thenprint"habe mich verirrt !":end
1070 v=v+1:gosub1000
1095 print"ausgang gefunden (j/n)"
1100 v=m(t)
1110 ifi=3thenreturn
1120 goto1010

  1 REM ******************************** 
  2 REM *   IRRGAERTEN UND MAEUSE I    * 
  3 REM * <C> 1985 BEI MICHAEL NICKLES * 
  4 REM ******************************** 
  5 POKE 53280,0:POKE 53281,0:PRINT"{CLR,RVSON,WHITE}MAUS I{RVOFF,DOWN}" 
 10 RI$(1)="LINKS" 
 11 RI$(2)="GERADEAUS" 
 12 RI$(3)="RECHTS" 
 20 DIM M(20) 
 100 REM HAUPTPROGRAMM ---------------- 
 101 : 
 110 GOSUB 1000 
 120 PRINT"ICH FINDE KEINEN AUSGANG!":END 
 1000 REM REKURSIVES UP --------------- 
 1001 : 
 1005 I=0 
 1010 I=I+1 
 1015 PRINT"KANN ICH ";RI$(I); " GEHEN (J/N)" 
 1020 INPUTBE$ 
 1025 IF LEFT$ (BE$,1)="N" THEN1110 
 1030 M(V)=I 
 1050 PRINT"AUSGANG GEFUNDEN (J/N)" 
 1055 INPUTBE$ 
 1060 IF LEFT$ (BE$,1)="J" THENPRINT"GESCHAFFT !":END 
 1065 IF V=20 THENPRINT"HABE MICH VERIRRT !":END 
 1070 V=V+1:GOSUB 1000 
 1095 PRINT"AUSGANG GEFUNDEN (J/N)" 
 1100 V=M(T) 
 1110 IF I=3 THENRETURN 
 1120 GOTO 1010 

Diese Maus funktioniert auf der Basis unserer »Immer-an-der-Wand-lang«-Methode«. Der Programmablauf ist äußerst einfach: Die Maus fragt einfach, ob sie nach links gehen kann. Ist dies der Fall, so speichert sie den ersten Zug und fragt, ob der Ausgang gefunden ist. Ist links nicht möglich, so versucht die Maus geradeaus zu gehen. Geht dies auch nicht, so versucht sie es mit rechts. Funktionieren alle drei Richtungen nicht (zum Beispiel, wenn wir die Maus beschummeln), stellt sie dies in Zeile 1110 fest und gibt die Suche auf. Die merkwürdige Abfrage mag zunächst verblüffend sein. Um die Maus zum Beispiel durch den Irrgarten in Bild 1 zu schicken, ist folgende Befehlsfolge notwendig:

geradeaus-rechts-geradeaus-links-rechts-rechts-links etc.

Bei der Eingabe ist zu beachten, daß sich Links-Rechts-Angaben nicht auf ihre Position (Spieler), sondern aus der Sicht der Maus und ihrer momentanen Bewegungsrichtung bezogen werden muß. Unsere Maus ist allerdings zu schwach für den Irrgarten in Bild 1. Irrgarten 1 erfordert nämlich 22 Richtungsänderungen bis zum Ausgang. Aufgrund der rekursiven GOSUB-Programmierung kann die Maus jedoch nur maximal 20 Schritte speichern (eigentlich 24, aber man soll sich immer etwas »Spielraum« lassen – deshalb Einschränkung auf 20).

Grundlagen des Backtracking

Wer glaubt, daß es auch ganz ohne Rekursives geht, hat recht:

Zu dem Programm in Listing 3 habe ich nichts zu sagen. Sie sehen es sicher selbst. Aus der Links-Rechts-Methode läßt sich einfach nichts herausholen, was auch nur im entferntesten mit KI zu tun hat.

1 rem ********************************
2 rem *   irrgaerten und maeuse ii   *
3 rem * <c> 1985 bei michael nickles *
4 rem ********************************
5 poke53280,0:poke53281,0:print"{clr}{rvon}{wht}maus ii{rvof}{down}"
10 ri$(1)="links"
11 ri$(2)="geradeaus"
12 ri$(3)="rechts"
100 rem hauptprogramm ----------------
110 i=0
120 i=i+1
125 ifi=4thenprint"habe mich verirrt !":end
130 print"kann ich ";ri$(i);" gehen (j/n)"
140 inputbe$
150 ifbe$="n"then120
155 i=0
160 print"ausgang gefunden (j/n)"
170 inputbe$
180 ifbe$="j"thenprint"prima !":end
200 goto120

  1 REM ******************************** 
  2 REM *   IRRGAERTEN UND MAEUSE II   * 
  3 REM * <C> 1985 BEI MICHAEL NICKLES * 
  4 REM ******************************** 
  5 POKE 53280,0:POKE 53281,0:PRINT"{CLR,RVSON,WHITE}MAUS II{RVOFF,DOWN}" 
 10 RI$(1)="LINKS" 
 11 RI$(2)="GERADEAUS" 
 12 RI$(3)="RECHTS" 
 100 REM HAUPTPROGRAMM ---------------- 
 110 I=0 
 120 I=I+1 
 125 IF I=4 THENPRINT"HABE MICH VERIRRT !":END 
 130 PRINT"KANN ICH ";RI$(I);" GEHEN (J/N)" 
 140 INPUTBE$ 
 150 IF BE$="N" THEN120 
 155 I=0 
 160 PRINT"AUSGANG GEFUNDEN (J/N)" 
 170 INPUTBE$ 
 180 IF BE$="J" THENPRINT"PRIMA !":END 
 200 GOTO 120 

Backtracking – diese Bezeichnung trifft bei Programmen zu, die verschiedene Lösungen ausprobieren und einen Lösungsweg, der nicht zum Ziel führt, »rückwärts« wieder verlassen können, um eine andere Lösungsalternative auszuprobieren.

Unsere nächste Maus soll nach solch einem Backtracking-Verfahren arbeiten. Machen wir uns einmal ein paar Gedanken über unser neues Programm.

Nehmen wir einmal an, die Maus arbeitet ähnlich wie wir, wenn wir ein Adventure spielen. Sie zeichnet sich eine Karte des Irrgartens. Bei jedem Schritt, den die Maus tiefer in das Labyrinth vordringt, wird diese Karte größer. Anhand der Karte kann die Maus jederzeit feststellen, wo sie schon war, welchen Weg sie bisher gegangen ist.

Hier noch einmal eine kleine Definition in bezug auf zweidimensionale, logische Labyrinthe:

Bei jedem Irrgarten kann man den Ausgang mit dem Eingang durch den absoluten Lösungsweg verbinden. Der Lösungsweg ist also der einzige, kürzeste Weg, der notwendig ist, um vom Eingang zum Ausgang zu gelangen.

Alle anderen Wege (eventuelle Verzweigungen des Lösungswegs) enden mehr oder weniger in Sackgassen. Unsere Maus betritt den Eingang und geht bis zur ersten »Kreuzung«. Der Weg vom Eingang bis zur ersten Kreuzung ist mit absoluter Sicherheit ein Teilstück des Lösungsweges. Kommt die Maus an der ersten Kreuzung an, gibt es folglich nur zwei Möglichkeiten:

a. Sie schlägt einen neuen Weg ein, der wiederum einen Abschnitt des Lösungsweges repräsentiert. Sie bleibt also auf dem richtigen Weg.

b. Die Maus kommt vom einzig richtigen Lösungsweg ab und gerät in eine Sackgasse oder sogar in ein Sackgassengebiet. Dieser Fall tritt mit Sicherheit häufiger als Fall a ein.

Wir wollen der Einfachheit halber zunächst einmal folgendes festlegen: Jeder Weg, der vom Lösungsweg wegführt, endet früher oder später in einer absoluten Sackgasse, aus der nur ein einziger Weg hinausführt: der Weg, durch den man in sie geraten ist (zum Beispiel ein langer Korridor, der plötzlich endet).

Unsere Maus erhält von uns einen Radiergummi. Mit ihm kann sie alle Wege, die sie bereits in ihre Karte gezeichnet hat und die als absolute Sackgasse enden, wieder herausradieren. Die Karte, die dann letztendlich übrigbleibt, stellt nur noch den absoluten Lösungsweg dar. Dieses Herausradieren, also das Widerrufen bereits gefällter Entscheidungen, die sich als falsch erwiesen haben – das Löschen falscher oder unbrauchbarer Notizen –bezeichnet man als den eigentlichen Backtracking-Vorgang. Das folgende Schema zeigt den Irrgarten, bei dem alle falschen Wege wegradiert wurden. Der Weg, der noch vorhanden ist, ist der absolute Lösungsweg (Bild 5).

Bild 5 zeigt den Irrgarten von Bild 1, nachdem er von unserer nächsten Maus durchwandert worden ist.

Das heißt, alles, was vom Irrgarten noch übriggeblieben ist, ist der absolute Lösungsweg (auch durch Pfeil deutlich gemacht). Der restliche Teil des Irrgartens ist entfernt worden: Die schwarz ausgemalten Wege sind von der Maus als absolute Sackgassen analysiert worden. Nachdem die Maus einen solchen Weg durch die einzig mögliche Richtung wieder verlassen hat, entfernt sie ihn sofort für immer aus ihrem Gedächtnis. Im Labyrinth sind jedoch noch zwei andere ausgemalte Flächen zu sehen: eine gelbe und eine rote. Für die folgenden Überlegungen wollen wir uns auf die Wegabschnitte X, A, B, C und D beziehen.

Nehmen wir einmal an, unsere Maus steht an der Stelle X. Sie befindet sich also im rot ausgemalten Wegteil. Wenn wir einmal von der Richtung absehen, aus der sie gerade gekommen ist, hat die Maus nun drei Möglichkeiten. Sie kann zu A, B oder C gehen. Unsere Maus entscheidet sich zunächst für A. Leider erweist sich A als absolute Sackgasse. Die Maus geht also zurück zu X und vergißt A (wird schwarz ausgemalt). Nun versucht die Maus es bei B. Wieder Pech. Also zurück zu X und B vergessen. Nun geht die Maus nach C. Sie weiß an dieser Stelle noch nicht, daß auch dieser Wegabschnitt nach der nächsten Abbiegung in einer Sackgasse enden wird. Von C aus hat die Maus zwei Möglichkeiten: Sie kann nach X und nach D gehen. Unsere Maus ist jedoch so programmiert, daß sie nur und wirklich nur dann zurück zu dem Punkt geht, aus dem sie gerade kommt, wenn dies die einzige Möglichkeit ist. Sie hat also das Bestreben, immer tiefer in das Labyrinth vorzudringen. Sie zieht stets die unbekannten Wegabschnitte den bereits begangenen vor.

Die Programmierung der dritten Maus

Diese Regel zwingt die Maus also nun dazu, nach Punkt D zu gehen. In Punkt D stellt sie jedoch wieder fest, daß sie in einer absoluten Sackgasse gelandet ist. Sie geht somit die einzig mögliche Richtung zurück (zurück zu C) und vergißt Wegabschnitt D. Durch das Eliminieren des Wegteils D ist nun auch C zur absoluten Sackgasse geworden. Die Maus wählt wieder die einzig mögliche Richtung, geht nach X und eliminiert Wegteil C. Dadurch, daß die Wegteile A, B, C eliminiert worden sind, ist nun auch Teil X zur absoluten Sackgasse geworden. Die Maus nimmt also die einzige Richtung ein, die von X aus noch möglich ist. Sie landet dadurch wieder auf dem richtigen Lösungsweg. Sie sehen also, wie unsere Maus arbeitet, wenn sie in einer Sackgasse gelandet ist. Aber wie setzt man dieses Wissen über Mäuse in ein Programm um? Wie uns bereits klar ist, braucht unsere neue Maus ein Gedächtnis, mit dem sie sich merken kann, wo sie bereits war – somit also letztendlich den absoluten Lösungsweg. Dieses Gedächtnis muß flexibel sein. Das heißt, es muß sowohl speichern als auch vergessen können. Zunächst erweitert unsere Maus ihr Gedächtnis mit jedem Schritt vorwärts. Gerät sie jedoch in eine Sackgasse, so muß sie einen Schritt rückwärts machen und somit bereits Gelerntes, das sich als falsch, nämlich als Sackgasse erwiesen hat, wieder vergessen. Solch ein flexibles Gedächtnis wird in unseren Mausprogrammen stets mittels eines dimensionierten Feldes realisiert.

Wie muß dieses Feld aussehen?

Wir haben definiert, daß die Irrgärten, in denen sich unsere Maus zurechtfinden wird, zweidimensional logisch aufgebaut sein müssen. Es gibt in jedem Raum genau vier mögliche Richtungen: N, S, O und W. Im Prinzip könnten wir auch Richtungen wie NW, SW, NO und SO erlauben. Wichtig ist nur, daß alle Richtungen in der gleichen Ebene verlaufen. Der Einfachheit halber beschränken wir uns jedoch auf die vier Grundhimmelsrichtungen. Was liegt nun näher, als eine Tabelle anzulegen, die zu jedem Raum die möglichen Richtungen speichert.

Dieses Gedächtnis sieht dann aus wie Tabelle 1. Die Tabelle 1 ist wie folgt zu interpretieren:

Wenn man von Raum 0 aus nach Norden geht, gelangt man zu Raum 1. Geht man nach Osten, so gelangt man zu Raum 2 und so weiter.

Hoppla, ist das nicht etwa eine Landkarte, wie man sie zur Programmierung von Abenteuerspielen benötigt?

Richtig. Dies ist genau die Methode, die ich im ersten Adventure-Programmierkurs zum Definieren der einzelnen Räume eines Spiels festgelegt habe (wer will, kann sie in Sonderheft 2/85 nachlesen!).

Für das »Gedächtnis« unserer Maus legen wir folgendes fest:

1. Zu Beginn des Programmes erhält jedes Element der Tabelle den Wert 1. Das heißt, jede Möglichkeit, die die Maus noch nicht ausprobiert hat, hat den Wert 1.
2. Will die Maus in eine Richtung gehen, die nicht möglich ist, so erhält die entsprechende Stelle den Wert 2. Sackgassen kennzeichnen sich also durch dreimaliges Vorkommen einer 2 in ihrer »Zeile«.
3. Ist eine Richtung möglich, so wird in die entsprechende Tabellenstelle die Nummer des Raumes geschrieben, zu dem diese Richtung führt.

Je größer die Tabelle ist, umso größer ist die Gedächtnisleistung der Maus. 38 KByte Basic-RAM sind genug, um der Maus ein Gedächtnis für über 1000 Räume zur Verfügung zu stellen.

Natürlich benötigen wir auch noch einen Zeiger, der immer auf den Raum der Tabelle zeigt, in dem sich die Maus gerade befindet. Vielleicht finden Sie es noch verwirrend, wie man bei einem Labyrinth überhaupt von Räumen sprechen kann, beziehungsweise, was die Zeiger 1 und 2 sollen. Die folgenden Beispiele werden es Ihnen klarmachen:

In Bild 6 sind die ersten drei Schritte der Maus eingezeichnet. Die Maus beginnt ihre Suche immer in Raum 0, dem Labyrintheingang oder dem Ausgangspunkt, wenn die Maus inmitten eines Labyrinthes ausgesetzt wird. Die Maus läuft nun nach Norden zu Raum 1. Ein Raum kann also als Wegkreuzung angesehen werden. Wenn uns die Maus später fragt, ob sie nach Norden gehen kann, will sie nicht wissen, wie weit sie nach Norden gehen kann, sondern lediglich, ob sie bis zur nächsten Kreuzung in nördlicher Richtung gehen kann (dies schließt natürlich auch Sackgassen ein). Von Punkt 1 aus bieten sich der Maus vier Richtungen an. Süden scheidet für sie zunächst aus, da sie, wie wir bereits festgelegt haben, immer unerforschte Gebiete bevorzugt. Die Maus geht nach Norden weiter. Warum eigentlich gerade nach Norden? Ganz einfach. Die Maus geht nach einem festgelegten Schema vor – N, O, S, W. Das heißt, sie versucht immer zuerst nach Norden zu gehen. Gelingt dies nicht, so versucht sie es mit Osten, dann mit Süden und mit Westen.

Entsprechend wird die endgültige Maustabelle auch definiert (Spartenreihenfolge: N-O-S-W). So gelangt die Maus schließlich zu Raum 2. Im Gedächtnis der Maus sieht es jetzt aus wie in Tabelle 2.

Bisher hat die Maus noch nie eine negative Antwort auf einen Richtungsversuch bekommen. Daher enthält die Tabelle 2 keine 2-Elemente: Woher weiß die Maus eigentlich, daß man von Raum 1 mittels »Süden« nach Raum 0 gelangt – sie hat dies doch noch gar nicht ausprobiert!!!

Unsere Maus ist nicht dumm. Sie erlaubt sich einen kleinen Kunstgriff, der sich so formulieren läßt:

Regel 1

Gelange ich mittels Befehl X (»N«) von Raum A zu Raum B, so kann ich bei logischen Systemen (Labyrinthen) voraussetzen, daß ich durch den Gegenbefehl zu X (»S«) von Raum B zu Raum A gelange.

Die Maus macht also nicht nur zu den aktuellen Vorgängen in ihr Gedächtnis Einträge, sondern gleichzeitig auch zu dem Gegenvorgang. Deshalb hat sie in der Spalte S bei Raum 1 sofort eine 0 eingetragen, nachdem sie in der N-Spalte von 0 eine 1 eingetragen hat. Der Zeiger des Gedächtnisses steht auf Raum 2 – dort, wo sich die Maus gerade befindet.

Jetzt wird's spannend. Die Maus ist in einer Sackgasse gelandet. Dies ist der Anfang vom Backtracking-Verfahren. Die Maus versucht vergeblich, eine andere Richtung als die, die sie einen Schritt zurückwirft, zu finden, denn sie will ja immer vorwärts. Enttäuscht muß sie ihr Gedächtnis mit 2 füllen. Dies verdeutlicht Tabelle 4.

Gemäß unserer Definition sind Räume mit drei 2-Elementen in einer Zeile absolute Sackgassen.

Die Maus weiß das auch und entschließt sich zu einem Rückwärtsschritt. Dazu setzt sie den Zeiger auf ihr Gedächtnis um 1 zurück. Raum 2 muß nun eliminiert (schwarz ausgemalt) werden. Das heißt, alle Wege, die zu Raum 2 führen, müssen zerstört werden. Natürlich gibt es nur einen Weg zu Raum 2, da nur ein Weg aus einer Sackgasse herausführen kann. Die Maus weiß auch ganz genau, welcher Weg dies ist. Wir definieren:

Regel 2

Wenn ein Versuchsergebnis falsch ist, dann muß ich einen Schritt zurückgehen (Backtracking). Durch den Befehl X bin ich von A nach B (in eine Sackgasse) geraten. Ich muß also zurück zu A. Dies erreiche ich durch den Gegenbefehl von X. Wenn ich wissen will, durch welchen Befehl (Richtung) ich von A nach B gelangt bin, so muß ich den Gegenbefehl zum Gegenbefehl von X bilden (Regel 3). Diesen muß ich dann aus meinem Gedächtnis löschen, um nicht noch einmal zu diesem negativen Ergebnis zu gelangen.

Regel 3

Wenn man vom Gegenbefehl eines Befehls X wiederum den Gegenbefehl bildet, so erhält man wieder den ursprünglichen Befehl X (Analogie: Bilden von Kehrwerten).

Anhand dieser drei Regeln läßt sich nahezu jeder Backtracking-Vorgang (»Aus Irrtum lernen«) beschreiben.

Aus Regel 2 weiß die Maus, daß sie den Wert 2 in Raum 2, Spalte N auf 2 setzen muß. (Tabelle 4)

Nach dem Backtracking sieht es im Gedächtnis aus wie in Tabelle 5. Die Maus steht jetzt wieder in Raum 1. Das neue Irrgartenbild entspricht Bild 7.

Wie macht die Maus nun weiter?

Nun, sie hat doch ihr N-O-S-W-Schema. Norden hat sie in Raum 1 schon ausprobiert. Also ist jetzt Osten dran. Stellt die Maus nach einem abgeschlossenen Backtracking fest, daß ihre jetzige Position wieder drei Zweien enthält, führt sie einen weiteren Backtracking aus (Vergleichen Sie das Beispiel in Bild 2, Raum X).

Sicher haben Sie bereits bemerkt, daß ich für die letzten Beispiele den Ausgang des Labyrinths als Eingang benutzt habe. Ich tat dies, um schneller in eine Sackgassensituation zu gelangen. Die Tabelle 6 zeigt, wie das Gedächtnis der Maus arbeitet, wenn die Maus vom Eingang links unten ausgehend (wie in Bild 1) ihren Weg zum Ausgang sucht (Bild 8). Das fertige Maus-Programm finden Sie in Listing 4.

Dokumentation zum Listing 4

Die restlichen Variablen sind lediglich Hilfsvariablen.

Unterprogramme:

Bedienungsanleitung zur dritten Maus

Nach dem Programmstart müssen Sie sich ein wenig gedulden, da die Maus erst ihr Gedächtnis löschen muß.

Dann werden Sie nach der Anfangsrichtung gefragt. Es ist die Richtung, die von Raum 0 (Eingang) zu Raum 1 führt. Dies ist notwendig, damit die Maus den Eingang niemals als Sackgasse interpretiert.

Sodann stellt die Maus Fragen, zum Beispiel:

»Kann ich nach Norden gehen?« Sie müssen dann »J« oder »N« antworten. Ab und zu gibt die Maus auch automatisch an, wohin sie will (um aus einer Sackgasse rauszukommen). Sie sagt dann zum Beispiel »Ich gehe nach Norden«. Durch Drücken der SPACE-Taste gibt die Maus ihren Gedächtnisstand aus – also den Weg, den sie bisher vom Eingang aus gegangen ist.

Unsere dritte Maus ist schon ziemlich schlau. Sie bemerkt es, wenn man sie beschummelt und hat auch mit dem Irrgarten von Bild 1 keinerlei Probleme. Allerdings ist ihr Gedächtnis auf 1000 Richtungen begrenzt, die sie sich merken kann.

Mit Hilfe einer relativen Datei kann dieses Gedächtnis auf bis zu 15000 Räume vergrößert werden. Sie können so eine Änderung mit ihrem bisher erworbenen Wissen leicht selbst vornehmen.

In diesem Kapitel haben Sie einige wichtige Grundlagen der Künstlichen Intelligenz kennengelernt. Ein entscheidender Faktor, der bei einem Lebewesen auf Intelligenz schließen läßt, ist das Erkennen von Fehlern und das Lernen aus Irrtümern. Ein weiterer entscheidender Faktor ist das Zurücknehmen einer Entscheidung, die sich als Fehler erwiesen hat – der Backtracking-Vorgang.

Als nächsten Kapitel schneiden wir erstmals ein ganz anderes Themengebiet der KI an: Programme, die einen menschlichen Gesprächspartner simulieren können. Zur Übung empfehle ich Ihnen an dieser Stelle jedoch erst einmal das Maus-Programm so zu verbessern, daß der Speicher der Maus als relative Datei angelegt wird. Mit Ihrem bisher erworbenen Wissen über Dateiverwaltung und relative Dateien dürfte dies nicht allzu schwierig sein.

1 rem ********************************
2 rem *   irrgaerten und maeuse iii  *
3 rem * <c> 1985 bei michael nickles *
4 rem ********************************
5 poke53280,0:poke53281,0:print"{clr}{rvon}{wht}maus iii{rvof}{down}"
10 m%=1000:dimm(m%,3):rem gedaechtnis
20 ri$(0)="norden"
22 ri$(1)="osten"
24 ri$(2)="sueden"
26 ri$(3)="westen"
30 mz=1           :rem ged. zeiger
40 fori1=0tom%    :rem gedaechtnis
42 : fori2=0to3   :rem loeschen
44 :   m(i1,i2)=-1
46 : nexti2
48 nexti1
100 print"biite geben sie die anfangsrichtung ein:
110 print"norden=1
120 print"osten =2
130 print"sueden=3
140 print"westen=4
150 geti$:ifval(i$)=0orval(i$)>3then150
160 x=val(i$)-1:goto1141
1000 rem hauptprogramm ---------------------------------------------------------
1001 :
1100 rem richtung ausprobieren
1101 :
1110 x=0            :rem 1. versuch = n
1115 :  gosub5000   :rem sackgasse ?
1120 :  ifm(mz,x)<>-1then1200
1125 :  print"kann ich nach ";ri$(x);" gehen ?";            :rem x probieren
1130 :  geti$:ifi$<>"j"andi$<>"n"andi$<>" "then1130
1131 :  ifi$=" "then10000
1135 :  ifi$="n"thenprint" nein.":m(mz,x)=-2:x=x+1:goto1115 :rem x geht nicht
1140 print" ja."    :rem x geht
1141 :  m(mz,x)=mz+1:rem richt. merken
1142 :  mz=mz+1     :rem bewegen
1144 :  ifmz>m%thenprint"habe mich verirrt - gebe auf !":end:rem memory full
1146 :    g=x:gosub6000:x=g                                 :rem gegenbefehl
1148 :    m(mz,x)=mz-1
1150 :              :rem merken
1152 :    g=x:gosub6000:x=g                                 :rem gegenbefehl
1160 :  goto1000
1200 :  ifm(mz,x)=-2thenx=x+1:goto1115                      :rem x geht nicht
1210 :  ifm(mz,x)>-1thenx=x+1:goto1115                      :rem prioritaet !!!
5000 rem feststellen ob maus in sackgasse ist (3 * -2) -------------------------
5001 :
5010 ic=0
5015 forn=0to3
5020 : ifm(mz,n)=-2thenic=ic+1
5030 nextn
5040 ific<3thenreturn
5050 ific=4thenprint"ich lasse mich nicht reinlegen !":end
5100 rem backtracking - schritt zurueck ----------------------------------------
5101 :
5110 mz=mz-1   :rem zeiger um 1 zurueck
5120 forn=0to3
5125 : m(mz+1,n)=-1                                    :rem irrweg loeschen
5130 : ifm(mz,n)<>mz+1then5140
5134 : m(mz,n)=-2                                      :rem irrweg loeschen
5136 : g=n:gosub6000
5137 : print"ich gehe nach "ri$(g)"."
5140 nextn
5145 x=0       :rem reset auf n
5147 ifmz=1thenprint"bin wieder am eingang!":poke109,0:wait198,1:run
5150 goto5000  :rem pruefen
6000 rem gegenbefehl bilden ----------------------------------------------------
6001 :
6010 : ifg=0theng=2:goto6080
6020 : ifg=1theng=3:goto6080
6030 : ifg=2theng=0:goto6080
6040 : ifg=3theng=1:goto6080
6080 return
10000 rem loesung ausgeben -----------------------------------------------------
10001 :
10010 print"{clr}durch folgende befehlsfolge gelangt man vom eingang zu meinem ";
10020 print"jetzigen standort:"
10030 fori1=0tomz-1
10040 : fori2=0to3
10045 :   ifm(i1,i2)>0andm(i1,i2)<>i1-1thenprintri$(i2)",";:i2=4
10050 : nexti2
10060 nexti1
10070 print
10080 print"soll ich weitermachen ?"
10090 geti$:ifi$<>"j"andi$<>"n"then10090
10095 ifi$="j"then1125:rem weitermachen
10099 end

  1 REM ******************************** 
  2 REM *   IRRGAERTEN UND MAEUSE III  * 
  3 REM * <C> 1985 BEI MICHAEL NICKLES * 
  4 REM ******************************** 
  5 POKE 53280,0:POKE 53281,0:PRINT"{CLR,RVSON,WHITE}MAUS III{RVOFF,DOWN}" 
 10 M%=1000:DIM M(M%,3):REM GEDAECHTNIS 
 20 RI$(0)="NORDEN" 
 22 RI$(1)="OSTEN" 
 24 RI$(2)="SUEDEN" 
 26 RI$(3)="WESTEN" 
 30 MZ=1           :REM GED. ZEIGER 
 40 FOR I1=0 TOM%    :REM GEDAECHTNIS 
 42 : FOR I2=0 TO3   :REM LOESCHEN 
 44 :   M(I1,I2)=-1 
 46 : NEXT I2 
 48 NEXT I1 
 100 PRINT"BIITE GEBEN SIE DIE ANFANGSRICHTUNG EIN: 
 110 PRINT"NORDEN=1 
 120 PRINT"OSTEN =2 
 130 PRINT"SUEDEN=3 
 140 PRINT"WESTEN=4 
 150 GET I$:IF VAL (I$)=0OR VAL (I$)>3 THEN150 
 160 X=VAL (I$)-1:GOTO 1141 
 1000 REM HAUPTPROGRAMM --------------------------------------------------------- 
 1001 : 
 1100 REM RICHTUNG AUSPROBIEREN 
 1101 : 
 1110 X=0            :REM 1. VERSUCH = N 
 1115 :  GOSUB 5000   :REM SACKGASSE ? 
 1120 :  IF M(MZ,X)<>-1 THEN1200 
 1125 :  PRINT"KANN ICH NACH ";RI$(X);" GEHEN ?";            :REM X PROBIEREN 
 1130 :  GET I$:IF I$<>"J"AND I$<>"N"AND I$<>" " THEN1130 
 1131 :  IF I$=" " THEN10000 
 1135 :  IF I$="N" THENPRINT" NEIN.":M(MZ,X)=-2:X=X+1:GOTO 1115 :REM X GEHT NICHT 
 1140 PRINT" JA."    :REM X GEHT 
 1141 :  M(MZ,X)=MZ+1:REM RICHT. MERKEN 
 1142 :  MZ=MZ+1     :REM BEWEGEN 
 1144 :  IF MZ>M% THENPRINT"HABE MICH VERIRRT - GEBE AUF !":END :REM MEMORY FULL 
 1146 :    G=X:GOSUB 6000:X=G                                 :REM GEGENBEFEHL 
 1148 :    M(MZ,X)=MZ-1 
 1150 :              :REM MERKEN 
 1152 :    G=X:GOSUB 6000:X=G                                 :REM GEGENBEFEHL 
 1160 :  GOTO 1000 
 1200 :  IF M(MZ,X)=-2 THENX=X+1:GOTO 1115                      :REM X GEHT NICHT 
 1210 :  IF M(MZ,X)>-1 THENX=X+1:GOTO 1115                      :REM PRIORITAET !!! 
 5000 REM FESTSTELLEN OB MAUS IN SACKGASSE IST (3 * -2) ------------------------- 
 5001 : 
 5010 IC=0 
 5015 FOR N=0 TO3 
 5020 : IF M(MZ,N)=-2 THENIC=IC+1 
 5030 NEXT N 
 5040 IF IC<3 THENRETURN 
 5050 IF IC=4 THENPRINT"ICH LASSE MICH NICHT REINLEGEN !":END 
 5100 REM BACKTRACKING - SCHRITT ZURUECK ---------------------------------------- 
 5101 : 
 5110 MZ=MZ-1   :REM ZEIGER UM 1 ZURUECK 
 5120 FOR N=0 TO3 
 5125 : M(MZ+1,N)=-1                                    :REM IRRWEG LOESCHEN 
 5130 : IF M(MZ,N)<>MZ+1 THEN5140 
 5134 : M(MZ,N)=-2                                      :REM IRRWEG LOESCHEN 
 5136 : G=N:GOSUB 6000 
 5137 : PRINT"ICH GEHE NACH "RI$(G)"." 
 5140 NEXT N 
 5145 X=0       :REM RESET AUF N 
 5147 IF MZ=1 THENPRINT"BIN WIEDER AM EINGANG!":POKE 109,0:WAIT 198,1:RUN 
 5150 GOTO 5000  :REM PRUEFEN 
 6000 REM GEGENBEFEHL BILDEN ---------------------------------------------------- 
 6001 : 
 6010 : IF G=0 THENG=2:GOTO 6080 
 6020 : IF G=1 THENG=3:GOTO 6080 
 6030 : IF G=2 THENG=0:GOTO 6080 
 6040 : IF G=3 THENG=1:GOTO 6080 
 6080 RETURN 
 10000 REM LOESUNG AUSGEBEN ----------------------------------------------------- 
 10001 : 
 10010 PRINT"{CLR}DURCH FOLGENDE BEFEHLSFOLGE GELANGT MAN VOM EINGANG ZU MEINEM "; 
 10020 PRINT"JETZIGEN STANDORT:" 
 10030 FOR I1=0 TOMZ-1 
 10040 : FOR I2=0 TO3 
 10045 :   IF M(I1,I2)>0AND M(I1,I2)<>I1-1 THENPRINTRI$(I2)",";:I2=4 
 10050 : NEXT I2 
 10060 NEXT I1 
 10070 PRINT 
 10080 PRINT"SOLL ICH WEITERMACHEN ?" 
 10090 GET I$:IF I$<>"J"AND I$<>"N" THEN10090 
 10095 IF I$="J" THEN1125:REM WEITERMACHEN 
 10099 END 

Eliza

HI, I AM ELIZA TELL ME YOUR PROBLEM
> I HATE SCHOOL
SAY, DO YOU HAVE ANY PSYCHOLOGICAL PROBLEMS?
>I CAN'T GET NO SATISFACTION
HOW DO YOU KNOW YOU CAN'T GET NO SATISFACTION
>I JUST DON'T HAVE ANY
WHAT DOES THAT SUGGEST TO YOU?
>I NEED GIRLS AND DRUGS AND ROCKN ROLL
I SEE
>CAN YOU GIVE ME DRUGS?
DON'T YOU BELIEVE THAT I CAN GIVE  DRUGS!
>I LIKE YOU ELIZA
WE WERE DISCUSSING YOU -- NOT ME
>BY THE WAY - MY NAME IS MIKE
NAMES DON'T INTEREST ME
>DON'T YOU LIKE MY NAME?
OH, I LIKE YOUR NAME
>YOU LIE!
YOU'RE NOT REALLY TALKING ABOUT ME, ARE YOU?
>I AM
DID YOU COME TO ME BECAUSE YOU ARE
>YOU MAKE ME SICK
WE WERE DISCUSSING YOU -- NOT ME
>MAYBE I GET SATISFACTION SOON
YOU DON'T SEEM QUITE CERTAIN
>YOU KNOW TO MUCH
OH, I KNOW TO MUCH
>YES
ARE YOU SURE?
>I HATE YOU!
I'M NOT SURE I UNDERSTAND YOU
>SHUT UP!
COME COME ELUDICATE YOUR THOUGHTS
>WHY DON'T YOU GIVE UP ASKING?
DO YOU REALLY BELIEVE I DON'T GIVE UP ASKING?
>I HOPE SO
CAN YOU ELABORATE ON THAT?
>YES
I SEE
>WHY CAN'T I GET ANY ROCKN ROLL?
DO YOU THINK YOU SHOULD BE ABLE TO GET ANY ROCKN ROLL?
>HAHAHA
THAT IS QUITE INTERESTING
>YOU ARE STUPID!
WHAT MAKES YOU THINK I AM STUPID?
>YOU GIVE ALWAYS STUPID ANSWERS
YOU'RE NOT REALLY TALKING ABOUT ME, ARE YOU?
>YOUR ANSWERS ARE ABSOLUTELY NONSENS
WHY NONSENS?
>I AM BORN TO BE WILD
HOW LONG HAVE YOU BEEN BORN TO BE WILD?
>SINCE I'VE BEEN BORN
SAY, SO YOU HAVE ANY PSYCHOLOGICAL PROBLEMS?
>CAN'T YOU RECOGNIZE THAT?
WE WERE DISCUSSING YOU -- NOT ME
>I AM NOT THE PSYCHIATRIST
DO YOU BELIEVE IT IS NORMAL TO BE NOT THE PSYCHIATRIST?
>YOU WON!
OH, I WON
>YES
I UNDERSTAND
>AHHHHHHHHHHHHHHHHH AHHHHHH AHHHHHH AHHHHHHHHH AHHHHH AHHHHHHHHH

Eliza ist ein Programm, das seine Funktionsweise am besten selbst erklärt. Deshalb habe ich zunächst auf eine Einleitung verzichtet und stattdessen einen Dialog aufgeführt, den ich erst vor kurzem mit »Eliza« hatte.

Eliza ist jetzt über 25 Jahre alt. Trotzdem ist dieses Programm auch heute noch ein vorzügliches Beispiel für die Programmierung von Sprache verstehenden KI-Programmen. Eliza wurde in den 60er Jahren von dem Computerwissenschaftler Josef Weizenbaum geschrieben. Ziel des Programms war es, einen Psychiater zu simulieren. Der Erfolg von Eliza war überwältigend – zahlreiche menschliche Gesprächspartner dachten tatsächtlich, sie hätten es mit einer denkenden, intelligenten Maschine zu tun. Noch viel erstaunlicher ist die Tatsache, daß das Eliza-Programm nur 8 KByte RAM benötigt!

Kein Wunder, denn vor 25 Jahren dachte noch niemand daran, daß es bereits 1983 Homecomputer mit 64 KByte RAM geben würde. Eliza wurde damals noch auf einem Großrechner betrieben. Erst Ende der 70er Jahre fand Eliza auch in Deutschland weite Verbreitung – auf dem PET 2001 von Commodore, einem der ersten erschwinglichen Homecomputer überhaupt. Der RAM-Speicher des PET war 8 KByte groß – groß genug für die Eliza. Auch ich begegnete Eliza 1980 auf einem PET 2001 bei einem Freund. Heute ist der PET längst Nostalgie. Kaufen kann man ihn nicht mehr und wer ihn hat, gibt ihn einfach nicht mehr her. Zuerst wurde er vom ersten Farb-Homecomputer VC 20 in die Ecke gedrängt, um schließlich vom C 64 endgültig überrollt zu werden. Mit ihm geriet auch ein berühmtes Programm in Vergessenheit – die bereits oben erwähnte Eliza. Auch meine alten PET-Programmkassetten verstaubten schnell in ihren Hüllen, als ich meinen C 64 mit atemberaubenden Action-Games hatte. Erst vor einem halben Jahr fand ich Eliza wieder. Eliza ist eines der ganz wenigen Programme, die auf wirklich allen Commodore-Computern mit 8 KByte laufen. Ich speicherte die Eliza also einfach auf Disk, um sie bei Gelegenheit einigen Freunden auf dem C 64 vorzustellen. Das Resultat war verblüffend: Das Eliza-Programm hat auch heute nichts an Originalität eingebüßt. Nach wie vor versetzt es in Erstaunen und spätestens dann in eine gewisse Ehrfurcht, wenn man hört, wie kurz der Programmcode ist.

Josef Weizenbaum, der Vater von Eliza, hat später noch verbesserte Programmversionen erstellt. Eine davon wurde unter dem Namen DOCTOR bekannt.

Wer heute intelligente Adventures oder gar KI-Programme schreiben will, kommt an dem Programm Eliza nicht vorbei. Zur Einführung in die Programmierung von Programmen, die Sprache verstehen, werden wir deshalb nun zusammen einmal das Eliza-Programm analysieren. Bevor Sie sich jedoch meine nun folgende Theorie zu Gemüte führen, sollten Sie erst einmal mit der Eliza spielen. Das Listing zur Eliza finden Sie in Listing 5.

5 goto100
10 restore
20 fori=1ton:reads$:next
30 return
100 dims%(38),r%(38),n%(38)
110 n1=38:n2=12:n3=118
120 n=n1+n2+n3:gosub10
130 forx=1ton1
140 reads%(x),l:r%(x)=s%(x):n%(x)=s%(x)+l-1:next
160 print"hi, i am eliza tell me your problem
170 inputi$:i$=" "+i$+" "
200 forl=1tolen(i$)
210 ifmid$(i$,l,1)="'"theni$=left$(i$,l-1)+right$(i$,len(i$)-l):goto210
220 next
230 ifi$=p$thenprint"please don't repeat yourself":goto170
280 restore:s=0
300 fork=1ton1
305 ifs>0then340
310 readk$
320 fora=1tolen(i$)-len(k$)
325 ifmid$(i$,a,len(k$))=k$thens=k:t=a:f$=k$
330 next
340 a=0:next
365 ifs>0thenk=s:l=t:goto400
370 k=n1:goto560
400 n=n1
405 gosub10
410 c$=" "+right$(i$,len(i$)-len(f$)-l+1)
420 forx=1ton2/2:reads$,r$
440 forl=1tolen(c$)
450 ifl+len(s$)>len(c$)then510
480 ifmid$(c$,l,len(s$))<>s$then510
490 c$=left$(c$,l-1)+r$+right$(c$,len(c$)-l-len(s$)+1):l=l+len(r$)
500 goto540
510 ifl+len(r$)>len(c$)then540
520 ifmid$(c$,l,len(r$))<>r$then540
530 c$=left$(c$,l-1)+s$+right$(c$,len(c$)-l-len(r$)+1)
540 next:next
555 ifmid$(c$,2,1)=" "thenc$=right$(c $,len(c$)-1)
560 n=n1+n2
570 gosub10
580 forx=1tor%(k):readf$:nextx
590 r%(k)=r%(k)+1:ifr%(k)>n%(k)thenr%(k)=s%(k)
600 ifright$(f$,1)<>"*"thenprintf$:p$=i$:goto170
620 printleft$(f$,len(f$)-1);c$:goto170
1050 data"can you","can i","you are","youre","i dont","i feel","why dont you"
1060 data"why cant i","are you","i cant","i am","im ","you ","i want","what"
1070 data"how","who","where","when","why","name","cause","sorry","draem","hello"
1080 data"hi ","maybe"," no","your","always","think","alike","yes","friend"
1090 data"computer","eliza","money","nokeyfound"
1230 data" are "," am ","were ","was "," you "," i ","your ","my "," ive "
1235 data" youve "," im "," youre "
1330 data"don't you believe that i can*"
1340 data"perhaps you would like to be able to*"
1350 data"you want me to be able to*"
1360 data"perhaps you don't want to*","do you want to be able to*"
1365 data"what makes you think i am*","does it please you to believe i am*"
1390 data"perhaps you would like to be*"
1400 data"do you sometimes wish you were*"
1410 data"don't you really*","why don't you*","do you wish to be able to*"
1440 data"does that trouble you?","tell me more about such feelings."
1460 data"do you often feel*","do you enjoy feeling*"
1480 data"do you really believe i don't*","perhaps in good time i will*"
1500 data"do you want me to*","do you think you should be able to*"
1520 data"why can't you*","why are you interested in whether or not i am*"
1540 data"would you prefer if i where not*","perhaps in your fantasies i am*"
1560 data"how do you know you can't*","have you tried?","perhaps you can now*"
1590 data"did you come to me because you are*","how long have you been*"
1610 data"do you believe it is normal to be*","do you enjoy being*"
1630 data"we were discussing you-- not me.","oh, i*"
1650 data"you're not really talking about me, are you?"
1660 data"what would it mean to you if you got*","why do you want*"
1680 data"suppose you soon got*","what if you never got*"
1700 data"i sometimes also want*","why do you ask?"
1720 data"does that question interest you?"
1730 data"what answer would please you the most?"
1740 data"what do you think?","are such questions in your mind often?"
1760 data"what is that you really want to know?","have you asked anyone else?"
1780 data"have you asked such questions before?"
1790 data"what else comes to mind when you ask that?"
1800 data"names don't interest me.","i don't care about names-- please go on."
1820 data"is that the real reason?","don't any other reasons come to mind?"
1840 data"does that reason explain anything else"
1850 data"what other reasons might there be?","please don't apologize!"
1870 data"apologies are not necessary."
1880 data"what feelings do you have when you apologize?","don't be so defensive!"
1900 data"what does that dream suggest you?","do you dream often?"
1920 data"what persons appear in your dreams?","are you disturbed by your dreams?"
1940 data"how do you do ... plaese state your problem."
1950 data"you don't seem quite certain.","why the uncertain tone?"
1970 data"can't you be more positive?","you aren't sure?","don't you know?"
2000 data"why no*","don't say no it's always so negative","why not?"
2030 data"are you sure?","why no?","why are you concerned about my*"
2060 data"what about your own*","can't you think of a specific example?","when?"
2090 data"what are you thinking of?","really, always?"
2110 data"do you really think so?","but you are not sure you*"
2130 data"do you doubt you*","in what way?","what resemblance do you see?"
2160 data"what does the similarity suggest to you?"
2170 data"what other connections do you see?"
2180 data"could there really be some connections?","how?"
2200 data"you seem quite positive.","are you sure?","i see.","i understand."
2240 data"why do you bring up the topic of friends?","do your friends worry you?"
2260 data"do your friends pick on you?","are you sure you have any friends?"
2280 data"do you impose on your friends?"
2290 data"perhaps your love for friends worries you.","do computers worry you?"
2310 data"are you talking about me in particular?"
2320 data"are you frightened by machines?","why do you mention computers?"
2340 data"what do you think machines have to do with your problem?"
2350 data"don't you think computers can help people?"
2360 data"what is it about machines that worries you?"
2370 data"say, do you have any psychological problems?"
2380 data"what does that suggest to you","i see","i'm not sure i understand you."
2410 data"come come elucidate your thoughts","can you elaborate on that?"
2430 data"that is quite interesting.","why do you have problems with money?"
2450 data"do you think money is everything?"
2460 data"are you sure that money is the problem?"
2470 data"i think we want to talk about you, not  about me","whats about me?"
2490 data"why do you always bring up my name?"
2530 data1,3,4,2,6,4,6,4,10,4,14,3,17,3,20,2,22,3,25,3,28,4,28,4,32,3,35,5,40,9
2540 data40,9,40,9,40,9,40,9,40,9,49,2,51,4,55,4,59,4,63,1,63,1,64,5,69,5,74,2
2550 data76,4,80,3,83,7,90,3,93,6,99,7,116,3,113,3,106,7

  5 GOTO 100 
 10 RESTORE 
 20 FOR I=1 TON:READ S$:NEXT 
 30 RETURN 
 100 DIM S%(38),R%(38),N%(38) 
 110 N1=38:N2=12:N3=118 
 120 N=N1+N2+N3:GOSUB 10 
 130 FOR X=1 TON1 
 140 READ S%(X),L:R%(X)=S%(X):N%(X)=S%(X)+L-1:NEXT 
 160 PRINT"HI, I AM ELIZA TELL ME YOUR PROBLEM 
 170 INPUTI$:I$=" "+I$+" " 
 200 FOR L=1 TOLEN (I$) 
 210 IF MID$ (I$,L,1)="'" THENI$=LEFT$ (I$,L-1)+RIGHT$ (I$,LEN (I$)-L):GOTO 210 
 220 NEXT 
 230 IF I$=P$ THENPRINT"PLEASE DON'T REPEAT YOURSELF":GOTO 170 
 280 RESTORE :S=0 
 300 FOR K=1 TON1 
 305 IF S>0 THEN340 
 310 READ K$ 
 320 FOR A=1 TOLEN (I$)-LEN (K$) 
 325 IF MID$ (I$,A,LEN (K$))=K$ THENS=K:T=A:F$=K$ 
 330 NEXT 
 340 A=0:NEXT 
 365 IF S>0 THENK=S:L=T:GOTO 400 
 370 K=N1:GOTO 560 
 400 N=N1 
 405 GOSUB 10 
 410 C$=" "+RIGHT$ (I$,LEN (I$)-LEN (F$)-L+1) 
 420 FOR X=1 TON2/2:READ S$,R$ 
 440 FOR L=1 TOLEN (C$) 
 450 IF L+LEN (S$)>LEN (C$) THEN510 
 480 IF MID$ (C$,L,LEN (S$))<>S$ THEN510 
 490 C$=LEFT$ (C$,L-1)+R$+RIGHT$ (C$,LEN (C$)-L-LEN (S$)+1):L=L+LEN (R$) 
 500 GOTO 540 
 510 IF L+LEN (R$)>LEN (C$) THEN540 
 520 IF MID$ (C$,L,LEN (R$))<>R$ THEN540 
 530 C$=LEFT$ (C$,L-1)+S$+RIGHT$ (C$,LEN (C$)-L-LEN (R$)+1) 
 540 NEXT :NEXT 
 555 IF MID$ (C$,2,1)=" " THENC$=RIGHT$ (C $,LEN (C$)-1) 
 560 N=N1+N2 
 570 GOSUB 10 
 580 FOR X=1 TOR%(K):READ F$:NEXT X 
 590 R%(K)=R%(K)+1:IF R%(K)>N%(K) THENR%(K)=S%(K) 
 600 IF RIGHT$ (F$,1)<>"*" THENPRINTF$:P$=I$:GOTO 170 
 620 PRINTLEFT$ (F$,LEN (F$)-1);C$:GOTO 170 
 1050 DATA "CAN YOU","CAN I","YOU ARE","YOURE","I DONT","I FEEL","WHY DONT YOU" 
 1060 DATA "WHY CANT I","ARE YOU","I CANT","I AM","IM ","YOU ","I WANT","WHAT" 
 1070 DATA "HOW","WHO","WHERE","WHEN","WHY","NAME","CAUSE","SORRY","DRAEM","HELLO" 
 1080 DATA "HI ","MAYBE"," NO","YOUR","ALWAYS","THINK","ALIKE","YES","FRIEND" 
 1090 DATA "COMPUTER","ELIZA","MONEY","NOKEYFOUND" 
 1230 DATA " ARE "," AM ","WERE ","WAS "," YOU "," I ","YOUR ","MY "," IVE " 
 1235 DATA " YOUVE "," IM "," YOURE " 
 1330 DATA "DON'T YOU BELIEVE THAT I CAN*" 
 1340 DATA "PERHAPS YOU WOULD LIKE TO BE ABLE TO*" 
 1350 DATA "YOU WANT ME TO BE ABLE TO*" 
 1360 DATA "PERHAPS YOU DON'T WANT TO*","DO YOU WANT TO BE ABLE TO*" 
 1365 DATA "WHAT MAKES YOU THINK I AM*","DOES IT PLEASE YOU TO BELIEVE I AM*" 
 1390 DATA "PERHAPS YOU WOULD LIKE TO BE*" 
 1400 DATA "DO YOU SOMETIMES WISH YOU WERE*" 
 1410 DATA "DON'T YOU REALLY*","WHY DON'T YOU*","DO YOU WISH TO BE ABLE TO*" 
 1440 DATA "DOES THAT TROUBLE YOU?","TELL ME MORE ABOUT SUCH FEELINGS." 
 1460 DATA "DO YOU OFTEN FEEL*","DO YOU ENJOY FEELING*" 
 1480 DATA "DO YOU REALLY BELIEVE I DON'T*","PERHAPS IN GOOD TIME I WILL*" 
 1500 DATA "DO YOU WANT ME TO*","DO YOU THINK YOU SHOULD BE ABLE TO*" 
 1520 DATA "WHY CAN'T YOU*","WHY ARE YOU INTERESTED IN WHETHER OR NOT I AM*" 
 1540 DATA "WOULD YOU PREFER IF I WHERE NOT*","PERHAPS IN YOUR FANTASIES I AM*" 
 1560 DATA "HOW DO YOU KNOW YOU CAN'T*","HAVE YOU TRIED?","PERHAPS YOU CAN NOW*" 
 1590 DATA "DID YOU COME TO ME BECAUSE YOU ARE*","HOW LONG HAVE YOU BEEN*" 
 1610 DATA "DO YOU BELIEVE IT IS NORMAL TO BE*","DO YOU ENJOY BEING*" 
 1630 DATA "WE WERE DISCUSSING YOU-- NOT ME.","OH, I*" 
 1650 DATA "YOU'RE NOT REALLY TALKING ABOUT ME, ARE YOU?" 
 1660 DATA "WHAT WOULD IT MEAN TO YOU IF YOU GOT*","WHY DO YOU WANT*" 
 1680 DATA "SUPPOSE YOU SOON GOT*","WHAT IF YOU NEVER GOT*" 
 1700 DATA "I SOMETIMES ALSO WANT*","WHY DO YOU ASK?" 
 1720 DATA "DOES THAT QUESTION INTEREST YOU?" 
 1730 DATA "WHAT ANSWER WOULD PLEASE YOU THE MOST?" 
 1740 DATA "WHAT DO YOU THINK?","ARE SUCH QUESTIONS IN YOUR MIND OFTEN?" 
 1760 DATA "WHAT IS THAT YOU REALLY WANT TO KNOW?","HAVE YOU ASKED ANYONE ELSE?" 
 1780 DATA "HAVE YOU ASKED SUCH QUESTIONS BEFORE?" 
 1790 DATA "WHAT ELSE COMES TO MIND WHEN YOU ASK THAT?" 
 1800 DATA "NAMES DON'T INTEREST ME.","I DON'T CARE ABOUT NAMES-- PLEASE GO ON." 
 1820 DATA "IS THAT THE REAL REASON?","DON'T ANY OTHER REASONS COME TO MIND?" 
 1840 DATA "DOES THAT REASON EXPLAIN ANYTHING ELSE" 
 1850 DATA "WHAT OTHER REASONS MIGHT THERE BE?","PLEASE DON'T APOLOGIZE!" 
 1870 DATA "APOLOGIES ARE NOT NECESSARY." 
 1880 DATA "WHAT FEELINGS DO YOU HAVE WHEN YOU APOLOGIZE?","DON'T BE SO DEFENSIVE!" 
 1900 DATA "WHAT DOES THAT DREAM SUGGEST YOU?","DO YOU DREAM OFTEN?" 
 1920 DATA "WHAT PERSONS APPEAR IN YOUR DREAMS?","ARE YOU DISTURBED BY YOUR DREAMS?" 
 1940 DATA "HOW DO YOU DO ... PLAESE STATE YOUR PROBLEM." 
 1950 DATA "YOU DON'T SEEM QUITE CERTAIN.","WHY THE UNCERTAIN TONE?" 
 1970 DATA "CAN'T YOU BE MORE POSITIVE?","YOU AREN'T SURE?","DON'T YOU KNOW?" 
 2000 DATA "WHY NO*","DON'T SAY NO IT'S ALWAYS SO NEGATIVE","WHY NOT?" 
 2030 DATA "ARE YOU SURE?","WHY NO?","WHY ARE YOU CONCERNED ABOUT MY*" 
 2060 DATA "WHAT ABOUT YOUR OWN*","CAN'T YOU THINK OF A SPECIFIC EXAMPLE?","WHEN?" 
 2090 DATA "WHAT ARE YOU THINKING OF?","REALLY, ALWAYS?" 
 2110 DATA "DO YOU REALLY THINK SO?","BUT YOU ARE NOT SURE YOU*" 
 2130 DATA "DO YOU DOUBT YOU*","IN WHAT WAY?","WHAT RESEMBLANCE DO YOU SEE?" 
 2160 DATA "WHAT DOES THE SIMILARITY SUGGEST TO YOU?" 
 2170 DATA "WHAT OTHER CONNECTIONS DO YOU SEE?" 
 2180 DATA "COULD THERE REALLY BE SOME CONNECTIONS?","HOW?" 
 2200 DATA "YOU SEEM QUITE POSITIVE.","ARE YOU SURE?","I SEE.","I UNDERSTAND." 
 2240 DATA "WHY DO YOU BRING UP THE TOPIC OF FRIENDS?","DO YOUR FRIENDS WORRY YOU?" 
 2260 DATA "DO YOUR FRIENDS PICK ON YOU?","ARE YOU SURE YOU HAVE ANY FRIENDS?" 
 2280 DATA "DO YOU IMPOSE ON YOUR FRIENDS?" 
 2290 DATA "PERHAPS YOUR LOVE FOR FRIENDS WORRIES YOU.","DO COMPUTERS WORRY YOU?" 
 2310 DATA "ARE YOU TALKING ABOUT ME IN PARTICULAR?" 
 2320 DATA "ARE YOU FRIGHTENED BY MACHINES?","WHY DO YOU MENTION COMPUTERS?" 
 2340 DATA "WHAT DO YOU THINK MACHINES HAVE TO DO WITH YOUR PROBLEM?" 
 2350 DATA "DON'T YOU THINK COMPUTERS CAN HELP PEOPLE?" 
 2360 DATA "WHAT IS IT ABOUT MACHINES THAT WORRIES YOU?" 
 2370 DATA "SAY, DO YOU HAVE ANY PSYCHOLOGICAL PROBLEMS?" 
 2380 DATA "WHAT DOES THAT SUGGEST TO YOU","I SEE","I'M NOT SURE I UNDERSTAND YOU." 
 2410 DATA "COME COME ELUCIDATE YOUR THOUGHTS","CAN YOU ELABORATE ON THAT?" 
 2430 DATA "THAT IS QUITE INTERESTING.","WHY DO YOU HAVE PROBLEMS WITH MONEY?" 
 2450 DATA "DO YOU THINK MONEY IS EVERYTHING?" 
 2460 DATA "ARE YOU SURE THAT MONEY IS THE PROBLEM?" 
 2470 DATA "I THINK WE WANT TO TALK ABOUT YOU, NOT{2SPACE}ABOUT ME","WHATS ABOUT ME?" 
 2490 DATA "WHY DO YOU ALWAYS BRING UP MY NAME?" 
 2530 DATA 1,3,4,2,6,4,6,4,10,4,14,3,17,3,20,2,22,3,25,3,28,4,28,4,32,3,35,5,40,9 
 2540 DATA 40,9,40,9,40,9,40,9,40,9,49,2,51,4,55,4,59,4,63,1,63,1,64,5,69,5,74,2 
 2550 DATA 76,4,80,3,83,7,90,3,93,6,99,7,116,3,113,3,106,7 

Zum Programmablauf läßt sich nicht viel sagen. Einfach RUN eingeben und Sie haben einen garantiert außergewöhnlich geduldigen Gesprächspartner vor sich. Gute Unterhaltung!

Wenn Sie sich nun eine Weile mit dem Eliza-Programm »unterhalten« haben, haben Sie sicherlich festgestellt, daß nicht selten relativ unsinnige Antworten zustandekommen. Daß im Programm nicht viel Intelligenz stecken kann, sieht man schon am Listing: Das Hauptprogramm besteht aus nur zirka 50 Zeilen, der restliche Teil aus DATA-Zeilen. In der Tat, Eliza hat keine Ahnung von dem Gesprächsinhalt der Dialoge, die sie führt. Der Eliza-Effekt, wie wir es einmal nennen wollen, besteht also darin, aus eingegebenen Sätzen und Antworten neue Fragen zu formulieren. Daß Eliza Antwort gibt, ohne nachzudenken und darauf verzichtet, die Antwort auf Sinngehalt zu untersuchen, zeigt sich dann, wenn man anstelle von einfachen Sätzen wirre Zeichenfolgen eingibt.

Ich muß an dieser Stelle zugeben, daß der Beispielsdialog, den ich zur Einleitung dieses Kursabschnitts gezeigt habe, nur deshalb relativ intelligent erscheint, weil ich durch gewählte Antworten (unter Kenntnis, wie Eliza arbeitet), vermeiden konnte, daß Eliza unsinnige Antworten gibt.

Geben Sie nach Programmstart doch bitte einmal den folgenden Satz ein:

»CAN YOU X«

Eliza antwortet mit »DON'T YOU BELIEVE I CAN DO X«.

Nach dem Schlüsselbegriff CAN YOU hat Eliza also einfach den Satzrest X abgeschnitten und an einen ihrer Standardsätze angehängt. Hätte man als ersten Satz
»CAN YOU DANCE« eingegeben, so hätte Eliza mit »DON'T YOU BELIEVE THAT I CAN DANCE« geantwortet. Geben wir jetzt nochmals »CAN YOU X« ein. Eliza antwortet jetzt mit:
»PERHAPS YOU WOULD LIKE TO BE ABLE TO X«. Beim dritten gleichen Versuch antwortet Eliza schließlich mit »YOU WANT ME TO BE ABLE TO X«. Gibt man zum viertenmal »CAN YOU X« ein, so erhält man wieder die erste Antwort. Eliza hat also nur eine begrenzte Anzahl von Antworten und Fragen zu bestimmten Schlüsselwörtern parat.

Eliza ist also eigentlich gar kein KI-Programm, sondern lediglich eine einfache Gesprächs-Simulation. Trotzdem will ich das Programm ausführlich besprechen, denn es läßt sich vieles aus ihm herausholen. Es bietet sich zum Beispiel sehr an, eine eliza-artige Routine in ein Text-Adventure einzubauen. Man könnte die Schlüsselwörter von Eliza speziell auf das Adventure abrechnen. Der Spieler könnte dann einen richtigen Dialog mit dem Computer führen, der in etwa so aussehen könnte:

Und so kann es noch lange weitergehen.

Dies sieht momentan natürlich wieder viel intelligenter aus, als es in Wirklichkeit ist. Auf jeden Fall bietet es sich an, das Eliza-Programm einmal genau unter die Lupe zu nehmen, um das Prinzip zu verstehen, das hinter dem Bilden der Antworten steht: Die wichtigsten Infomationen werden der vorausgegangenen Frage entnommen. Alle Gesprächspartner-Simulationsprogramme bauen irgendwie auf dem Eliza-Prinzip auf. Es ist also unbedingt erforderlich, die Programmierung der Eliza zu verstehen, wenn man eigene Simulationsprogramme dieser Art schreiben will. Wie gesagt, das Eliza-Programm benötigt lediglich 8 KByte RAM. Das heißt, uns stehen noch 30 KByte Basic-RAM zur Verfügung. Nehmen wir alle 64 KByte RAM und bedienen uns auch noch einer relativen Datei auf Disk, so können wir Programme entwickeln, die den »IQ« der Eliza um ein Hundertfaches übersteigen.

Eliza unter der Lupe

Das Eliza-Listing läßt sich in zwei große Hauptabschnitte unterteilen:

Dem Steuerprogramm (Zeile 5 bis 620) und DATA-Zeilen (Zeile 1050 bis 2250).

Programmieranfänger sehen im Steuerprogramm lediglich ein Wirrwarr von Stringoperationen. Man muß schon ziemlich genau hinschauen, um zu erkennen, was sich in den einzelnen Zeilen des Steuerprogramms abspielt. Lassen Sie uns dies jetzt einmal gemeinsam tun:

Eliza: Dokumentation zum Listing

Die gesamte Datei läßt sich in 3 Bereiche gliedern:

Beispiel: Aus »I'M HUNGRY« wird »IM HUNGRY«. Dies ist notwendig, um später I AM und IM gleichsetzen zu können. Im Prinzip ist dieses Kürzen nicht unbedingt notwendig, da in der Schlüsselwort-Tabelle I AM und I'M aufgeführt werden.

Nun haben wir auch schon das komplette Programm Eliza dokumentiert. Ich weiß, daß es für einen Anfänger schwierig ist, das Programmkonzept der Eliza komplett zu verstehen. Meine Dokumentation kann Ihnen nur helfen; verstehen werden Sie das Programm jedoch erst dann, wenn Sie es eigenständig Schritt für Schritt durcharbeiten.

Im folgenden möchte ich das Eliza-Konzept noch einmal mit ganz einfachen Worten zusammenfassen:

Der Eliza-Effekt

Der Eliza-Effekt besteht darin, aus einer Antwort eine neue Frage zu formulieren.

Eliza untersucht eingegebene Sätze auf Schlüsselwörter hin. Nehmen wir einmal an, jemand gibt als Antwortsatz »I HATE SCHOOL« ein. Eliza macht sich nun keineswegs die Mühe, den ganzen Satz in einzelne Wörter zu zerlegen – wie ich es zum Beispiel im ersten Adventure-Sonderheft gemacht habe.

Eliza beruft sich vielmehr zunächst auf die Tabelle der Schlüsselwörter. Zunächst nimmt sie das erste Wort der Tabelle (CAN YOU) als Schlüsselwort beziehungsweise Vergleichsstring K$. Nun wird der gesamte Befehlsstring I$ durchsucht.

FORI=1 TO LEN(I$)
: IF MID$(IS,I,LEN(K$))=K$ THEN REM GEFUNDEN
NEXTI

Das Suchen erfolgt also einfach durch Durchlaufen des gesamten Befehlsstrings und Vergleichen mit dem Schlüsselwort K$. Dieser Suchalgorithmus ist sehr primitiv; es gibt einen viel besseren, den ich Ihnen später noch kurz vorstellen werde.

Aus dem Listing können wir lesen, daß Eliza bei dem Befehlsstring »I HATE SCHOLL« mit Sicherheit kein Schlüsselwort finden wird. Daher wird Eliza zu »I HATE SCHOOL« auch keine geistreichen Bemerkungen geben können. Sie bringt eine Ausweichfrage – sie weicht also einfach auf ein anderes Thema aus (wie wir es auch tun, wenn wir nicht mehr weiter wissen). Nach einer erfolglosen Schlüsselwortsuche steht der Tabellenzeiger auf Satz 38 (NOKEYFOUND). Der letzte Satz der Schlüsselworttabelle ist somit immer der Hinweiser auf die Ausweichfragen (zum Beispiel SAY DO YOU HAVE ANY PSYCHOLOGICAL PROBLEMS) oder Verlegenheitsantworten (I SEE).

Aus dem Listing können wir erkennen, wo die Ausweichsätze stehen: S%(38) zeigt auf den Beginn und N%(38) auf das Ende beziehungsweise den letzten der Verlegenheitssätze. R%(38) ist, wie bereits dokumentiert, der Zeiger auf den Ausweichbereich. Er wird immer dann um 1 erhöht (auch zurückgestellt wenn größer als N%), wenn Eliza auf den Ausweichbereich zugegriffen hat. Eliza kennt genau 7 Ausweichsätze, die in den Sätzen 106 bis 113 des Bildes 1 stehen. Das heißt, Eliza wiederholt sich bei jeder 7. Ausweichantwort. Von der Größe der einzelnen Bereiche, also dem Antwortenreichtum eines Eliza-Programms, hängt es ab, wie schnell die eigentliche »Dummheit des Programmes« vom Spieler erkannt wird.

Hat Eliza beim ersten Durchlauf also kein Schlüsselwort gefunden, so bricht sie alle weiteren »Berechnungen« ab und antwortet sofort mit einer Verlegenheitsantwort oder stellt eine Ausweichfrage. Dies kann man mit einem Adventure-Parser vergleichen, der abbricht, wenn er ein Wort nicht kennt – ICH KENNE DAS WORT X NICHT.

Lassen Sie uns jetzt jedoch einmal von einem interessanten Befehlssatz ausgehen. Unter Befehlssatz verstehe ich alle Arten von Sätzen, die ein Spieler beziehungsweise Anwender auf einen INPUT-Befehl hin eingibt. So zum Beispiel »YOU APPEAR IN MY DREAMS«. Eliza findet nun das Schlüsselwort »YOU« – Satz 13 in Bereich 2. Anhand des Listings können wir herausfinden, daß Eliza mit »We were discussing you - not me« antworten muß. Sicher haben Sie bereits bemerkt, daß im Listing manche Sätze mit einem Sternchen enden und andere wiederum nicht. Sätze, die nicht mit einem Sternchen enden, werden direkt ausgegeben, also so wie sie im Listing stehen. Der Antwortsatz »WE WERE DISCUSSING YOU - NOT ME« steht dort an Stelle 32 und hat am Ende kein Sternchen. Wie wir bereits wissen, steht der YOU-Zeiger jetzt auf Satz 33. Bei der nächsten Satzeingabe muß also als Antwort Satz 33 kommen – wenn im Befehlssatz wieder das Schlüsselwort YOU gefunden wird. Probieren wir dies doch einfach einmal aus. Nach Eingabe von »YOU APPEAR IN MY NIGHTMARES« folgt in der Tat die Antwort »OH, I APPEAR IN YOUR NIGHTMARES«. Der Satz lautet jedoch nur »OH, I« und ist mit einem Sternchen versehen. Bei der Antwort wurde zu Satz 33 also »APPEAR IN YOUR NIGHTMARES« zugefügt. Vergleichen wir nun einmal Eingabe und Ausgabe:

Eingabe: YOU APPEAR IN MY NIGHTMARES

Ausgabe: OH, I APPEAR IN YOUR NIGHTMARES

Hier sieht man ganz deutlich, was passiert ist. Eliza hat vom Eingabesatz den Satzbereich nach dem Schlüsselwort YOU abgetrennt und anschließend an den Ausgabesatz 33 OH, I angefügt. Dieser abgetrennte Bereich taucht im Programm als C$ auf. Bevor C$ jedoch an Satz 33 angefügt wurde, veränderte sich noch etwas: Gemäß Bereich 2 wurde das Wort MY durch YOUR ersetzt.

Damit ist der Eliza-Effekt auch schon beschrieben.

Mit dem jetzt erworbenen Wissen sollte es Ihnen nicht mehr allzu schwer fallen, das Eliza-Programm selbst unter die Lupe zu nehmen.

Die Eliza-Methoden sind zwar sehr simpel, zeigen bei einer Analyse des Programms jedoch ganz einleuchtend, wie man Probleme der Sprachverarbeitung, zum Beispiel Grundlagen der Stringprogrammierung oder der Zerlegungsverfahren für Zeichenketten, angehen kann.

Das Zufallsprinzip – programmierter Zufall

Künstliche Intelligenz ist das, was der Mensch besser kann. So lautet eine der vielen Definitionen, die im Laufe der letzten Zeit entworfen wurden – Versuche, zu beschreiben, was künstliche Intelligenz eigentlich überhaupt ist. Wie ist die obige Definition zu interpretieren? Am besten läßt sie sich wohl so erklären: Stellen wir uns doch einmal einen Arbeiter in einer Farbrik vor. Er hat eine bestimmte vorgegebene Aufgabe, die er an einer Maschine verrichtet. Die Aufgabe könnte zum Beispiel darin bestehen, Werkzeugteile, die auf Fließband A ankommen, auf Fließband B umzuladen. Der Arbeiter steht also zwischen den Fließbändern A und B und verrichtet seine Arbeit. Viel nachzudenken braucht er nicht, um die Aufgabe richtig zu erfüllen – er kennt den Handgriff genau, der notwendig ist: Das Werkzeugteil von Band A nehmen und auf Band B legen. Dieser Handgriff wiederholt sich wieder und wieder. Der Arbeiter ist also gewissermaßen auf eine Tätigkeit programmiert. Stellen wir uns nun einmal einen Roboter, oder genauer gesagt einen Roboterarm vor, der die gleiche Arbeit verrichtet. Auch er hat bei korrekter Programmierung keine Probleme beim Erfüllen des Auftrags. Der Arbeiter hat dem Roboter gegenüber einen gewaltigen Vorteil. Er ist in der Lage, darüber nachzudenken, was er gerade tut. Vielleicht überlegt er, ob er für seine monotone Arbeit ausreichend Lohn erhält. Wenn ihm die Arbeit schließlich zu dumm wird, wenn er »keinen Bock« mehr hat, so kann er die Arbeit hinwerfen, wobei er sich sogar klar darüber ist, welche Folgen das für ihn haben kann. Unser Arbeiter kann aus dem System aussteigen – er kann aus seiner aufgetragenen Funktion ausbrechen, aus seiner Programmierung aussteigen. Vom Roboter ist eine solche Reaktion niemals zu erwarten – er arbeitet solange weiter, bis ein mechanischer Defekt auftritt oder bis man ihm eine neue Aufgabe gibt. Wer also Programme schreiben will, die möglichst realistisch menschliches Verhalten oder sogar Intelligenz simulieren sollen, der darf diesen Faktor des aus-dem-System-aussteigen-könnens nicht vernachlässigen. Und hier stellt sich die Frage, wie man nun ein solches Aussteigen aus dem System programmieren kann. Am einfachsten wäre es mit einem Basic-Befehl wie:

IF KEIN BOCK MEHR THEN MACH, WAS DU WILLST.

Einen solchen Befehl gibt es jedoch nicht, und es wird ihn höchstwahrscheinlich auch niemals geben. Es gibt jedoch eine andere Lösung...

Schließlich geht es uns ja nur um eine realistische Simulation menschlichen Verhaltens: Sehen wir doch einmal Bild 9 an.

Jeder hat dieses Black-Box-Schema bestimmt schon einmal in irgendeinem Schullehrbuch gesehen. Die Begriffe »Eingabe« und »Ausgabe« sind sehr allgemein zu verstehen. Eine Eingabe kann zum Beispiel eine Zahl, ein Satz oder gar eine ganze Tabelle sein, die zur Bearbeitung eingegeben wird. Was passiert aber nun mit der Eingabe, und wie kommt es zu einer bestimmten Ausgabe? Hierfür steht die Black-Box, das ist der Kasten mit dem Fragezeichen. Am besten läßt sich diese Frage anhand von Bild 10 beantworten: Dieses Struktogramm ist typisch für ein Programm, das menschliches Verhalten simulieren soll.

Auf den ersten Blick ist gleich festzustellen, daß es zur Bearbeitung einer Eingabe nur zwei Möglichkeiten gibt. Entweder geht das Programm logisch vor, das heißt, das Programm berechnet die Ausgabe, die als Antwort auf eine bestimmte Frage am logischsten zu sein scheint. Hier wird zum Beispiel der bestmögliche Zug bei einer Schachstellung berechnet. Oder das Programm geht unlogisch vor. Hier gibt das Programm eine Antwort vor, die unabhängig von der Eingabe berechnet wird.

Nehmen wir an, wir unterhalten uns mit einem Programm, zum Beispiel mit ELIZA, und dabei entsteht folgender Dialog:

Mensch: Ich habe Angst vor großen Hunden.

Computer: Finden Sie nicht auch, daß das Wetter heute besonders schlecht ist?

Unter die zweite Kategorie fallen jedoch nur solche Antworten, die wirklich absolut zufällig entstanden sind. Gibt nämlich ELIZA eine Verlegenheitsantwort, weil sie im Eingabesatz kein Schlüsselwort findet, so zählt dies als logisches Vorgehen! Am interessantesten in Bild 10 ist die Formel, mit der ermittelt wird, ob die Antwort auf eine Eingabe zufällig oder per Berechnung folgerichtig erfolgt.

Hierzu dient eine einfache RND-Funktion, mit der eine Zufallszahl erzeugt wird, die im Bereich zwischen 1 und 100 liegt:

X=INT(100*RND(1))+1

In der Variablen ZU wird angegeben, wie groß der Zufallsanteil in der »Black-Box« ist.

Nehmen wir einmal an, der Zufallsanteil beträgt 0 Prozent. Es soll also jede Eingabe logisch beantwortet werden

INT(100*RND(1))+1

ist aber immer größer als 0! So wird also immer die linke Spalte angewählt. Hat die Variable ZU hingegen den Wert 100 Prozent, so wird

INT(100*RND(1))+1

immer kleiner als 100 – die Antwort wird immer zufälliger ermittelt. Mittels dieser Zufallsformel ist es also möglich, das Logik/Zufalls-Verhältnis genau festzulegen.

Das folgende Schülerprogramm (Listing 6) arbeitet nach diesem Prinzip. Es wird ein Schüler simuliert, der nach dem kleinen Einmaleins abgefragt wird. Der Computer stellt die Aufgaben automatisch – man muß nach jeder Antwort einfach eine Taste drücken. Zu Beginn des Programms läßt sich ein Wert für ZU, nämlich der Intelligenzgrad des Schülers, eingeben. Je kleiner der Intelligenzanteil (also je größer ZU ist), um so öfter gibt der Schüler eine falsche Antwort.

10 rem ********************************
11 rem *   schueler - simulation      *
12 rem * <c> 1986 bei michael nickles *
13 rem ********************************
100 print"{clr}{yel}{rvon}schueler-simulation{rvof}"
110 input"{down}{down}zufallsanteil";zu
120 ifzu<0orzu>100then110
130 print"{down}{down}logiganteil  :"100-zu"%"
140 print"{down}zufallsanteil:"zu"%"
150 print"{down}{down}{down}bitte eine taste druecken!":poke198,0:wait198,1
1000 rem aufgabe stellen -------------------------------------------------------
1001 :
1010 a=int(10*rnd(1))+1
1020 b=int(10*rnd(1))+1
1030 print"wieviel ist"a"*"b"?   ";
2000 rem antwort des schuelers -------------------------------------------------
2001 :
2010 x=int(100*rnd(1))+1
2020 ifx>zu then2100:rem logische antwort
2030 ifx<=zuthen2200:rem zufallsantwort
2100 rem richtige antwort ----------
2101 :
2110 c=a*b
2120 printc
2130 poke198,0:wait198,1:goto1000
2200 rem zufallsantwort ------------
2201 :
2210 c=int(100*rnd(1))+1
2220 printc
2230 poke198,0:wait198,1:goto1000

 10 REM ******************************** 
 11 REM *   SCHUELER - SIMULATION      * 
 12 REM * <C> 1986 BEI MICHAEL NICKLES * 
 13 REM ******************************** 
 100 PRINT"{CLR,YELLOW,RVSON}SCHUELER-SIMULATION{RVOFF}" 
 110 INPUT"{2DOWN}ZUFALLSANTEIL";ZU 
 120 IF ZU<0OR ZU>100 THEN110 
 130 PRINT"{2DOWN}LOGIGANTEIL{2SPACE}:"100-ZU"%" 
 140 PRINT"{DOWN}ZUFALLSANTEIL:"ZU"%" 
 150 PRINT"{3DOWN}BITTE EINE TASTE DRUECKEN!":POKE 198,0:WAIT 198,1 
 1000 REM AUFGABE STELLEN ------------------------------------------------------- 
 1001 : 
 1010 A=INT (10*RND (1))+1 
 1020 B=INT (10*RND (1))+1 
 1030 PRINT"WIEVIEL IST"A"*"B"?{3SPACE}"; 
 2000 REM ANTWORT DES SCHUELERS ------------------------------------------------- 
 2001 : 
 2010 X=INT (100*RND (1))+1 
 2020 IF X>ZU  THEN2100:REM LOGISCHE ANTWORT 
 2030 IF X<=ZU THEN2200:REM ZUFALLSANTWORT 
 2100 REM RICHTIGE ANTWORT ---------- 
 2101 : 
 2110 C=A*B 
 2120 PRINTC 
 2130 POKE 198,0:WAIT 198,1:GOTO 1000 
 2200 REM ZUFALLSANTWORT ------------ 
 2201 : 
 2210 C=INT (100*RND (1))+1 
 2220 PRINTC 
 2230 POKE 198,0:WAIT 198,1:GOTO 1000 

Probieren Sie nach Eingabe des Programmes einmal verschiedene ZU-Werte aus.

Es läßt sich mit diesem Programm jede Art von Schüler simulieren – vom Dummkopf bis zur Intelligenzbestie.

Für das Programmieren von Schüler-Simulationen lassen sich folgende Regeln festlegen:

1. Regel: Kein Mensch ist perfekt. Also darf auch eine Simulation niemals vom perfekten Menschen ausgehen. Es ist also falsch, bei der obigen Schülersimulation dem Zufall 0 Prozent Anteil zuzuordnen. Dann wäre der Schüler nämlich hundertprozentig irrtumsfrei. Lassen Sie deshalb auch zur Simulation einer Intelligenzbestie den Zufallsanteil mindestens 1 betragen!

2. Regel: Gehen wir nun noch mal davon aus, daß ein extrem intelligenter Schüler simuliert werden soll. Die erste Regel besagt ja, daß ZU hier mindestens 1 betragen soll. Dies hat zur Folge, daß der Schüler in 99 Prozent der Fälle eine richtige Antwort gibt. Tritt jedoch das eine Prozent ZU in Kraft, so kann es zu einer absolut idiotischen Antwort kommen, wie zum Beispiel 1 mal 1 = 78. Sehr gute Schüler können sich schon mal irren, jedoch nicht derartig extrem. Auch eine falsche Antwort soll bei einer Extrem-guter-Schüler-Simulation deshalb niemals den Eindruck von Dummheit, sondern vielmehr den Eindruck eines Irrtums, also einer versehentlich falschen Antwort erwecken. Man muß also für diesen 1-Prozent-Fall im Programm eine falsche Antwort vorsehen, die nur geringfügig vom richtigen Ergebnis abweicht. Man kann zum Beispiel die Zeile 2210 so abändern:

2210 C=A*B: C=C+ INT(6*RND(1))--3

Jetzt liegen auch falsche Antworten in der Nähe der richtigen.

3. Regel: ZU darf nicht konstant sein. Wird ein Schüler sehr lange abgefragt, so treten irgendwann Ermüdungserscheinungen auf – die Leistungsfähigkeit geht zurück, ZU nimmt zu.

Die drei Regeln sind äußerst simpel. Sie können bei bestimmten Grenzfällen auch kombiniert werden.

Noch viel anschaulicher wird die Bedeutung des programmierten Zufalls beim Pacman-Algorithmus:

Jeder kennt das Labyrinth in Bild 11, das Zuhaus von Pacman und seinen Gegnern, den vier Gespenstern. Pacman war das erste Videospiel, das von Pong und Space Invader Schema abwich. Die meisten von uns haben sie miterlebt, die Pacman-Welle, die zirka 1979 über die ganze Video-Spielwelt schwappte. In der Tat, Pacman war das erste Videospiel, dessen Programmierung »intelligente« Rechenalgorithmen erforderte. Im Gegensatz zur primitiven Links-rechts-Bewegung der Space Invader war es hier erforderlich, vier Gespenster (mehr oder weniger intelligent) durch ein Labyrinth laufen zu lassen; und das mit dem Ziel, den Pacman des Spielers zu fangen. Von kaum einem anderen Videospiel gab es soviele Programmversionen wie von Pacman: Pac man, Munchy, Puckman, MS. Pacman und Side Pacman, um nur einige von ihnen zu nennen. Viele haben bestimmt auch schon einmal versucht, eine eigene Pacman-Version (sei es auch nur in Basic) zu programmieren. Das ist gar nicht so leicht! Sind die Gespenster zu intelligent, so hat der Spieler kaum eine Chance. Sind sie aber dumm, dann gewinnt der Spieler problemlos, und das Spiel verliert seinen Reiz. Intelligenz (Logik, Berechnung) und Dummheit (Zufallsbewegung) der Gespenster müssen richtig miteinander abgestimmt sein, um einen Spielwitz zu schaffen.

Das Logik-Zufalls-Verhältnis bleibt beim Pacman-Algorithmus übrigens auch bei steigendem Level konstant. Gelangt der Spieler in die nächste Spielrunde, so wird einfach die gesamte Ablaufgeschwindigkeit des Programmes gesteigert. Der Spieler muß dann schneller reagieren und hat weniger Zeit zum Nachdenken – er empfindet die neue Spielrunde schwerer als die zuvor bewältigte. Wie sieht der Algorithmus für ein solches Spiel aus? Lassen Sie uns zunächst davon ausgehen, daß das Gespenst absolut logisch vorgeht. Und das geht so: Das Gespenst bewegt sich zu Beginn des Spiels in einem beliebigen Gang des Labyrinths in eine beliebige Richtung. Es bewegt sich solange in diese Richtung, bis es an eine Abzweigung gelangt. Dann »überlegt« es sich, welche mögliche Richtung am ehesten zum Spieler führt. In dem Fall, der in Bild 12 vorliegt, würde sich das Gespenst für die Richtung SÜDEN (nach unten) entscheiden.

Verhalten sich alle Gespenster gemäß diesem Schema, so hätte der Spieler, wie bereits gesagt, keine Chance. Wir müssen also den Zufall ins Spiel bringen. Dieser Zufall sorgt dann dafür, daß sich ein Gespenst bei einer Wegrichtung nicht immer logisch verhält und den Weg in Richtung Spieler nimmt, sondern daß es ab und zu auch einen willkürlich gewählten Weg nimmt und diesen solange geht, bis es wieder an eine Kreuzung gelangt. Das folgende Programm in Listing 7 simuliert ein Pacman-Spiel mit einem Gespenst. Der Pacman wir mit einem Joystick in Port 2 gesteuert, die Variable ZU wird zu Beginn des Spiels eingegeben. In dem Spiel Pacman gibt es normalerweise vier Gespenster: Inky, Blinky, Winky und Dinky. In unserem Beispiel programmieren wir erst mal nur ein Gespenst, weil das Basic-Programm sonst viel zu langsam wird.

Probieren Sie bitte auch hier wieder verschiedene ZU-Werte aus. Sie werden schnell feststellen, daß es gar nicht einfach ist, den optimalen ZU-Wert zu finden. Trotzdem kann man auf den Zufallsfaktor in KI-Simulationen und Spielen nicht verzichten, wie es die beiden Beispiele gezeigt haben. Soweit ist ja wohl alles klar. Aber eine Anmerkung möchte ich zum Schluß noch machen: Bei ELIZA gibt es keinen Zufallsfaktor. ELIZA ist jedoch auch keine extrem gute Simulation. Ein Zufallsfaktor ließe sich in das Programm aber leicht einbauen und würde es mit Sicherheit noch verbessern.

0 rem ********************************
1 rem *     pac-man ki-programm      *
2 rem * <c> 1985 bei michael nickles *
3 rem ********************************
4 poke53280,0:poke53281,0:print"{clr}";
10 print"{clr}{yel}{rvon}taktik / zufall experiment{rvof}"
20 print"{down}wie gross soll der zufallsanteil sein
30 inputzu
40 ifzu<0orzu>100then10
50 print"{down}{down}zufall:"zu"%"
60 print"{down}{down}taktik:"100-zu"%"
70 print"{down}{down}{down}bitte eine taste druecken!"
80 poke198,0:wait198,1
99 gosub10000
100 x=17:y=16:xx=1024+x+y*40:xp=peek(xx):pokexx,42
110 gg=1361:gp=peek(gg):pokegg,160:gw=-1
1000 rem steuerung spielfigur --------------------------------------------------
1001 :
1010 jo=56320
1020 ifpeek(jo)=126thenwy=-1:wx=0
1030 ifpeek(jo)=125thenwy=1 :wx=0
1040 ifpeek(jo)=123thenwy=0 :wx=-1
1050 ifpeek(jo)=119thenwy=0 :wx=1
1100 pokexx,xp
1110 x=x+wx:y=y+wy
1120 xx=1024+x+40*y
1130 xp=peek(xx)
1140 ifxp=102thenx=x-wx:y=y-wy:goto1120
1150 ifx=-1andy=10thenx=33:y=10:goto1120
1160 ifx=34andy=10thenx=0:y=10:goto1120
1200 xp=peek(xx)
1210 pokexx,42
2000 rem steuerung gespenster --------------------------------------------------
2001 :
2032 ifgw<>40thenifpeek(gg-40)=32orpeek(gg-40)=96then2100
2034 ifgw<>-40thenifpeek(gg+40)=32orpeek(gg+40)=96then2100
2035 ifgw<>1thenifpeek(gg-1)=32orpeek(gg-1)=96then2100
2037 ifgw<>-1thenifpeek(gg+1)=32orpeek(gg+1)=96then2100
2040 pokegg,gp:gg=gg+gw
2042 ifgg=1459thengg=1424:gw=1 :rem tunnel
2043 ifgg=1423thengg=1458:gw=-1:rem tunnel
2045 ifgg=xxthenpoke53280,1:end
2050 ifpeek(gg)<>32thengg=gg-gw:goto2100
2070 gp=peek(gg):pokegg,160
2080 goto1000
2100 rem neue richtung waehlen -------------------------------------------------
2101 :pokegg,gp
2110 rem welche richtungen sind moeglich
2120 rz=0:fori=0to3:ri(i)=0:nexti
2130 ifgw<>40thenifpeek(gg-40)=96orpeek(gg-40)=32thenri(rz)=-40:rz=rz+1
2140 ifgw<>-40thenifpeek(gg+40)=96orpeek(gg+40)=32thenri(rz)=+40:rz=rz+1
2150 ifgw<>1thenifpeek(gg-1)=96 orpeek(gg-1)=32 thenri(rz)=-1 :rz=rz+1
2160 ifgw<>-1thenifpeek(gg+1)=96 orpeek(gg+1)=32 thenri(rz)=+1 :rz=rz+1
2200 rem wahl des besten zuges -------------------------------------------------
2201 :
2205 rem  fori=1to4:print" ";ri(i);:next:pokegg,87:printpeek(gg+40):wait198,1
2210 gy=int((gg-1024)/40)
2220 gx=gg-1024-gy*40
2230 fori=0torz
2235 : ifgx=xthen2255
2240 : ifri(i)=1andgx<x    thengw=1
2250 : ifri(i)=-1andgx>x   thengw=-1
2255 : ifgy=ythen2280
2260 : ifri(i)=40andgy<y   thengw=40
2270 : ifri(i)=-40andgy>y  thengw=-40
2280 nexti
2300 rem zufalls-element -------------------------------------------------------
2301 :
2310 if int(100*rnd(1))+1>zuthen2400
2320 rem zufallszug
2330 gw=ri(int(rz)*rnd(1))
2400 rem ausfuehren des zuges --------------------------------------------------
2401 :
2404 gg=gg+gw
2405 ifgg=1459thengg=1424:gw=1 :rem tunnel
2406 ifgg=1423thengg=1458:gw=-1:rem tunnel
2410 ifgg=xxthenpoke53280,1:end
2420 gp=peek(gg):pokegg,160
2430 goto1000
10000 rem up-spielfeld zeichnen ------------------------------------------------
10001 :
10010 print"{clr}{lblu}";
10020 data"{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}"
10025 data"{CBM-+}                {CBM-+}                {CBM-+}"
10030 data"{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}"
10035 data"{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}"
10040 data"{CBM-+}                                 {CBM-+}"
10045 data"{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}"
10050 data"{CBM-+}       {CBM-+} {CBM-+}      {CBM-+}      {CBM-+} {CBM-+}       {CBM-+}"
10055 data"{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}"
10060 data"      {CBM-+} {CBM-+} {CBM-+}             {CBM-+} {CBM-+} {CBM-+}      "
10065 data"{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{$a0}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{$a0}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}"
10070 data"            {CBM-+}{yel}supermike{lblu}{CBM-+}            "
10075 data"{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{$a0}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{$a0}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}"
10080 data"      {CBM-+} {CBM-+} {CBM-+}{$a0}{$a0}{$a0}{$a0}{$a0}{$a0}{$a0}{$a0}{$a0}{$a0}{$a0}{$a0}{$a0}{CBM-+} {CBM-+} {CBM-+}      "
10085 data"{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{$a0}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{$a0}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}"
10090 data"{CBM-+}                {CBM-+}                {CBM-+}"
10095 data"{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}"
10100 data"{CBM-+}     {CBM-+}                     {CBM-+}     {CBM-+}"
10105 data"{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+} {CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}{CBM-+}{CBM-+} {CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}"
10110 data"{CBM-+}       {CBM-+} {CBM-+}      {CBM-+}      {CBM-+} {CBM-+}       {CBM-+}"
10115 data"{CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+} {CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+} {CBM-+}"
10120 data"{CBM-+}                                 {CBM-+}"
10125 data"{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}{CBM-+}"
10130 restore
10140 fori=1to22:readi$:printi$:next
10150 return

  0 REM ******************************** 
  1 REM *     PAC-MAN KI-PROGRAMM      * 
  2 REM * <C> 1985 BEI MICHAEL NICKLES * 
  3 REM ******************************** 
  4 POKE 53280,0:POKE 53281,0:PRINT"{CLR}"; 
 10 PRINT"{CLR,YELLOW,RVSON}TAKTIK / ZUFALL EXPERIMENT{RVOFF}" 
 20 PRINT"{DOWN}WIE GROSS SOLL DER ZUFALLSANTEIL SEIN 
 30 INPUTZU 
 40 IF ZU<0OR ZU>100 THEN10 
 50 PRINT"{2DOWN}ZUFALL:"ZU"%" 
 60 PRINT"{2DOWN}TAKTIK:"100-ZU"%" 
 70 PRINT"{3DOWN}BITTE EINE TASTE DRUECKEN!" 
 80 POKE 198,0:WAIT 198,1 
 99 GOSUB 10000 
 100 X=17:Y=16:XX=1024+X+Y*40:XP=PEEK (XX):POKE XX,42 
 110 GG=1361:GP=PEEK (GG):POKE GG,160:GW=-1 
 1000 REM STEUERUNG SPIELFIGUR -------------------------------------------------- 
 1001 : 
 1010 JO=56320 
 1020 IF PEEK (JO)=126 THENWY=-1:WX=0 
 1030 IF PEEK (JO)=125 THENWY=1 :WX=0 
 1040 IF PEEK (JO)=123 THENWY=0 :WX=-1 
 1050 IF PEEK (JO)=119 THENWY=0 :WX=1 
 1100 POKE XX,XP 
 1110 X=X+WX:Y=Y+WY 
 1120 XX=1024+X+40*Y 
 1130 XP=PEEK (XX) 
 1140 IF XP=102 THENX=X-WX:Y=Y-WY:GOTO 1120 
 1150 IF X=-1AND Y=10 THENX=33:Y=10:GOTO 1120 
 1160 IF X=34AND Y=10 THENX=0:Y=10:GOTO 1120 
 1200 XP=PEEK (XX) 
 1210 POKE XX,42 
 2000 REM STEUERUNG GESPENSTER -------------------------------------------------- 
 2001 : 
 2032 IF GW<>40 THENIF PEEK (GG-40)=32OR PEEK (GG-40)=96 THEN2100 
 2034 IF GW<>-40 THENIF PEEK (GG+40)=32OR PEEK (GG+40)=96 THEN2100 
 2035 IF GW<>1 THENIF PEEK (GG-1)=32OR PEEK (GG-1)=96 THEN2100 
 2037 IF GW<>-1 THENIF PEEK (GG+1)=32OR PEEK (GG+1)=96 THEN2100 
 2040 POKE GG,GP:GG=GG+GW 
 2042 IF GG=1459 THENGG=1424:GW=1 :REM TUNNEL 
 2043 IF GG=1423 THENGG=1458:GW=-1:REM TUNNEL 
 2045 IF GG=XX THENPOKE 53280,1:END 
 2050 IF PEEK (GG)<>32 THENGG=GG-GW:GOTO 2100 
 2070 GP=PEEK (GG):POKE GG,160 
 2080 GOTO 1000 
 2100 REM NEUE RICHTUNG WAEHLEN ------------------------------------------------- 
 2101 :POKE GG,GP 
 2110 REM WELCHE RICHTUNGEN SIND MOEGLICH 
 2120 RZ=0:FOR I=0 TO3:RI(I)=0:NEXT I 
 2130 IF GW<>40 THENIF PEEK (GG-40)=96OR PEEK (GG-40)=32 THENRI(RZ)=-40:RZ=RZ+1 
 2140 IF GW<>-40 THENIF PEEK (GG+40)=96OR PEEK (GG+40)=32 THENRI(RZ)=+40:RZ=RZ+1 
 2150 IF GW<>1 THENIF PEEK (GG-1)=96 OR PEEK (GG-1)=32  THENRI(RZ)=-1 :RZ=RZ+1 
 2160 IF GW<>-1 THENIF PEEK (GG+1)=96 OR PEEK (GG+1)=32  THENRI(RZ)=+1 :RZ=RZ+1 
 2200 REM WAHL DES BESTEN ZUGES ------------------------------------------------- 
 2201 : 
 2205 REM  FORI=1TO4:PRINT" ";RI(I);:NEXT:POKEGG,87:PRINTPEEK(GG+40):WAIT198,1 
 2210 GY=INT ((GG-1024)/40) 
 2220 GX=GG-1024-GY*40 
 2230 FOR I=0 TORZ 
 2235 : IF GX=X THEN2255 
 2240 : IF RI(I)=1AND GX<X     THENGW=1 
 2250 : IF RI(I)=-1AND GX>X    THENGW=-1 
 2255 : IF GY=Y THEN2280 
 2260 : IF RI(I)=40AND GY<Y    THENGW=40 
 2270 : IF RI(I)=-40AND GY>Y   THENGW=-40 
 2280 NEXT I 
 2300 REM ZUFALLS-ELEMENT ------------------------------------------------------- 
 2301 : 
 2310 IF INT (100*RND (1))+1>ZU THEN2400 
 2320 REM ZUFALLSZUG 
 2330 GW=RI(INT (RZ)*RND (1)) 
 2400 REM AUSFUEHREN DES ZUGES -------------------------------------------------- 
 2401 : 
 2404 GG=GG+GW 
 2405 IF GG=1459 THENGG=1424:GW=1 :REM TUNNEL 
 2406 IF GG=1423 THENGG=1458:GW=-1:REM TUNNEL 
 2410 IF GG=XX THENPOKE 53280,1:END 
 2420 GP=PEEK (GG):POKE GG,160 
 2430 GOTO 1000 
 10000 REM UP-SPIELFELD ZEICHNEN ------------------------------------------------ 
 10001 : 
 10010 PRINT"{CLR,LIG.BLUE}"; 
 10020 DATA "+++++++++++++++++++++++++++++++++++" 
 10025 DATA "+{16SPACE}+{16SPACE}+" 
 10030 DATA "+ +++++ ++++++++ + ++++++++ +++++ +" 
 10035 DATA "+ +++++ ++++++++ + ++++++++ +++++ +" 
 10040 DATA "+{33SPACE}+" 
 10045 DATA "+ +++++ +++ +++++++++++ +++ +++++ +" 
 10050 DATA "+{7SPACE}+ +{6SPACE}+{6SPACE}+ +{7SPACE}+" 
 10055 DATA "+++++++ + ++++++ + ++++++ + +++++++" 
 10060 DATA "{6SPACE}+ + +{13SPACE}+ + +{6SPACE}" 
 10065 DATA "+++++++ +++{SHIFT-SPACE}+++++++++++{SHIFT-SPACE}+++ +++++++" 
 10070 DATA "{12SPACE}+{YELLOW}SUPERMIKE{LIG.BLUE}+{SPACE,11SPACE}" 
 10075 DATA "+++++++ +++{SHIFT-SPACE}+++++++++++{SHIFT-SPACE}+++ +++++++" 
 10080 DATA "{6SPACE}+ + +{13SHIFT-SPACE}+ + +{6SPACE}" 
 10085 DATA "+++++++ +++{SHIFT-SPACE}+++++++++++{SHIFT-SPACE}+++ +++++++" 
 10090 DATA "+{16SPACE}+{16SPACE}+" 
 10095 DATA "+ +++++ ++++++++ + ++++++++ +++++ +" 
 10100 DATA "+{5SPACE}+{21SPACE}+{5SPACE}+" 
 10105 DATA "+++++ + +++ +++++++++++ +++ + +++++" 
 10110 DATA "+{7SPACE}+ +{6SPACE}+{6SPACE}+ +{7SPACE}+" 
 10115 DATA "+ ++++++++++++++ + ++++++++++++++ +" 
 10120 DATA "+{33SPACE}+" 
 10125 DATA "+++++++++++++++++++++++++++++++++++" 
 10130 RESTORE 
 10140 FOR I=1 TO22:READ I$:PRINTI$:NEXT 
 10150 RETURN