© Rawpixel.com/Shutterstock.com
Classic Games Reloaded – Teil 10

Neuronale Netzwerke spielen Tic Tac Toe


Im heutigen Artikel werde ich damit beginnen, Ihnen zu demonstrieren, wie sich neuronale Netzwerke im Rahmen der Spieleentwicklung einsetzen lassen. In diesem Zusammenhang werden wir uns zwei unterschiedliche Trainingsmethoden anschauen, mit denen sich ein untrainiertes Netzwerk in einen Meister des Tic-Tac-Toe-Spiels verwandeln lässt. Darüber hinaus werden wir auch noch auf die sogenannten Convolution-basierten neuronalen Netzwerke zu sprechen kommen, da diese nicht nur im Bereich der Objekt- und Mustererkennung wahre Wunder vollbringen, sondern auch bei komplexeren Spielen stets den Überblick über das Spielgeschehen behalten.

Es sei einmal dahingestellt, ob sich der Film „War-Games – Kriegsspiele“ aus dem Jahr 1983 zu den Filmklassikern zählen lässt. Sehenswert ist der Film allemal, auch wenn er mittlerweile ein wenig wie aus der Zeit gefallen scheint. Über die Botschaft, die uns der Film vermitteln möchte, wird es in der Öffentlichkeit heutzutage wohl keinen Dissens mehr geben. Oder möchte jemand etwa allen Ernstes behaupten, dass man aus einem atomaren Schlagabtausch als Gewinner hervorgehen kann? Allerdings beinhaltet der Film auch einige Elemente, die zwar im Jahr 1983 wie pures Science-Fiction gewirkt haben dürften, über die sich KI-Forscher in der heutigen Zeit aber durchaus den Kopf zerbrechen: Welches Potenzial steckt in der künstlichen Intelligenz und welche Fortschritte werden wir auf diesem Gebiet in der näheren Zukunft wohl noch erzielen? Der heimliche Star des Films ist zweifelsohne der lernfähige NORAD-Computer WOPR (War Operation Plan Response), welcher dazu verdonnert wurde, tagein, tagaus mögliche Szenarien für einen atomaren Schlagabtausch durchzurechnen. Und obwohl der Computer eigentlich lernfähig ist, scheint es ihm nicht möglich zu sein, aus der Vielzahl gescheiterter Simulationen die einzig sinnvolle Schlussfolgerung zu ziehen: Bei einem atomaren Schlagabtausch gibt es keine Gewinner. Auf dem Höhepunkt des Spannungsbogens beginnt der Computer auf Befehl hin, alle nur denkbaren Partien Tic Tac Toe im Spiel gegen sich selbst zu analysieren, bis er schließlich zum Ergebnis kommt, dass sich das Spiel nicht gewinnen lässt, sofern beide Spieler im Verlauf einer Partie keine Fehler begehen. Zugegeben, der nun folgende Analogieschluss – dass sich auch ein Atomkrieg nicht gewinnen lässt – gehört nach wie vor ins Reich der Science-Fiction. Allerdings dürften sich einige der Zuschauer, die sich für das Thema künstliche Intelligenz interessiert haben, wahrscheinlich auch noch mit einer ganz anderen Frage auseinandergesetzt haben: Wie genau hat der Computer eigentlich das Spiel Tic Tac Toe erlernt? Auf ein klassisches KI-Verfahren wie den Minimax-Algorithmus (siehe hierzu den Artikel „Classic Games Reloaded, Teil 5“; Entwickler Magazin, 4.2019) dürfte der Computer wohl eher nicht zurückgegriffen haben. Da derartig hochentwickelte Computerprogramme heutzutage unter anderem auf diversen neuronalen Netzwerken basieren, wäre es so gesehen doch einmal eine gleichermaßen lehrreiche wie unterhaltsame Beschäftigung, ein solches Netzwerk mit Hilfe verschiedener Trainingsmethoden in einen perfekten Tic-Tac-Toe-Spieler zu verwandeln. Los geht’s!

Tic Tac Toe aus der Perspektive eines neuronalen Netzwerks

Im Grunde genommen lassen sich sämtliche Informationen einer einzelnen Tic-Tac-Toe-Brettstellung (Game State) in einem klitzekleinen Array hinterlegen, welches gerade einmal aus neun Elementen besteht. Um die Zustände der einzelnen Spielfelder zu charakterisieren, könnte man in diesem Zusammenhang beispielsweise auf die nachfolgend genannten Zahlenwerte zurückgreifen:

  • Ein leeres Spielfeld wird durch eine 0 repräsentiert.

  • Ein von Spieler 1 (X) besetztes Spielfeld wird durch eine 1 repräsentiert.

  • Ein von Spieler 2 (O) besetztes Spielfeld wird durch eine -1 repräsentiert.

