# 6. Kapitel: Der Computer lernt

Wie in der letzten Folge deutlich wurde, fällt es schwer, einem Programm Intelligenz zuzusprechen, dessen Vorgehensweise man vollständig durchschaut hat. Zwar spielt das Kalaha-Programm clever genug, um in den höheren Spielstufen den meisten Menschen überlegen zu sein, doch zu offensichtlich wird die Rolle des Computers als elektronischer Knecht, der nur eine Folge vorgegebener Anweisungen ausführt. Jeder Taschenrechner kann schließlich besser mit Zahlen umgehen als ein Mensch, ohne deshalb als intelligent zu gelten.

Was unseren bisherigen Programmbeispielen fehlte, war die Fähigkeit zu wirklich eigenständigen geistigen Leistungen, die sogar für den Programmierer zu überraschenden Ergebnissen führen. Zwar erwecken manche Programme besonders in der Entwicklungsphase durchaus den Eindruck, als ob sie über eine gehörige Portion Eigenleben verfügen, doch im allgemeinen ist das mehr auf die Unvollkommenheit des Programmierers als auf maschinelle Intelligenz zurückzuführen. Ein gründliches Debugging bereitet diesen ersten Anzeichen einer Roboterrebellion meist ein schnelles Ende.

Was dem Normalprogrammierer ein Greuel ist - nämlich ein Programm, das in Eigeninitiative Speicherinhalte oder sogar sich selbst verändert - gilt dagegen im Bereich der künstlichen Intelligenz als erstrebenswertes Ziel. Lernfähigkeit heißt das Thema, das nach wie vor für die KI-Forscher eine große Herausforderung darstellt, und das nicht nur aus wissenschaftlichem Ehrgeiz. Lernende Programme könnten z.B. erheblich dazu beitragen, die enormen Kosten der Softwareentwicklung und -installation zu senken, indem sie sich selbständig an unterschiedliche Anforderungen der Anwender anpassen. Der Programmierer stände damit nicht mehr vor dem Dilemma, entweder ein hochspezialisiertes Programm zu schreiben, das vielleicht nur für eine einzige Anwendung zu gebrauchen ist, oder aber ein vielseitiges Programm, das jedoch sehr kompliziert und unhandlich wird.

Trotz dieser attraktiven Aussichten ist die Realisierung solcher Systeme noch nicht besonders weit fortgeschritten. Auch wenn teilweise schon recht überzeugende Demonstrationen lernfähiger Programme existieren (z.B. elektronische Ratten, die von selbst den Weg durch ein Labyrinth finden), so sind die Anwendungsgebiete jedoch meistens noch zu akademisch, um eine praktische Bedeutung zu gewinnen. Weiterhin brauchen viele dieser Experimentalprogramme teure Großrechenanlagen, um effektiv zu arbeiten, und auch eine gewisse psychologische Hemmschwelle sollte man nicht unterschätzen: Maschinen, die über vorgegebene Anweisungen hinaus Eigeninitiative entwickeln, haben schon etwas Unheimliches an sich. Zahlreiche schaurige Visionen in Science Fiction-Romanen geben einen deutlichen Hinweis auf die bei vielen Menschen vorhandenen Ängste.

Untersucht man jedoch die verschiedenen Voraussetzungen, die ein Programm erfüllen muß, um zumindest annähernd eine Lernfähigkeit im menschlichen Sinne zu realisieren, so macht sich schnell Ernüchterung breit. Zu kompliziert ist die Palette der menschlichen Wahrnehmungs- und Verarbeitungsmöglichkeiten, um sie einfach auf eine Maschine übertragen zu können, und nach dem heutigen Stand der Technik sind selbständig denkende machthungrige Roboter nach wie vor in den Bereich der Fiktion zu verweisen. Viel realistischer ist dagegen die Bedrohung, die von einem simplen Programmfehler in einem militärischen Abwehrsystem ausgehen kann!

## Minischach: Klein, aber oho!

Um die Möglichkeiten und Probleme maschineller Lernfähigkeit zu untersuchen, dient uns in dieser Folge ein Mini-Schachspiel, das extra zu diesem Zweck erfunden wurde. Das Spielgeschehen findet auf einem 4x4-Brett statt, auf dem zu Beginn wie im Bild ersichtlich acht Bauern aufgestellt werden.

