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
1 Einleitung
1.1 Motivation
1.2 Begriffsklärung, theoretisches Fundament
2 Objekt der Optimierung
2.1 Das Spiel „Qubic“
2.1.1 Spieltheoretische Begründung
2.1.2 Berechenbares Nash-Gleichgewicht
2.1.3 Min-Max-Algorithmus
2.1.4 Stellungsbewertung
3 Programmierung des Spiels
3.1 Allgemeiner Aufbau einer Brettspielsimulation
3.2 Stellungsbewertung
4 Messen der Spielstärke
4.1 Standardspieler
4.1.1 Totale Ordnung für Standardspieler
4.2 Elo-Punktesystem
4.3 Zuordnung der Spielstärke zur Suchtiefe
4.3.1 Spieler mit Spielstärken in Hunderterschritten
4.3.2 Spieler mit dazwischenliegenden Spielstärken
4.4 Ressourcenverbrauch und weitere Erkenntnisse
5 Anwendung genetischer Algorithmen
5.1 Chromosom als Gewichtsvektor
5.1.1 Qubic-Gewinnlinien
5.1.2 Skalarproduktes von Matrizen
5.1.3 Chromosomenmatrix
5.2 Genetische Operatoren
5.2.1 Mögliche Arten der Fortpflanzung
5.2.2 Die verwendeten Methoden
6 Drei Versuchsreihen
6.1 Generationszyklen mit beschränkten Chromosomen
6.1.1 Entwicklung der Spielstärken
6.1.2 Entwicklung der Chromosomen
6.1.3 Hoher Selektionsdruck
6.2 Generationszyklen mit freien Chromosomen
6.3 Kontinuierliche Verbesserung mit freien Chromosomen
7 Schlussbemerkungen
7.1 Kontinuierliche Verbesserung schlägt Generationenmodell
7.2 Unerwartete Verteilung der Werte innerhalb der „guten“ Chromosomen
Zielsetzung & Themen
Die Arbeit untersucht die praktische Anwendbarkeit von genetischen Algorithmen und Evolutionsstrategien zur Optimierung der Parameter eines Stellungsbewertungsmoduls für das 3D-Brettspiel "Qubic". Ziel ist es, mittels verschiedener Evolutionsansätze (Generationenmodell vs. kontinuierliche Verbesserung) leistungsfähige Spielstrategien zu entwickeln und deren Konvergenzverhalten im hochdimensionalen Parameterraum zu analysieren.
- Grundlagen genetischer Algorithmen und Evolutionsstrategien
- Spieltheoretische Analyse und Modellierung von "Qubic"
- Entwicklung und Evaluation von Stellungsbewertungs-Parametermatrizen
- Vergleichende Untersuchung von Generationszyklen und kontinuierlichen Optimierungsmodellen
- Analyse des Selektionsdrucks und der Parameterkonvergenz
Auszug aus dem Buch
Genetische Algorithmen (GA)
Genetische Algorithmen sind Verfahren, die zur Lösung von Such- und Optimierungsproblemen dienen. Der Erfolg der Genetischen Algorithmen liegt in der Nachahmung der biologischen Evolution, die selbst ein fortwährender Optimierungsprozess ist. Zu diesem Zweck bedient sich der Genetische Algorithmus der Evolutionsmechanismen
• Genetische Variation
Erzeugung neuer Erbsubstanz durch Rekombination und Mutation
• Selektion
Eliminierung oder Weitergabe der Erbsubstanz
• Zufälle
Die Individuen einer Population befinden sich ständig in einem Kampf ums Dasein. Träger vorteilhafter Merkmale überleben mit höherer Wahrscheinlichkeit (survival of the fittest) und können somit ihre Anlagen an die nächste Generation weitergeben. Folglich besitzt die Folgegeneration die Gene der “besseren“ Eltern. Diese Idee nutzt der Genetische Algorithmus, indem er mit einer Population von Individuen, welche je eine mögliche Lösung des Problems repräsentieren, arbeitet.
(Czogalla, 2005)
Zusammenfassung der Kapitel
1 Einleitung: Kurze Motivation und theoretische Einordnung der Fachgebiete genetische Algorithmen, Evolutionsstrategien und genetische Programmierung.
2 Objekt der Optimierung: Detaillierte Vorstellung des Spiels "Qubic" inklusive spieltheoretischer Grundlagen, des Min-Max-Algorithmus und der Notwendigkeit einer Stellungsbewertung.
3 Programmierung des Spiels: Beschreibung der notwendigen Komponenten einer Brettspielsimulation und Erläuterung der Konzepte zur Stellungsbewertung.
4 Messen der Spielstärke: Einführung von Standardspielern als Messskala und Implementierung eines Elo-Punktesystems zur quantitativen Evaluierung der Spielstärke.
5 Anwendung genetischer Algorithmen: Definition der Chromosomenmatrix als Gewichtsvektor und Beschreibung der verwendeten genetischen Operatoren wie Mutation und Crossover.
6 Drei Versuchsreihen: Praktische Durchführung und Analyse der drei verschiedenen Optimierungsszenarien mit ihren jeweiligen Konvergenzergebnissen.
7 Schlussbemerkungen: Zusammenfassende Bewertung der Effizienz der Ansätze sowie Diskussion der unerwarteten Ergebnisse bei der Verteilung der Chromosomenwerte.
Schlüsselwörter
Genetische Algorithmen, Evolutionsstrategien, Qubic, Optimierung, Stellungsbewertung, Chromosomenmatrix, Mutation, Crossover, Spielstärke, Elo-Punktesystem, Selektionsdruck, Parameterkonvergenz, Brettspielsimulation, Min-Max-Algorithmus, Heuristik.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die praktische Anwendung genetischer Algorithmen zur Optimierung der Spielstärke des Brettspielprogramms "Qubic".
Was sind die zentralen Themenfelder der Untersuchung?
Die Schwerpunkte liegen auf der Entwicklung von Bewertungsfunktionen für Spielstellungen, dem Vergleich verschiedener evolutionärer Optimierungsmodelle und der Analyse des Konvergenzverhaltens genetischer Parameter.
Welches primäre Ziel verfolgt die Forschungsarbeit?
Ziel ist es, durch evolutionäre Mechanismen Parameter für eine 28-dimensionale Matrix zu finden, die es dem Programm ermöglicht, eine möglichst hohe Spielstärke gegen definierte Standardgegner zu erreichen.
Welche wissenschaftlichen Methoden kommen zum Einsatz?
Es werden heuristische Optimierungsmethoden (genetische Algorithmen) verwendet, die mit spieltheoretischen Konzepten, statistischen Analysen und einer Elo-basierten Leistungsmessung kombiniert werden.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die spieltheoretische Analyse, die technische Realisierung der Simulation, den Aufbau der Messskala sowie die detaillierte Durchführung und Auswertung dreier unterschiedlicher experimenteller Versuchsreihen.
Welche Schlüsselbegriffe charakterisieren die Arbeit?
Die wichtigsten Begriffe umfassen genetische Algorithmen, Evolutionsstrategien, Qubic, Crossover, Mutation, Spielstärke und Parameter-Optimierung.
Warum wurde "Qubic" als Studienobjekt gewählt?
Qubic bietet durch seine einfachen Regeln in Kombination mit einem enorm großen, aber endlichen Zustandsraum eine ideale Basis für die Erprobung heuristischer Optimierungsverfahren, da eine vollständige Analyse des Spielbaums praktisch unmöglich ist.
Zu welchem unerwarteten Ergebnis führten die Versuchsreihen?
Überraschenderweise zeigte sich, dass das Modell der "kontinuierlichen Verbesserung" (ohne strikte Generationsgrenzen) deutlich effizienter agierte als das klassische Generationenmodell.
Welchen Einfluss hatte der Selektionsdruck auf die Evolution?
Ein hoher Selektionsdruck führte dazu, dass alle untersuchten Populationen gegen sehr ähnliche, "schiefe" Chromosomenstrukturen konvergierten, die ein defensives Spielverhalten begünstigten.
- Quote paper
- Bsc Hubert Schölnast (Author), 2009, Genetische Algorithmen in der Praxis, Munich, GRIN Verlag, https://www.grin.com/document/148855
