Einem Agenten beibringen, Tic-Tac-Toe durch Selbstspiel zu meistern | von Sébastien Gilbert | September 2023


Überraschenderweise wird ein Software-Agent des Spiels nie müde.

Ah! Grundschule! Dies war die Zeit, in der wir wertvolle Fähigkeiten wie Lesen und Schreiben, Rechnen und Tic-Tac-Toe optimal erlernten.

Foto von Sonnenwende Hannan An Unsplash

Mit einem Freund ein Tic-Tac-Toe-Match zu spielen, ohne vom Lehrer erwischt zu werden, ist eine Kunst. Sie müssen das Spielblatt diskret unter dem Schreibtisch weitergeben und dabei den Eindruck erwecken, dass Sie sich aufmerksam mit dem Thema befassen. Der Spaß lag wahrscheinlich mehr an der Undercover-Operation als am Spiel selbst.

Wir können einem Software-Agenten nicht die Kunst beibringen, nicht im Klassenzimmer erwischt zu werden, aber können wir einem Agenten beibringen, das Spiel zu meistern?

In meinem vorherigen Beitrag haben wir einen Agenten untersucht, der das Spiel lernt SumTo100 durch Selbstspiel. Es war ein einfaches Spiel, das es uns ermöglichte, den Zustandswert anzuzeigen, was uns dabei half, eine Vorstellung davon zu entwickeln, wie der Agent das Spiel lernt. Mit Tic-Tac-Toe gehen wir einen viel größeren Zustandsraum an.

Den Python-Code finden Sie in dieses Repository. Das Skript, das das Training durchführt, ist learn_tictactoe.sh:

#!/bin/bash
deklariere -i NUMBER_OF_GAMES=30000
deklarieren Sie -i NUMBER_OF_EPOCHS=5

export PYTHONPATH='./'

Python-Vorverarbeitung/generate_positions_expectations.py \
--outputDirectory=./learn_tictactoe/output_tictactoe_generate_positions_expectations_level0 \
--game=tictactoe \
--numberOfGames=$NUMBER_OF_GAMES \
--gamma=0,95 \
--randomSeed=1 \
--agentArchitecture=Keine \
--agentFilepath=Keine \
--opponentArchitecture=Keine \
--opponentFilepath=Keine \
--epsilons="[1.0]" \
--temperature=0

dataset_filepath="./learn_tictactoe/output_tictactoe_generate_positions_expectations_level0/dataset.csv"

Python train/train_agent.py \
$dataset_filepath \
--outputDirectory="./learn_tictactoe/output_tictactoe_train_agent_level1" \
--game=tictactoe \
--randomSeed=0 \
--validationRatio=0.2 \
--batchSize=64 \
--architecture=SaintAndre_1024 \
--dropoutRatio=0.5 \
--learningRate=0.0001 \
--weightDecay=0.00001 \
--numberOfEpochs=$NUMBER_OF_EPOCHS \
--startingNeuralNetworkFilepath=Keine

für Level in {1..16}
Tun
dataset_filepath="./learn_tictactoe/output_tictactoe_generate_positions_expectations_level${level}/dataset.csv"
Python-Vorverarbeitung/generate_positions_expectations.py \
--outputDirectory="./learn_tictactoe/output_tictactoe_generate_positions_expectations_level${level}" \
--game=tictactoe \
--numberOfGames=$NUMBER_OF_GAMES \
--gamma=0,95 \
--randomSeed=0 \
--agentArchitecture=SaintAndre_1024 \
--agentFilepath="./learn_tictactoe/output_tictactoe_train_agent_level${level}/SaintAndre_1024.pth" \
--opponentArchitecture=SaintAndre_1024 \
--opponentFilepath="./learn_tictactoe/output_tictactoe_train_agent_level${level}/SaintAndre_1024.pth" \
--epsilons="[0,5, 0,5, 0,1]" \
--temperature=0

deklarieren -i next_level=$((level + 1))
Python train/train_agent.py \
"./learn_tictactoe/output_tictactoe_generate_positions_expectations_level${level}/dataset.csv" \
--outputDirectory="./learn_tictactoe/output_tictactoe_train_agent_level${next_level}" \
--game=tictactoe \
--randomSeed=0 \
--validationRatio=0.2 \
--batchSize=64 \
--architecture=SaintAndre_1024 \
--dropoutRatio=0.5 \
--learningRate=0.0001 \
--weightDecay=0.00001 \
--numberOfEpochs=$NUMBER_OF_EPOCHS \
--startingNeuralNetworkFilepath="./learn_tictactoe/output_tictactoe_train_agent_level${level}/SaintAndre_1024.pth"