Wie bei dem großen Original gehen sie jeweils einen Schritt geradeaus in Vorwärtsrichtung; eine andere Figur schlagen können sie nur diagonal. Sobald ein Bauer die letzte Reihe erreicht, verwandelt er sich in eine Dame, die sich in alle Richtungen beliebig weit bewegen kann. Um die Zugmöglichkeiten und damit auch den Speicherbedarf unseres lernfähigen System nicht unnötig auszuweiten, wurde allerdings ein Schlagzwang für die Damen eingeführt: Sie müssen also eine andere Figur schlagen, falls sie können. Verloren hat ein Spieler, wenn er nicht mehr ziehen kann, weil er keine Figuren mehr besitzt, oder seine Bauern alle blockiert sind. Die Partie gilt als remis, wenn vier Züge lang (zwei auf jeder Seite) kein Bauer bewegt und keine Figur geschlagen wurde.

Zu Beginn fragt das Programm, ob bereits eine Datei auf Datenträger mit den Ergebnissen vorangegangener Partien existiert. Falls ja, so wird sie geladen, anderenfalls führt der Rechner sofort seinen ersten Zug aus. Daß er die Partie immer beginnen darf, hat übrigens seinen guten Grund: In einer früheren Testversion spielte das Programm als Nachziehender nur mit den schwarzen Steinen und sorgte dabei - wie es sich für ein lernfähiges Programm gehört - gleich für eine große Überraschung. Nachdem es eine erhebliche Anzahl saftiger Niederlagen eingesteckt hatte, behauptete es plötzlich bereits nach meinem ersten Zug 'Ich habe verloren' und wollte um keinen Preis weiterspielen. Nicht etwa, daß mein CPC jetzt beleidigt war. Er hatte nur entdeckt, daß der Anziehende das Spiel bei optimaler Strategie auf jeden Fall gewinnt! Also wurde der Spieß umgedreht, und in der vorliegenden Version muß das Programm beweisen, daß es diesen Gewinnweg selbständig herausfinden kann.

Doch jetzt zur weiteren Bedienung: Sie können einen Zug eingeben, indem Sie den Cursor zunächst zur gewünschten Figur steuern und <ENTER> oder <COPY> drücken. Begeben Sie sich dann mit dem Cursor zu dem Zielfeld; ein zweiter Druck auf die <ENTER>- oder <COPY>-Taste führt den Zug aus. Illegale Züge werden nicht akzeptiert, das Programm reagiert in diesem Fall nur mit einem Warnton. Beachten Sie, daß kein Bauernzug möglich ist, wenn Ihre Dame eine gegnerische Figur schlagen kann! Wenn Sie nach dem Partieende die Frage 'Noch ein Spiel' mit <N> beantworten, so schreibt das Programm alle bislang vorliegenden Erkenntnisse unter dem Namen MSCHACH.DAT auf Datenträger und wird danach beendet.

## Schwer von Begriff?

Nach den ersten Partien gegen das Minischach-Programm scheint diese Frage wirklich einige Berechtigung zu haben. Munter verliert es bei konsequentem Gegenspiel eine Partie nach der anderen, ohne dabei bemerkenswerte Fortschritte zu machen, und der Fachmann ahnt bereits, was hier abläuft: Die Zugauswahl erfolgt rein zufällig. Bei genauer Beobachtung kann man allerdings feststellen, daß das Programm nie zweimal auf die gleiche Weise verliert. Früher oder später wird es auch zu Situationen kommen, in denen das Programm aufgibt, bevor es endgültig mattgesetzt wird; es erkennt den unvermeidlichen Verlust bereits im voraus.

Diese Lerneffekte werden um so deutlicher, je konsequenter Sie bestimmte Varianten bevorzugen (soweit es der Zufallsgenerator zuläßt). Ergänzend sei hier weiterhin bemerkt, daß das Programm seine Erfahrungen auch auf spiegelbildliche (d.h. an der vertikalen Mittelachse gespiegelte) Situationen anwenden kann. Trotzdem läßt es sich nicht verheimlichen, daß es im Vergleich zum Menschen nervtötend langsam lernt. Daß eine Verlustpartie grundsätzlich nicht wiederholt wird, gibt natürlich etwas Hoffnung: Früher oder später muß sich die Spielstärke dabei ja verbessern, es fragt sich nur, nach wieviel Partien.

