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 Erlernen der Spielstrategie durch den Computer mithilfe von Machine Learning. So könnten im Idealfall Mensch und Computer gegeneinander Käsekästchen spielen.

Das Spiel besteht aus einem Spielfeld, dass in kleinere Felder unterteilt ist (in unserem Fall in 9). Das Spiel wird abwechselnd in Zügen gespielt, wer am Zuge ist, muss eine Linie beanspruchen (also die Grenze zwischen zwei kleineren Feldern im Feld). Wer mit seinem Strich ein Feld schließt (also den letzten Strich um ein Feld beansprucht) oder zwei Feld schließt, gewinnt das Feld und ist sofort noch einmal am Zuge. Das Spiel endet, wenn alle Linien beansprucht wurden, gewonnen hat die Person die, die meisten Felder hat.

Wir haben das Spiel zunächst in drei wesentliche Elemente gegliedert: Linien, Felder und eine Relation die jedem Feld die seine Linien zuordnet. In Python haben wir die Felder und Linien als Pygame-Sprite-Klasse (Eine Art Grundgerüst für grafische Objekte) implementiert.

Beide haben pygamespezifische Attribute, so wie eine Nummer, eine Farbe und die Information über den Zustand, also ob die Linie schon angeklickt wurde, bzw. ob ein Spieler das Feld schon gewonnen hat. Dazu kommt noch eine Update Methode,die auf gerufen wird, wenn sich der Zustand des Objektes ändern soll. Das Objekt gilt nun als gesetzt und es wird die Farbe geändert.

Für die Relation haben wir einen Dictionary verwendet, der jedem Feld die vier Linien zuordnet, die es um schließen. Die Linien und Felder werden in Pygame-Sprite-Gruppen initialisiert. Um weitere Daten für das Spiel und die Darstellung zu speichern und verarbeiten haben wir eine „Game“-Klasse erstellt. Ansonsten haben wir noch einige Getter-Funktionen, die es erleichtern per Nummer auf Linien und Felder zuzugreifen.

Diesen ganzen kleinen Bausteinen folgt als Letztes die „Main“-Funktion. Als Erstes wird die Initialisierung der Sprite-Guppen und des Game-Objekts ausgeführt. Pygame wird initialisiert und es öffnet sich ein Fenster für die Grafikoberfläche. Das Eigentliche Spiel läuft dann im Game-Loop ab. Hier werden mit den Event-Funktionen von Pygame die Eingaben der Spieler Erfasst. Bei einem Mausklick wird überprüft ob sich an der Position Cursors eine Linie befindet. Wenn diese Linie bisher noch nicht gesetzt ist wird ihr Zustande geändert und es werden Funktionen des Game-Objekts aufgerufen. Anschließend wird überprüft ob sich der Zustand es Spielfelds verändert hat, ggf. der Neue Punktestand angezeigt und es wir kontrolliert ob das Spiel abgeschlossen wurde, also keine Züge mehr möglich sind. Am Ende des Game-Loops wird mit den Pygame-Grafik-Funktionen das Spielfeld angezeigt.

In unserem Fall sind mit Neuronale Netzen, künstliche Neuronale Netze (kNN) gemeint. Sie Algorithmen, die dem menschlichen Gehirn nachempfunden sind. Sie besteht aus Neuronen (Knotenpunkten) die miteinander verknüpft sind, dabei ist der Output des einen Neurons der Input des Nächsten. Informationen, die von anderen Neuronen oder von außen aufgenommen wurden (bei uns durch das übergebene Spielfeld), werden modifizieren und als Ergebnis ausgeben. Dies erfolgt über drei verschiedene Schichten: den Input (Eingabeschicht), den Output (Ausgabeschicht) und die sogenannten Hidden-Neuronen (verborgene Schichten).

Neat ist eine Pythonbibliothek und funktioniert als evolutionäres Neuronales Netz. Ein evolutionäres/genetisches Neuronales Netz orientiert sich an der Grundidee von Darwins Evolutionstheorie und wird genutzt, um Probleme zu lösen. Lösungsmöglichkeiten werden durch Individuen/Genome beschrieben mit einer Fitness. Hierbei handelt es sich um eine reelle Zahl, die sagt aus wie effektiv ein Individuum/Genom ist, je effektiver eine Lösungsmöglichkeit ein Problem löst des so höher ist sie(Fitness-Funktion). Im Laufe der Evolution, über mehrere Generationen verändern sich die Genome, auf Grund von Selektion, Mutation, Kombination. Parameter wie Mutationsrate, Generation, Population und viele weitere kann man in Neat, genau genommen in der Konfigurationsdatei, konfigurieren.

Um einen Besseren Überblick zu bekommen sollte man den Neat Ablauf kennen:

1. Initialisierung - Eine Zufällige Anfangspopulation wird erstellt

2. Evaluation - Jedem Individuum wird mit der Fitness-Funktion eine Fitness zu gewissen

3. Selektion & Kombination - Die Individuen mit den schlechtesten Fitness-werten werden gelöscht, die anderen werden miteinander kombiniert und geklont um auf die Anfangspopulationsgröße zukommen

4. Mutation - Ein Teil oder alle Individuen mutieren, wenn die vorher festgelegte maximale Fitness oder Generation erreicht wurde, endet das Programm, sonst folgt Punkt 2.

Multithreading ist ein Programmierkonzept das die quasi gleichzeitige Ausführung mehrerer Programmabschnitte ermöglicht. Einzelne Teilprozesse werden sogenannten Threads zugeordnet, die in einer kontrollierten Reihenfolge ausgeführt werden. So können mehrere Prozesse scheinbar parallel ablaufen, obwohl ein Kern der CPU zur gleichen Zeit nur einen einzelnen abarbeiten kann. In Python kann diese Nebenläufigkeit mithilfe des „threading“-Moduls umgesetzt werden.

Wir haben uns als Gruppe schnell für eine Künstliche Intelligenz als Lösungsansatz entschieden. Unsere Gruppe hat sich vor allem durch ein gemeinsames Interesse an KI`s gebildet. Als wir uns Auf das Projekt Käsekästchen geeinigt haben, hatten wir die Möglichkeit anstelle einer KI einen herkömmlichen Algorithmus zu schreiben. Wir haben durch Recherche im Internet herausgefunden, dass sich das Spiel Mathematisch Lösen lässt. Demnach wäre ein Algorithmus, welcher das Spielfeld analysiert, die Gewinnchancen für jeden möglichen Zug errechnet und den besten ausführt, programmierbar. Sodass die Züge je nachdem ob der Algorithmus oder der Spieler beginnt, zu einem Sieg oder zumindest einem Unentschieden für den Computer führen würde. Wir haben uns Allerdings dazu entschieden eine Künstliche Intelligenz zu programmieren, und den Mathematischen Algorithmus als Ausweichplan zu nehmen, da wir uns gerne mit dem Thema und der Programmierung einer KI auseinandersetzen wollten. Darüber hinaus erschien es uns eine größere Herausforderung eine KI zu Programmieren als einen „einfachen“ Algorithmus zu schreiben.

Hier findet ihr unsere Finale Datei, die eine KI erzeugen kann. Und in dieser ZIP findet ihr ein Programm zum erneuten spielen gegen eine bereits abgespeicherte KI.

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.