Genetische Algorithmen und Evolutionsstrategien sind heuristische Optimierungsmethoden, die ihr Vorbild in der natürlichen Evolution haben. In dieser Arbeit wird diese Methode benutzt, um die Parameter des Stellenbewertungsmoduls des Brettspielprogramms „Qubic“ (eine dreidimensionale Variante von Tic-Tac-Toe) zu optimieren. Es werden insgesamt 28 Parameter definiert, die zusammen das Chromosom eines Spielers bilden. In verschiedenen Versuchsreihen müssen die Spieler durch das Spiel gegen genormte Standardspieler ihre absolute Spielstärke unter Beweis stellen. In einer dieser Reihen wird auch eine relative Spielstärke durch direkten Vergleich der Spieler untereinander ermittelt.
Nachkommen werden entweder durch Mutation des Genoms eines Spielers, oder durch Zusammenfügen von Teilen der Gene zweier Elternteile („Crossover“) erzeugt. Diese Nachkommen nehmen entweder als eine neue Generation am Selektionsprozess teil, oder ersetzen innerhalb der Population den jeweils zu diesem Zeitpunkt schlechtesten Spieler. Je nach Versuchsreihe entscheidet die absolute oder die relative Spielstärke darüber, mit welcher Wahrscheinlichkeit jedes Individuum seine Gene an Nachkommen weitergeben darf.
Die Methode, strikt voneinander getrennte Generationen zu verwenden, wird mit einem kontinuierlichen Austausch von Individuen verglichen. Dabei schneidet die kontinuierliche Verbesserung überraschend gut ab, was das Entwicklungstempo der Population betrifft.
Bestimmte Überlegungen legen nahe, dass die Chromosomen guter Spieler eine gewisse Struktur aufweisen müssen. Durch den Vergleich einer Versuchsreihe, die ausschließlich solche strukturierten Chromosomen verwendet, mit einer Reihe, die sich nicht an diese Vorgaben halten muss, kann gezeigt werden, dass die Chromosomen guter Spieler tatsächlich einige Eigenschaften aufwiesen die erwartet wurden. Einige andere Ergebnisse sind aber überraschend.
Inhaltsverzeichnis
- Einleitung
- Motivation
- Begriffsklärung, theoretisches Fundament
- Objekt der Optimierung
- Das Spiel „Qubic“
- Spieltheoretische Begründung
- Berechenbares Nash-Gleichgewicht
- Min-Max-Algorithmus
- Stellungsbewertung
- Programmierung des Spiels
- Allgemeiner Aufbau einer Brettspielsimulation
- Stellungsbewertung
- Messen der Spielstärke
- Standardspieler
- Totale Ordnung für Standardspieler
- Elo-Punktesystem
- Zuordnung der Spielstärke zur Suchtiefe
- Spieler mit Spielstärken in Hunderterschritten
- Spieler mit dazwischenliegenden Spielstärken
- Ressourcenverbrauch und weitere Erkenntnisse
- Anwendung genetischer Algorithmen
- Chromosom als Gewichtsvektor
- Qubic-Gewinnlinien
- Skalarproduktes von Matrizen
- Chromosomenmatrix
- Genetische Operatoren
- Mögliche Arten der Fortpflanzung
- Die verwendeten Methoden
- Drei Versuchsreihen
- Generationszyklen mit beschränkten Chromosomen
- Entwicklung der Spielstärken
- Entwicklung der Chromosomen
- Hoher Selektionsdruck
- Fazit
- Literaturverzeichnis
Zielsetzung und Themenschwerpunkte
Die Bachelorarbeit befasst sich mit der praktischen Anwendung genetischer Algorithmen zur Optimierung der Parameter eines Stellenbewertungsmoduls für das Brettspiel „Qubic“. Ziel ist es, die Spielstärke eines computergesteuerten Spielers durch die Evolution von Chromosomen, die die Parameter des Stellenbewertungsmoduls repräsentieren, zu verbessern.
- Anwendung genetischer Algorithmen in der Praxis
- Optimierung der Spielstärke eines Brettspielprogramms
- Entwicklung von Chromosomen zur Darstellung von Spielstrategien
- Vergleich verschiedener Evolutionsstrategien
- Analyse der Struktur von Chromosomen guter Spieler
Zusammenfassung der Kapitel
Die Einleitung führt in die Thematik der genetischen Algorithmen und deren Anwendung in der Praxis ein. Sie erläutert die Motivation für die Arbeit und stellt das theoretische Fundament dar. Das zweite Kapitel beschreibt das Brettspiel „Qubic“ als Objekt der Optimierung. Es beleuchtet die spieltheoretischen Grundlagen, das Konzept des Nash-Gleichgewichts und den Min-Max-Algorithmus. Außerdem wird die Bedeutung der Stellungsbewertung im Kontext des Spiels diskutiert.
Kapitel drei befasst sich mit der Programmierung des Spiels „Qubic“. Es werden der allgemeine Aufbau einer Brettspielsimulation und die Implementierung der Stellungsbewertung erläutert. Kapitel vier widmet sich der Messung der Spielstärke. Es werden verschiedene Methoden zur Bewertung der Spielstärke von Standardspielern vorgestellt, darunter das Elo-Punktesystem und die Zuordnung der Spielstärke zur Suchtiefe.
Kapitel fünf beschreibt die Anwendung genetischer Algorithmen zur Optimierung der Spielstärke. Es werden die Darstellung von Chromosomen als Gewichtsvektoren, die Verwendung von Matrizen zur Berechnung des Skalarprodukts und die genetischen Operatoren wie Mutation und Crossover erläutert. Schließlich werden in Kapitel sechs drei Versuchsreihen vorgestellt, die die Entwicklung der Spielstärke und die Struktur der Chromosomen untersuchen.
Schlüsselwörter
Die Schlüsselwörter und Schwerpunktthemen des Textes umfassen genetische Algorithmen, Evolutionsstrategien, praktische Anwendung, Brettspielprogrammierung, Spielstärke, Stellungsbewertung, Chromosomen, Mutation, Crossover, Qubic, Min-Max-Algorithmus, Nash-Gleichgewicht.
- Arbeit zitieren
- Bsc Hubert Schölnast (Autor:in), 2009, Genetische Algorithmen in der Praxis, München, GRIN Verlag, https://www.grin.com/document/148855