Im weiteren Verlauf dieses Kapitels wird noch eine Programmänderung besprochen werden, die Ihnen einen großen Teil der Lehrtätigkeit abnimmt. Bevor wir dazu kommen, soll jedoch genau erläutert werden, wie das Programm überhaupt funktioniert, welche Ursachen seine geistige Trägheit hat und was beim Menschen anders läuft. Zu diesem Zweck beginnen wir mit der internen Darstellung des Spielbretts, die sehr einfach ist: Es handelt sich um ein Array namens b(sp,re), in dem folgende Werte stehen können:

-1 0 1 2 3 4 | Randfeld außerhalb leer weißer Bauer weiße Dame schwarzer Bauer schwarze Dame

Anstatt des eigentlich nur notwendigen 4x4-Arrays wird also ein 6x6-Feld mit Umrandung benutzt, die bei der Untersuchung der Zugmöglichkeiten sehr hilfreich ist, wie sich noch zeigen wird. Werfen wir jetzt einen Blick auf das Minischach-Listing, das Sie sich auf dem Drucker oder Bildschirm ausgeben lassen sollten, um die weiteren Erläuterungen verfolgen zu können. Die Aufgabe des Initialisierungsteils ist im wesentlichen nur die Dimensionierung verschiedener Felder und die Vorbereitung der Grafikelemente. Nach dem Spielstart ab Zeile 450 wird zunächst der Zugzähler zz und der Remiszähler rz (er überwacht die Einhaltung der Remisregel!) mit 0 initialisiert und das Spielbrett b(x,y) mit der Anfangsverteilung belegt.

GOSUB 1250 sorgt für die Bildschirmausgabe, und die Zuweisung spieler=1 bestimmt, daß der Rechner immer beginnt. Falls Sie anfangen wollen, muß hier spieler=2 stehen. Die sich aus dieser Spielversion ergebenden Dateien sollten allerdings separat geführt werden, da sonst auf lange Sicht ein Memory full droht. Der eigentliche Spielablauf wird in den Zeilen 600-670 kontrolliert, indem abwechselnd die Unterprogramme Zug Computer und Zug Gegner aufgerufen werden. Nach Abschluß der Partie enthält die Variable erg das Spielergebnis; in Abhängigkeit von diesem Wert schließt sich eine Auswertung an, zu der wir noch kommen. Zunächst werden wir etwas tiefer in die Datenstrukturen des Programms eindringen.

## Gepackte Daten: Dicht an dicht

Eines ist klar: Wer etwas lernen will, braucht ein gutes Gedächtnis, und wie man weiß, hat der Mensch deren sogar zwei: Ein Kurzzeit- und ein Langzeitgedächtnis. Diese Trennung ermöglicht es, selektiv zu lernen, d.h. nur wirklich wichtige Daten werden nach einer Auswertung langfristig bereitgehalten. Gerade bei einem Microcomputer mit begrenztem Speicherplatz ist es außerordentlich ratsam, dieses Verfahren zu kopieren; doch zunächst müssen wir klären, welche Daten überhaupt für eine Speicherung in Frage kommen.

Als erstes kommen z.B. die verschiedenen Spielsituationen in Betracht, die im Laufe der Partien auftreten. Schließlich soll sich das Programm ja merken, in welchen Positionen es durch welche Züge gewonnen bzw. verloren hat. Damit deuten sich aber auch schon die ersten Speicherplatzsorgen an: Ein 4x4-Integerarray zur Darstellung des Brettes benötigt insgesamt 16x2=32 Bytes, das macht bei 1000 verschiedenen Positionen fast 32 KByte aus, und die kommen bei Minischach locker zusammen! Wie man sieht, empfiehlt es sich, bei speicherintensiven Problemen solche Überlegungen vor der Programmerstellung durchzuführen, um vor unangenehmen Überraschungen sicher zu sein.