Die Verwendung von unterschiedlichen Zahlenwerten birgt jedoch den Nachteil, dass die Berechnung des Aktivierungszustands eines Neurons für Spieler 1 zu einem anderen Ergebnis führt als für Spieler 2. Um dieser Problematik entgegenzuwirken, bietet sich stattdessen die Verwendung eines erweiterten Input-Arrays mit 18 Elementen an. In den ersten neun Arrayelementen wird zunächst die Brettstellung des ersten Spielers gespeichert:

  • Ein von Spieler 1 (X) besetztes Spielfeld wird durch eine 1 repräsentiert.

  • Ein Spielfeld, welches nicht von Spieler 1 besetzt ist, wird durch eine 0 repräsentiert.

In den zweiten neun Arrayelementen wird hingegen die Brettstellung des zweiten Spielers hinterlegt:

  • Ein von Spieler 2 (O) besetztes Spielfeld wird durch eine 1 repräsentiert.

  • Ein Spielfeld, welches nicht von Spieler 2 besetzt ist, wird durch eine 0 repräsentiert.

Im Unterschied zum eingangs betrachteten Input-Array mit seinen neun Elementen werden in der zweiten Variante unseres Input-Arrays keine expliziten Informationen über die noch unbesetzten Spielfelder gespeichert. Da diese zusätzlichen Informationen für die Bewertung einer Brettstellung durchaus von Vorteil sein können, würde sich alternativ auch die Verwendung eines auf 27 Elemente erweiterten Input-Arrays anbieten. In den ersten neun Elementen dieses Arrays wird zunächst wiederum die Brettstellung des ersten Spielers hinterlegt:

  • Ein von Spieler 1 (X) besetztes Spielfeld wird durch eine 1 repräsentiert.

  • Ein Spielfeld, welches nicht von Spieler 1 besetzt ist, wird durch eine 0 repräsentiert.

Auch was die zweiten neun Array-Elemente betrifft, bleibt alles beim Alten:

  • Ein von Spieler 2 (O) besetztes Spielfeld wird durch eine 1 repräsentiert.

  • Ein Spielfeld, welches nicht von Spieler 2 besetzt ist, wird durch eine 0 repräsentiert.

In den dritten neun Array-Elementen können wir dann zusätzlich noch speichern, welche der Spielfelder bereits besetzt oder noch frei sind:

  • Ein leeres Spielfeld wird durch eine 1 repräsentiert.

  • Alle besetzten Spielfelder werden durch eine 0 repräsentiert.

Training eines neuronalen Netzwerks mittels Imitation Learning

Menschen und Tiere verbessern ihre Fähigkeiten für gewöhnlich in erster Linie durch Beobachtung und Nachahmung. Wenn wir ein Spiel wie Tic Tac Toe oder Schach erlernen möchten, dann lassen wir uns normalerweise zunächst einmal die Spielregeln erklären. Die ersten Partien werden wir in der Regel zwar verlieren, allerdings werden wir dank der Anleitung durch unseren Trainingspartner mit der Zeit ein Gespür dafür entwickeln, welche Spielzüge unsere Siegchancen verbessern und auf welche Züge man tunlichst verzichten sollte.

Im Rahmen unseres mainPlayingNeuralNetTicTacToe-Programmbeispiels werden wir nun auf den zuvor beschriebenen Prozess des sogenannten Imitationslernens (Imitation Learning) zurückgreifen, um einem neuronalen Netzwerk sämtliche Spielzüge beizubringen, mit deren Hilfe sich eine Tic-Tac-Toe-Partie wenn möglich siegreich beenden lässt. Das Training erfolgt mittels Backpropagation auf Basis von 1000 Spielen (Minimax-Algorithmus gegen Zufallsspieler). Das Trainingsziel ist erreicht, wenn unser neuronales Netz dazu in der Lage ist, den Minimax-Algorithmus in möglichst perfekter Weise nachzuahmen. Erwähnt sei noch, dass wir dem Netzwerk sämtliche Informationen über die jeweiligen Brettstellungen in Form des zuvor beschriebenen 18-Element-Input-Arrays präsentieren. Kommen wir nun auf die Details der Implementierung zu sprechen. Da es sich bei Tic Tac Toe zugegebenermaßen um ein doch recht schlichtes Spiel handelt, können wir den kompletten Spielablauf einer Partie innerhalb einer einfachen do-while-Spielschleife implementieren:

do // Beginn eines neuen Spiels { // [Game Logic] } while (true); // Ende eines laufenden Spiels

Bevor wir unser neuronales Netzwerk trainieren können, müssen zunächst einmal die bereits angesprochenen 1 000 Trainingsspiele aufgezeichnet werden. Wie genau das funktioniert, schauen wir uns nun einmal für den Fall an, dass der KI-Spieler den ersten Spielzug ausführt (NeuralNetPlayer1):

