Kultivierung künstlicher Intelligenz als Beispiel für ein einfaches Spiel

In diesem Artikel werde ich die Erfahrung des Wachstums einfacher künstlicher Intelligenz (KI) unter Verwendung eines genetischen Algorithmus teilen und auch über die Mindestmenge an Befehlen sprechen, die zur Bildung eines Verhaltens erforderlich sind.

Das Ergebnis der Arbeit war, dass die KI, die die Regeln nicht kannte, das Tic-Tac-Toe-Spiel unabhängig beherrschte und die Schwächen der Bots entdeckte, die dagegen spielten. Aber ich habe mit einer noch einfacheren Aufgabe angefangen.

Befehlssatz

Alles begann mit der Vorbereitung einer Reihe von Befehlen, die AI haben könnte. Hochsprachen enthalten Hunderte verschiedener Operatoren. Um das notwendige Minimum hervorzuheben, habe ich mich für die Assembler-Sprache entschieden. Es stellte sich jedoch heraus, dass es viele Befehle enthält.

Ich brauchte die KI, um Daten zu lesen und auszugeben, mit dem Speicher zu arbeiten, Berechnungen und logische Operationen durchzuführen, Übergänge und Schleifen durchzuführen. Ich bin auf die Brainfuck-Sprache gestoßen, die nur 8 Befehle enthält und beliebige Berechnungen durchführen kann (d. H. Ist Turing abgeschlossen). Im Prinzip ist es für die genetische Programmierung geeignet, aber ich bin noch weiter gegangen.

Ich fragte mich: Wie viele Befehle sind mindestens erforderlich, um einen Algorithmus zu implementieren? Wie sich herausstellte - eins!

Der URISC-Prozessor enthält nur einen Befehl: subtrahieren und überspringen Sie die nächste Anweisung, wenn die subtrahierte mehr als die dekrementierte war. Dies reicht aus, um einen Algorithmus zu erstellen.

Oleg Mazonka ging noch weiter, er entwickelte das BitBitJump- Team und bewies, dass es laut Turing vollständig ist. Der Befehl enthält drei Adressen, kopiert ein Bit von der ersten in die zweite Speicheradresse und überträgt die Steuerung an die dritte Adresse.

Nachdem ich Olegs Ideen ausgeliehen hatte, um die Arbeit zu vereinfachen, entwickelte ich das SumIfJump-Team. Der Befehl enthält vier Operanden: A, B, C, D und führt Folgendes aus: Fügt Daten aus der Zelle zur Adresse A zur Adresse B hinzu. Wenn der Wert größer als das angegebene * ist, geht er zur Adresse C, andernfalls zur Adresse D.


Wenn Operand A auf die Speicherzelle N0 zugreift, werden Daten eingegeben, und wenn sie in die Zelle N1 gelangen, werden sie ausgegeben.

Unten finden Sie den SumIfJump-Code für FreePascal (ein kostenloses Analogon von Delphi).

procedure RunProg(s: TData); var a, b, c, d: TData; begin Inc(NStep); if NStep > MaxStep then begin ProgResult := 'MaxStep'; Exit; end; a := s; b := s + 1; c := s + 2; d := s + 3; a := Prog[a]; b := Prog[b]; c := Prog[c]; d := Prog[d]; if a = 0 then begin ProgResult := 'Input'; Exit; end; if a = 1 then begin ProgResult := 'Output'; Exit; end; Prog[b] := Prog[b] + Prog[a]; if Prog[b] < ProgLength div 2 then RunProg(c) else RunProg(d); end; 

SumIfJump implementiert selbstmodifizierenden Code. Es kann alle in der üblichen Programmiersprache verfügbaren Algorithmen ausführen. Der Code ist leicht zu ändern und hält jeder Manipulation stand.

Einfache Aufgabe

Unsere KI hat also nur ein Team. Während Tic-Tac-Toe ein sehr schwieriges Spiel für ihn ist, begann ich mit einem einfacheren.



Der Bot gibt eine Zufallszahl und die KI sollte die Daten lesen und eine Antwort geben. Wenn die Zahl größer als der Durchschnitt ist (aus dem Bereich der Zufallszahlen), sollte die KI eine Zahl angeben, die kleiner als der Durchschnitt ist, und umgekehrt.

Das Genom unserer KI besteht aus 256 Zellen mit Werten von 0 bis 255. Jeder Wert ist ein Speicher, ein Code und eine Adresse. Die Anzahl der Codeausführungsschritte ist auf 256 begrenzt. Die Operanden werden nacheinander gelesen.

Anfänglich wird das Genom durch eine Reihe von Zufallszahlen gebildet, sodass die KI nicht weiß, was sie spielen muss. Darüber hinaus weiß er nicht, dass er Daten nacheinander eingeben und ausgeben muss, um auf den Bot zu reagieren.

