Welchen Algorithmus sollte ich für die "genetische KI-Verbesserung" verwenden?

Question

Zunächst einmal: Dies ist keine Frage dazu, wie man ein Programm spielen lässt Five in a Row. Das habe ich schon gemacht.

Einführende Erklärung

Ich habe ein fünf-in-einer-Reihe-Spiel als Rahmen erstellt, um mit der genetischen Verbesserung der KI zu experimentieren (auweia, das klingt furchtbar anmaßend). Wie bei den meisten rundenbasierten Spielen wird der beste Zug dadurch entschieden, dass jedem möglichen Zug eine Punktzahl zugewiesen wird und dann der Zug mit der höchsten Punktzahl gespielt wird. Die Funktion zum Zuweisen einer Punktzahl zu einem Zug (einem Feld) sieht ungefähr so aus:

1. Wenn das Feld bereits ein Token hat, beträgt die Punktzahl 0, da es illegal wäre, ein neues Token in das Feld zu platzieren.

2. Jedes Feld kann Teil von bis zu 20 verschiedenen Gewinnreihen sein (5 horizontal, 5 vertikal, 10 diagonal). Die Punktzahl des Feldes ist die Summe der Punktzahl jeder dieser Reihen.

3. Die Punktzahl einer Reihe hängt von der Anzahl der freundlichen und feindlichen Token in der Reihe ab. Beispiele:

   • Eine Reihe mit vier freundlichen Tokens sollte eine unendliche Punktzahl haben, denn wenn Sie dort ein Token platzieren, gewinnen Sie das Spiel.
   • Die Punktzahl für eine Reihe mit vier feindlichen Tokens sollte sehr hoch sein, denn wenn Sie kein Token dort platzieren, wird der Gegner in seinem nächsten Zug gewinnen.
   • Eine Reihe mit sowohl freundlichen als auch feindlichen Tokens wird eine Punktzahl von 0 haben, da diese Reihe nie Teil einer Gewinnreihe sein kann.

Nach diesem Algorithmus habe ich einen Typ namens TBrain deklariert:

type
  TBrain = array[cFriendly..cEnemy , 0..4] of integer; 

Die Werte im Array geben die Punktzahl einer Reihe mit entweder N freundlichen Tokens und 0 feindlichen Tokens oder 0 freundlichen Tokens und N feindlichen Tokens an. Wenn sich 5 Tokens in einer Reihe befinden, gibt es keine Punktzahl, da die Reihe voll ist.

Es ist eigentlich ziemlich einfach, zu entscheiden, welche Werte im Array stehen sollten. Brain[0,4] (vier freundliche Tokens) sollte "unendlich" sein, nennen wir das 1.000.000. vBrain[1,4] sollte sehr hoch sein, aber nicht so hoch, dass das Gehirn das Blockieren mehrerer feindlicher Siege bevorzugen würde, anstatt selbst zu gewinnen.

Betrachten Sie das folgende (unwahrscheinliche) Brett:

  0123456789
 +----------
0|1...1...12
1|.1..1..1.2
2|..1.1.1..2
3|...111...2
4|1111.1111.
5|...111....
6|..1.1.1...
7|.1..1..1..
8|1...1...1.

Spieler 2 sollte sein Token in (9,4) platzieren, um das Spiel zu gewinnen, nicht in (4,4), obwohl er dann 8 potenzielle Gewinnreihen für Spieler 1 blockieren würde. Ergo, vBrain[1,4] sollte (vBrain[0,4]/8)-1 sein. Wenn wir so arbeiten, können wir optimale Werte für das "Gehirn" finden, aber noch einmal, darum geht es mir nicht. Ich möchte einen Algorithmus finden, um die besten Werte zu finden.

Ich habe dieses Framework so implementiert, dass es vollkommen deterministisch ist. Es gibt keine zufälligen Werte, die den Punktzahlen hinzugefügt werden, und wenn mehrere Felder die gleiche Punktzahl haben, wird das obere linke Feld gewählt.

Eigentliches Problem

Das war es für die Einführung, jetzt zum interessanten Teil (zumindest für mich)

Ich habe zwei "Gehirne", vBrain1 und vBrain2. Wie sollte ich diese iterativ verbessern? Ich stelle mir etwas in der Art vor:

1. Initialisieren Sie vBrain1 und vBrain2 mit zufälligen Werten.
2. Simulieren Sie ein Spiel zwischen ihnen.
3. Weisen Sie die Werte vom Gewinner dem Verlierer zu und ändern Sie dann zufällig einen davon leicht.

Dies scheint nicht zu funktionieren. Die Gehirne werden nicht schlauer. Warum?

Sollte die Score-Methode einige kleine zufällige Werte zu dem Ergebnis hinzufügen, damit zwei Spiele zwischen denselben beiden Gehirnen unterschiedlich wären? Wie stark sollten sich die Werte für jede Iteration ändern? Wie sollten die "Gehirne" initialisiert werden? Mit konstanten Werten? Mit zufälligen Werten?

Hat das überhaupt etwas mit KI oder genetischen Algorithmen zu tun?

PS: Die Frage hat nichts mit Five in a Row zu tun. Das habe ich nur gewählt, weil ich ein sehr einfaches "Gehirn" deklarieren kann, um Experimente durchzuführen.

Answer 1

Wenn Sie dieses Problem wie einen genetischen Algorithmus angehen möchten, benötigen Sie eine gesamte Population von "Gehirnen". Bewerten Sie sie dann gegeneinander, entweder jede Kombination oder verwenden Sie einen Turnierstil. Wählen Sie dann die besten X % der Bevölkerung aus und verwenden Sie diese als Eltern der nächsten Generation, wobei Nachkommen durch Mutation (die Sie haben) oder genetischen Crossover (z.B. Austausch von Zeilen oder Spalten zwischen zwei "Gehirnen") erstellt werden.

Außerdem, wenn Sie keinen evolutionären Fortschritt sehen, benötigen Sie möglicherweise mehr als nur Gewinn/Verlust, sondern entwickeln Sie ein Art Punktesystem, damit Sie die gesamte Population effektiver bewerten und die Auswahl erleichtern können.

Answer 2

Im Allgemeinen kann man das Gehirn durch den Einsatz von genetischen Algorithmen intelligenter machen.

Zufälligkeit oder Mutation spielt eine wesentliche Rolle bei der genetischen Programmierung.

Ich mag dieses Tutorial, Genetische Algorithmen: Cooler Name & Verdammt Einfach.
(Es verwendet Python für die Beispiele, aber es ist nicht schwer, sie zu verstehen)

Answer 3

Schauen Sie sich Neuro Evolution of Augmenting Tologies (NEAT) an. Ein schickes Akronym, das im Grunde bedeutet, die Evolution von Neuralen Netzen - sowohl deren Struktur (Topologie) als auch Verbindungsgewichte. Ich schrieb eine .Net-Implementierung namens SharpNEAT, die Sie sich ansehen können. SharpNEAT V1 hat auch ein Tic-Tac-Toe-Experiment.

http://sharpneat.sourceforge.net/