Was also tun? Eine hilfreiche Technik ist das sogenannte Packen der Daten, bei der eine Kodierung gesucht wird, die möglichst wenig Speicherplatz erfordert. Intuitiv ist klar, daß eine Integervariable, die Zahlenwerte von -32768 bis 32767 darstellen kann, mit einem Bereich von 0 bis 3 glatt unterfordert ist: Hier stehen insgesamt 16 Bit (mit Vorzeichen) zur Verfügung, die noch wesentlich mehr Informationen aufnehmen können. Da unser Spielfeld genau 16 Felder umfaßt, bietet es sich an, zunächst einmal bitweise zu verschlüsseln, welche von ihnen belegt (Bit gesetzt) oder leer sind (Bit zurückgesetzt). Die Startposition sieht dann zeilenweise gelesen so aus:

psn1 = 1111 0000 0000 1111

Doch das allein reicht natürlich nicht. Zusätzlich muß notiert werden, um welche Figuren es sich handelt. Auf dem Spielbrett sind den verschiedenen Figurenarten die Ziffern von 1 bis 4 zugeordnet; subtrahiert man hier den Wert 1, so ergibt sich ein Bereich von 0 bis 3, für dessen Darstellung man nur zwei Bit braucht:

Figur | dez. | bin.
--- | --- | ---
1 (weißer Bauer) 2 (weiße Dame) 3 (schwarzer Bauer) 4 (schwarze Dame) | 0 1 2 3 | 00 01 10 11

Damit können wir die Figuren (ohne Berücksichtigung der Leerfelder) einfach in der Reihenfolge aufzählen, in der sie von links oben nach rechts unten auftreten. Da sich mit Sicherheit nie mehr als acht Steine auf dem Brett tummeln, kommen wir auch hier mit 16 Bit aus, die für die Startposition so aussehen:

psn2 = 00 00 00 00 10 10 10 10

Wie man sich anhand weiterer Beispiele vor Augen führen kann, ist die gesamte Spielsituation durch diese beiden 16-Bit-Werte eindeutig erfaßt. Obwohl wir für die Darstellung jetzt nur noch 4 anstatt 32 Bytes benötigen (also 2 Integervariablen), gehen keine Informationen verloren! Der einzige Nachteil liegt mitunter darin, daß bei einer Neubearbeitung gepackter Daten diese erst wieder dekodiert werden müssen, was natürlich etwas Zeit kostet.

Die praktische Realisierung des Packens zeigen die Programmzeilen 1400 - 1520 im Rahmen des Unterprogramms Zug Computer. Damit es mit dem Vorzeichenbit keinen Arger gibt, werden die gepackten Daten zunächst in Realvariablen (p1! und p2!) aufgenommen. Anschließend sorgt dann die UNT-Funktion für eine Umwandlung in vorzeichenbehaftete Integerwerte (psn1 und psn2). Wie Sie dem Listing entnehmen können, wird die ganze Prozedur danach noch einmal wiederholt, und zwar mit rückwärts laufendem Spaltenindex, wodurch die kodierte Form des gespiegelten Bretts entsteht (psx1 und psx2).

Im weiteren Verlauf tritt ein kleines Maschinenprogramm in Aktion, dem neben den eben besprochenen Variablen noch die Startadressen zweier Arrays übergeben werden, die einen wichtigen Bestandteil des Langzeitgedächtnisses bilden: In l.psn1(i) und l.psn2(i) (das kleine l steht für Langzeit) merkt sich das Programm alle entscheidenden Situationen vorangegangener Partien in kodierter Form. Die Assemblerroutine schaut praktisch nur nach, ob die aktuelle Brettposition dort schon verzeichnet ist. Ist das der Fall, so wird in Zeile 1570 die Variable flag auf -1 gesetzt; i enthält dann die Nummer, unter der die Position vermerkt ist. Xflag wird gesetzt, falls die spiegelbildliche Positiion gefunden wurde.

Damit erfüllt unser Programm bereits eine wesentliche Voraussetzung für Lernfähigkeit: Es kann sich erinnern. Doch die Erkenntnis, daß eine Spielsituation schon einmal da war, hilft bei der Zugauswahl natürlich nicht weiter. Es fehlt ein Hinweis darauf, welche Züge sich an dieser Stelle bereits als günstig oder ungünstig erwiesen haben.

