Umsetzung einer KI für das Spiel "TicTacToe" mit Hilfe von Reinforcement- oder Q-learning

Umsetzung einer KI für das Spiel „TicTacToe“ mit Hilfe von Reinforcement- oder Q-learning

Einleitung

Beim Q-Lernen wird eine Art Tabelle (siehe Abb. XXX) erstellt, welche für einen jeweiligen sensorischen Zustand X eine Menge von möglichen Aktionen A mit Wertungen, den Q-Werten, enthält. Je nach Wahl einer Auswahlregel werden dann beispielsweise die Aktionen ausgeführt, welche den höchsten Q-Wert aufweisen. So reagiert diese künstliche Intelligenz auf eine gegebene Situation und schafft dadurch natürlich eine neue. Nun wird wiederum eine Aktion gewählt und ausgeführt, bis die KI an ein vorgegebenes Ziel gelangt ist.

Abbildung in dieser Leseprobe nicht enthalten

Abb. XXX Tabelle

Spielregeln für TicTacToe

Zunächst eine kleine Erläuterung zu den Spielregeln von TicTacToe. Gegeben ist ein Spielfeld von drei mal drei Feldern, auf das zwei Spieler abwechselnd ihre Steine (auch Kreise oder Kreuze) ablegen. Ziel ist es drei Steine diagonal, horizontal oder vertikal in einer Reihe zu legen. Dabei dürfen die Steine, die sich auf dem Spielbrett befinden nicht mehr bewegt werden. Das Spiel ist zu Ende, sobald einer der Spieler das Ziel erreicht hat, oder das Spielbrett mit Steinen vollständig besetzt ist.

Vorüberlegung

Doch wie werden die Q-Werte dafür definiert? Nun, man könnte sie von Hand „eintragen“. Das wäre sehr mühsam, schließlich sind es ca. 4500 unterschiedliche Situationen. Da hilft das Lernverfahren, das sogenannte Reinforcement- oder Q-learning (engl. to learn = lernen). Man geht dabei zum Beispiel von einer Tabelle mit Zufalls -Q-Werten aus, mit Zufallszahlen zwischen 0 und 1. In unserem Fall wäre das eine Tabelle nach dem Schema in Abb. XXX mit einer Spalte für die Situation auf dem Spielfeld und 9 Spalten für die Q-Werte der Aktionen die auf eines der Spielfelder „zeigen“. Der Lernalgorithmus erzeugt dann ein imaginäres Spielbrett. Er spielt gegen sich selbst auf der Grundlage der eben erwähnten Tabelle. Nach jedem Zug bekommt der Algorithmus lediglich die Information, ob das Spiel beendet ist, und wenn ja das sogenannte Reinforcement, z.B. 1 für gewonnen und 0 für verloren. Nach einer vorgegebenen Gleichung werden dann bei jedem Schritt die Q-Werte der jeweiligen Situation verändert, und zwar in Abhängigkeit der Q-Werte (der spielerischen Möglichkeit für einen Sieg) der nächsten Situation. Näheres dazu aber erst im nächsten Abschnitt.

Das Programm

Zunächst einmal der Algorithmus in kürzester Form

1. Einlesen bzw. Berechnung der Parameter

2. Temperaturänderung, Spielfeld auf NULL setzen, Lernschrittzähler erhöhen

SPIELER I:

3. Kodieren der Situation und Einlesen der entsprechenden Q-Werte aus der Datei

4. Bewertung der vorangegangenen Aktion (ab dem zweiten Zug)

5. Auswahl der nächsten Aktion/des nächsten Spielzuges nach der Boltzmann-Maschine und den Q- Werten

6. Aktion ausführen

7. Wenn Spiel beendet (Sieg oder Unentschieden, dann Endbewertung, gehe zu 14.)

SPIELER II:

8. Kodieren der Situation und Einlesen der entsprechenden Q-Werte aus der Datei

9. Bewertung der vorangegangenen Aktion (ab dem zweiten Zug)

10. Auswahl der nächsten Aktion/des nächsten Spielzuges nach der Boltzmann-Maschine und den Q- Werten

11. Aktion ausführen

12. Wenn Spiel beendet (Sieg, dann Endbewertung, gehe zu 14.)

13. Gehe zu 3.

14. Gehe zu 2. solange Lernschrittzähler Soll nicht erreicht

- Temperaturänderung und Aktionswahl

Die Temperatur wird zur Umsetzung der sogenannten Boltzmannmaschine benötigt. Diese dient der späteren Aktionswahl. Das Prinzip ist sehr einfach. Zu Beginn hat das System (der Algorithmus) eine sehr hoch initialisierte TemperaturT. Je höher diese Temperatur ist, desto größer ist die Rolle des Zufalls bei der Auswahl der Aktion. Am Anfang ist also viel Zufall im Spil, was auch berechtigt ist, sind doch die Q-Werte noch nicht sehr aussagekräftig, d.h. zufällig initialisiert. Mit jedem Spiel wird dieTallerdings durch den Faktor DT<1 heruntergefahren, was zum Ende hin eine Auswahl des größten Q-Wertes entspricht.

Abbildung in dieser Leseprobe nicht enthalten

Die TemperaturänderungsrateDT) wird zuvor so berechnet, so dass die Temperatur T) in einer vorgegebenen Zahl von Lernschritten (S) auf ihr Minimum (z.B. 0.002) abkühlt.

Abbildung in dieser Leseprobe nicht enthalten

Nun direkt zu den Gleichungen für die Boltzmann-Maschine. Für jede mögliche Aktion wird eine Wahrscheinlichkeit für die Auswahl mit Hilfe der jeweiligen Q-Werte (w) errechnet:

Abbildung in dieser Leseprobe nicht enthalten

Es werden nur die möglichen Aktionen berücksichtigt, es könnte sonst im Algorithmus zu Fehlern oder Verlangsamerung durch zusätzliche Abragen kommen !

FürTÆ• ist diese WahrscheinlichkeitPunabhängig von den Q-Werten und somit für jede Aktion gleich groß. FürTÆ0 wird der Einfluß der Q-Werte noch verstärkt. Diese Wahrscheinlichkeiten ergeben in der Summe 1. Jede einzelne dieser bezeichnet also einen mehr oder weniger oder auch gleich großen Intervall zwischen 0 und 1.

Abbildung in dieser Leseprobe nicht enthalten

Nun wird eine Zufallszahl im Intervall (0;1) initialisiert ind je nachdem in welchen „Wahrscheinlichkeitsbereich“ diese Zahl fällt, wird die zugehörige Aktion ausgewählt. Aufgrund der Gleichverteilung der Bereiche bei hohen Temperaturen gleicht es anfänglich einer Zufallsauswahl.

- Kodierung der Situation

Abbildung in dieser Leseprobe nicht enthalten

Die Situation wird in einem Array von 9 Elementen (für jedes Feld eines) gespeichert. Wobei die Elemente die Werte 0 (frei), 1 (Spieler I) und 2 (Spieler II) annehmen können. Die Situation wird kodiert, indem eine eineindeutige Zahl mit 3 Grundziffern, eben 0,1 und 2, erzeugt wird.

Z.B. wenn Spieler I das Spielfeld 1 besetzt und der Rest des Spielfeldes noch frei ist, dann wäre der Situationscode 100 000 000. Würde Spieler II danach die 5 besetzen, dann wäre er 100 020 000. Dieser Code wird dann in eine Dezimalzahl umgewandelt (was wiederum eineindeutig ist) und entspricht dann der Zeilennummer in der „Tabelle“ der Q-Werte in der Datei.

- Die Bewertung der Situation - die Q-Werte

Wie schon erwähnt werden nach jedem Spielzug die Q-Werte verändert, sie werden gewichtet. Diese Wichtung passiert so, dass wenn ein Zug zum Sieg führt er aufgewertet wird, d.h. die Q-Werte und somit die Wahrscheinlichkeit für die Aktionswahl erhöht werden. Bei einer Niederlage entsprechend abgewertet. Doch wie werden Züge mitten im Spiel gewichtet? Nun man versucht zu bestimmen welche Möglichkeiten (Q-Werte) im nächsten Zug (mit der neuen Situation) vorhanden sind, also nach dem Maximum zu suchen dessen Aktion am ehesten zum Sieg führt. Man lässt allerdings nicht jede Aktion „durchprobieren“, sondern man verlässt sich auf die Aktionswahl. Nachdem der vermeintliche Gegner seinen Zug vollendet hat, liegt dem Algorithmus eine neue Situation und damit neue Q-Werte vor. Wie schon erwähnt stellt das Maximum die größte Chance auf einen Sieg dar. Nun wird der Q-Wert der vorangegangenen Aktion folgendermaßen abhängig von diesem Maximum verändert:

Abbildung in dieser Leseprobe nicht enthalten

wneustellt hierbei den neuen Q-Wert für die vorangegangene Aktion dar, w den alten. max(w’) ist das Maximum der Q-Wert der Situation nach dem gegnerischen Zug.a(empfohlen 0.5) undg(empfohlen 0.9) sind Parameter, die die Lerngeschwindigkeit bzw. den Einfluss des Maximums darstellen.rist das schon beschriebene Reinforcement.

- Die Endbewertung

Die Endbewertung läuft nach denselben Gleichungen ab, wie jede einzelne vorangegangene Bewertung auch. Nur wie ist das Q-Wert-Maximum der nächsten Situation wenn das Spiel beendet ist? Nun es entspricht bei Sieg dem Grenzwert der Q-Werte, um einen optimalen Lernvorgang zu gewährleisten. Hier die Herleitung der Maximumsberechnung:

Abbildung in dieser Leseprobe nicht enthalten

(d.h.wneugeht gegen -(r/(g-1)), hier liegt nur eine vereinfachte Schreibweise vor)