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
Häufig gestellte Fragen zum Thema "Umsetzung einer KI für das Spiel „TicTacToe“ mit Hilfe von Reinforcement- oder Q-learning"
Was ist Q-Learning und wie wird es bei TicTacToe angewendet?
Q-Learning ist eine Art von Reinforcement Learning, bei der eine Tabelle (oder eine andere Datenstruktur) erstellt wird, die für jeden möglichen Zustand des Spiels TicTacToe (jede mögliche Anordnung der Kreuze und Kreise auf dem Spielfeld) die erwarteten Belohnungen (Q-Werte) für jede mögliche Aktion (das Setzen eines Kreuzes oder Kreises auf ein leeres Feld) speichert. Der Algorithmus wählt dann basierend auf diesen Q-Werten die beste Aktion aus, um das Spiel zu gewinnen.
Wie funktionieren die Spielregeln von TicTacToe?
TicTacToe wird auf einem 3x3-Spielfeld gespielt. Zwei Spieler setzen abwechselnd ihre Steine (entweder Kreuze oder Kreise) auf leere Felder. Ziel ist es, drei eigene Steine in einer horizontalen, vertikalen oder diagonalen Reihe zu platzieren. Das Spiel endet, wenn ein Spieler dies erreicht hat oder alle Felder belegt sind (Unentschieden).
Wie werden die Q-Werte initialisiert und wie lernt die KI?
Die Q-Werte werden in der Regel mit Zufallszahlen initialisiert. Die KI lernt, indem sie gegen sich selbst spielt und nach jedem Zug eine Rückmeldung (Reinforcement) erhält, ob der Zug gut war (z.B. näher am Gewinn) oder schlecht (z.B. näher an der Niederlage). Basierend auf dieser Rückmeldung werden die Q-Werte angepasst, sodass gute Züge höhere Q-Werte erhalten und somit in Zukunft wahrscheinlicher gewählt werden.
Was ist eine Boltzmann-Maschine und wie wird sie in diesem Kontext verwendet?
Die Boltzmann-Maschine wird verwendet, um die Aktionsauswahl basierend auf den Q-Werten zu steuern. Sie führt eine "Temperatur" ein, die bestimmt, wie stark die Q-Werte die Aktionsauswahl beeinflussen. Bei hoher Temperatur werden die Aktionen eher zufällig ausgewählt (Exploration), während bei niedriger Temperatur die Aktion mit dem höchsten Q-Wert bevorzugt wird (Exploitation). Die Temperatur wird im Laufe des Lernprozesses schrittweise reduziert, um von Exploration zu Exploitation überzugehen.
Wie wird die Spielsituation kodiert?
Die Spielsituation wird durch ein Array von 9 Elementen dargestellt, wobei jedes Element den Zustand eines Feldes auf dem Spielfeld repräsentiert (0 für leer, 1 für Spieler I, 2 für Spieler II). Diese Darstellung wird in eine eindeutige Zahl (einen Situationscode) umgewandelt, indem eine Zahl zur Basis 3 erstellt und dann in eine Dezimalzahl konvertiert wird. Diese Dezimalzahl dient als Zeilennummer in der Q-Wert-Tabelle.
Wie werden die Q-Werte nach jedem Spielzug aktualisiert?
Die Q-Werte werden nach jedem Spielzug basierend auf der folgenden Formel aktualisiert: w_neu = w + alpha * (r + gamma * max(w') - w), wobei w_neu der neue Q-Wert, w der alte Q-Wert, alpha die Lernrate, r das Reinforcement, gamma der Diskontierungsfaktor und max(w') das Maximum der Q-Werte für die nächste Spielsituation ist.
Was passiert bei der Endbewertung, wenn das Spiel beendet ist?
Die Endbewertung verwendet dieselbe Aktualisierungsformel wie während des Spiels. Allerdings wird das Maximum der Q-Werte der "nächsten" Situation (die es nicht gibt, da das Spiel beendet ist) als ein Grenzwert berechnet, der sicherstellt, dass die Q-Werte korrekt aktualisiert werden, um einen optimalen Lernprozess zu gewährleisten. Dieser Grenzwert wird hergeleitet aus dem Reinforcement und dem Diskontierungsfaktor. Er entspricht bei Sieg dem Grenzwert der Q-Werte, um einen optimalen Lernvorgang zu gewährleisten: w_neu geht gegen -(r/(g-1)).
- Arbeit zitieren
- Sven Hubert (Autor:in), 2000, Umsetzung einer KI für das Spiel "TicTacToe" mit Hilfe von Reinforcement- oder Q-learning, München, GRIN Verlag, https://www.grin.com/document/102354