## Der Zuggenerator

Viele Programm für strategische Brettspiele enthalten einen sogenannten Zuggenerator. Dieser Programmteil hat die Aufgabe, eine Liste aller legalen Züge anzufertigen, aus der das Hauptprogramm dann seine Auswahl trifft. Weiterhin können Zuglisten für die Überprüfung von Eingaben benutzt werden: Ist ein Zug nicht in der Liste enthalten, so ist er illegal und wird zurückgewiesen.

Auch unser Minischach-Programm enthält einen solchen Regelexperten, der gleich noch genauer zur Sprache kommt. Zunächst stellt sich aber wieder die Frage nach einer günstigen Datenstruktur für die Darstellung der Zuglisten. Wenn Sie noch einmal einen Blick auf die Darstellung des Schachbrettes werfen, können Sie sich sofort klarmachen, daß ein Zug vollständig durch vier Zahlen von 1 bis 4 charakterisiert ist: Von (Spalte,Reihe) nach (Spalte,Reihe). In dem Programm sind übrigens grundsätzlich die Startkoordinaten in den Variablen sp,re und die Zielkoordinaten in x,y enthalten.

Wer die vorangegangenen Ausführungen über das Packen von Daten aufmerksam verfolgt hat, kann sich hier leicht ausrechnen, daß zur Speicherung dieser vier Zahlen 4x2=8 Bits (d.h. 1 Byte) vollkommen ausreichen; wir erhalten also pro gepacktem Zug einen Wert von 0 bis 255. Und jetzt ein besonderer Trick: Dieser Wert kann ohne weiteres mit Hilfe der CHR$-Funktion in ein ASCII-Zeichen verwandelt werden, so daß wir die Zugliste als String darstellen können! Dem Unterprogramm ab Zeile 2570 können Sie entnehmen, wie dieser Vorgang in der Praxis aussieht.

Die Verarbeitung der Zugliste als String bietet einige handfeste Vorteile. So weist Z.B. ein Leerstring sofort darauf hin, daß ein Spieler verloren hat, da er keinen Zug mehr ausführen kann. Weiterhin läßt sich mit Hilfe der INSTR-Funktion außerordentlich bequem feststellen, ob ein Zug in der Liste enthalten und damit legal ist. Auch Manipulationen durch MID$ und ähnliche Funktionen sind möglich, um z.B. als schlecht erkannte Züge aus einer Liste zu streichen.

Den einzigen Nachteil dieser Methode werden besonders CPC 464-Besitzer bei vollem Speicher mitunter erleben, wenn der Rechner eine Garbage Collection durchführt, um seine Strings mitsamt unseren Zuglisten aufzuräumen: Er stellt zu diesem Zweck alle laufenden Aktivitäten ein und ist während der Zeit auch nicht weiter ansprechbar. Die Stringverwaltung des 664/6128 wurde in dieser Hinsicht verbessert, braucht dafür aber auch zwei zusätzliche Bytes Speicherplatz pro Stringvariable.

Doch jetzt, wie versprochen, ein genauerer Blick auf den Zuggenerator ab Zeile 2060. Zu Beginn wird hier eine Variable seite definiert, die das Erstellen der Zuglisten sowohl für die weißen als auch für die schwarzen Steine ermöglicht, in Abhängigkeit davon, wer gerade am Zug ist. Danach wird das Spielfeld auf Damen hin abgetastet, und, soweit welche vorhanden sind, ein Unterprogramm aufgerufen, das eventuell mögliche Schlagzüge in die Zugliste schreibt - sie sind ja verpflichtend! Deshalb geht es auch gleich zurück (RETURN), falls die Zugliste nach dieser Prozedur nicht mehr leer ist. Anderenfalls wird das Spielfeld noch einmal durchgecheckt, um Bauernzüge und nicht-schlagende Damenzüge zu registrieren.

Die drei Unterprogramme ab Zeile 2220 erkunden die verschiedenen Bewegungsmöglichkeiten der Figuren. Für die Ermittlung der Damenzüge sind insbesondere zwei bereits im Initialisierungsteil erzeugte Arrays dx(ri) und dy(ri) nützlich; sie enthalten für alle acht Bewegungsrichtungen einen sogenannten Richtungsoffset, der fortlaufend zu den Koordinaten der Startposition addiert wird, bis ein Hindernis (z.B. der mit -1 belegte Rand) der Zugstraße eine Ende setzt. Wer Minischach mit veränderten Spielregeln probieren möchte, kann hier folgende Änderungen vornehmen:

    FOR ri = 0 TO 3: 'verwandelt die Damen in Türme

oder

    FOR ri = 4 TO 7: 'verwandelt die Damen in Läufer.

## Reduzierte Zuglisten

Kehren wir jetzt zu dem Modul Zug Computer zurück. Was passiert hier ab Zeile 1590, nachdem unser Programm mit Hilfe des Maschinenprogramms versucht hat, sich zu erinnern? Falls die aktuelle Position noch nicht im Langzeitgedächnis enthalten ist, so wird der eben besprochene Zuggenerator aufgerufen, um die dazugehörige Zugliste zu ermitteln. Andernfalls wird eine bereits fertige Zugliste l.zliste$(i) benutzt, die ebenfalls Bestandteil des Langzeitgedächtnisses ist und - wie Sie sich wahrscheinlich schon denken können - um alle Züge reduziert wurde, die sich bei vorherigen Partien in dieser speziellen Situation als verlustträchtig erwiesen haben. Sie enthält also nur gute Züge bzw. Züge, über die noch nichts bekannt ist. Sollte in dem einen oder anderen Fall eine leere Liste in Erscheinung treten, so weiß das Programm, daß es verloren hat (erg=2), und es geht zurück ins Hauptprogramm.

Ansonsten wird das Spiel jedoch mit einigen Eintragungen ins Kurzzeitgedächtnis fortgesetzt, das dazu dient, den Ablauf einer Partie in allen Einzelheiten zu protokollieren. Die Variablenfelder beginnen alle mit k, benutzen den Zugzähler zz als Index und haben im einzelnen folgende Bedeutung:

k.psn1(zz), k.psn2(zz):

Die Brettposition vor Ausführung eines Zuges in gepackter Form.

k.zliste$(zz):

Die zur Auswahl des Zuges benutzte Zugliste.

k.index(zz):

Diese Variable erhält den Wert -1, falls die aktuelle Position noch nicht im Langzeitgedächtnis vermerkt ist. Anderenfalls gibt sie an, unter welchem Index die Eintragung gefunden wurde.

k.znr(zz):

Gibt die Position des gewählten Zuges in der Zugliste an; sie wird in Zeile 1670 nach einem Zufallsprinzip ermittelt. Falls Sie möchten, daß das Programm systematisch lernt, so können Sie die Zeile einfach in k.znr(zz)=1 abändern; das Programm führt dann stur immer den ersten in der Liste vorhandenen Zug aus.

Was nach der Eintragung ins Kurzzeitgedächtnis passiert, ist schnell geklärt: Der ausgewürfelte Zug wird mit Hilfe von MID$ der Zugliste entnommen, in einen Zahlenwert verwandelt und anschließend bitweise in vier Koordinaten zerlegt, mit denen das Unterprogramm Zug ausführen den Rest erledigt. Danach wird nur noch der Zugzähler zz erhöht und es geht zurück ins Hauptprogramm: Der Gegner ist an der Reihe.

Und damit kommen wir zu der Auswertung nach Ende einer Partie. Schauen wir uns zunächst an, was passiert, wenn der Rechner die Partie gewonnen hat (ab Zeile 810). Es ist sofort klar, daß die Zugliste, die zu der Position vor dem Gewinnzug gehört, genau auf diesen einen Zug reduziert werden kann; einen besseren wird das Programm auf keinen Fall finden. Die einzige Frage ist nur noch, ob die Position schon im Langzeitgedächtnis vermerkt ist oder nicht. Im ersten Fall wird die Manipulation der Zugliste direkt dort vorgenommen, im zweiten Fall muß zunächst eine neue Eintragung vorgenommen und die Variable mp (Memory Pointer), die immer auf den nächsten freien Platz in Langzeitgedächtnis zeigt, um 1 erhöht werden. Es gelangen also nur Positionen vom Kurz- ins Langzeitgedächtnis, bei denen ein konkreter Anlaß zur Reduzierung der Zugliste vorliegt. Für alle anderen Positionen können die vollständigen Listen ja jederzeit vom Zuggenerator erzeugt werden.

