Mathesis Wiki

Unser Projektziel ist einen selbstlernenden Gegner zu programmieren, der mithilfe von maschinellem Lernen besser wird und so in einem Spiel gute Entscheidungen treffen und möglicherweise menschliche Spiele schlagen kann. Die Idee für so ein Projekt ist nicht die neuste. So gewann das Computerprogramm Deep Blue erstmals schon 1997 gegen den damaligen Schachweltmeister Kasparow und konnte so ein komplexes Spiel gegen einen starken menschlichen Spieler gewinnen, auch wenn das Programm kaum auf künstliche Intelligenz zurückgriff. Jahre später gelang es Deep Mind einen der weltbesten Go-Spieler 2016 zu besiegen. Dabei benutzte das Programm neuronale Netze und konnte Go, ein Spiel noch komplexer als Schach, meistern. Nun stellten wir uns die Frage, ob wir ebenfalls mit Hilfe von maschinellem Lernen ein Programm entwickeln können, um ein simpleres Spiel zu meistern. Dafür entschieden wir uns für Vier gewinnt. Zudem haben wir uns vorher in Vorbereitung an Tic Tac Toe gesetzt, um zum einen die Grundlagen von maschinellem Lernen zu lernen und zu verstehen und zum anderen die für unser Projekt benötigten Python Kenntnisse zu erwerben.

Um unser Projekt zu realisieren, haben wir uns für Reinforcement Learning, zu deutsch bestärkendes Lernen, entschieden. Dies ist eine Unterkategorie von machinellem Lernen und gehört zu der Gruppe Überwachtes Lernen. Grundsätzlich geht es bei maschinellem Lernen darum, anhand von Beispielen zu lernen und anschließend zu einer Verallgemeinerung des Problems zu kommen und dadurch unbekannte Daten einschätzen und bewerten zu können. Bei Überwachtem Lernen wird dem Programm zu den Eingaben auch Funktionswerte gegeben, sodass das Programm im Laufe des Lernens Zusammenhänge erkennen kann. Beim Bestärkendem Lernen wird dabei dem Programm, bzw. dem Agentem, nicht die beste Strategie vorgegeben, sondern anhand der gewählten Aktion des Agenten in einer Situation eine Belohnung oder eine Bestrafung gegeben. Ähnlich wie wenn man einem Hund eine Belohnung für das Erlernen eines Tricks, wie „Sitz“ gibt. Das ganze funktioniert dann folgendermaßen: Der Agent befindet sich in einer Umwelt, die aus einer Menge von Zuständen besteht. Dabei kann der Agent in einer bestimmten Situation entscheiden, welche Aktion er wählt und er somit in einen Folgezustand mit einer gewissen Belohnung kommt. Der Agnet versucht dann anchließend mithilfe seiner Aktionen den zu erwarteten Gewinn zu maximieren und dafür eine möglichst gute Strategie zu entwickeln.

Nachdem wir uns die Grundlagen von Reinforcement Learning angeeignet hatten, ging es dann ans programmieren. Tic Tac Toe haben wir deswegen benutzt, da es deutlich weniger mögliche Zustände gibt und somit einfacher zu erlernen ist, aber trotzdem noch ähnlich genug zu Vier Gewinnt ist, um das bereits gelernte anwenden zu können. Bei der Umsetzung war die erste Stufe überhaupt ein Tic Tac Toe Spiel mithilfe von Python zu programmieren, sodass man gegeneinander spielen kann. Dieses Problem konnten wir jedoch schnell mithilfe der turtle von Python lösen. Die nächste Stufe war dann die Programmierung von Reinforcement Learning und die Umsetzung mit Python. Dafür haben wir dann verschiedene Quellen genutzt und mussten dann schließend das ganze dann noch mit dem zuvor programmiertem Spiel zusammenbringen. Das maschinelle Lernen wurde dabei folgendermaßen umgesetzt: Alle möglichen Zustände werden von einer Tabelle repräsentiert, in der zusätzlich die zu erwartende Belohnung steht. So kann der Agent dann in jedem Spielzustand auf die Tabelle zurückgreifen und anhand der Belohnung den bestmöglichen Zug wählen und die zu erwartende Belohnung gegebenenfalls anpassen.

