Minimax
Inhaltsverzeichnis
Einleitung
Die Hauptmotivation für mein Projekt bestand darin einen guten und vor allem einfachen Algorithmus für eine Spiele KI zu finden. Neben Neurale Netzwerke, die viel Speicher benötigen und der guten alten Brute Force Methode, die doch seeeehr lange braucht, bin ich auf den Minimax Algorithmus gestoßen, der im wesentlichen bei ziemlich allen Spielen Verwendung findet, aufgrund der Schnelligkeit und des simplen Grundkonzeptes. Wie gut die KI schlussendlich mit diesem Algorithmus funktioniert, hängt davon ab, wie eine Situation bewertet wird
Funktionsweise anhand von 4 Gewinnt
Die Funktionsweise gliedert sich in 2 Teile
Numerische Bewertung der Lage der Spielsteine
Wir versuchen nun Spielsituationen im Spiel 4 Gewinnt numerisch zu bewerten, dabei stehen positive Werte für die KI und negative für den Gegner der KI und mehre Steine vom gleichen Spieler nebeneinander besitzen eine bessere Wertung als nur einer bzw. wenn beispielsweise keine Aussicht mehr auf 4 in einer horizontalen mehr möglich ist soll das Programm diese Stellung nicht in die Gesamtstellung miteinbeziehen.
Zugsimulation
- 1.Zug
Die KI macht den ersten Zug auf das erste mögliche Feld. Daraufhin werden sofort alle möglichen Züge des Gegners durchvariiert und die Stellungen der Steine bewertet. Es werden danach alle Züge des Gegners bis auf den für ihn günstigsten verworfen. Jetzt wird der erste Zug wieder rückgängig gemacht und die gleiche Prozedur wir für die restlichen möglichen Züge durchgeführt. Danach werden alle Bewertungen für die möglichen Züge des ersten Zuges von der KI verglichen und die drei besten Züge der KI und des Gegners werden gespeichert.
- Alle weiteren Züge
Um schlussendlich ein Vorausdenken der KI zu ermöglichen werden diese Züge der KI und des Gegners hergenommen, gesetzt und die gleiche Prozedur wie beim ersten Versuch für jeden der drei gespeicherten Züge durchgeführt. Danach hätte man 9 mögliche Züge, da für die drei gespeicherten Züge, jeweils die drei besten Züge berechnet, aber um Speicherplatz zu sparen, wenn bei der Vergrößerung der zu vorausschauenden Züge, die gespeicherten Züge nicht exponentiell wachsen werden von diesen 9 Zügen ebenfalls die besten 3 hergenommen und wieder in die Schleife eingesetzt. Wenn schlussendlich die Anzahl der gewünschten Züge simuliert wurde, wird nochmal die Wertung der 3 Zugfolgen betrachten und der erste Zug der besten Zugfolge wird ins Spielfeld schlussendlich gesetzt.
Download