Bevölkerung und Auswahl

Die erste Population besteht aus 256 AIs, die anfangen, mit dem Bot zu spielen. Wenn die KI die richtigen Aktionen ausführt, beispielsweise Eingabedaten anfordert und dann etwas anzeigt, erhält die KI Punkte. Je korrekter die Aktionen, desto mehr Punkte.

Die 16 AIs, die die meisten Punkte erzielt haben, geben 15 Nachkommen und nehmen weiterhin am Spiel teil. Ein Nachkomme ist eine Mutante. Die Mutation erfolgt durch Ersetzen einer zufälligen Zelle in der übergeordneten Kopie durch einen zufälligen Wert.



Wenn in der ersten Population keine KI Punkte erzielt hat, wird die nächste Population gebildet. Und so weiter, bis ein Teil der KI beginnt, die richtigen Aktionen auszuführen und den „richtigen“ Nachwuchs zu geben.

Evolution

N.	Meilensteine
1	KI macht nichts. Das Programm dauert 256 Schritte und endet.
2	Begann Daten anzufordern.
3	Er begann Daten anzufordern und etwas auszugeben. Die Reihenfolge der Anfragen und Antworten ist chaotisch.
4	Die Dateneingabe und -ausgabe erfolgt nacheinander, manchmal treten Fehler auf. In der Hälfte der Fälle gibt AI die richtige Antwort.
5	Gibt regelmäßig korrekte Antworten, aber manchmal treten Fehler auf.
6	Gab die richtige Antwort in 30.000 Iterationen. Auswahl wird hochgeladen.

Zwischen bedeutenden Ereignissen vergingen Tausende von Generationen. Das Programm wurde in mehreren Threads auf Core i7 gestartet. Die Berechnungen dauerten ca. 15 Minuten.

Interessante Punkte

1. Als der KI- „Anführer“ einen zufälligen Fehler machte und nicht genügend Punkte erzielte, begann sich die Bevölkerung zu verschlechtern, weil Nachkommen von "sekundären" Eltern gebildet.
2. Es kam vor, dass im Strom mit Außenstehenden, die die Zeit markierten, eine erfolgreiche Mutation auftrat, die zu einer explosiven Erhöhung der gesammelten Punkte führte. Danach wurde dieser Fluss der Anführer.
3. Manchmal traten lange Zeit keine erfolgreichen Mutationen auf, und selbst 500.000 Generationen reichten nicht aus, um die Auswahl zu vervollständigen.

Fazit

Abschließend habe ich dasselbe mit dem Tic-Tac-Toe-Spiel gemacht. Die Genomgröße wurde wie im ersten Fall verwendet. Die Anzahl der Schritte wurde auf 1024 und die Populationsgröße auf 64 erhöht (zur schnelleren Berechnung). Die Berechnung dauerte etwas länger. Alles geschah nach dem gleichen Szenario.

Zuerst spielte die KI gegen den "Randomizer". Ich habe den Bot angerufen, der zufällig geht. Ziemlich schnell begann AI ihn zu schlagen und füllte eine Zeile aus. Außerdem habe ich die Aufgabe kompliziert, indem ich dem Randomizer einen kleinen Grund hinzugefügt habe: die Linie zu besetzen, wenn möglich, oder zu verteidigen. In diesem Fall fand AI jedoch die Schwächen des Bots und begann ihn zu schlagen. Vielleicht ist die Geschichte darüber ein Thema für einen separaten Artikel.

Der Sohn bat mich, ein Programm zu schreiben, damit die AIs untereinander spielen und nicht mit dem Bot. Es gab Ideen, dasselbe zu tun, um Dame zu spielen oder zu gehen, aber dafür hatte ich bereits nicht genug Zeit.

Die einzige Methode, mit der ich neue Individuen bekam, war eine Mutation. Sie können auch Crossover und Inversion verwenden. Vielleicht beschleunigen diese Methoden das Erreichen des gewünschten Ergebnisses.

Am Ende war die Idee geboren: AI die Möglichkeit zu geben, alle Prozesse auf einem PC zu verwalten und um Computerressourcen zu kämpfen. Verbinden Sie einen PC mit dem Internet und nutzen Sie den Pool alter Bitcoin-Farmen als Rechenleistung ...

Wie gesagt, Blogger Mikhail Tsarkov führte ein ähnliches Experiment durch :

Vielleicht übernehmen sie die Welt, aber was ist, wenn?

Referenzen

1. Genetische Algorithmen
2. Copy Bit - Die einfachste Rechenmaschine / Oleg Mazonka
3. URISC - Wikipedia
4. Vollständigkeit - Wikipedia