Lösung von Ein- und Mehrpersonenspielen auf der Grafikkarte mit perfekten Hashfunktionen

Inhaltsverzeichnis

1 Einleitung

1.1 Motivation und Hintergrund

1.2 Aufbau der Arbeit

2 Grundlagen

2.1 Spiele und Spieltheorie

2.2 Theoretische Grundlagen zum Hashing

2.2.1 Vorüberlegungen

2.2.2 Minimale perfekte Hashfunktionen

2.3 GPU-Grundlagen

2.3.1 Entwicklung der Grafikkarten

2.3.2 Architektur moderner Grafikprozessoren

2.3.3 NVIDIA CUDA™

2.3.4 ATI Stream™ und OpenCL

2.4 Breitensuche mit GPU-Unterstützung

3 Das Einpersonenspiel „Englisches Solitär“

3.1 Hashfunktion für Spielzustände

3.2 Lösen des Spiels

3.3 Implementierung und Resultate

4 Das Einpersonenspiel „Frösche und Kröten“

4.1 Hashfunktion für Spielzustände

4.2 Lösen des Spiels

4.3 Implementierung und Resultate

5 Das Zweipersonenspiel „Mühle“

5.1 Hashfunktion für Spielzustände

5.2 Lösen des Spiels

5.2.1 Bewertung von Spielzuständen

5.2.2 Retrogerade Analyse für Zug- und Sprungphase

5.2.3 Implementierung und Resultate für Zug- und Sprungphase

5.2.4 Klassifizierung von Zuständen der Setzphase

5.2.5 Implementierung und Resultate für die Setzphase

5.3 Ein optimaler Spieler

6 Fazit

Zielsetzung und thematische Schwerpunkte

Die Arbeit befasst sich mit der effizienten Lösung kombinatorischer Ein- und Mehrpersonenspiele unter Ausnutzung der massiven Parallelität von Grafikprozessoren (GPUs), wobei Hashfunktionen als zentrales Mittel zur effizienten Speicherverwaltung der Spielzustandsräume eingesetzt werden.

• Grundlagen der Spieltheorie und kombinatorische Optimierung
• Architektur und Programmierung moderner Grafikprozessoren (insb. NVIDIA CUDA)
• Konstruktion minimaler perfekter Hashfunktionen zur Zustandsabbildung
• Implementierung von Breitensuche-Algorithmen auf der GPU
• Fallstudien zu den Spielen Englisches Solitär, Frösche und Kröten sowie Mühle

Auszug aus dem Buch

Zusammenfassung der Kapitel

1 Einleitung: Einführung in die Nutzung von Grafikprozessoren für kombinatorische Problemstellungen und den Aufbau der Arbeit.

2 Grundlagen: Vermittlung der spieltheoretischen Basis, der mathematischen Grundlagen für perfekte Hashfunktionen sowie der technischen GPU-Architektur und Schnittstellen.

3 Das Einpersonenspiel „Englisches Solitär“: Anwendung von Hashing und Breitensuche zur effizienten Lösung dieses klassischen Halma-Spiels auf der GPU.

4 Das Einpersonenspiel „Frösche und Kröten“: Untersuchung und Implementierung einer Lösung mittels spezialisierter Hashfunktionen für die Zustände dieses Spiels.

5 Das Zweipersonenspiel „Mühle“: Komplexere Lösung eines Mehrpersonenspiels inklusive Bewertung von Spielzuständen und retrogerader Analyse.

6 Fazit: Zusammenfassende Bewertung der erreichten Beschleunigungen durch Hash-basierte GPU-Lösungsansätze und Ausblick auf weiterführende Methoden.

Schlüsselwörter

GPU, GPGPU, CUDA, Hashing, perfekte Hashfunktionen, kombinatorische Spiele, Breitensuche, Englisches Solitär, Frösche und Kröten, Mühle, Parallelisierung, Zustandsgraph, Manycore, Spieltheorie, Speicherverwaltung

Häufig gestellte Fragen

Worum geht es in dieser Diplomarbeit grundsätzlich?

Die Arbeit untersucht, wie kombinatorische Brettspiele durch den Einsatz moderner Grafikprozessoren effizienter gelöst werden können, indem der Spielzustandsraum durch Hashfunktionen kompakt im Speicher verwaltet wird.

Welche zentralen Themenfelder werden abgedeckt?

Die zentralen Felder sind die parallele Programmierung auf GPUs (NVIDIA CUDA), die theoretische Informatik im Bereich Hashing (perfekte Hashfunktionen) und die algorithmische Spieltheorie.

Was ist das primäre Ziel der Forschung?

Das Ziel ist die signifikante Beschleunigung der Suche nach Lösungen für kombinatorische Spiele, um Zustandsräume zu bewältigen, die auf CPUs sequentiell nur sehr langsam oder gar nicht berechenbar wären.

Welche wissenschaftlichen Methoden werden angewendet?

Es werden mathematische Partitionierungsverfahren für Zustandsräume, Hashing-Verfahren mittels Binomial- und Multinomialkoeffizienten sowie Breitensuche-Algorithmen für parallele Architekturen eingesetzt.

Was wird im Hauptteil der Arbeit behandelt?

Der Hauptteil gliedert sich in drei Fallstudien: das Einpersonenspiel Englisches Solitär, das Einpersonenspiel Frösche und Kröten sowie das anspruchsvolle Zweipersonenspiel Mühle.

Welche Keywords charakterisieren die Arbeit am besten?

GPU-Computing, perfekte Hashfunktionen, Zustandssuche, Parallelisierung und kombinatorische Optimierung.

Warum spielt die Wahl der Hashfunktion eine so wichtige Rolle?

Da der verfügbare Speicher auf einer Grafikkarte (VRAM) begrenzt ist, erlauben minimale perfekte Hashfunktionen eine äußerst speichereffiziente Verwaltung der Spielzustände.

Wie konnte das Spiel „Mühle“ effizient analysiert werden?

Durch eine Partitionierung des Zustandsraums in Abhängigkeit von den Stein-Farben (Multinomialkoeffizienten) und die Verwendung einer retrogeraden Analyse, um Gewinnzustände rückwärts zu berechnen.

Welchen Vorteil bietet die GPU gegenüber einer CPU für diese Aufgaben?

Die massive Anzahl an spezialisierten Recheneinheiten (Manycore-Architektur) ermöglicht es, Millionen von Spielzuständen parallel zu expandieren und zu verarbeiten, was zu einer Beschleunigung um Faktoren zwischen 13 und 18 führt.