Nach den ersten sichtbaren Ergebnissen von maschinellem Lernen im Bezug auf Tic Tac Toe haben wir uns dann um unser eigentliches Projekt gekümmert: Vier Gewinnt. Ursprünglich wollten wir das ganze ähnlich wie bei Tic Tac Toe umsetzen. Dabei ist dann für uns ein grundsätzliches Problem enstanden. Vier Gewinnt hat einen erheblich größeren Zustandsraum als Vier Gewinnt ist schlicht nicht so einfach umsetzbar wie Tic Tac Toe, somit war unsere eigentliche Übung wie man Reinforcement Learning programmiert, quasi nicht mehr zu gebrauchen. Wir haben zwar dadurch einige Python Kenntnisse erworben, aber der Weg zum Ziel, ein Programm, welches mit Hilfe von maschinellem Lernen Vier Gewinnt löst, war nicht mehr erkennbar. Somit mussten wir uns andere Herangehensweisen überlegen. Schließlich sind wir in unseren Überlegungen zum Anfang unseres Projektes zurückgekehrt und haben eine Herangehendsweise für unsere Problem gefunden. Die Lösung war die Umsetzung mithilfe neuronaler Netzwerke, sowie es Deep Mind gezeigt hat, um weitaus komlexere Spiele zu meistern, als Vier Gewinnt. Der Vorteil neuronaler Netzwerke ist, dass sie nicht jeden Zustand „auswendig“ lernen, wie eine Tabelle, sondern mithilfe von Beispielen Muster erkennen und dadurch Zusammenhänge erstellen können. Dies hat den Vorteil, dass wir ein Programm umsetzen können, was anschließend nur den Aufbau des neuronalen Netzwerk und die Gewichtungen der Verknüpfungen zwischen den Schichten speichern muss und nicht eine ganze Tabelle. Also haben wir nach Möglichkeiten gesucht, wie man sich mit Python die Erstellung neuronaler Netze erleichtern kann und sind auf Keras gestoßen. Keras hat den Vorteil, dass man schnell Modelle erstellen und damit arbeiten kann. Dabei dauert das trainieren von Netzen aber sehr lange. Zudem ist es als Anfänger schwer verständlich, was man für Schichten und welcher Anzahl man diese verwenden sollte. Diese Probleme haben sich dann auch bei unserem Vier Gewinnt Spiel gezeigt. Beispielsweise habe ich einen Agenten stundenlang trainiert ohne am Ende ein sichtbares Ergebnis oder einen lern Erfolg zu haben.

Insgesamt betrachtet haben wir durch das Projekt viel gelernt und konnten auch Teile unserer Ziele umsetzen. Da wir keinerlei Vorkenntnisse in Python hatten, haben wir schon allein durch das Erlernen und anwenden einer Programmiersprache viel dazu gelernt. Zudem haben wir durch unser Projekt die Grundlagen von maschinellem Lernen, sowie die Möglichkeiten und Grenzen davon besser verstanden.

Unser eigentliches Projektziel, einen selbstlernenden Gegner zu programmieren, der annehmbar Vier Gewinnt spielt, haben wir jedoch nicht erreicht. Gegen Gegner, die komplett zufällig spielen gewinnt unser Agent, aber einen Zug vorraussehen und dementsprechend Entscheidungen treffen, kann er noch nicht. Dafür müsste man das verwendete Neuronale Netz überarbeiten und zusätzlich eventuell den Algorithmus dahingehend verbessern, dass er schon im Voraus mehrere Spielzüge durchspielt und bewertet.

Reinforcement Learning:

http://www.incompleteideas.net/book/RLbook2018trimmed.pdf
https://keon.github.io/deep-q-learning/

Keras(Neuronale Netze):

https://www.tensorflow.org/tutorials/keras/classification
https://adventuresinmachinelearning.com/keras-tutorial-cnn-11-lines/
https://github.com/adventuresinML/adventures-in-ml-code/blob/master/keras_cnn.py
https://towardsdatascience.com/solving-sudoku-with-convolution-neural-network-keras-655ba4be3b11
https://www.pyimagesearch.com/2018/12/31/keras-conv2d-and-convolutional-layers/
https://medium.com/applied-data-science/how-to-build-your-own-alphazero-ai-using-python-and-keras-7f664945c188

Tic Tac Toe:

http://www.incompleteideas.net/book/RLbook2018trimmed.pdf
https://towardsdatascience.com/reinforcement-learning-implement-tictactoe-189582bea542
https://github.com/agrawal-rohit/playing-games-with-python/tree/master/Tic%20Tac%20Toe

Vier Gewinnt:

https://medium.com/applied-data-science/how-to-build-your-own-alphazero-ai-using-python-and-keras-7f664945c188