Erledigt

Das Skript durchläuft Aufrufe an zwei Programme:

Das Erlernen des Spiels durch den Agenten erfolgt über einen Zyklus aus der Generierung von Spielen und dem Training, um das Spielergebnis anhand des Spielstatus vorherzusagen:

Abbildung 1: Der Zyklus der Match-Generierung und des neuronalen Netzwerktrainings. Bild vom Autor.

Der Zyklus beginnt mit der Simulation von Spielen zwischen zufälligen Spielern, also Spielern, die zufällig aus der Liste der legalen Aktionen in einem bestimmten Spielzustand auswählen.

Warum generieren wir zufällig gespielte Spiele?

Bei diesem Projekt geht es um das Lernen durch Selbstspielen, daher können wir dem Agenten keine a priori Informationen darüber geben Spielanleitung. Da der Agent im ersten Zyklus keine Ahnung von guten oder schlechten Zügen hat, müssen die Übereinstimmungen durch Zufallsspiele generiert werden.

Abbildung 2 zeigt ein Beispiel für ein Match zwischen zufälligen Spielern:

Abbildung 2: Beispiel eines zufällig gespielten Tic-Tac-Toe-Matches. Bild vom Autor.

Welche Lektion können wir aus der Beobachtung dieses Spiels lernen? Aus der Sicht des „X“-Spielers können wir davon ausgehen, dass dies ein Beispiel für ein schlechtes Spiel ist, da es mit einer Niederlage endete. Wir wissen nicht, welche Züge für die Niederlage verantwortlich sind, also gehen wir davon aus alle Entscheidungen Die vom „X“-Spieler erstellten Dateien waren schlecht. Wenn einige Entscheidungen gut waren, setzen wir auf Statistiken (andere Simulationen könnten einen ähnlichen Zustand durchlaufen), um ihren vorhergesagten Zustandswert zu korrigieren.

Die letzte Aktion von Spieler „X“ erhält den Wert -1. Die anderen Aktionen erhalten einen diskontierten negativen Wert, der geometrisch um den Faktor γ (Gamma) ∈ [0, 1] abnimmt, wenn wir uns dem ersten Schritt nähern.

Abbildung 3: Zielwerte für Spielzustände. Bild vom Autor.

Staaten aus Spielen, die zu einem Sieg führten, erhalten ähnliche positive abgezinste Werte. Aus Ziehungen gezogene Staaten erhalten den Wert Null. Der Agent vertritt die Sichtweise sowohl des ersten als auch des zweiten Spielers.

Die Spielzustände sind Tensoren

Wir benötigen eine Tensordarstellung für den Spielzustand. Wir verwenden einen [2x3x3]-Tensor, bei dem die erste Dimension die Kanäle darstellt (0 für „X“ und 1 für „O“) und die beiden anderen Dimensionen die Zeilen und Spalten sind. Die Belegung eines (Zeile, Spalte)-Quadrats wird im (Kanal, Zeile, Spalte)-Eintrag als 1 kodiert.

Abbildung 4: Die Spielzustandsdarstellung durch einen [2x3x3]-Tensor. Bild vom Autor.

Die durch die Generierung von Übereinstimmungen erhaltenen Paare von (Zustandstensor, Zielwert) bilden den Datensatz, auf dem das neuronale Netzwerk in jeder Runde trainiert. Der Datensatz wird zu Beginn des Zyklus erstellt und nutzt dabei die Erkenntnisse aus früheren Runden. Während in der ersten Runde ein reines Zufallsspiel stattfindet, werden in den folgenden Runden nach und nach realistischere Matches generiert.

Dem Spiel Zufälligkeit verleihen

In der ersten Runde der Match-Generierung tritt man gegen zufällige Spieler an. In den folgenden Runden tritt der Agent gegen sich selbst an (daher „Selbstspiel“). Der Agent ist mit einem regressiven neuronalen Netzwerk ausgestattet, das darauf trainiert ist, den Spielausgang vorherzusagen, was ihm ermöglicht, die rechtliche Maßnahme auszuwählen, die den höchsten erwarteten Wert bringt. Um die Vielfalt zu fördern, wählt der Agent Aktionen basierend auf einem Epsilon-Greedy-Algorithmus aus: Mit der Wahrscheinlichkeit (1-ε) wird die beste Aktion ausgewählt; andernfalls wird eine zufällige Aktion ausgewählt.

Abbildung 5 zeigt die Entwicklung der Validierungsverluste über fünf Epochen für maximal 17 Trainingsrunden:

Abbildung 5: Die Entwicklung des Validierungsverlusts für verschiedene Trainingsrundenzahlen. Bild vom Autor.

Wir können sehen, dass die ersten paar Trainingsrunden einen schnellen Rückgang des Validierungsverlusts zeigen, und dann scheint es ein Plateau bei einem mittleren quadratischen Fehlerverlust von 0,2 zu geben. Dieser Trend zeigt, dass das neuronale Regressionsnetzwerk des Agenten den Ausgang eines gegen ihn selbst gespielten Spiels ausgehend von einem bestimmten Spielstatus besser vorhersagen kann. Da die Aktionen beider Spieler nicht deterministisch sind, ist die Vorhersagbarkeit des Spielausgangs begrenzt. Das erklärt, warum sich der Validierungsverlust nach einigen Runden nicht mehr verbessert.

Verbesserung von Runde zu Runde

Mit dem Spiel SumTo100, Wir könnten den Zustand in einem 1D-Gitter darstellen. Allerdings können wir mit Tic-Tac-Toe die Zustandswertentwicklung nicht direkt anzeigen. Um die Verbesserung zu messen, können wir den Agenten mit der vorherigen Version seiner selbst vergleichen und den Unterschied zwischen Gewinnen und Verlusten beobachten.

Wenn wir ε = 0,5 für die erste Aktion beider Spieler und ε = 0,1 für den Rest des Spiels verwenden und 1000 Spiele pro Vergleich durchführen, erhalten wir Folgendes:

Abbildung 6: Vergleich des Agenten mit seiner Vorgängerversion. Bild vom Autor.

Bis zu den 10 Trainingsrunden überstieg die Anzahl der Siege die Anzahl der Niederlagen (was eine Verbesserung zeigt). Danach verbesserte sich der Agent von Runde zu Runde nicht mehr.

Zeit zu sehen, wie unser Agent Tic-Tac-Toe spielt!

Ein nützliches Merkmal eines regressiven neuronalen Netzwerks ist die Möglichkeit, die Bewertung jedes legalen Schritts durch den Agenten anzuzeigen. Spielen wir ein Spiel gegen den Agenten und zeigen wir, wie er seine Optionen einschätzt.

Manuelles Spielen

Der Agent beginnt und spielt „X“:

Abbildung 7: Ein Spiel gegen den Agenten mit den Aktionsbewertungen. Bild vom Autor.

So wird man von einer seelenlosen Tic-Tac-Toe-Maschine brutal zerquetscht!

Sobald ich das „O“ in das Quadrat (1, 0) einfügte, stieg die erwartete Rendite von 0,142 auf 0,419 und mein Schicksal war besiegelt.

Mal sehen, wie es funktioniert, wenn der Agent als Zweiter spielt:

Abbildung 8: Ein Spiel gegen den Agenten, mit Aktionsbewertungen. Bild vom Autor.

Es ist nicht in die Falle getappt und das Spiel endete unentschieden.

Spiele gegen einen zufälligen Spieler

Wenn wir simulieren eine große Anzahl von Spielen gegen einen zufälligen Spieler, das ist, was wir bekommen:

Abbildung 9: Ergebnisse von 1000 Spielen gegen einen zufälligen Spieler. Bild vom Autor.

Von 1000 Spielen (der Agent spielte in der Hälfte der Spiele als Erster) gewann der Agent 950 Spiele, verlor niemanden und es gab 50 Unentschieden. Das ist kein Beweis dafür, dass unser Agent optimal spielt, aber er hat auf jeden Fall ein ordentliches Spielniveau erreicht.

Als Nachtrag zu Einen Agenten darin schulen, ein einfaches Spiel durch Selbstspiel zu meistern Wo das Spiel leicht zu knacken war und der Zustandsraum klein war, verwendeten wir dieselbe Technik, um Tic-Tac-Toe zu meistern. Obwohl dies immer noch ein Spielzeugproblem ist, ist der Zustandsraum von Tic-Tac-Toe groß genug, dass das regressive neuronale Netzwerk des Agenten benötigt wird, um Muster in den Zustandstensoren zu finden. Diese Muster ermöglichen die Verallgemeinerung für unsichtbare Zustandstensoren.

Der Code ist verfügbar in diesem Repository. Probieren Sie es aus und teilen Sie mir Ihre Meinung mit!



Quelllink

Hinterlasse eine Antwort

Deine Email-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *

Sie können diese HTML- Tags und -Attribute verwenden: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

de_DEGerman