for (uint32_t i = 0; i < NumTrainingGames; i++) { uint32_t moveCounter = 0; GameState.Reset_Bord(); // [Aufzeichnung der einzelnen Tic-Tac-Toe-Partien] }

Im Rahmen des eine Partie eröffnenden Spielzugs wird der erste Spielstein immer auf dieselbe Spielfeldposition (Koordinaten: 0, 0) gesetzt:

if (moveCounter == 0) GameState.Make_Move(0, 0, ConstBoardSymbol_Player1);

Sofern im weiteren Spielverlauf ein siegbringender Zug möglich ist, wird dieser natürlich mit Hilfe der AIPlayer_MakeWinMoveIfPossible()-Funktion auch ausgeführt. Falls ein solcher Zug allerdings nicht möglich ist, wird zunächst der nächstbeste Zug ermittelt. In diesem Zusammenhang greift die Find_BestMovePlayer1()-Funktion auf den bereits angesprochenen Minimax-Algorithmus zurück:

else { if (AIPlayer_MakeWinMoveIfPossible(&GameState, ConstBoardSymbol_Player1) == false) { GameState.Get_BoardData(Board); CMove bestMove = Find_BestMovePlayer1(Board); GameState.Make_Move(bestMove.row, bestMove.column, ConstBoardSymbol_Player1); }}

Nachdem der Minimax-Spieler seinen Spielzug ausgeführt hat, können wir diesen für das spätere Training aufzeichnen:

TrainingGameArray[i].Record_Move(GameState.LastMove_Row, GameState.LastMove_Column); moveCounter++;

Im Fall, dass der zuvor ausgeführte Zug zum Spiel-ende geführt hat, kann die Spielschleife verlassen werden:

if (Check_If_TrainingGame_Is_Finished(&GameState) == true) break;

Im nächsten Schritt führt der Gegenspieler einen zufällig generierten Spielzug aus, der selbstverständlich ebenfalls aufgezeichnet wird:

AIPlayer_RandomMove(&GameState, ConstBoardSymbol_Player2); TrainingGameArray[i].Record_Move(GameState.LastMove_Row, GameState.LastMove_Column); moveCounter++;

Sofern der zuvor von Spieler 2 ausgeführte Zug zum Ende des Spiels geführt hat, kann die Spielschleife verlassen werden. Andernfalls ist wiederum Spieler 1 mit seinem nächsten Zug an der Reihe:

if (Check_If_TrainingGame_Is_Finished(&GameState) == true) break;

Kommen wir nun auf die Trainingsphase zu sprechen. Mit Hilfe der zuvor aufgezeichneten Trainingsspiele werden wir ein neuronales Netzwerk so lang trainieren, bis es schließlich in der Lage dazu ist, unseren Minimax-Spieler in möglichst perfekter Weise zu imitieren:

for (uint32_t e = 0; e < maxEpochs; e++) { epoch++; error = 0.0f; for (uint32_t i = 0; i < NumTrainingGames; i++) { // [Trainieren und lernen] } if (error < minTolerableError) break; }

Das neuronale Netz soll nach Abschluss des Trainings später einmal die jeweils bestmöglichen Spielzüge ausführen können. Im Verlauf der Trainingsphase werden die vom Netzwerk vorgeschlagenen Spielzüge allerdings zunächst noch ignoriert. So gesehen wird der Zahlenwert (brainOutput), der sich am Ausgabeneuron abgreifen lässt, lediglich für die Fehlerberechnung (Abweichungen zwischen den Spielzügen des Minimax-Algorithmus gegenüber den Spielzügen des neuronalen Netzes) sowie für den Lernvorgang (Modifikation der synaptischen Plastizitätswerte) benötigt:

float brainOutput; TicTacToePlayingBrain.Calculate_Output(&brainOutput, GameState.BoardDataArray);

Nachdem das neuronale Netz die Berechnung des neuen Spielzugs abgeschlossen hat, wird zunächst der zuvor aufgezeichnete Spielzug ausgeführt, welcher im Vorfeld des Trainings mit Hilfe des Minimax-Algorithmus ermittelt wurde:

GameState.Make_Move(TrainingGameArray[i].MoveArray[moveCounter].row, TrainingGameArray[i].MoveArray[moveCounter].column, ConstBoardSymbol_Player1);

Unter Berücksichtigung des zuvor ausgeführten Spielzugs können wir schließlich mit dem Training unseres neuronalen Netzwerks fortfahren:

desiredMove = 0.01f + 0.1f * static_cast<float>(GameState.LastMove_Column + GameState.LastMove_Row * ConstNumBoardColumns); error += TicTacToePlayingBrain.Learning(&desiredMove); moveCounter++;

Als Nächstes müssen wir überprüfen, ob die aufgezeichnete Tic-Tac-Toe-Partie bereits vollständig durchgespielt wurde. Sollte dies der Fall sein, kann die Spielschleife verlassen werden:

if (moveCounter == TrainingGameArray[i].NumMoves) break;

Wenn die Tic-Tac-Toe-Partie allerdings noch nicht beendet ist, muss nunmehr der zuvor aufgezeichnete zufallsbasierte Zug des Gegenspielers ausgeführt werden:

GameState.Make_...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Gewinner-Teams

Wir bieten Lizenz-Lösungen für Teams jeder Größe: Finden Sie heraus, welche Lösung am besten zu Ihnen passt.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang