Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

--- ws2021:kaesekaestchen [2021/04/09 15:11]
kyrill.ho
+++ ws2021:kaesekaestchen [2021/04/13 15:35] (aktuell)
kyrill.ho [Ziele]
@@ Zeile 2: / Zeile 2: @@
-==== Inhaltsverzeichnis ====
-  *  Teilnehmer*innen \\
-  *  Projektbeschreibung \\
-  *  Ziele \\
-  *  Dokumentation \\
-  * Fazit\\
+===== Teilnehmer*innen =====
-==== Teilnehmer*innen ====
 Ameli Siedersleben \\ Finn Gonnermann \\ Kyrill  Hoffmann\\ Laurin Dahm
-==== Projektbeschreibung ====
+===== Projektbeschreibung =====
 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.
-==== Ziele ====
+===== Ziele =====
 __ ** Grundziele ** __
 \\
@@ Zeile 23: / Zeile 16: @@
 __ ** 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.
+Das Erlernen der Spielstrategie durch den Computer mithilfe von Machine Learning. So könnten im Idealfall Mensch und Computer gegeneinander Käsekästchen spielen.
-==== Dokumentation ====
+===== Dokumentation =====
-== Tag 1 - 10.12.2020 ==
+=== So funktioniert das Käsekästchen-Spiel ===
-Ü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. \\
+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. \\
+{{ :ws2021:kasegrundlagen.png?300 |Grundlagen von Käsekästchen}} \\
+=== Wie funktioniert die Implementierung in Pygame? ===
-Erste Schritte mit PyGame und Programmierung des Spielfeldes und des Mauszeigers.
+Wir haben das Spiel zunächst in drei wesentliche Elemente gegliedert: Linien, Felder und eine Relation die jedem Feld die seine Linien zuordnet.
-Als erste, provisorische Grundfläche haben wir folgende Zeichnung genommen.
+In Python haben wir die Felder und Linien als Pygame-Sprite-Klasse (Eine Art Grundgerüst für grafische Objekte) implementiert.
-{{ :ws2021:kaesekaestchen_grundflaeche.jpg?200 |}}
-Und als Mauszeiger wird diese Grafik verwendet.
-{{ :ws2021:kaesekaestchen_crosshair.png?300 |}}
-== Tag 2 - 17.12.2020 ==
+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.
-Bekanntmachung mit dem Mathesis WIKI und Gestaltung der Projektseite und der ersten Einträge.
+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.
-== Tag 3 - 07.01.2021 ==
+Für die Relation haben wir einen Dictionary verwendet, der jedem Feld die vier Linien zuordnet, die es um schließen.
-Programmierung des Spiels abgeschlossen. Somit können jetzt schon 2 Spieler an einem Computer spielen.
+Die Linien und Felder werden in Pygame-Sprite-Gruppen initialisiert.
-{{:ws2021:kaesekaestchen_2spieler.zip|Hier}} gibts den Code dafür. Im Untenstehenden Video sieht man die Visualisierung des Spiels.(Beide Spieler wurden hierbei von einer Person gespielt) \\
+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.\\
-{{:ws2021:kaesekaestchen.mp4?1000 | Visualisierung unseren Codes}}
+{{:ws2021:kaesekaestchen.mp4?500|So sieht das ganze dann aus.}}
-.
-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.
+=== Was sind Neuronale Netze? ===
+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).\\
-== Tag 4 - 14.01.2021 ==
+{{ :ws2021:nnetze2.jpg?300 |Neuronales Netzwerk}}\\
-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. \\
-{{ :ws2021:nearal_networks.png?370 | Neuronales Netzwerk}} \\
-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.\\
+=== Was ist Neat? ===
-{{ :ws2021:blackbox.png?450 | Neat-Blackbox}}\\
+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 [[https://neat-python.readthedocs.io/en/latest/xor_example.html|Konfigurationsdatei]], konfigurieren.
+Um einen Besseren Überblick zu bekommen sollte man den Neat Ablauf kennen:\\
-== Tag 5 - 21.01.2021 ==
+.	Initialisierung
-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: \\
+-	Eine Zufällige Anfangspopulation wird erstellt
-[[https://www.youtube.com/watch?v=aircAruvnKk|Allgemeines zu neuronalen Netzen]] \\
+.	Evaluation
-Für das allgemeine Verständnis von Neuronalen Netzwerken.
+-	 Jedem Individuum wird mit der Fitness-Funktion eine Fitness zu gewissen
-[[https://www.youtube.com/watch?v=MMxFDaIOHsE&list=PLzMcBGfZo4-lwGZWXz5Qgta_YNX3_vLS2|Tutorial für Neat in Flappy Bird]] \\
+.	Selektion & Kombination
-Für das Verständnis der Python-Bibliothek Neat.
+-       Die Individuen mit den schlechtesten Fitness-werten werden gelöscht, die anderen werden miteinander kombiniert und geklont um auf die Anfangspopulationsgröße zukommen
+.	Mutation
+-       Ein Teil oder alle Individuen mutieren, wenn die vorher festgelegte maximale Fitness oder Generation erreicht wurde, endet das Programm, sonst folgt Punkt 2.
-[[https://www.youtube.com/watch?v=y7AKtWGOPAE|Spiele mit KI verbinden]] \\
+=== Kurze Erklärung zu Threads ===
-Beispiele von KIs in anderen Spielen und der Fitnesspunkte.
-== Tag 6 - 28.01.2021 ==
+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.
-Umprogrammieren des Spiels in Arrays, damit die KI nicht mit der Visuellen Darstellung arbeiten muss.(Verringert die Laufzeit) \\
+In Python kann diese Nebenläufigkeit mithilfe des „threading“-Moduls umgesetzt werden.
-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.
-{{ :ws2021:arrays_kaese.png?500 | Darstellung in Arrays}}
-== Tag 7 - 04.02.2021 ==
+=== Der Computer als Gegner - Warum eine KI ? ===
-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 [[https://neat-python.readthedocs.io/en/latest/xor_example.html | diesem Link]] findet. Hier nur ein kleiner Ausschnitt davon. \\
-{{ :ws2021:config.png?200 | Neat Kofigurationsdatei}}\\
- 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. \\
+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.
-Mit dieser Config-Datei können wir uns nun des Codes annehmen. \\
+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.
-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. \\
+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.
-{{ :ws2021:ki1implement.png?200 | Implementierung in den Code}} \\
-Des Weiteren muss dieses Codefragment immer enthalten sein. Es bringt die oben genannten Einstellungen in unseren Code hinein. \\
- {{ :ws2021:start_neural_network.png?200 | Neat-Startfunktion}} \\
-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).\\
-{{ :ws2021:grafik_ki_threads.png?370 | Verbindung mithilfe von Threads}}\\
-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.
-[[https://www.youtube.com/watch?v=olYdb0DdGtM|Threading zum ansteuern mehrerer KIs(wie bei uns)]]
-== Tag 8 - 11.02.2021 ==
-Nach der Implementierung der KI mussten noch einige Fehler behoben werden... Einiges hat nicht ganz so funktioniert wie es sollte. Also mussten wir Debuggen.{{:ws2021:kaesekizurerklaerung.zip|Hier}} findet ihr den fertigen Code mit einigen Erklärungen dazu.
-== Tag 9 - 18.02.2021 ==
-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 {{:ws2021:ki_generator.zip|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 {{:ws2021:kase_load_ki_test.zip| folgender Datei }} eingelesen und gegen sie gespielt werden.
-Als Beispiel finden Sie {{:ws2021:beispielkis.zip| Hier }} die KIs für 3 und 100 Generationen. Einen Durchlauf mit 1000 Generationen wird gerade berechnet und könnte demnächst folgen.
-== Tag 10 - 25.02.2021 ==
-Ü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. \\
-\\
-{{:ws2021:kaeseki.mp4?1000|Spiel gegen die KI}}\\
+=== Finale Datei ===
-==== [[Protokoll]] ====
+{{:ws2021:kaseki_finalfinal.zip|Hier}} findet ihr unsere Finale Datei, die eine KI erzeugen kann. Und in {{:ws2021:kase_load_ki_test.zip|dieser ZIP}} findet ihr ein Programm zum erneuten spielen gegen eine bereits abgespeicherte KI.
+===== Protokoll =====
+Das gesamte Protokoll findet ihr [[Protokoll| hier]] 8-).
-==== Fazit ====
+===== Fazit =====
 Haben wir unsere Ziele erreicht?

Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge