• Teilnehmer*innen
  
• Projektbeschreibung
  
• Ziele
  
• Dokumentation
  
• Fazit
  

Ameli Siedersleben
Finn Gonnermann
Kyrill Hoffmann
Laurin Dahm

Wir bauen ein Käsekästchenspiel! Und lassen einen Computer dieses Spiel lernen.
Käsekästchen wird normalerweise in langweiligen Unterrichtsstunden mit dem Banknachbar auf einem Blatt kariertem Papier gespielt. Dies wollen wir verändern in dem wir es digitalisieren und einem Computer mithilfe von Machine Learning beibringen.

Grundziele
Zuerst wollen wir das Spiel Käsekästchen in Python mit Hilfe von Pygame programmieren, sodass 2 Spieler an einem PC gegeneinander spielen können.

Weitere Ziele
Das Erlenen der Spielstrategie durch den Computer mithilfe von Machine Learning. So könnten im Idealfall Mensch und Computer gegeneinander Käsekästchen spielen.

Überlegung der Grundlagen des Spiels Käsekästchen anhand von Zeichnungen in Paint. Das Spiel ist für 2 Spieler gedacht. Pro Zug kann immer eine Seite in dem Gitter gemalt werden. Wenn ein Kästchen von allen 4 Seiten umschlossen ist, erhält derjenige der es geschlossen hat einen Punkt und direkt einen weiteren Zug. Ziel ist es mehr Kästchen zu erhalten als der Gegner.

Erste Schritte mit PyGame und Programmierung des Spielfeldes und des Mauszeigers. Als erste, provisorische Grundfläche haben wir folgende Zeichnung genommen. Und als Mauszeiger wird diese Grafik verwendet.

Bekanntmachung mit dem Mathesis WIKI und Gestaltung der Projektseite und der ersten Einträge.

Programmierung des Spiels abgeschlossen. Somit können jetzt schon 2 Spieler an einem Computer spielen. Hier gibts den Code dafür. Im Untenstehenden Video sieht man die Visualisierung des Spiels.(Beide Spieler wurden hierbei von einer Person gespielt)

.

Weiterhin recherchierten wir nach möglichen Gewinnstrategien im Spiel. Zuletzt haben wir uns informiert welches Machine Learning packages in Python zu unserem Projekt am besten passen würden.

Obenstehende Grafiken wurden verworfen. Code wurde verändert um für das Machine Learning besser zu funktionieren. Wir werden versuchen mit Neat(einer Python-Bibliothek für neuronale Netze) dem Computer Käsekästchen beizubringen. Neuronale Netze bestehen grundlegend aus 3 verschiedenen Ebenen. Input-Layer, Hidden-Layers und Output-Layer.

Input sind Eingaben, Output ist die Ausgabe bzw. das Ergebnis. Der eigentlich wichtige Teil sind die Hidden-Layers, wo auch das eigentliche Verarbeiten abläuft. Hierfür wird mit verschiedenen Parametern gearbeitet, um am Ende präzise eine Entscheidung zu treffen. Diese Funktion (Die „Blackbox“) übernimmt in unserem Beispiel zu einem großen Teil die Pythonbibliothek Neat. Neat funktioniert als Evolutionäres Neuronales Netz und entwickelt sich von Generation zu Generation weiter, vergrößert oder verkleinert die Menge an Neuronen oder stellt Parameter anders ein. Der Benutzer muss „nur“ den Code passend für Neat umschreiben und in einer Konfigurationsdatei einige Parameter richtig einstellen. Den Rest macht Neat dann von allein. Somit ist es auch für uns als Anfänger relativ gut möglich einen Machine Learning Algorithmus zu erstellen.

Wir haben uns ein Bild zu KI, deren Anwendung und Funktionsweise gemacht. Außerdem haben wir einen Vortrag der Laborleiterin zu Neural Networks gehört. Wir haben folgende Videos/Tutorials zur Hilfe gezogen:

Allgemeines zu neuronalen Netzen
Für das allgemeine Verständnis von Neuronalen Netzwerken.

Tutorial für Neat in Flappy Bird
Für das Verständnis der Python-Bibliothek Neat.

Spiele mit KI verbinden
Beispiele von KIs in anderen Spielen und der Fitnesspunkte.

Umprogrammieren des Spiels in Arrays, damit die KI nicht mit der Visuellen Darstellung arbeiten muss.(Verringert die Laufzeit)
Auf der linken Seite sind die Arrays, der Übersicht halber, übereinander zu sehen. [0] steht für False, also dass eine Linie noch nicht gesetzt ist. True bedeutet, dass eine Linie gesetzt ist, ganz gleich von welchem Spieler(Da dies für das Spiel irrelevant ist). Rechts sieht man das, zu dem Array zugehörige, Spielfeld.

Erste Versuche der Implementierung von Neat in unseren Code. Bevor Neat in den Code implementiert wird, müssen einige Sachen beachtet werden. Zuerst wird die Konfigurationsdatei benötigt, welche man unter diesem Link findet. Hier nur ein kleiner Ausschnitt davon.

Einige wichtige Größen müssen hier eingestellt werden. Dazu zählen pop_size und fitness_threshold. Pop_size gibt die größe der Population, also der Menge der einzelnen Teil-KIs, an und fitness_threshold gibt die Obergrenze an zu erreichender Fitness an. Fitness ist hierbei ein Wert, der dafür steht wie effektiv eine KI ist. Pro eingenommenes Kästchen erhält die KI eine bestimmte Menge an Fitnesspunkten. Wenn fitness_threshold überstiegen wurde, bricht das Programm ab und die KI ist für die eingestellten Werte finalisiert. In dieser Konfigurationsdatei gibt außerdem noch sehr viele weitere Einstellungen, die wir hier aber nicht weiter erklären wollen.

Mit dieser Config-Datei können wir uns nun des Codes annehmen.

Dafür müssen zuerst Variablen für Genome und Netze erstellt werden in welchen dann Neat die für die KI wichtigen Genome (Infos zum Spielverhalten) und Neuronale Netze zwischenspeichert.

Des Weiteren muss dieses Codefragment immer enthalten sein. Es bringt die oben genannten Einstellungen in unseren Code hinein.

Zuletzt muss noch die run(n) Funktion definiert und aufgerufen werden, in der mit n die Anzahl der Generationen definiert wird. Also wie oft soll das Programm durchlaufen.

Ein weiterer Punkt unseres Tagesplans war die Einbindung von Threads in unsere Arbeit. Treads sind Ausführungsreihenfolgen eines Programms. Die Befehle, die unsere Threads verfolgen starten für jedes Spiel abwechselnd die KIs. Wir wollen 2 KIs gegeneinander spielen lassen, damit für den Lernprozess nicht ständig jemand vor dem PC sitzen muss uns dieser generell schneller Abläuft. Somit brauchen wir auch 2 Threads, welche Abwechselnd Spiele spielen. Da wir in Neat 15 Individuen pro Generation eingestellt haben, gibt es pro Evolutionsstufe mithilfe der Threads 15 * 15 = 225 Spiele (da jedes Individuum der ersten KI gegen jedes Individuum der zweiten KI spielt).

So kann man die Arbeit der Threads in unserem Beispiel erklären. KI1 und KI2 werden von Threads 1 und 2 gestartet und spielen in game gegeneinander.

Threading zum ansteuern mehrerer KIs(wie bei uns)

Nach der Implementierung der KI mussten noch einige Fehler behoben werden… Einiges hat nicht ganz so funktioniert wie es sollte. Also mussten wir Debuggen.Hier findet ihr den fertigen Code mit einigen Erklärungen dazu.

Fertigstellung einer KI welche gegen den Menschen spielen kann. Wir haben das Programm mit verschiedenen anzahlen an Generationen durchlaufenlassen und die daraus entstehenden KI`s getestet. Die KI , welche das Spiel über 100 Generationen gelernt hat, ist in der Lage das Spiel zu gewinnen, allerdings nur wenn der menschliche Spieler sich sehr wenig Mühe gibt. Der Code für das erstellen der KI und das einmalige Spiel gegen sie ist Hier zu finden. In Codezeile 906 kann man die Anzahl der Generationen, welche Neat durchspielen soll einstellen. Die generierte Künstliche Intelligenz wird dann in einer PKL-Datei gespeichert und kann zu einem Späteren Zeitpunkt mit folgender Datei eingelesen und gegen sie gespielt werden. Als Beispiel finden Sie Hier die KIs für 3 und 100 Generationen. Einen Durchlauf mit 1000 Generationen wird gerade berechnet und könnte demnächst folgen.

Überarbeitung des MathesisWIKI Eintrags. Implementierung eines Algorithmus, der gegen die KI spielt.

Nach einiger Rechenzeit gab es dann auch eine KI, die an dem Algorithmus gelernt hat. Diese ist jedoch auch nicht überragend.

Das gesamte Protokoll findet ihr hier.

Haben wir unsere Ziele erreicht?

Wir haben ein simples Käsekästchen-Spiel programmiert. Die Spielfeldgröße kann frei gewählt werden und es hat eine einfache grafische Darstellung. Mit Unserer Neat-Implementierung können wir KIs trainieren, gegen die wir auch spielen können. Aber nach mehr als 100 Generationen Entwicklung hat die KI immer noch kaum sinnvolle Züge gemacht. Allerdings haben auch wir einen Algorithmus geschrieben der halbwegs vernünftige Züge macht.

Was haben wir gelernt?

Wir haben beim arbeiten an unserem Projekt erste Erfahrungen mit KI-Entwicklung und der Funktionsweise von einfachen neuronalen Netzwerken sowie Threading gesammelt und generell das Programmieren in Python trainiert.

Das Spiel Käsekästchen ist komplexer als es aussieht. Wahrscheinlich ist der Neat-Algorithmus nicht Ideal für Käsekästchen oder auch Brettspiele im allgemeinen. Eine KI für ein simples Videospiel zu entwickeln wäre wohl ein erfolgversprechenderes Projekt als unseres. Besonders gut dafür geeignet sind Spiele mir eher statischen Level und möglichst wenigen Entscheidungs-Möglichkeiten für die KI. Außerdem gibt es online viel Material dazu wie man Kis, für Spiele wie Mario oder Sonic, erstellen kann.