Der Memory-Pointer, d.h. die Anzahl der bereits gespeicherten Positionen und Zuglisten, wird übrigens laufend in der linken oberen Bildschirmecke angezeigt. Sollte er sich bedrohlich dem Wert 2000 nähern, so müssen Sie vorsorglich die Dimensionierung des Langzeitgedächtnisses in Zeile 150 erhöhen.

Etwas komplizierter ist die Auswertung, falls der Rechner eine Partie verliert (ab Zeile 870). Klar ist sofort, daß der letzte Zug aus der Zugliste eliminiert werden muß, doch dabei kann ein Spezialfall auftreten. Falls dieser Zug der einzige in der Liste ist, d.h. keine Alternativzüge mehr übrig bleiben, so heißt das automatisch, daß auch der vorherige Zug des Rechners als Verlustzug zu betrachten ist - er führt ja, falls der Gegner es will, zu einer Position mit einer leeren Zugliste! Ist dann der vorherige Zug ebenfalls ohne Alternative, so muß die Auswertung auf den vorvorigen Zug ausgedehnt werden, usw. Auf diese Weise kann es passieren, daß durch einen einzigen Partieverlust ganze Zugfolgen bis hin zum Partieanfang eliminiert werden.

Zum Abschluß bleibt noch, welche Auswertung bei einem Remis in Frage kommt. Entscheidend ist dabei, ob das Programm lernen soll, zu gewinnen, oder nicht zu verlieren - im ersten Fall muß das gleiche Verfahren wie bei einer Verlustpartie angewendet, im zweiten Fall dagegen die Auswertung der gewonnenen Spiele übernommen werden. Im Programm wurde ein weiser Kompromiß geschlossen: Es findet überhaupt keine Auswertung statt! Wenn Sie wollen, können Sie aber durch ein entsprechendes GOTO in Zeile 940 die Remis-Routine über die eine oder andere Auswertung umleiten.

## Der programmierte kleine Bruder

Damit haben Sie nun alle für das Lernverhalten des Rechners wichtigen Programmteile kennengelernt, und wir werden uns jetzt der Frage zuwenden, warum der Lernvorgang vergleichsweise langsam stattfindet, obwohl sich in der Datenstruktur durchaus Parallelen zum menschlichen Gedächtnis finden lassen. Doch mit dem Speichern von Positionen und Eliminieren von Verlustzügen ist es offensichtlich nicht getan. Insbesondere besitzt der Mensch zusätzlich die Fähigkeit, aus seinen Erfahrungen allgemeine Regeln abzuleiten, wie z.B.

> Es ist schlecht, wenn der Gegner eine Dame erhält,

und kann die Regeln auch wieder auf konkrete Spielsituationen anwenden. Es liegt auf der Hand, daß diese Fähigkeit einen Lernvorgang außerordentlich beschleunigt, da die bereits gewonnenen Erfahrungen auch auf Situationen angewendet werden können, die bislang noch nicht aufgetreten sind.

Damit berühren wir ein Gebiet, mit dem Elektronengehirne ihre Schwierigkeiten haben. Regeln wie das obige Beispiel werden im allgemeinen durch Bewertungsfunktionen erfaßt (siehe Kapitel 4). Daraus resultiert praktisch die Forderung nach einem Programm, das im Verlauf des Lernvorgangs die Bewertungsfunktion oder zumindest die Gewichtsfaktoren einer vorgegebenen Formel selbst verändert. Doch bislang gibt es in dieser Hinsicht kaum vorzeigbare Ergebnisse, und die wenigen Experimentalprogramme kranken meist am gleichen Problem wie unser Beispiel: Sie lernen zu langsam. Zwar beherrscht unser Programm immerhin eine Art der Verallgemeinerung, nämlich die Anwendung seines Wissens auf spiegelbildliche Situationen, doch das ist sehr wenig.

Auf welch absurde Weise sich der Mangel an Abstraktionsfähigkeit bemerkbar machen kann, soll die folgende kurze Szene verdeutlichen: In tagelanger, aufopferungsvoller Lehrtätigkeit haben Sie das Minischach-Programm soweit gebracht, daß es allen Ihren Gemeinheiten und taktischen Schlichen gewachsen ist. Auch bei stärkstem Gegenspiel gelingt es kaum noch, eine Partie gegen den Rechner zu gewinnen. Stolz auf die Erfolge Ihres Schülers wollen Sie das Programm beenden und den gesamten Lerninhalt auf Datenträger schreiben lassen, da stürmt Ihr kleiner Bruder in den Raum. Spaßeshalber erklären Sie ihm die Regeln und laden ihn zu einer Partie ein. Und siehe da: Obwohl der Kleine oft mit den denkbar dümmsten Zügen operiert, verliert das ach so gelehrige Programm plötzlich wieder eine Partie nach der anderen - was ist passiert?

Ganz klar: Sie haben dem Programm zwar beigebracht, wie man gegen einen guten, aber nicht, wie man gegen einen schlechten Spieler gewinnt! Da das Programm nicht verallgemeinert, nützen ihm die Erfahrungen aus den vorherigen Partien überhaupt nichts, wenn es auf vollkommen unbekannte Stellungen stößt. Also legen Sie dem Knirps nahe, weitere Partien zu spielen, um das Programm auch in dieser Beziehung sturmfest zu machen, doch leider hat der nach 10 Minuten die Nase voll und zieht von dannen. Was nun?

Doch bevor Sie in Versuchung kommen, selber den Dummi zu spielen, hier eine bessere Lösung: Warum soll der Computer nicht diese Rolle übernehmen? Das Ganze stellt überhaupt kein Problem dar. Sie müssen nur die Erweiterung kleiner Bruder mit MERGE "BRUDER" dazuladen, und danach lernt der Computer, indem er gegen sich selbst spielt, eine Partie nach der anderen! Nach Drücken von <DEL> wird das Gemetzel bei nächster Gelegenheit abgebrochen, und das Programm schreibt wie gewohnt sein Langzeitgedächtnis auf Datenträger.

Auf den ersten Blick scheint hier wirklich ein alter KI-Traum (oder ein Trauma?) in Erfüllung zu gehen: Ohne menschliches Zutun erarbeitet sich die Maschine eine Qualifikation, die sie irgenwann in die Lage versetzen wird, sich in der Realität (d.h. gegen menschliche Gegner) zu bewähren. Schaut man sich jedoch an, was auf dem Bildschirm abläuft, so stehen einem die Haare zu Berge: Da ja beide Kontrahenten ihre Züge zufallsgesteuert wählen, kommen kaum sinnvolle Zugfolgen zustande. Bei dem Führer der schwarzen Steine bleibt das auch so, während der Führer der weißen Steine ständig dazulernt; er müßte also nach einer ausreichenden Anzahl von Partien die Mehrzahl der Spiele gewinnen. Lassen Sie Ihrem CPC ruhig zwei oder drei Nächte Zeit, und probieren Sie, was bei diesem Langzeitexperiment herauskommt.

Das Programm des Autors operiert inzwischen mit einer Datei, die auf Disk ca. 30 KByte belegt und 1950 gespeicherte Positionen umfaßt. Damit gewinnt es in der Tat die meisten Partien gegen den kleinen Bruder, und auch erfahrene Gegner werden mitunter schon deutlich abserviert. Entstanden ist die Datei in einigen harten Lehrstunden und durchrechneten Nächten; die Kombination beider Methoden hat sich als recht sinnvoll erwiesen.

Trotzdem sollte man nicht verschweigen, daß das Programm in der vorliegenden Form von seiner Leistungsfähigkeit her kaum befriedigt. Die Erwartungen, die bei der Planung in das Projekt gesetzt wurden, erfüllt es nur teilweise. Aber trotzdem gab es gute Gründe, es im Software-Experiment vorzustellen. Einerseits demonstriert es interessante Programmiertechniken (z.B. gepackte Daten, Zuggenerator), die auch bei anderen Gelegenheiten nützlich werden können; andererseits ist es recht aufschlußreich, dem Programm bei seinen Lernbemühungen zuzuschauen. Und vielleicht hat ja der eine oder andere Leser noch eine Idee, wie man das Programms verbessern kann?!