Künstliche Intelligenz

von Konrad Rudolph ( www.geocities.com/konrad_rudolph )

Ein Computer hat wahrscheinlich nur einen wesentlichen Nachteil gegenüber dem menschlichen Gehirn: er ist nicht kreativ. Daher gehört es zu den schwersten Programmieraufgaben, eine passable künstliche Intelligenz zu simulieren.
Die verschiedenen Prinzipien alle zu erläutern, wäre sicherlich zu aufwendig. Ich habe einige Beispiele für Ansätze von KI zusammengetragen. Darunter befinden sich Beispiele, wie man ein Programm dazu bringt, aus Fehlern zu lernen oder wie man Gewinnstrategien per Formeln entwickelt:

Lernmatrizen
Strategien

Lernmatrizen

Um einen Computer aus Fehlern lernen zu lassen, muß er seine Erfahrungen speichern können - und zwar nicht nur in einer Variable, er braucht ja quasi für jede Situation einen eigenen Speicher. Um überhaupt einen halbwegs vernünftigen Zugriff auf diese Speicher hinzubekommen, bieten sich Matrizen (Arrays) zum Speichern an.
Als Beispiel für eine Situation, in der ein Computer lernen soll, wähle ich das NIM - Spiel. Es besticht wegen seiner Einfachheit: Von einer Anzahl von Hölzern A nehmen zwei Spieler abwechselnd beliebig viele Hölzer, mindestens jedoch eines und maximal eine vorher festgelegte Zahl M. Wer den Gegner zwingt, das letzte Hölzchen zu nehmen, hat gewonnen.
Das ganze läßt sich einfach genug in BASIC umsetzen. Nun soll der eine Spieler der Computer sein und er soll aus seiner Erfahrung bei diesem Spiel lernen. Da er aber erst nach einiger Zeit sinnvolle Erfahrungen gesammelt hat, lassen wir ihn die ersten 100 Spiele gegen 'sich selbst' spielen, danach eine Runde gegen den Spieler. Der Computer hat etwas gelernt. Anfangs hatte ich versucht, dieses 'gegen sich selbst spielen' so zu realisieren, daß der eine Spieler Erfahrungen nutzt un der andere nur auf Zufall spielt aber das klappt nicht, da der Zufallsspiele schon nach kurzer Zeit keine Chance mehr hat. Der 'Denker' gewinnt immer und hat so keine Gelegenheit, falsche Erfahrungen zu korrigieren. Daher greit der Zufallsspieler auch auf das Erfahrungsarray zu, speichert aber seine eigenen Erfahrungen nicht...
Wir wählen eine geringe Anzahl von Hölzern: 9. Die Anzahl der maximal zu nehmenden setzen wir auf 3. Damit hätten wir:

DIM Count AS INTEGER
CONST Max = 3

Count = 9
Nun müssen wir ein Array definieren, in dem der Computer seine Erfahrungen speichern soll. Für jede mögliche Situation muß ein Feld in dieser Matrix reserviert sein: wir haben eine maximale Hölzchenzahl von neun und man darf maximal 3 Hölzer nehmen, wir wählen also ein zweidimensionales Array mit den Ausmaßen (9, 3). Der Typ sei INTEGER, da wir in dem Array die Erfahrung in Form von Zahlwerten speichern wollen. Zuletzt initiieren wir das Array. Das heißt, wir setzen alle Werte auf einen gleichen Wert, der die Erfahrung 'null' symbolisiert. Der Wert sollte allerdings gerade nicht null sein, da er sowohl nach oben (gute Erfahrungen) als auch nach unten (schlechte Erfahrungen) schwanken kann. Außerdem brauchen wir eine ebenso große Matrix, in der gespeichert wird, welche Situationen im aktuellen Spiel verwendet wurden.
DIM Experience(1 TO Count, 1 TO Max) AS INTEGER
DIM Used(1 TO Count, 1 TO Max) AS INTEGER

FOR I = 1 TO Count
  FOR J = 1 TO Max
    Experience(I, J) = 64
  NEXT
NEXT
Der Wert 64 bietet sich geradezu an, da er eine Potenz von 2 ist, also oft geteilt werden kann, ohne einen Bruch zu ergeben.
Im Folgenden spielt nun der Computer 100 Runden gegen sich selbst, wobei er einmal seine Wahl dem Zufall überläßt, das andere Mal jedoch seine Erfahrungen benutzt; der interessante Teil beginnt. Zuerst einmal der Quelltext, die Erklärungen folgen nach:
  1. DIM OnTurn AS STRING
    DIM Lost AS STRING
    DIM Won AS LONG

    FOR I = 1 TO 100

    IF I MOD 2 THEN OnTurn = "Random" ELSE OnTurn = "Thinker"
    DO
  2. DO
    FOR J = 1 TO Max
      P(J) = INT(RND * Experience(Count, J) / 2)
    NEXT
    Take = 1
    IF P(2) > P(1) THEN SWAP P(1), P(2): Take = 2
    IF P(3) > P(1) THEN Take = 3
    LOOP WHILE Take > Count
  3. IF OnTurn = "Thinker" THEN
      Used(Count, Take) = 1
    END IF
  4. PRINT "There are still"; STR$(Count); " matches."
    PRINT OnTurn; " takes"; STR$(Take); " matches.": PRINT
  5. Count = Count - Take
    IF OnTurn = "Random" THEN
      OnTurn = "Thinker"
    ELSE
      OnTurn = "Random"
    END IF
    LOOP UNTIL Count <= 1
  6. If Count = 1 THEN
      Lost = OnTurn
    ELSE
      IF OnTurn = "Random" THEN Lost = "Thinker" ELSE Lost = "Random"
    END IF
    Count = 9
    PRINT Lost; " lost the game!"
  7. IF Lost = "Random" THEN
      Won = Won + 1
      FOR J = 1 TO Count
        FOR K = 1 TO Max
          IF Used(J, K) THEN
            IF Experience(J, K) < 8388608 THEN
              Experience(J, K) = Experience(J, K) * 2
            END IF
            Used(J, K) = 0
          END IF
        NEXT
      NEXT
    ELSE
      FOR J = 1 TO Count
        FOR K = 1 TO Max
          IF Used(J, K) THEN
            IF Experience(J, K) > 1 THEN
              Experience(J, K) = Experience(J, K) / 2
            END IF
            Used(J, K) = 0
          END IF
        NEXT
      NEXT
    END IF

    NEXT
  1. Zuerst einmal wird ein String deklariert, in dem gespeichert wird, wer am Zug ist. Immer abwechselnd beginnen der Zufallsspieler un der Denker, wobei der Zufallspieler ja auch Zugriff auf die Erfahrungen der anderen hat.
  2. In der Schleife, die so lange ausgeführt wird, bis A = 0 ist, multipliziert der Computer den Wert aus der aktuellen Spalte für die Zahl der noch vorhandenen Hölzer des Eperience Arrays mit einem Zufallswert. Dadurch spielt nicht nur die Erfahrung, die ja durchaus auch einmal falsch sein kann, eine Rolle, sondern auch noch der Zufall. Das gewährleistet, daß der Computer falsche Erfahrungen mit der Zeit richtigstellt. Die entstehenden Werte, P(1), P(2) und P(3) durchsucht er nach dem höchsten Wert, also der, wo die besten Erfahrungen mit gemacht wurden (modifiziert durch Zufall!). Daraus erkennt er die Zahl der zu nehmenden Hölzer. Er speichert sie in Take.
  3. Falls der Lerncomuter am Zug ist, trägt er in das Feld Used(Count, Take) den Wert 1 ein, um zu speichern, welche Werte er in diesem Spiel benutzt hat. Auf diese Weise kann er nachher seine Züge nachvollziehen, um seine Erfahrungen zu verändern.
  4. Das Ergebnis des letzten Zuges wir auf dem Bildschirm ausgegeben.
  5. Die Zahl der existierenden wir mit der Zahl der genommenen Hölzer verrechnet. Es wird bestimmt, wer als nächstes am Zug ist. Im Abschluß wird überprüft, ob das Spiel bereit beendet ist - die Schleife schließt sich.
  6. Es wird überprüft, wer das Spiel verloren hat, das wir auf dem Bildschirm ausgegeben, außerdem wird die Zahl der Hölzer auf 9 zurückgesetzt.
  7. Es folgt die - wahrscheinlich - wichtigste Partie des Programms: Der Computer schaut für jeden Wert nach, ob er während des Spieles benutzt wurde. Im Falle eines Sieges werden all diese Werte verdoppelt, bei einem Verlust werden sie halbiert. Daher der Anfangswert 64 (als Zweierpotenz).
    Das mag etwas roh erscheinen, da ja nicht alle Züge die man in einem Spiel getätigt hat, unbedingt gut - bei einem Gewinn - oder schlecht - bei einem Verlust - sein müssen. Aber diese Methode geht genau auf! Je mehr Spiele man den Computer spielen läßt, desto genauer kristallisiert sich eine Struktur heraus (diese wird ausführlicher in dem Thema Strategien erläutert, da man genau diese Struktur auch in einer mathematischen Formel umschreiben kann).
Hier ein Beispiel, wie Die Experience Matrix nach bereits 100 Spielen aussieht. Noch genauere Ergebnisse gibt es, je mehr Spiele gespielt werden.
64 2048 16 32 1 2048 8 32 1
64 64 8192 64 2 64 2048 32 2
64 64 16 16384 2 32 16 16384 2
Es zeigt sich eine deutliche 'Treppchentendenz', d.h. Die Werte sind so angeordnet, daß der Computer in je drei Situationen des Spiels auf einen Wert zusteuert. Zum Beispiel nimmt der Computer bei den Zügen 2, 3, 4 jeweils 1, 2, 3 Hölzer, so daß er als nächste Zugmöglich die 1 zusteuert, also den Gegner Schachmatt gesetzt hat (Wer das letzte Hölzchen zieht, hat ja verloren). Zu diesem Thema siehe mehr unter Strategien.

... Vollständigen Quelltext downloaden (Programm learn.bas)

Top

Strategien

Viele Spiele sind so logisch aufgebaut, daß sie im Grunde nur einen Algorithmus umschreiben (und nicht umgekehrt). Ein klassischen Beispiel dafür ist das NIM Spiel.
Für die, die es nicht kennen: Von einer Anzahl von Hölzern A nehmen zwei Spieler abwechselnd beliebig viele Hölzer, mindestens jedoch eines und maximal eine vorher festgelegte Zahl M. Wer den Gegner zwingt, das letzte Hölzchen zu nehmen, hat gewonnen.
Die Grundstruktur des Programmes, so daß der User gegen den Computer spielt, ist einfach programmiert; allerdings nimmt dann der Computer immer eine zufällige Zahl von Hölzern. Wie bekommt man ihn nun dazu, 'klug' zu spielen? Eine Möglichkeit wäre, ihn selbst merken zu lassen, was vorteilhaft für ihn ist und was nicht - Erfahrungen sammeln. Diese Methode wird in Lernmatrizen erläutert. Die andere Methode wäre, ihm zu sagen, mit welcher Strategie er gewinnen kann. Da man ihm schlecht sagen kann 'hey, du, leg' immer so viele Hölzer, daß...', müssen wir unsere Worte übersetzen. Klar - wir sprechen schließlich schon die ganze Zeit BASIC mit dem Computer. Aber, wie ich dem Artikel 'Über mich' auch erwähne, die Mathematik ist die Grundlage von allem - dann also erst Recht die der Programmierung. Und letztendlich handelt es sich ja bei der Strategie darum, eine Variable möglichst günstig zuzuweisen. Also wäre eine Formel wohl nicht fehlplatziert (Tatsächlich ist eine entsprechende Übersetzung der Strategie in BASIC oder auch in die 'menschliche Sprache' wesentlich länger, wie im Folgenden bemerkt werden kann. Die Formel besitzt nur knapp 40 Zeichen.
Ich finde es viel faszinierender, einen Sachbestand in einer Formel zu unschreiben, als in BASIC. Doch zuerst einmal: Wie lautet denn nun eigentlich diese tolle Strategie? Man kann sie durch ein einfaches Gedankenexperiment herausbekommen.
Zuerst einmal nehmen wie als Hölzerzahl 10 an und als die Zahl der maximal zu nehmenden 3. Nun gehen wir vom Ende des Spieles aus: Es existiert noch ein Hölzchen. Der Spieler, der nun am Zug ist, hat also verloren. Nun nehmen wir den zweiten Fall: Es gibt noch 2 Hölzer; der Spieler, der dran ist, hat keine Probleme, das Spiel zu gewinnen, indem er ein Holz nimmt. Bei drei Hölzern verhält es sich ähnlich. Ebenso bei vier.
Bei fünf Hölzern wird es interessant: Es ist dem Spieler nicht möglich, eine andere Zahl als 2, 3 oder 4 zu erhalten; dort haben wir aber gesehen, hätte der andere Spieler sicher gewonnen. Also hat ein Spieler, der auf der Position 5 sitzt, genauso verloren, wie auf der Position eins,m wenn der andere Spieler perfekt spielt (wovon man immer ausgeht). Positionen wie 1 und 5 kommen immer wieder vor; ich nenne sie 'sichere Positionen', da von ihnen aus keine Möglichkeit besteht, zu gewinnen. Die nächste sichere Position wäre in diesem Fall 9.
Wenn man die Anfangszahl der Hölzer verändert, ändern sich diese Postionen logischer Weise nicht. Allerdings ändern sie sich, wenn man den Max-Wert ändert (die maximale Zahl zu nehmender Hölzer):

Max sichere Positionen Differenz zwischen sicheren Positionen
3 1, 5, 9, 13, 17, 21... 4 (= Max + 1)
4 1, 6, 11, 16, 21, 26... 5 (= Max + 1)
5 1, 7, 13, 19, 25, 31... 6 (= Max + 1)
6 1, 8, 15, 22, 29, 36... 7 (= Max + 1)
7 1, 9, 17, 25, 33, 41... 8 (= Max + 1)
Die Differenz zwischen den einzelnen stabilen Positionen ist immer der Wert Max. Man könnte als eine Formel aufstelle, die es erlaubt, die nächstkleinere stabile Position zu errechnen:
NP = INT(Count / (Max + 1)) * (Max + 1) + 1
wobei NP die nächste Position sei und Count die aktuelle Hölzchenzahl. Diese Formel liefert allerdings Fehlwerte: Wenn Count eine Zahl direkt unter einer sicheren Position ist, ergibt NP einen Wert, der um eins größer ist, als die Zahl der Hölzer. Dem kann leicht mit folgender Anweisung abgeholfen werden:
IF NP > Count THEN NP = NP - Max - 1
Falls jemand eine bessere Lösung für diese Formel herausbekommt, die diese Fehlwerte mit abdeckt, schicke er sie bitte an mich, die Formel wird dann auf dieser Site mit dem Namen des Absenders veröffentlicht.
Um die Zahl der zu ziehenden Hölzer zu bekommen, muß nur noch NP von Count abgezogen werden...

zum Anfang